这套题阳间多了
蒋叶桢, 张炀杰, 我分别开题A, B, H, 12min我过了H, 14min张炀杰过了B, 35min蒋叶桢过了A.
我, 张炀杰过完了题以后继续读题, 张炀杰读L, 我读了M, 稍微想了想发现不太会, 和张炀杰商量了一下, 张炀杰说应该可以二分答案, 于是在想M. 我又去读了G, 好像和树剖有关? 于是丢给了张炀杰. 继续读了L, 是一道数学题, 没太看懂, 和刚过完A的蒋叶桢讨论, 蒋叶桢建了个数学模型, 并且开始打表. 我继续读了K, 数数题, 丢给蒋叶桢. 然后和蒋叶桢一起想L, 并发现了L的做法, 我1h19min过了L.
没带电源, 电脑没电了, 回了一趟宿舍拿电源. 期间张炀杰和蒋叶桢在做D和M, 张炀杰说D是个裸的长链剖分, 打完以后WA第31个点, 不知道为什么. 然后去打M, 细节没打出来, 给了蒋叶桢打. 我回来后继续摸鱼, 和张炀杰想为什么D WA了. 蒋叶桢1h45min过了M,
我提出特判$k \ge \ leaf$, 改了以后交一发还是WA31. 三个人都实在想不出为什么D会错了, 于是我重新打了一遍, 2h7min过了. 嗯?
蒋叶桢推K, 我继续读题, 翻译完G, 张炀杰和蒋叶桢一眼就看出是个费用流, 2h53min过.
期间张炀杰在看J. 我打完以后蒋叶桢马上打K, 我去看I. I是图论题, 和张炀杰交流了一下, 没太想明白, 张炀杰给我讲了J, 打牌模拟题.
这时蒋叶桢3h39min过了K, 然后来想I, 于是张炀杰和我开始打J. 蒋叶桢想到了I, 于是我们停止打J, 蒋叶桢开始打I, 我又推翻了张炀杰J的打法, 开始想细节. 蒋叶桢I细节没想清楚, 于是我上机打J, 但是第二个样例死循环了. 很迷.
最后一小时全员贡献为0, 然后就结束了.
-
蒋叶桢yyds!!!
-
分工不当, 我应该读题, 而不是敲键盘. J 张炀杰没读仔细, 我STL不太会, 浪费了很多时间, 其实J是个很简单的模拟.
$n \times m$大小的地图中有$k$个摄像头, 第$i$个的侦察范围是半径为$s_i$的圆. 从(0, 0)走到(n, m), 但能被摄像头发现. 求是否可行.
$10 \le n, m \le 10^4$, $1 \le k \le 1000, 0 < s \le 10^4$
摄像头的监控范围可看作圆, 相交的圆做并查集, 然后再新增两个点, 一个为地图的"左下边界之外", 另一个为地图的"右上边界之外". 如果有圆和这两个点相交, 那么也把他并进去. 最后判断这两个是否在一个并查集中, 是则表面地图被"分割", 不能走到; 否则可以.
复杂度 $O(n\alpha(n))$
没写, 直接copy蒋叶桢的. (蒋叶桢是分了上下左右四个边界外的).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#define LL long long
#define LD long double
const int MAXN=1015;
struct Sensor
{
int x,y,s;
}S[MAXN];
int fa[MAXN];
int FindFa(int x)
{
if(fa[x]==x)
return x;
return fa[x]=FindFa(fa[x]);
}
void Merge(int x,int y)
{
int A=FindFa(x),B=FindFa(y);
if(A!=B)
{
fa[A]=B;
}
}
int jl(int x,int y,int X,int Y)
{
return (x-X)*(x-X)+(y-Y)*(y-Y);
}
void Read(int &x)
{
int f=1;x=0;char ch=getchar();
while(ch<'0'||'9'<ch)
{
if(ch=='-')
f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x=x*f;
}
int N,M,K;
void Init()
{
for(int i=0;i<=K+5;i++)
fa[i]=i;
}
int main()
{
Read(M);
Read(N);
Read(K);
Init();
for(int i=1;i<=K;i++)
{
Read(S[i].x);
Read(S[i].y);
Read(S[i].s);
}
for(int i=1;i<=K;i++)
{
for(int j=1;j<K;j++)
{
if( jl(S[i].x,S[i].y,S[j].x,S[j].y) <= (S[i].s+S[j].s)*(S[i].s+S[j].s) )
{
Merge(i,j);
}
}
if(S[i].x-S[i].s<=0)
{
Merge(i,K+4);
}
if(S[i].x+S[i].s>=M)
{
Merge(i,K+2);
}
if(S[i].y-S[i].s<=0)
{
Merge(i,K+1);
}
if(S[i].y+S[i].s>=N)
{
Merge(i,K+3);
}
}
int key=0;
if(FindFa(K+3)==FindFa(K+2)) key=1;
if(FindFa(K+3)==FindFa(K+1)) key=1;
if(FindFa(K+4)==FindFa(K+2)) key=1;
if(FindFa(K+4)==FindFa(K+1)) key=1;
if(key)
printf("N\n");
else
printf("S\n");
}
|
$n$个数$a_i$, 求第一个数是不是最大.
$2 \le n \le 10^4, 1 \le a \le 10^5$
签到, 复杂度 $O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int n, a[10007];
int main()
{
Read(n);
for (int i = 1; i <= n; i++) {
Read(a[i]);
if (a[i] > a[1]) {
puts("N");
return 0;
}
}
puts("S");
return 0;
}
|
给出一棵大小为$n$的以$1$为根的树, 最多可以选$k$个点, 选了某个点后, 把选了的点到根的路径上的所有点(包括当前点和根)标记. 求最少选择多少点, 让所有点被标记.
$3 \le n \le 10^5, 1 \le k < n$
首先肯定选叶子最优, 证明很简单, 略. 然后显然贪心, 找最长链.
如何找最长链? 长链剖分.
即把树链剖分中, 以子树大小判断重儿子改成以子树深度判断"深儿子".
做完以后就得到了最长链的剖分. 然后排序, 贪心选就可以了.
复杂度 $O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
const int maxn = 1e5+10;
int n, k, son[maxn], dep[maxn], maxdep[maxn], top[maxn];
vector<int> G[maxn], leaves;
void dfs1(int u, int d) {
maxdep[u] = dep[u] = d;
for (auto v : G[u]) {
dfs1(v, d + 1);
if (maxdep[v] > maxdep[u]) {
maxdep[u] = maxdep[v];
son[u] = v;
}
}
if (!G[u].size())
leaves.push_back(u);
}
void dfs2(int u, int t) {
top[u] = t;
if (!son[u])
return;
dfs2(son[u], t);
for (auto v : G[u]) if (v != son[u])
dfs2(v, v);
}
bool cmp(int u, int v) {
return dep[u] - dep[top[u]] > dep[v] - dep[top[v]];
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 2; i <= n; i++) {
int f;
scanf("%d", &f);
G[f].push_back(i);
}
dfs1(1, 0);
dfs2(1, 1);
sort(leaves.begin(), leaves.end(), cmp);
if (k >= leaves.size())
printf("%d\n", n);
else {
int ans = 0;
for (int i = 0; i < k; i++) {
int u = leaves[i];
ans += dep[u] - dep[top[u]] + 1;
}
printf("%d\n", ans);
}
return 0;
}
|
某国家的领土范围为$(X_1, Y_1)$到$(X_2, Y2)$的矩形. 其中有$n$条平行于坐标轴的河流$(x_{i1}, y_{i1}), (x_{i2}, y_{i2})$(完全包含在领土内, 且是一条直线).
现在该国要对河流周围进行绿化, 绿化范围$r$表示: 对于河流上的每一个点和被绿化的点, 这两个点之间的距离最大为$r$. 一条河流周围被绿化的地看上去是一个矩形. 该国希望所有的绿化土地是该国国土面积的$P\%$, 求满足该条件的最小绿化范围$r$.
显然二分$r$.
对每个河流, 我们可以算出绿化矩形. 先把这些矩形和国土矩形求交集, 然后这些矩形求并集即可.
矩形面积并可以用扫描线 + 线段树求.
需要注意以下两点:
- 不能直接放到叶子修改(如果这样的话区间操作有什么意义呢?)
正确的做法是设一个变量 cover, 表示完全覆盖这一个区间的次数.
在push up的时候, 不对 cover 进行任何修改, 这样每次访问到 cover 不为0的区间, 我们就知道他一定是被覆盖了的; 否则向下找.
如果 cover 不为0, 那么需要更新 val 为该区间的长度; 否则需要从下网上更新.
-
查询永远是根, 所以不需要打lazy tag.
-
本题细节: 由于我用线段树维护了两个边界的闭区间(宽度为$r-l+1$), 而这题是连续的, 实际上宽度应该为$r-l$, 所以在处理线段树的时候我丢进去的是update(l, r-1)
-
如果是离散的点的面积, 则不需要进行上述-1处理, 但同时需要对"-1的线段"( update(l, r, -1)的区间 )进行y+1处理. 原因如下图所示:
离散点矩形面积
复杂度 $O(nlog^2 n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
const int maxn = 1e4+10;
const int maxx = 1e5+10;
struct Node {
int l, r, mid, is_cover, val;
}tree[maxx<<2];
struct Seg {
int x1, y1, x2, y2, d;
Seg() {}
Seg(int x1_, int y1_, int x2_, int y2_, int d_ = 0) {
x1 = x1_, y1 = y1_, x2 = x2_, y2 = y2_;
if (x1 > x2)
swap(x1, x2);
if (y1 > y2)
swap(y1, y2);
d = d_;
}
bool operator < (const Seg &S) const {
return y1 == S.y1 ? x1 < S.x1 : y1 < S.y1;
}
} segments[maxn], horizontal[maxn<<1];
int xx1, yy1, xx2, yy2;
int n, p;
LL area;
void Build(int u, int l, int r) {
tree[u] = Node{l, r, (l+r)>>1, 0, 0};
if (l < r) {
Build(LCH(u), l, tree[u].mid);
Build(RCH(u), tree[u].mid + 1, r);
}
}
void Update(int u, int l, int r, int d) {
if (tree[u].l == l && tree[u].r == r) {
if (l == r) {
tree[u].is_cover += d;
tree[u].val = tree[u].is_cover > 0;
}
else {
tree[u].is_cover += d;
tree[u].val = tree[u].is_cover ? tree[u].r - tree[u].l + 1 : tree[LCH(u)].val + tree[RCH(u)].val;
}
}
else {
if (r <= tree[u].mid)
Update(LCH(u), l, r, d);
else if (l > tree[u].mid)
Update(RCH(u), l, r, d);
else {
Update(LCH(u), l, tree[u].mid, d);
Update(RCH(u), tree[u].mid + 1, r, d);
}
tree[u].val = tree[u].is_cover ? tree[u].r - tree[u].l + 1 : tree[LCH(u)].val + tree[RCH(u)].val;
}
}
void Push(int cur, int r) {
Seg &s = segments[cur];
int sx1 = max(xx1, s.x1 - r), sx2 = min(xx2, s.x2 + r) - 1;
int sy1 = max(yy1, s.y1 - r), sy2 = min(yy2, s.y2 + r);
horizontal[cur] = Seg(sx1, sy1, sx2, sy1, 1);
horizontal[cur + n] = Seg(sx1, sy2, sx2, sy2, -1);
}
bool Check(int r) {
for (int i = 1; i <= n; i++)
Push(i, r);
sort(horizontal + 1, horizontal + 1 + n + n);
Build(1, xx1, xx2);
LL cur = 0;
int pre_y = horizontal[1].y1;
for (int i = 1; i <= n<<1; i++) {
int x1 = horizontal[i].x1, x2 = horizontal[i].x2, y = horizontal[i].y1, d = horizontal[i].d;
int h = y - pre_y, w = tree[1].val;
cur += 1ll * h * w;
Update(1, x1, x2, d);
pre_y = y;
}
return ((cur * 100) >= (area * p));
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
segments[i] = Seg(x1, y1, x2, y2);
}
scanf("%d%d%d%d%d", &p, &xx1, &yy1, &xx2, &yy2);
area = 1ll * (xx2 - xx1) * (yy2 - yy1);
int l = 1, r = max(xx2, yy2), ans = -1;
while (l <= r) {
int mid = (l+r)>>1;
if (Check(mid)) {
r = mid - 1;
ans = mid;
}
else
l = mid + 1;
}
printf("%d\n", ans);
return 0;
}
|
某水族馆有一种神奇的🐟, 当某一个鱼缸里没有雌鱼时, 某一条雄鱼会变成雌鱼. 水族馆里有$n$个鱼缸, 其中第$i$个鱼缸中有$a_i$条雄鱼和$b_i$条雌鱼(保证初始状态合法). 把某一个鱼缸中的一条鱼移动到另一个鱼缸需要$1$点花费. 求把所有雄鱼变成雌鱼的最小花费.
$2 \le n \le 3000, 0 \le a, b \le 10^5, a = 0 \ or\ b > 0$
关键点都想出来了, 但是不太会实现, 搞了好久好久好久😭
先进行一下特判, 如果没有雄鱼, 直接输出$0$即可.
先考虑没有空缸的情况.
对一个非空鱼缸, 我们只会进行以下操作之一:
- 把所有雄鱼拿出来, 移动到其他缸里(可能是多个鱼缸);
- 把所有雌鱼拿出来, 让雄鱼依次变成雌鱼, 再一个一个拿雌鱼, 最后留一只雌鱼. 拿出来的鱼移动到其他缸里(可能是多个鱼缸).
证明简单, 略.
我们把进行第一种操作的鱼缸称为$M$, 进行第二种操作的鱼缸称为$F$.
手玩可以发现有以下性质:
- $M$拿出来的鱼一定会移动到某些$F$中
证明:
$M$($a_i, b_i$)拿出来的雄鱼$a_i$会放到$F$的雄鱼里, 让拿过来的雄鱼$a_i$变成雌鱼的最优方式就是这个$F$进行他的操作, 这样这$a_i$条雄鱼会被移动两次, 贡献为$2a_i$. 如果不是这样的操作, 那么只可能是把这些鱼再放到其他缸内, 这样贡献一定会大于$2a_i$, 不优. 如果是把$M$放到其他$M$里, 也会造成贡献大于$2a_i$, 不优.
所以, $M$的贡献是$2a_i$.
- $F$拿出来的鱼一定会移动到某些$M$中
证明:
放到$M$中, 由于$M$中的雄鱼不需要通过移动雌鱼让雄鱼变性, 所以放好以后就不用动了. 假如$F$($a_j, b_j$)拿出来的鱼$(a_i + b_j - 1)$放在某些其他$F$中, 则这些鱼还可能需要再拿出来(目标$F$有雄鱼的话), 贡献会增加, 不优.
所以, $F$的总贡献是$a_j + b_j - 1$.
由上述性质, 可以推知:
- 至少存在一个$M$和一个$F$才是可行的.
那么, 我们的任务就是给$n$个非空的鱼缸标号.
事实上如果题目到这里就结束了, 我们可以直接贪心解决.
但是! 这道题有空鱼缸! 加入空鱼缸之后就变得复杂多了.
空鱼缸有这些作用:
- 作为一个 雄鱼消除器
由前两条性质我们可以得到, 在没有空鱼缸的情况下, $M$中的一只雄鱼的贡献为$2$. 如果我们把这一条鱼移动到空鱼缸里, 贡献就是$1$了, 更优.
- 作为一个$M$
如果所有的非空鱼缸都是$F$的话, 可以把他们移动到空鱼缸内.
- 作为一个$F$
如果所有非空鱼缸都是$M$的话, 可以把他们都移动到空鱼缸内, 然后再对收集了雄鱼的空鱼缸进行$F$的操作(如果有必要).
作用$2,3$削弱了对非空鱼缸的"至少一个为$M$, 一个为$F$“的限制条件, 即可以全是$M$或者$F$.
同时, 还有这样的性质:
移动到空鱼缸里的鱼一定是某个$M$内的雄鱼
证明:
由作用1可得, 这样做可以使答案更优. $M$的雌鱼不需要移动. $F$的雄鱼或者雌鱼移动到这里, 贡献是$1$; 而原来的贡献也是$1$, 移动的话不仅不会使答案更优, 还会浪费一个可能可以减小答案的空鱼缸, 不优.
贪心一下, 当然是把尽量多的$M$中的雄鱼移动到空鱼缸中.
那么, 哪些鱼缸需要标记成$M$, 不再仅仅取决于$2a_i$与$a_i + b_i - 1$的大小关系了, 空鱼缸能对我们的选择进行影响. 所以, 贪心的方法不可行. 尝试一个能够对比两种决策(标记成$M$还是$F$)的优劣性的做法 —— DP.
一步一步来.
我们不需要给空鱼缸标号, 把他和非空鱼缸分离开, $dp$的第一维只考虑非空鱼缸.
由于空鱼缸的数量会对结果造成影响, 所以在状态中加入空鱼缸.
$dp(i, j)$表示前$i$个(非空)鱼缸, 另外有$j$个空鱼缸被使用, 即有$j$条$M$中的雄鱼被拿出来且分别放在了空鱼缸中.
如果没有空鱼缸, 鱼缸的标号是有限制条件的, 所以我们需要知道鱼缸的标号情况. 但是不需要知道具体的标号情况, 而需要知道有没有标号为$F$的和有没有标号为$M$的. 所以, 我们附加上两个状态, 分别表示前$i$个中有无$F$, $M$. 最后状态长这样:
$$dp(i, j, 0 / 1, 0 / 1)$$
表示前$i$个(非空)鱼缸中, 移动了$j$条雄鱼到$j$个空鱼缸中, 前$i$个鱼缸有/无$F$, 前$i$个鱼缸有/无$M$
$dp$方程老长老长了:
首先边界条件$dp(0, 0, 0, 0) = 0$, 其他$dp(0, 0)$的不存在, 可直接设为INF. 当$i>1$时, $dp(i, j, 0, 0)$也不存在, 设为INF.
$dp(i, j, 0, 1)$ 从以下状态转移:
$$
\begin{aligned}
&dp(i-1, j, 0, 1) + 2a_i &\text{之前有M, 当前为M, 不移动到空} \\
&dp(i-1, j, 0, 0) + 2a_i &\text{之前无M, 当前为M, 不移动到空} \\
&dp(i-1, max(0, j - a_i), 0, 1) + 2 * a_i - min(j, a_i) &\text{之前有M, 当前为M, 全移动到空} \\
&dp(i-1, max(0, j - a_i), 0, 0) + 2 * a_i - min(j, a_i) &\text{之前无M, 当前为M, 全移动到空}
\end{aligned}
$$
$dp(i, j, 1, 0)$ 从以下状态转移:
$$
\begin{aligned}
dp(i-1, j, 1, 0) + a_i + b_i - 1 \\
dp(i-1, j, 0 ,0) + a_i + b_i - 1
\end{aligned}
$$
$F$中的鱼不需要移到空鱼缸, 只有这两个状态需要转移
$dp(i, j, 1, 1)$ 从以下状态转移:
$$
\begin{aligned}
&dp(i-1, j, 1, 1) + 2 * a_i \\
&dp(i-1, max(0, j - a_i), 1, 1) + 2 * a_i - min(j, a_i) \\
&dp(i-1, j, 1, 1) + a_i + b_i - 1 \\
&dp(i-1, j, 1, 0) + 2 * a_i \\
&dp(i-1, max(0, j - a_i), 1, 0) + 2 * a_i - min(j, a_i) \\
&dp(i-1, j, 0, 1) + a_i + b_i - 1
\end{aligned}
$$
写不动了方程不一一解释了, 代码注释里有写.
最后, 取答案需要分情况讨论:
没有空鱼缸, 那么必须满足"至少一个$M$, 一个$F$“的条件, 所以答案是$dp(non\_empty, 0, 1, 1)$
有空鱼缸, 没有限制条件. 枚举空鱼缸的使用数量, 对$dp(non\_empty, k, 0/1, 0/1), 0 \le k \le empty\_tank$ 取min就是答案了.
复杂度 $O(n^2)$
终于写完了…
总结一下, 为什么没有想到这样的dp
首先, 没有想到只需要保存"前$i$个是否有标号为$M$或$F$“这样的状态, 傻乎乎地保存前$i$个有$j$个标号为$M$.
其次, 没有想到把空鱼缸数量保存在状态里. 可能是受到保存了$M$的个数的影响, 再加一维就炸了, 所以根本没往这方面想.
由于一开始开了LL, 然后炸空间了, 所以$dp$滚了第一维. 后来发现最大值不会超过int, 于是改回了int, 但是滚动数组依然保留, 没算不滚会不会炸.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
const int MAXN = 3e3+10;
int n, empty_tank, non_empty, a[MAXN], b[MAXN];
int dp[2][MAXN][2][2], male = 0;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d%d", &x, &y);
if (!x && !y)
empty_tank++;
else {
a[++non_empty] = x;
male += x;
b[non_empty] = y;
}
}
if (!male) {
puts("0");
return 0;
}
for (int i = 0; i <= empty_tank; i++) {
dp[0][i][0][0] = dp[0][i][0][1] = dp[0][i][1][0] = dp[0][i][1][1] = INTINF;
dp[1][i][0][0] = dp[1][i][0][1] = dp[1][i][1][0] = dp[1][i][1][1] = INTINF;
}
dp[0][0][0][0] = 0;
for (int i = 1; i <= non_empty; i++) {
for (int j = 0; j <= empty_tank; j++) {
int cur = i&1;
// 初始化
dp[cur][j][0][0] = dp[cur][j][0][1] = dp[cur][j][1][0] = dp[cur][j][1][1] = INTINF;
//至少有一个是F或者M, 所以00不存在.
dp[cur][j][0][0] = INTINF;
int &dpij01 = dp[cur][j][0][1];
// 之前有M, 当前为M, 不移动到空
dpij01 = min(dpij01, dp[cur^1][j][0][1] + 2 * a[i]);
// 之前无M, 当前为M, 不移动到空
dpij01 = min(dpij01, dp[cur^1][j][0][0] + 2 * a[i]);
// 之前有M, 当前为M, 全移动到空
dpij01 = min(dpij01, dp[cur^1][max(0, j - a[i])][0][1] + 2 * a[i] - min(j, a[i]));
// 之前无M, 当前为M, 全部移到空
dpij01 = min(dpij01, dp[cur^1][max(0, j - a[i])][0][0] + 2 * a[i] - min(j, a[i]));
int &dpij10 = dp[cur][j][1][0];
// 由于F移动到空和不移动到空的花费相同, 移动的话浪费了空, 不划算, 所以F不移动到空
// 之前有F, 当前为F
dpij10 = min(dpij10, dp[cur^1][j][1][0] + a[i] + b[i] - 1);
// 之前无F, 当前为F
dpij10 = min(dpij10, dp[cur^1][j][0][0] + a[i] + b[i] - 1);
int &dpij11 = dp[cur][j][1][1];
// 之前有F和M, 当前为M, 不移动到空
dpij11 = min(dpij11, dp[cur^1][j][1][1] + 2 * a[i]);
// 之前有F和M, 当前为M, 全移动到空
dpij11 = min(dpij11, dp[cur^1][max(0, j - a[i])][1][1] + 2 * a[i] - min(j, a[i]));
// 之前有F和M, 当前为F, 不移动到空
dpij11 = min(dpij11, dp[cur^1][j][1][1] + a[i] + b[i] - 1);
// 之前有F无M, 当前为M, 不移动到空
dpij11 = min(dpij11, dp[cur^1][j][1][0] + 2 * a[i]);
// 之前有F无M, 当前为M, 全移动到空
dpij11 = min(dpij11, dp[cur^1][max(0, j - a[i])][1][0] + 2 * a[i] - min(j, a[i]));
// 之前无F有M, 当前为F, 不移动到空
dpij11 = min(dpij11, dp[cur^1][j][0][1] + a[i] + b[i] - 1);
}
}
int ans = INTINF;
if (empty_tank)
for (int i = 0; i <= empty_tank; i++) {
ans = min(ans, dp[non_empty&1][i][0][0]);
ans = min(ans, dp[non_empty&1][i][1][0]);
ans = min(ans, dp[non_empty&1][i][0][1]);
ans = min(ans, dp[non_empty&1][i][1][1]);
}
else
ans = dp[non_empty&1][0][1][1];
printf("%d\n", ans);
return 0;
}
|
$n \times n$的矩阵$M_{i, j}$, 选择$n$个数, 要求每行每列只有一个被选中, 且$n$个数的乘积最大. 求选了哪些数(输出第$i$列选的是第几个数)
$1 \le n \le 100$
二分图的带权匹配. 行和列匹配, 选择的就是哪行哪列的数了.
乘积取对数, 就是求和了.
最大值取个相反数, 就是最小值了.
最小费用最大流.
复杂度 $O($能过$)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
const int maxn = 210;
const int maxm = 3e4 + 10;
int n, s, t;
struct Edge {
int to, next, cap, flow;
LD cost;
} edges[maxm];
int head[maxn], mm = 0;
void AddEdge(int u, int v, int cap, LD cost) {
edges[mm] = Edge{v, head[u], cap, 0, cost};
head[u] = mm++;
}
void AddNet(int u, int v, int cap, LD cost) {
AddEdge(u, v, cap, cost);
AddEdge(v, u, 0, -cost);
#ifdef D
printf("(%d, %d), cap = %d, cost = %Lf\n", u, v, cap, cost);
#endif
}
LD d[maxn];
int inq[maxn], p[maxn], a[maxn];
bool EK(int &flow, LD &cost) {
for (int i = 1; i <= 2*n+2; i++)
d[i] = INTINF;
queue<int> q;
q.push(s), d[s] = 0;
inq[s] = 1, p[s] = -1, a[s] = INTINF;
while (!q.empty()) {
int u = q.front();
q.pop(), inq[u] = 0;
for (int i = head[u]; ~i; i = edges[i].next) {
Edge &e = edges[i];
if (d[e.to] > d[u] + e.cost && e.cap > e.flow) {
d[e.to] = d[u] + e.cost;
a[e.to] = min(a[u], e.cap - e.flow);
p[e.to] = i;
if (!inq[e.to])
q.push(e.to), inq[e.to] = 1;
}
}
}
if (d[t] >= INTINF)
return false;
flow += a[t];
cost += a[t] * d[t];
for (int i = p[t]; ~i; i = p[edges[i^1].to]) {
edges[i].flow += a[t];
edges[i^1].flow -= a[t];
}
return true;
}
int main() {
scanf("%d", &n);
memset(head, -1, sizeof(head));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
int p;
scanf("%d", &p);
AddNet(i, j+n, 1, -log(p));
}
s = 2*n + 1, t = s + 1;
for (int i = 1; i <= n; i++) {
AddNet(s, i, 1, 0);
AddNet(i+n, t, 1, 0);
}
int flow = 0;
LD cost = 0;
while (EK(flow, cost));
for (int u = 1+n; u <= 2*n; u++)
for (int i = head[u]; ~i; i = edges[i].next) {
Edge &e = edges[i];
if (e.flow && e.to != t) {
printf("%d ", e.to);
break;
}
}
puts("");
return 0;
}
|
跑步, 总共跑$v$圈. 每圈有$n$个标记, 求跑完$p\%$时, 至少需要经过几个标记. 对于$p = 10, 20, \dots 80, 90$输出$9$个答案.
$1 \le v, n \le 10^4$
水题, $\lceil \frac{vnp}{100} \rceil$.
复杂度 $O(1)$
1
2
3
4
5
6
7
8
9
10
|
int v, n;
int main() {
scanf("%d%d", &v, &n);
int sum = v * n;
for (int i = 1; i < 10; i++)
printf("%d ", (int)ceil(1.0 * sum * i / 10));
puts("");
return 0;
}
|
$n$个点$m$条边, 每个点有点权$t_i$, 每条边有边权$d_i$. $q$个询问如下 a b k op, 表示询问一条$a$到$b$的最短路, 且满足路径上(除端点)的点权小于等于所有点点权的第$k$小(或大于第$k$大), 当 op 为$0$时表示第k小, $1$表示第$k$大.
其中$k$小/大是去重以后的. ($k$可能大于去重以后的点权总数.)
$1 \le n \le 400, 0 \le m \le \frac{n(n-1)}{2}, -10^9 \le t_i \le 10^9, 1 \le q \le 10^5$
最短路问题, 且$n$很小, 自然尝试Floyd.
和灾后重建很像, 我们把询问离线, 然后就可以在Floyd的过程中更新对应的答案了.
以$k$小为例, 先对询问递增排序, 再对点的权值递增排序, 按照排序以后的顺序枚举最外层的点(Floyd中间点). 这样做完这个中间点以后, 已经加入的点(用来更新的中间点)权值一定不比当前中间点大, 并且比当前中间点大的点都没有加入. 所以, 我们在这张"临时"的图上对"路径上的点权小于等于"这个中间点的权值的询问进行查询. $k$大反过来做一遍即可.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
const int MAXN = 4e2+10;
const int MAXQ = 1e5+10;
struct QLow {
int id, a, b;
};
vector<QLow> qlow[MAXN];
struct QHigh {
int id, a, b;
};
vector<QHigh> qhigh[MAXN];
struct Planet {
int id, t;
bool operator < (const Planet &P) const {
return t == P.t ? id < P.id : t < P.t;
}
} planets[MAXN];
int n, m, q, G[MAXN][MAXN], tmp[MAXN][MAXN], ans[MAXQ];
int main() {
// freopen("in", "r", stdin);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
planets[i].id = i;
scanf("%d", &planets[i].t);
}
sort(planets + 1, planets + 1 + n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
G[i][j] = i == j ? 0 : INTINF;
for (int i = 1; i <= m; i++) {
int x, y, d;
scanf("%d%d%d", &x, &y, &d);
G[x][y] = G[y][x] = min(d, G[x][y]);
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int a, b, k, t, cnt = 0;
scanf("%d%d%d%d", &a, &b, &k, &t);
if (t) {
for (int j = n; j; j--) {
while (j > 1 && planets[j].t == planets[j-1].t)
j--;
if (++cnt >= k) {
qhigh[j].push_back(QHigh{i, a, b});
break;
}
}
// 出题人不讲武德, k会大于去重后的总数
// 如果不加下面的话会WA31
if (cnt < k)
qhigh[1].push_back(QHigh{i, a, b});
}
else {
for (int j = 1; j <= n; j++) {
while (j < n && planets[j].t == planets[j+1].t)
j++;
if (++cnt >= k) {
qlow[j].push_back(QLow{i, a, b});
break;
}
}
if (cnt < k)
qlow[n].push_back(QLow{i, a, b});
}
}
memset(ans, INTINF, sizeof(ans));
memcpy(tmp, G, sizeof(G));
for (int k = 1; k <= n; k++) {
int id = planets[k].id;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
tmp[i][j] = tmp[j][i] = min(tmp[i][j], tmp[i][id] + tmp[id][j]);
for (auto x : qlow[k])
ans[x.id] = tmp[x.a][x.b];
}
memcpy(tmp, G, sizeof(G));
for (int k = n; k; k--) {
int id = planets[k].id;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
tmp[i][j] = tmp[j][i] = min(tmp[i][j], tmp[i][id] + tmp[id][j]);
for (auto x : qhigh[k])
ans[x.id] = tmp[x.a][x.b];
}
for (int i = 1; i <= q; i++)
printf("%d\n", ans[i] < INTINF ? ans[i] : -1);
return 0;
}
|
$n$个人围一圈打牌. 规则如下:
- 牌的大小如下 “$A23456789DQJK$”.
- 每个人开始抽$4$张牌, 随机选一个人先手, 多给一张牌"Wild”(没人要的野牌).
- 轮到某个人, 如果他手上有"Wild"且不是刚刚得到(先手第一次得到的"Wild"也算刚刚得到), 则把"Wild"给下家; 否则, 他选择手上出现次数最少的牌中的某一张传给下家, 如果有出现次数相同的牌, 则选择点数小的.
- 当一个人传完了牌以后, 轮到下家传.
定义"获胜状态"为手上有且仅有$4$张点数相等的牌.
当传完牌之后, 可能会产生若干个"获胜状态"的人. 如果只有一个人是"获胜状态”, 则他赢, 游戏结束; 如果有多个人是"获胜状态”, 则手牌点数小的人赢, 游戏结束.
给出$n$个人的初始手牌和先手$k$, 求最后获胜的是谁.
$2 \le n \le 13$
模拟即可.
用 set 保存手牌, 节点结构体含有某种牌的点数和数量数, 按照数量递增, 点数递增排序, 那么 set 里的第一个就是要给下家的牌了.
对于"Wild", 把他看成两种, 一种是刚拿到, 不能打. 那么设置他的"数量"为$6$(只要比$4$大就行), 他就排在了最后面; 另一种是(下一轮)马上打出, 那么设置他的"数量"为$0$, 他就排在了最前面.
刚拿到"Wild", 设为第一种, 打完其他牌以后, 删除第一种"Wild"(最后一个点), 再插入第二种"Wild".
详见代码.
关于 set 的删除操作:
auto x, x 是"副本", 不能直接修改. 他不是迭代器, 可以直接 erase(x).
插入:
todo
复杂度是玄学.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
const int maxn = 20;
int VAL[300];
struct Node {
int val, cnt;
bool operator < (const Node &N) const {
return cnt == N.cnt ? val < N.val : cnt < N.cnt;
}
};
int n, k;
char str[maxn];
set<Node> cards[maxn];
// 第一次wild 为 val = 14, cnt = 6
// 第二次wild 为 val = 0, cnt = 0
void Insert(int id, int val) {
if (val == 0) {
cards[id].insert(Node{VAL[1], 6});
return;
}
int app = 0;
// 如果有, 则次数加一
for (auto nd : cards[id]) {
if (nd.val == val) {
cards[id].erase(nd);
nd.cnt++;
cards[id].insert(nd);
app = 1;
break;
}
}
// 没有, 则新建
if (!app)
cards[id].insert(Node{val, 1});
}
void Erase(int id, int val) {
for (auto nd : cards[id])
if (nd.val == val) {
cards[id].erase(nd);
nd.cnt--;
if (nd.cnt > 0)
cards[id].insert(nd);
break;
}
}
int main() {
for (int i = 2; i <= 9; i++)
VAL[i+'0'] = i;
VAL['A'] = 1, VAL['D'] = 10, VAL['Q'] = 11, VAL['J'] = 12, VAL['K'] = 13, VAL[1] = 14, VAL[2] = 0;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%s", str);
for (int j = 0; str[j]; j++) {
int val = VAL[str[j]];
Insert(i, val);
}
}
cards[k].insert(Node{VAL[1], 6});
int cur = k, nxt = cur % n + 1;
while (1) {
set<Node>::iterator it = cards[cur].begin();
Erase(cur, (*it).val); // cur 减去一张牌
Insert(nxt, (*it).val); // nxt 加上一张牌
// 判断最后一个点是不是wild, 是的话改一下
it = cards[cur].end();
--it;
if ((*it).val == VAL[1]) {
cards[cur].erase(it);
cards[cur].insert(Node{VAL[2], 0});
}
int winner = 0, winner_val = 20;
for (int i = 1; i <= n; i++) {
if (cards[i].size() == 1) {
it = cards[i].begin();
if ((*it).cnt == 4) {
if ((*it).val < winner_val) {
winner_val = (*it).val;
winner = i;
}
}
}
}
if (winner) {
printf("%d\n", winner);
break;
}
cur = nxt;
nxt = cur % n + 1;
}
return 0;
}
|
求 $\sum_{i=0}^n \tbinom{n}{i} \mod 2$
$2 \le n \le 10^{18}$
组合数取模, 想到 Lucas 定理.
Lucas 定理:
$$\tbinom{n}{m} \equiv \Pi \tbinom{n_i}{m_i} \mod p$$
其中 $p$ 是一个质数, $n_i, m_i$ 是 $p$ 进制下的各位:
$$n = n_k p^k + n_{k-1} p^{k-1} + \dots + n_2 p^2 + n_1 p^1 + n_0 p^0$$
$$m = m_k p^k + m_{k-1} p^{k-1} + \dots + m_2 p^2 + m_1 p^1 + m_0 p^0$$
这道题中, $p=2$, 对于一个给定的$n$, 想知道有多少个$m, 0 \le m \le n$ 满足$\tbinom{n}{m} \equiv \Pi \tbinom{n_i}{m_i} \equiv 1 \mod 2$. 要满足以上条件, 则需要$\forall \tbinom{n_i}{m_i} \equiv 1 \mod 2$. 我们知道
$$\tbinom{0}{1} = 0, \tbinom{0}{0} = 1, \tbinom{1}{1} = 1, \tbinom{1}{0} = 1$$
所以对$n$和$m$二进制分解, 其中$n$为$0$的位对应的$m$的位上不能为1, 只能为0; $n$为$1$的位对应的$m$的位上可以为$0$也可以为$1$. 也就是说, 对于$n$为$1$的位, $m$的位可以有两种选择. 每一位的选择相互独立, 乘法原理. 所以, 设 count(n) 为 $n$的二进制分解下$1$的个数, 合法的$m$的个数为: $2^{count(n)}$
复杂度 $O(logn)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
LL n;
LL count(LL x) {
LL res = 0;
while (x) {
x -= lowbit(x);
res++;
}
return res;
}
int main() {
scanf("%lld", &n);
LL p = count(n);
printf("%lld\n", 1ll << p);
return 0;
}
|
连续放了$n$袋爆米花, 每袋里有$p_i$个, 有$c$个人吃这些爆米花. 吃的规则如下:
- 一个人一次只能吃连续的标号袋子里的爆米花
- 一旦某袋爆米花被某个人吃了, 这袋爆米花不能由其他人吃
- 一个人一次不能吃超过$t$个爆米花
- 一个人吃一次的用时为$1$
- $c$个人可以同时开始吃, 且可以吃$0$个
问吃完的最少用时.
$1 \le n \le 10^5, 1 \le c \le 10^5, 1 \le t \le 50, 1 \le p_i \le 10^4$
二分答案$s$(我也不知道为什么要这么想). 然后一个人最多吃的个数就是$st$, 又由于要吃连续的, 就可以按顺序贪心取$\sum p$, 保证其小于$st$且最大. 做完一个人就计数加一, 判断能否不超过$c$个人做完所有的$p$.
复杂度 $O(nlognp)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
const int MAXN = 1e5+10;
int n, c, t, p[MAXN];
bool Check(LL s) {
LL up = s * t;
int last = 0, cnt = 0;
for (int i = 1; i <= n; i++) {
if (p[i] - p[last] > up) {
if (++cnt == c)
return false;
last = --i;
}
}
return true;
}
int main() {
scanf("%d%d%d", &n, &c, &t);
for (int i = 1; i <= n; i++) {
scanf("%d", p + i);
p[i] += p[i-1];
}
int l = 0, r = INTINF, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (Check(mid)) {
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
printf("%d\n", ans);
return 0;
}
|