C
题目
https://codeforces.com/contest/1685/problem/C
给你一个 n个左括号 n个右括号 的序列
最小次数, 翻转子区间,让整个括号合法
范围
n 1e5
1s
256MB
题解
我的思路
括号嘛, 认知还在任意前缀1的个数大于等于0的个数
想的是先转换成0/1,两个指针包裹 两头贪心
没了, 没思路了, 感觉贪心都不对的
写了果然wa了
官方
别统计1和0, 直接 左括号1贡献,右括号-1贡献 XD
同样的也就是前缀和 大于等于0
一个数学结论, 至多两次就能让结果合法
如果 前缀i是 所有前缀中最大的,那么翻转 [1..i]和 [i+1,2n]
因为 对于 j<=i,新的前缀 newpre[j] = pre[i] - pre[j] >= 0
因为 对于 j> i,新的前缀 newpre[j] = pre[2n] - pre[j] + pre[i] = pre[i] - pre[j] >= 0
那么问题变成有没有办法一次翻转, 因为0次是直接合法,很容易判断,2次有上述方案
对于一次反转, 如果是[L,R], 那么必然有 L <= 首个负前缀l, R>= 最后一个负前缀r
再数学一点 对于 $i \in [L,R] $, newpre = pre[R] - pre[i-1] + pre[L] >= 0
pre[i-1] <= pre[L] + pre[R] 也就是 区间里所有的都不大于两头的和
而pre[i] 的可选值是 [L..l-1][l..r][r+1..R]
注意到[l..r] 始终被选, 而两头的随着L和R变化
如果L选[0..l-1]中最大
如果R选[r+1..2n]中最大
那么对于两头的来说, 一定成立,而对[l..r] 来说 它们是能选到的最大的,如果这个还不满足,则没有办法了
如果这个满足则是答案
代码
https://codeforces.com/contest/1685/submission/159099077
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
| #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;}
char s[200010];
int n;
int pre[200010];
void calc(int st){
int last = -1;
per(i,0,n){
if(pre[i+1] < 0){
last = i;
break;
}
}
int ml = 0;
int mr = 0;
rep(i,0,st){
ml = max(ml,pre[i+1]);
}
rep(i,last,n){
mr = max(mr,pre[i+1]);
}
rep(i,st,last+1){
if(pre[i+1] > ml+mr){
printf("2\n");
int maxi = 0;
rep(i,0,n){
if(pre[i+1] > pre[maxi]){
maxi = i+1;
}
}
printf("1 %d\n",maxi);
printf("%d %d\n",maxi+1,n);
return ;
}
}
printf("1\n");
int maxl = 0;
rep(i,0,st){
if(pre[i+1] > pre[maxl]) maxl = i+1;
}
int maxr = n-1;
rep(i,last,n){
if(pre[i+1] > pre[maxr]) maxr = i+1;
}
printf("%d %d\n",maxl+1,maxr);
}
void w(){
n = read();
n*=2;
scanf("%s",s);
rep(i,0,n) pre[i+1] = pre[i] + (s[i] =='('?1:-1);
rep(i,0,n){
if(pre[i+1] < 0){
calc(i);
return ;
}
}
printf("0\n");
}
int main(){
int t = read();
while(t--)w();
return 0;
}
|
D
题目
https://codeforces.com/contest/1685/problem/D1
https://codeforces.com/contest/1685/problem/D2
给一个1到n的排列p
定义一个排列p的代价为
$\sum {q_i - p_{q_{i+1}}}$
找最小代价的排列q
D2: Hard version: 最小代价排列中字典序最小的
范围
t 100 组测试
n 200, $\sum{n} \le 400$
1s
256mb
题解
我的思路
注意到上面的求和表达式,也就是每一项和它的后一项的差的绝对值,
那么如果一个排列q合法,那么 对它循环的旋转也合法
再来看期望最小值, 如果能够成 |1-1|+..+|v-v| ,全部是相同相减, 那么最小就是0, 而这种需要所有的跳转关系构成一个大环, 而这样解法也就唯一(对于循环的最小来说)
以样例中的2 1, => |1 - (P2=1)| + |2 - (P1=2)| = 0
对于不够成大环的, 必定跳转关系是多个小环
以样例中的2 3 1 4, 这样 是 1->3->2 构成环 ,4 单独一个环, 那么如果让环内代价为0, 那剩下的就是两头的链接代价,
|1 - (P3=1)| + |3 - (P2=3)| + |2 - (P4=4)| + |4 - (P1=2)| = 2+2
|3 - (P2=3)| + |2 - (P1=2)| + |1 - (P4=4)| + |4 - (P3=1)| = 3+3
|2 - (P1=2)| + |1 - (P3=1)| + |3 - (P4=4)| + |4 - (P2=3)| = 1+1
其实是环中选出一个值 和 其它环作拼接, (这里保证环内最小 不知道细节怎么证,但感觉看起来这样贪没啥问题
再比如样例 5 4 3 2 1, 环分别是 1->5, 2->4, 3
分别拿出来1,2,3
(5->1) (3) (4->2)
代价就是 |1-3| + |3-2| + |2-1|
这里也很清晰的是, 这样如果确定了拿出来的值,那么最小代价 = 2|max - min|
综上所述
找环
每个环拿出一个值来连接, 让所有拿出来的值 最大减最小尽量小, 这样D1 做完了
需要在这样的方法中, 1. 正负顺序, 2, 循环平移到1开始 的字典序列最小
问题来了
找环很简单, 但是如何让每个环拿出来一个值,差尽量小?
这里我想到的是染色+滑动窗口, 记录最小的滑动窗口和位置
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
| #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 p[210];
int p2i[210];
int c[210];
void w(){
int n = read();
fill(c+1,c+n+1,-1);
rep(i,1,n+1) {
p[i] = read();
p2i[p[i]] = i;
}
int color = 0;
rep(i,1,n+1) {
if(~c[i])continue;
int itr = i;
do{
c[itr] = color;
itr = p2i[itr];
}while(itr != i);
color++;
}
if(color == 1){
int itr = 1;
do{
printf("%d ",itr);
itr = p2i[itr];
}while(itr != 1);
printf("\n");
return ;
}
vector<int>cnt(color,0);
int ansst = 0;
int anssz = n+1;
int l = 1;
int r = 0;
int cur = 0;
while(cur < color && r+1 < n+1) if(++cnt[c[++r]] == 1) cur ++;
while(l <= r){
if( r-l+1 <= anssz){
anssz = r-l+1;
ansst = l;
}
if( -- cnt[c[l++]] == 0 ) cur--;
while(cur < color && r+1 < n+1){
++r;
cnt[c[r]] ++;
if(cnt[c[r]] == 1) cur ++;
}
if(cur < color)break;
}
fill(c+1,c+n+1,-1);
rep(i,ansst,ansst+anssz - 1 + 1){
if(~c[i])continue;
int itr = i;
do{
printf("%d ",p2i[itr]);
c[itr] = 1;
itr = p2i[itr];
}while(itr != i);
}
printf("\n");
}
int main(){
int t = read();
while(t--)w();
return 0;
}
|
然而实现以后wa2的第11个样例了
如果按照我上面所说的, (2,3) (1) (4) 这样的三个环, 那么 最大最小差是|4-1| = 3, 所以答案是6
然而, 给了一个拆掉环还更小的方法
q = 1 3 4 2
|1 - P3| + |3 - P4| + |4 - P2| + |2 - P1| = |1 - 2| + |3 - 4| + |4 - 3| + |2 - 1| = 4
emmmmmmm
所以我的思路的细节并卜行
官方 D1
也是先考虑什么时候可以得到零
也是按照 跳转构成的环 来看, 假设有k个环
跨环 的链接 至少是1, 所以下界是 2(k-1)
给出一种构造方法
初始化 p1 = p
for x = 1..n-1 如果 对当前p1 来说 x和 x+1在不同的环中, 则交换他们
显然根据学过的 排列的环的性质来讲, 每次交换两个环里的值 相当于把两个环合并
那么 也就是k-1次操作就可以全部合并成一个环
最后 $q_i = p1_{q_{i+1}}$ 了, 显然这就是一个环, 这个答案对于p1来说,就是0
但我们求的是对于p
$|q_i - p1_{q_{i+1}}| = |p1_{q_{i+1}} - p_{q_{i+1}}|$ 了, 反过来看操作毕竟交换是对称的, 考虑从p1变到p, 每一次交换至多会让结果+2, 因为交换的是两个相邻的值, 所以 答案不大于2(k-1)
综上 从下界看 不小于2(k-1), 从操作上看不大于2(k-1), 所以这个方案就是2(k-1)
至此 并查集随便搞一搞 D1 就做了
D2 现场只有4个人AC了 XD
pi向i连一条有向边
问题变成, 添加一些 i->i-1 和 i-1 -> i 变成 存在欧拉回路
其实和上面 等价的, 这里的环和上面的边对应, 而成欧拉回路, 就是和变成新的环
代码
D1
https://codeforces.com/contest/1685/submission/159201728
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
| #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 p[210];
int p2i[210];
int vis[210];
int fa[210];
int getfa(int i){ return i==fa[i]?i:(fa[i] = getfa(fa[i]));}
void link(int u,int v){
int fu = getfa(u);
int fv = getfa(v);
if(fu == fv)return;
fa[fu] = fv;
}
void w(){
int n = read();
fill(vis+1,vis+n+1,false);
iota(fa,fa+n+1,0);
rep(i,1,n+1) {
p[i] = read();
p2i[p[i]] = i;
}
rep(i,1,n+1){
if(vis[i])continue;
int itr = i;
do{
vis[itr] = true;
link(itr,i);
itr = p2i[itr];
}while(itr != i);
}
rep(v,1,n){
if(getfa(v) == getfa(v+1))continue;
swap(p[p2i[v]],p[p2i[v+1]]);
swap(p2i[v],p2i[v+1]);
link(v,v+1);
}
int itr = 1;
do{
printf("%d ",itr);
itr = p2i[itr];
}while(itr != 1);
printf("\n");
}
int main(){
int t = read();
while(t--)w();
return 0;
}
|
总结
C
括号匹配还是不熟, 1,-1贡献 比1和0统计好很多
这最大值翻转只需要两次也是妙啊
后面的切割和最值
完全就是math,math,math
D1
想到环 和 环之间是好的
但是我构造能力实在是太菜了
而且下界估计想法也有问题,错误的下界估计也会影响思路
感觉这个题还是属于排列的环相关的知识点
然后有上下界相等, 和操作与逆向操作对结果的影响
参考
官方
https://www.cnblogs.com/QQQ0000/p/16321569.html