day 1 模拟赛 1（周赛）

模拟赛 1（周赛）

T3 P12723 括号

一个括号序列的价值定义如下：

\(()=1,(X)=2X,XY=X+Y\)

例如 \((()())()(())\) 的价值为 \(4+1+2=7\)。

给定两个括号序列，比较他们的大小。

考虑如何求出一个括号序列的价值。

对于每个连续的 ()，他的贡献为 \(2^k\)，其中 k 为这个括号外边的括号层数，所以我们需要遍历一次括号序列，在这过程中计算当前的层数（碰到左括号加一，右括号减一），然后累加所以最内侧括号的价值即可。

最终的结果会很大，我们发现累加的数都是 2 的整数次方，我们可以像二进制一样，存一下对于每个 x 加过几次 \(2^x\)，然后最后统一进位，从低位到高位，设这一位的数为 \(a\)，则下一位需要增加 \(a/2\)，这一位余下 \(a\%2\)，最后把两个数的数组，从高位到低位比较即可。-------------------------------100分

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,ans1[3000500],ans2[3000500];signed main(){cin>>t;while(t--){string a,b;cin>>a>>b;int n=a.length(),x=0;for(int i=0;i<=n+100;i++)ans1[i]=0;for(int i=1;i<=n;i++){if(a[i-1]=='(')x++;else{x--;if(a[i-2]=='('){ans1[x]++;}}}for(int i=0;i<=n+100;i++){ans1[i+1]+=ans1[i]/2;ans1[i]%=2;}n=b.length(),x=0;for(int i=0;i<=n+100;i++)ans2[i]=0;for(int i=1;i<=n;i++){if(b[i-1]=='(')x++;else{x--;if(b[i-2]=='('){ans2[x]++;}}}for(int i=0;i<=n+100;i++){ans2[i+1]+=ans2[i]/2;ans2[i]%=2;}int flag=1;for(int i=n+100;i>=0;i--){if(ans1[i]>ans2[i]){flag=0;cout<<">\n";break;}else if(ans1[i]<ans2[i]){flag=0;cout<<"<\n";break;}}if(flag)cout<<"=\n";}return 0;
}

T4 P11207 卡牌

两人各有 \(n\) 张有序的卡牌，他们轮流按照顺序打出手中的牌。

这些卡牌有三种颜色，当一人打出牌后，若打出的所有牌，三种颜色的数量相同，那么这个人获胜。

你可以修改两人任意一人的任意卡牌，求最小的修改数量，使先手获胜。

注意到答案只有可能为 \(0,1,2\)，因为不管什么牌，我们都可以修改前 \(2\) 张牌，使得前 \(3\) 张牌互不相同，让先手在第二轮获胜。

先模拟一遍，如果先手先获胜，那么答案为 \(0\)，现在只需要考虑修改 \(1\) 次是否可行。

可以暴力枚举修改的卡牌位置，以及颜色，时间复杂度 \(O(n^2)\)。-------------------------------38分

考虑如何在判断 \(1\) 次修改是否可行上优化。

我们需要保证存在一个时刻先手方获胜且在这之前后手放不获胜。

记 \(lst_{i,j}\) 表示当前能否把一张颜色为 i 的卡牌换成颜色为 j 的，当已经出的卡牌数量为 3 的倍数时，如果轮到先手，且出牌的颜色为 \(n/3-1,n/3,n/3+1\)，那么就要检验能否换对应的颜色，如果可以，那么答案为 1，如果轮到后手，且出牌颜色个数分别为 \(n/3-1,n/3,n/3+1\)，那么此时就要将对应的颜色设为不可交换，不然后手就获胜了。

\(lst_{i,j}\) 设置为可以交换的条件是，我们枚举到了一个颜色 i，且之后没有被上面所说的情况舍弃掉。

循环结束，答案就是 \(2\) 了，复杂度 \(O(n)\)。-------------------------------100分

#include<bits/stdc++.h>
using namespace std;
int t,lst[3][3];
int main(){cin>>t;while(t--){int n;cin>>n;string s1,s2;cin>>s1>>s2;int p=0,v=0,w=0;int flag=0;for(int i=0;i<n;i++){if(s1[i]=='P')p++;else if(s1[i]=='V')v++;else w++;if(p==v&&v==w){flag=1;cout<<"0\n";break;}if(s2[i]=='P')p++;else if(s2[i]=='V')v++;else w++;if(p==v&&v==w){break;}}if(flag)continue;flag=0;p=0;v=0;w=0;memset(lst,0,sizeof(lst));for(int i=0;i<n;i++){if(s1[i]=='P'){p++;lst[0][1]=lst[0][2]=1;}else if(s1[i]=='V'){v++;lst[1][0]=lst[1][2]=1;}else{w++;lst[2][0]=lst[2][1]=1;}if((i*2+1)%3==0){if(p+1==v-1&&v-1==w)if(lst[1][0])flag=1;if(p+1==v&&v==w-1)if(lst[2][0])flag=1;if(p-1==v+1&&v+1==w)if(lst[0][1])flag=1;if(p==v+1&&v+1==w-1)if(lst[2][1])flag=1;if(p-1==v&&v==w+1)if(lst[0][2])flag=1;if(p==v-1&&v-1==w+1)if(lst[1][2])flag=1;}if(s2[i]=='P'){p++;lst[0][1]=lst[0][2]=1;}else if(s2[i]=='V'){v++;lst[1][0]=lst[1][2]=1;}else{w++;lst[2][0]=lst[2][1]=1;}if((i*2+2)%3==0){if(p+1==v-1&&v-1==w)lst[1][0]=0;if(p+1==v&&v==w-1)lst[2][0]=0;if(p-1==v+1&&v+1==w)lst[0][1]=0;if(p==v+1&&v+1==w-1)lst[2][1]=0;if(p-1==v&&v==w+1)lst[0][2]=0;if(p==v-1&&v-1==w+1)lst[1][2]=0;}}if(flag)cout<<"1\n";else cout<<"2\n";}return 0;
}

