C(math, 括号对)D(math,集合,数论,动归)E(并查集)
C
题目
https://atcoder.jp/contests/arc141/tasks/arc141_c
他给两个排列p和q, 长度2n
构造 长2n的括号字符串,含有n个左括号,n个右括号
使得p是所有 让 s[p[i]] 为合法括号序列中的字典序最小的
同时q是所有 让 s[q[i]] 为合法括号序列中的字典序最大的
范围
n<=2e5
2s
1024mb
题解
我的思路
显然开始和最后的位置分别是 左右括号
对于p, 当左右括号都可以选时,一定会选没有被选坐标最小的
当前缀完成匹配时, 只能选左括号, 这时选左括号坐标最小的
于是, 如果当前坐标以前的没有选完,那么说明当前位置是左括号,且没有被选的是右括号
对于q,类似的, 先选最大的, 左括号也是先选最大的
这样分别确定的右括号不少于 左括号个数
但是对于剩余没有填的位置怎么做,我没有思路了,因为它不只需要保证一个排列合法,它需要保证p和q都合法
官方
前面还是一样的, 但这里强调了是 奇数处出现, 因为 要前面匹配完,说明前面用了偶数个
而且不像我那样 需要 前缀未填完, 而只是 奇小于下一个偶, P[2i-1] < P[2i]
但说是 如果还是有多个候选的,那么就是没有方案
如果只有一个候选S,就看是否同时满足p和q
简单的来讲如果S或它的逆序是一个合法的括号序列, (一般情况也可以类似证明, 因为一般的S 可以表示成合法和 和 逆序合法的连接
令 L1 < L2 < L3 … < LN 分别是左括号的下标
R1 < R2 < R3 … < RN 分别是右括号的下标
既然S是合法的,那么有 Li < Ri
因此字典序最大的排列是$L_N,R_N,L_{N-1},R_{N-1},…,L_1,R_1$
因此 S是唯一的
并且确定的过程和上述描述的也是一致的
如果S的逆序是合法的
那么有
令 L1 < L2 < L3 … < LN 分别是左括号的下标
R1 < R2 < R3 … < RN 分别是右括号的下标
既然S的逆序列是合法的,那么有 Li > Ri
所以字典序最小的是$L_1,R_1,L_2,R_2,…,L_N,R_N$
并且确定的过程和上述描述的也是一致的
再对于一般序列来讲
又回到 括号序列的常用技巧,左括号+1,右括号-1
那么其实就是 一些在正平面的一些曲线和负平面的一些曲线,
显然由和0点隔开的 顺序上也相互独立(见官方youtube上画的图
这样 对于每一段来说,是正平面则由最大序列唯一确定, 是负平面则由最小序列
所以 整体都是唯一的
这样就是官方提接说的一般序列的 拼接类似
综上得证
代码
https://atcoder.jp/contests/arc141/submissions/32155305
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
| #include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}
int p[400010];
int q[400010];
char s[400010];
char sets(int i,char ch){
return (s[i] && s[i] != ch) ? 0 : (s[i] = ch);
}
bool work(){
int n = read() * 2;
rep(i,0,n) p[i] = read() - 1;
rep(i,0,n) q[i] = read() - 1;
for(auto [arr, cmp]:vector<pair<int *,int> > {{p, 1},{q,-1}}){
rep(i,0,n-1) {
if((arr[i] - arr[i+1]) * cmp <= 0) continue;
if(!sets(arr[i],'(') || !sets(arr[i+1],')')) return false;
}
}
rep(i,0,n) if(!s[i]) return false;
for(auto [arr,st,d]:vector<tuple<int*,int,int> >{{p,0,1},{q,n-1,-1}}){
int i0 = st;
int i1 = st;
int cnt = 0;
vector<bool> vis(n,false);
rep(i,0,n){
int pos ;
if(cnt == 0){
while(vis[i1] || s[i1] != '(') i1+=d;
pos = i1;
}else{
while(vis[i0])i0+=d;
pos = i0;
}
if(arr[i] != pos) return false;
vis[pos] = true;
cnt += s[pos] == '('?1:-1;
}
if(cnt) return false;
}
printf("%s\n",s);
return true;
}
int main(){
if(!work()) printf("-1\n");
return 0;
}
|
D
题目
https://atcoder.jp/contests/arc141/tasks/arc141_d
对于一个集合S, 任意两个元素不成倍数关系,那么认为是一个好集合
给一个n个元素,元素值范围在[1,2m]之间的集合, 元素值不重复, 给值时从小到大
对于每个元素,判断是否存在一个S的子集,包含该元素且是好集合
范围
M<=N<2M
M 3e5
题解
我的想法
既然给值就是从小到大, 那么省去了排序
既然一定要a[i], 那么它的倍数和约数一定不可行,而约数是log级别的个数,
这里虽然问是否能恰好m个, 但如果>=m 合法,删掉多于m的依然合法
所以变成能否有不少于m个
对于即不是ai倍数,也不是ai约数的, 考虑最多能取多少个
于是集合被化分成(ai,ai约数,ai倍数) (其它), 那么包含ai的最大的个数是 1+max(其它)
首先 值的倍数从均摊上讲 也是 log级别的, 因为 1/2+1/3+1/4… 在小的时候是 常数倍
但 剩下的如何尽可能多的取, 以及如果只是暴力去尝试的话, 显然 会达到至少 n平方
另一个就是互斥关系, 如果建立互斥关系的2-sat图, 跑tarjan ,能一次计算
注意到互斥关系不会变, 所以2-sat不会变, 但是怎么选一个而不选其它
官方
其实是个卡着边界的问题
考虑所有奇数的2的幂次倍
(1,2,4,8,16...),(3,6,12,24...),(5,10,20...)
注意到的是 ,一共有m组,且每组内部两两是倍数关系, 因此我们选的答案,不会同时出现在一组中, 所以 至多选m个
这个对答案也有帮助, 如果题目给的S, 在上述的2的幂次倍中 有的组不存在,那么显然达不到m
现在问题是跨组会不会有 倍数关系
假设 $x_1 < x_2$ 都是奇数, 选了 $x_1 2^{p_1},x_22^{p_2}$
那么如果成倍数一定是 $p_2 \ge p_1$ 且 $x_2$是$x_1$的倍数
换句话说, 要想合法, 那么一个数的约数对应的2的幂次要比它本身大
考虑 每个奇数的2的幂次的上下界, [Li,Ri]
直接动归转移方程
对于R[value] = min(R[value 的因子]) - 1 且存在于S
对于L[value] = max(L[value的倍数]) + 1 且存在于S
R1,R2,R3,...R,被选的值,L,...,L 将是合法解, [Li <= 被选的幂次 <= Ri]
因为前面的尽可能大,后面尽可能小且 被选值在范围中
综上 因为因子数和均摊倍数个数都是log级别,所以总的均摊代价就是log级别
代码
https://atcoder.jp/contests/arc141/submissions/32169715
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
107
108
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
ll read(){ll r;scanf("%lld",&r);return r;}
bool exist[600010];
vector<int> ys[600010];
int L[600010];
int R[600010];
int a[600010];
int n,m;
bool w(){
n = read();
m = read()*2;
rep(i,0,n) {
exist[a[i] = read()] = 1;
}
rep(i,1,m/2+1){
if(i%2 == 0)continue;
rep(t,3,m/2+1){
if(t%2 == 0)continue;
if(i*t > m)break;
ys[i*t].push_back(i);
}
}
rep(i,1,m+1){
if(i%2==0)continue;
bool found = false;
int itr = i;
while(itr <= m){
if(exist[itr]){
found = true;
break;
}
itr*=2;
}
if(!found)return false;
}
rep(i,1,m){
if(i%2 == 0) continue;
int pwr = 20;
for(auto item:ys[i]){
pwr = min(pwr,R[item]-1);
}
bool found = false;
while(pwr >= 0){
if(i * (1<<pwr) <= m){
if(exist[i * (1<<pwr)]){
R[i] = pwr;
found = true;
break;
}
}
pwr--;
}
if(!found) return false;
}
per(i,1,m){
if(i%2 == 0) continue;
int pwr = 0;
rep(k,3,m+1){
if(k%2==0)continue;
if(i*k > m)break;
pwr = max(pwr,L[i*k]+1);
}
bool found = false;
while( i*(1<<pwr) <= m){
if(exist[i * (1<<pwr)]){
L[i] = pwr;
found = true;
break;
}
pwr++;
}
if(!found) return false;
if(L[i] > R[i]) return false;
}
rep(i,0,n){
int v = a[i];
int pwr = 0;
while(v%2 == 0){
pwr++;
v/=2;
}
printf("%s\n", L[v] <= pwr && pwr <= R[v]?"Yes":"No");
}
return true;
}
int main(){
if(!w()) rep(i,0,n) printf("No\n");
return 0;
}
|
E
题目
https://atcoder.jp/contests/arc141/tasks/arc141_e
n方个点, (1..n,1..n)
q 个询问
每个询问 a,b,c,d
会把 点((a+k)%n,(b+k)%n) 和 点((c+k)%n,(d+k)%n) 相连, 其中k取 0 到 n-1
询问之间是影响的, 是在上一次结果上继续连
每次回答一个询问操作后,剩下的联通块数
范围
n 2e5
q 2e5
题解
我的思路
首先, 其实让a,b,c,d 变成 a1=(a+n-a)%n,b1=(b+n-a)%n,c1=(c+n-a)%n,d1=(d+n-a)%n, 因为k取[0..n-1], 所以等价
变成 k,(b1+k)%n,(c1+k)%n,(d1+k)%n
画图, 会发现 (k,(b1+k)%n) 在一条45度角的一条斜线上,((c1+k)%n,(d1+k)%n) 也在一条45度角的一条斜线上
- 如果共线, 那么 如果原来不是一个联通块,则 减少了 n-1个联通块, 如果原来是多个联通, 那么对结果影响 = -(个数-1)
有了这个思路, 我们问题通过图像可以变一变
沿着+1,+1的45度, 形成n组点,每组点有个属性内部是否相连
考虑两组之间的关系,
1次连接, 那么这两组形成的是n个连通块, 且内部联通关系,一旦有一个联通则连通
而这个值其实 = gcd(偏移量间隔)
所以未连接和 连接一次的偏移量间隔为 n
而对两个组的影响是相同的
所以变成
哪些组属于一个并查集合, 它们自身内部的偏移量等价(一个值) 它们与根的偏移量等价
似乎就可以做了
但感觉在合并并查集时更新需要注意
然后 真的 我就AC了???? atcoder真的是数学场吗
代码
https://atcoder.jp/contests/arc141/submissions/32185372
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
ll read(){ll r;scanf("%lld",&r);return r;}
int gcd(int a,int b){
while(b!=0){
a=a%b;
swap(a,b);
}
return a;
}
int fa[200010];
int a[4];
int inner[200010];
int tofa[200010];
ll n;
int getfa(int i){
if(i == fa[i]) return i;
int newfa = getfa(fa[i]);
tofa[i] = ((tofa[i] + tofa[fa[i]])%n)%inner[newfa];
return fa[i] = newfa;
}
void link(int u,int v,int off){
fa[v] = u;
inner[u] = gcd(inner[u],inner[v]);
tofa[v] = off % inner[u];
}
int main(){
n = read();
ll q = read();
ll ans = n*n;
iota(fa,fa+n,0);
fill(inner,inner+n,n);
rep(i,0,q){
rep(j,0,4) a[j] = read();
per(j,0,4) (a[j] += n-a[0])%=n;
int g1 = a[1] - a[0];
int g2 = (a[3]-a[2]+n)%n;
int off = a[2] - a[0];
int f1 = getfa(g1);
int f2 = getfa(g2);
if(f1 == f2){
ans -= inner[f1];
inner[f1] = gcd(inner[f1], 2*n + tofa[g1] - tofa[g2] + off);
ans -= -inner[f1];
}else{
ans -= inner[f1] + inner[f2];
link(f1,f2, (2*n + tofa[g1] - tofa[g2] + off)%n);
ans -= - inner[f1];
}
printf("%lld\n",ans);
}
return 0;
}
|
总结
C
这个基本的能想到, 但是没有尝试更多数据, 去考虑它的唯一性, 还在想怎么填中间的
这方面要培养,有点像反过来想题目, 如果题目本身设计上有唯一性只是需要证明, 这个思路方向, 因为毕竟是确定有答案的题目而不是开放性问题
另外就是括号序列还是不熟悉, 如果熟悉常见+1,-1套路,画图去思考也会简单不少
虽然从逻辑上 我的 当前前面未填完,则当前(,未填都是), 数学上好像 更多信息, 但这里反而成了干扰
据说能用DP做?
D
这数学性好强啊, 知识点是属于集合论的和数论的,甚至有点抽屉原理,
能想到奇数与它的2的幂次倍数的分组是这个题的核心一点
这一想出后面就自然很多了
E
我这赛后没有看题解,竟然AC了 ??????
参考
官方题解 https://atcoder.jp/contests/arc141/editorial/
官方youtube