T5 P12675 区间

有一个排列，你可以进行以下操作：

将 \(A_i\) 加上 1，代价为 1。

将一个 \(A_l=A_r\) 且 \(l<r\) 的区间赋值为 \(-10^9\)，代价为区间长度。

求最小的代价，使得所有元素变成 \(-10^9\)。

显然，最终一定会合并两个区间，合并时的左端点为 1，右端点为 n。考虑以下几种方案：

把 \(A_1\) 加到 \(A_n\)，然后直接对整个序列进行操作 2。（当 A 单调递增时可行）-------------------------------15分
有两个整数 \(1\le x<y\le n\)，我们先对 \([1,x],[y,n]\) 操作，然后再通过 \(a_x=a_y=-10^9\) 对 \([x,y]\) 进行操作。我们考虑代价，操作 2 所产生的代价为 \(n+2\)，因为 x,y 被计算了两次，操作 1 的代价为 \(|a_1-a_x|+|a_y-a_n|\)，考虑如何最小化操作 1 的代价，即我们如何选定 x,y。我们可以先尝试枚举，时间复杂度 \(O(n^2)\)。
还有一种情况，是因为情况 2 的操作 2 有 \(n+2\) 的贡献，我们可以把对 \([x,y]\) 操作改为对 \([x+1,y-1]\) 操作，可以减小 2 个操作 2 的代价，但多了操作 1 为保证 \(A_{x+1}=A_{y-1}\) 的代价，所有 \(|A_{x+1}-A_{y-1}|\le 1\) 时才划算。------------------------------47分

考虑如何优化方案 2，我们记 \(p_i\) 为 \([2,i]\) 中 \(|a_1-a_j|\) 的最小值，\(s_i\) 为 \([j,n-1]\) 中 \(|a_j-a_n|\) 的最小值，我们可以枚举断点 \(d\)，找到 \(p_{d-1}+s_{d+1}\) 的最小值即可。时间复杂度 \(O(n)\)。------------------------------100分

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int t,n;
int a[N],b[N];
int pre[N],pi[N],suf[N],si[N];
signed main(){cin>>t;while(t--){cin>>n;int ans=1e9;for(int i=1;i<=n;i++){pre[i]=suf[i]=0,pi[i]=0,si[i]=N;cin>>a[i];b[a[i]]=i;}ans=min(abs(a[1]-a[n])+n,ans);suf[n]=pre[1]=1e9;for(int i=2;i<=n;i++){if(abs(a[i]-a[1])<=pre[i-1]) pre[i]=abs(a[i]-a[1]),pi[i]=i;else pre[i]=pre[i-1],pi[i]=pi[i-1];}for(int i=n-1;i>=1;i--){if(abs(a[i]-a[n])<=suf[i+1]) suf[i]=abs(a[i]-a[n]),si[i]=i;else suf[i]=suf[i+1],si[i]=si[i+1];}for(int i=2;i<=n-2;i++){ans=min(abs(a[1]-a[i])+abs(a[n]-a[i+1])+n,ans);ans=min(pre[i]+suf[i+1]+n+2,ans);}for(int i=3;i<=n-2;i++){if(a[i]==n) continue;int x=min(i,b[a[i]+1]),y=max(i,b[a[i]+1]);if(3<=x&&y<=n-2) ans=min(abs(a[x-1]-a[1])+abs(a[y+1]-a[n])+n+1,ans);}cout<<ans<<"\n";}return 0;
}

T6 生成树（P12375）

我们在做 Kruskal 时，会先把所有边排序，然后从小到大判断边是否成环，如果不成环就加入最小生成树。

我们要想让最小生成树的边权和最大，就要让小边尽量出现在环上，这样树边会更大。

考虑有一个集合 \(\{1\}\)，我们要新加入的边都尽量与集合中的点相连，也就是让这个图尽可能是完全图，如果已经是完全图了，就新开一个结点，这条边就成为了生成树上的边。

我们发现，生成树上的边分别是 \(1,2,4,7,11,...\)，考虑如何计算贡献。

我们先用二分找到一个最大的 \(m<\frac{x(x-1)}{2}+n\)，对于前 x 个点，第 i 个点贡献为 \(1+\frac{(i-1)(i-2)}{2}\)，把 \(i=2-x\) 加起来，得到 \(\frac{(x^2-2x+6)(x-1)}{6}\)。对于 \(x+1\) ~ \(n\) 个点，我们要让最小生成树最大，剩下的边都应该是最大的，即 \(m-(n-x)+1,...,m\)，求和后得 \(\frac{(n-x)(2m-n+x+1)}{2}\)，最终答案即为

\[\boxed{\frac{(x^2-2x+6)(x-1)}{6}+\frac{(n-x)(2m-n+x+1)}{2}} \]

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int t;
int main(){cin.tie(0);ios::sync_with_stdio(0);cin>>t;while(t--){long long n,m;cin>>n>>m;long long l=1,r=2e9;while(l<=r){long long mid=(l+r)/2;if(m<mid*(mid-1)/2+n-mid)r=mid-1;else l=mid+1;}__int128 ans=__int128(l*l-2*l+6)*(l-1)/6+__int128(n-l)*(2*m-n+l+1)/2;cout<<int(ans%mod)<<"\n";}return 0;
}