\(Practice\) \(on\) \(codeforces\) \(in\) \(June\)
wk，误删了4个题，但我不想补了
\(CF1839D\)
题意：给一个正整数序列 \(a\)，给定 \(k\) 个 0，将其放进序列的任意位置里，可以进行无限次操作，每次将一个挨着0的数移动到序列的任意位置，最后删掉所有的0，求使得序列变成递增序列的最小操作数。
首先，我们可以精确地将球放进最终位置，那么就上限操作次数就是 \(n\)
然后考虑计算。我们称将球移动到最终位置为删点操作
显然一个0球可以使得一个区间变得有序，而这个区间实际上是往左往右扩展到的第一对递增的的球
进而我们就可以得到，一个 \(0\) 球右边一段，都可以一口气删掉，而第一个与其递增的球是可以不用删去而将最终序列里缺的球放在二者之间即可。则原序列递增序列是一个可以不被移动的集合 \(S\) (长度 \(\le k\))，简称这些点为固定点
则其代价就是 \(n-|S|\)
这么简单？是不是求个上升子序列就行了？
不不不
两个挨着的固定点，其中一个是可以不管的，所以事实上是一个连续的递增序列算一个就可以了
那考虑设 \(f[i,j]\) 为前 \(i\) 个数里，用最多 \(j\) 个 0 球将其排序的最小代价
显然有：
初始：\(f[0,i]=0,f[i,0]=[a_1<a_2<…<a_i]\inf\) \((i\in[1,n])\)
转移：\(f[i,j]=\min\left\lbrace f[i,j-1],f[i-1,j](a_{i-1}<a_i),\min_{a_k<a_i,0\le k<i-1}\lbrace f[k,j-1]+i-1-k\rbrace\right\rbrace\)
答案：\(\min\lbrace f[n,k],f[i,k-1]+n-i\rbrace\)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 505
int f[N][N],n,m,t,a[N];
int main(){
ios::sync_with_stdio(false);
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int tag=1;f[0][0]=0;
for(int i=1;i<=n;i++){
tag&=(a[i]>a[i-1]);
f[0][i]=0;
f[i][0]=tag?0:0x3f3f3f3f;
}
for(int j=1;j<=n;j++){
for(int i=1;i<=n;i++){
f[i][j]=f[i][j-1];
if(a[i-1]<a[i])f[i][j]=min(f[i][j],f[i-1][j]);
for(int k=0;k<i-1;k++){
if(a[k]<a[i]){
f[i][j]=min(f[i][j],f[k][j-1]+i-1-k);
}
}
}
}
for(int i=1;i<=n;i++){
int ans=f[n][i];
for(int j=1;j<=n;j++){
ans=min(ans,f[j][i-1]+n-j);
}
cout<<ans<<" ";
}cout<<"\n";
}
}
\(CF1838D\)
考场上读错题是直接心态爆炸的
首先注意到，无论怎么往返走，括号序列长度的奇偶性始终是不变的，那么如果 \(n\) 为奇数，直接判 \(No\)
现在来考虑什么情况下是绝对无解的
注意到如果一个相邻括号不同的序列，无论怎么往返走，其始终是合法的(因为增量是一个合法的串)，那么我们只需要考虑连续的左/右括号段。显然如果最前面的连续括号段是右括号段，则后面无论怎么搞也补不回来这些左括号。同理，如果后面是连续的左括号，也不论怎么走也是搞不回来这些右括号。所以得到了必要条件：第一个连续括号段是左括号段，最后一个连续括号段是右括号段
尝试证明其是充要条件：在这些段里，可以提前补足所有后面/前面缺的括号，那么这就是充分的
详细的说，我们使用头尾两个连续括号段，可以使得序列里所有的连续括号段长度变为 \(0/1\)，然后自我消灭后，就只会剩下 \(()()()()……\)，就得到了解
至于括号位置的维护，可以使用 set
int main(){
set<int>a;
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++){
char x;cin>>x;
if((i%2)^(x=='('))a.insert(i);
}
while(m--){
int x;cin>>x;
if(a.count(x))a.erase(x);
else a.insert(x);
if(n%2)cout<<"No\n";
else if(a.size()&&(*a.begin()%2||*a.rbegin()%2==0))cout<<"No\n";
else cout<<"Yes\n";
}
return 0;
}
\(CF1838E\)
给定一个长为 \(n\) 的序列 \(a\)，\(\forall i\in[1,n],a_i\in[1,k]\)，有序列 \(b\)，满足 \(a\) 是 \(b\) 的子序列且 \(b\) 的长度为 \(m\)
求满足条件的 \(b\) 数组个数
计数题，考虑进行DP。
题目换个描述就是，找有多少个 \(b\) 使得其与 \(a\) 的最长公共子序列长度为 \(n\)，模拟最长公共子序列的计算过程，有：
设 \(f[i,j]\) 为 \(a\) 在和 \(b\) 已经匹配了 \(i\) 位，\(b\) 的指针扫到了 \(j\)
显然有 \(f[i,j]=f[i-1,j-1]+f[i,j-1]\times \sum_{i=1}^k[i\neq a_{i+1}\or i=n]\)
注意到 \(\sum_{i=1}^k[i\neq a_i]=k-1(a_i\in [1,k])\)，就可以得到新的递推公式：
\(f[i,j]=f[i-1,j-1]+f[i,j-1]\times(k-1+[i=n])\)
复杂度 \(O(nm)\)，考虑加速计算
写出这个递推公式之后，可以看到它与原来的 \(a\) 数组毫无关系，那么这就意味着我可以随意对 \(a\) 进行更改
假设全部把它变成 \(1\)，问题就变成了找到长为 $m $ 且至少含有 \(n\) 个1的方案数
这是简单的，长为 $m $ 且至少含有 \(i\) 个1的方案数相当于我们从 \(m\) 个球中选出 $i $ 个涂成白色，剩下的涂其他 \(k-1\) 中颜色随意，就有 \((k-1)^{m-i}{m\choose i}\) 种方案
那么答案即为：
发现时间复杂度仍然是 \(O(m)\) ，无法承受
正难则反，注意到所有的序列个数是 \(k^m\)
那么选不出 \(n\) 个的方案数就是 \(\sum_{i=0}^{n-1}(k-1)^{m-i}{m\choose i}\)
所以可以得到：
还能推出一个组合恒等式：\(k^m=\sum_{i=0}^m(k-1)^{m-1}{m\choose i}\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
int power(int a,int b){
int ans=1;
while(b){
if(b&1)ans=a*ans%p;
a=a*a%p;
b>>=1;
}
return ans;
}
int a[1005050],n,k,m,t;
signed main(){
ios::sync_with_stdio(false);
cin>>t;
while(t--){
cin>>n>>m>>k;
for(int i=1;i<=n;i++)cin>>a[i];
int mul=1;
int ans=0;
for(int i=0;i<n;i++){
mul=mul*(m-i+1)%p*power(i,p-2)%p;
if(i==0)mul=1;
ans=(ans+power(k-1,m-i)*mul%p)%p;
}
ans=power(k,m)-ans;
ans=(ans%p+p)%p;
cout<<ans<<"\n";
}
}
\(CF1841C\)
考场上这破题居然没做出来。
首先，考场思路是：
先处理出值和正负号，设 \(s\) 为原序列值，设 \(ans\) 为最大增量(初始为零)。
对于一个数进行更改，有且只有三种情况。
- 把自身变大，这样可能会导致前面的正数中某部分变成负数。
- 把自己变小，这样可能会导致前面的负数中某部分变成正数。
- 对前面的数没有影响。
进一步思考，我们得到：设 \(mx[i]=\max_{i\le j\le n} val[j],val'\) 为更改后的权值，设更改 \(val[i]\)。
那么就有：
- \(val[i]<mx[i],val'\le mx[i]\)，此时不会对前面的产生影响。
- \(val[i]<mx[i],val'>mx[i]\)，此时会导致 \(j\in [1,i),mx[j]=val[j]<val'\) 变成负数。
- \(val[i]=mx[i],val'<val[i]\)，注意，如果 \([i+1,n]\) 中不存在 \(j\) 使得 \(val[j]=val[i]\)，则会导致 \([k,i]\) 里所有的正数变成负数。其中 \(k\) 定义为是满足 \(val[k]\ge val',k<i\) 的最大整数。
- \(val[i]=mx[i],val'>val[i]\)，这种情况只是让前面部分变成负数。
念至此，此题似乎用前缀和，套几个指针维护即可。
但，代码难度是较高的。赛场上的我就直接开莽，然后掉大分。
面对这种想到可做思路但代码难度较高时，可以再用五到十分钟思考是否还有更加优秀的性质。
显然，这个题，是有的。
回退到三种最初的影响情况，运用 比较两个等价决策 的方法（这是贪心的常用方法）。
对于第一种情况，不难发现实际上这个变成负数的量，只取决于改后的权值，初始权值和当前的位置。
而在初始权值相同的情况下，一定是位置最靠前的最优，直接处理出每个权值第一次出现位置，暴力枚举改后权值跑即可，这样的位置至多只有五个。
不难看出，对于第二种情况，把自己变小对前面造成影响，能造成影响当且仅当自身是后缀最大值，且只含这样一个最大值。
那么这个点，等价于是后缀最大值在更新的时候遇到的点。权值只有五种，那么这样的点也至多只有五个，暴力枚举改后的权值暴力跑即可。
第三种情况是容易统计的，在统计后缀最大值的时候处理即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
void read(int &x){
int w=1;x=0;char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-')w*=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
x*=w;
}
int n,m,t;
char a[505050];
int val[505050],pos[505050],w[5]={1,10,100,1000,10000},cnt[5];
int solve(){
int mx=val[n],ans=0;
for(int i=n;i;i--){
if(val[i]>=mx)ans+=val[i],mx=val[i];
else ans-=val[i];
}
return ans;
}
signed main(){
/*
不能操作的赢
那么肯定是尽量少
*/
ios::sync_with_stdio(false);
int t;cin>>t;
while(t--){
cin>>a+1;n=strlen(a+1);cnt[0]=cnt[1]=cnt[2]=cnt[3]=cnt[4]=0;
for(int i=1;i<=n;i++){
pos[i]=a[i]-'A';val[i]=w[pos[i]];
}
int mx=a[n];int s=solve(),d=0,p=s;
for(int i=1;i<=n;i++){
cnt[pos[i]]++;
if(cnt[pos[i]]==1){
int v=val[i];
for(int j=0;j<5;j++){
val[i]=w[j];s=max(s,solve());
}
val[i]=v;
}
}
for(int i=n;i;i--){
if(val[i]>mx){
int v=val[i];
for(int j=0;j<5;j++){
val[i]=w[j];s=max(s,solve());
}
val[i]=v;mx=val[i];
}
else if(val[i]<mx){
d=max(d,mx+val[i]);
}
}
cout<<max(s,d+p)<<"\n";
}
}
\(CF1841D\)
我觉得，这题没有C难。
说说思路
我最初的想法是看到 \(n\le 2000\)，想的是建图然后删点，后来发现是不需要的。
对于这样的选择问题，排序是很容易想到的。
注意到一对线段中靠后的线段对后面的选择起了决定性作用，而当我们将所有线段按右端点排序之后会发现对后面的线段的影响，越往后影响越大，这是显然的。
那么容易想到贪心策略：如果可能的话，这对线段中靠后线段尽可能靠前，因为这样会让后面的线段自由性更大。
接着就可以想到，如果枚举当前线段，则最优匹配线段就是与其相交的后面的最近的一个线段，这个可以通过指针处理
这时候我们反过来考虑，对于一个确定的靠后线段，要凑成对，肯定是尽量靠近它才对撒。
解决方案已经出来了：
- 将所有线段按右端点排序
- 记录 \(lst,mx\) 分别表示上一对线段的靠后线段的右端点，当前枚举到的符合条件的左端点的最远右端点
- 依次枚举每一条线段 \(i\)
- 如果 \(l_i\le lst\)，说明这个线段已经被删了，跳过
- 如果 \(l_i\le mx\)，说明现在构成了一对合法线段，将答案加上，\(mx'=-1,lst'=r_i\)
- 如果4,5都不满足，令 \(mx'=r_i\) 即可
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r;
sort(a+1,a+n+1);
int lst=-1,mx=-1,ans=0;
for(int i=1;i<=n;i++){
int l=a[i].l,r=a[i].r;
if(l<=lst)continue;
if(mx>=l){
++ans;lst=a[i].r;mx=-1;
}
else {
mx=r;
}
}
cout<<n-ans-ans<<"\n";
\(CF1841E\)
对于选择一个长为 \(k\) 的连续段，其贡献为 \(k-1\)，则我们显然要使得选择的段尽量少且满足要求
自然，每一次肯定是贪心选取最长的段进行填充，那么怎么高效去处理这个过程呢？
考虑令 \(a_i=m-a_i\)，就变成了有一排高度为 \(a_i\)，宽为 \(1\) 的矩形。由于我们需要的是段，所以我们提出的子段高度为1，那么考虑求出宽度为 \(k(k\in[1,n])\) 高为 \(1\) 的极长矩形的个数
注意到如果矩形的高度单调递增，则我们可以很方便地统计出每一个可能的宽度有多少高度(前后高度差)，并将其累计
那么如何将矩形化为这种情况呢？
单调栈
我们考虑维护一个高度递增的矩形集合，每次找第一个(也即高度最大的一个)，如果新矩形比它高，直接插入，否则以栈顶为起点，把高度比这个新矩形高的答案先统计掉，然后加上这个新矩形，宽度为 \(w+1\)，其中 \(w\) 为弹出栈的所有矩形宽度的总和。
大致的思路是这样的，代码还有一些细节。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 505050
#define int long long
int top,n,a[N],t,m,cnt[N];
struct node{
int h,w;
}sta[N];
signed main(){
ios::sync_with_stdio(false);
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
cin>>m;
sta[0].h=0;
for(int i=1;i<=n;i++)a[i]=n-a[i];
top=0;for(int i=1;i<=n;i++)cnt[i]=0;
for(int i=1;i<=n;i++){
if(top==0||sta[top].h<a[i])sta[++top]=(node){a[i],1};
else if(a[i]==sta[top].h)sta[top].w++;
else{
int w=0;
while(top&&sta[top].h>a[i]){
w+=sta[top].w;
cnt[w]+=sta[top].h-max(sta[top-1].h,a[i]);--top;
}
if(top&&sta[top].h==a[i])sta[top].w+=w+1;
else sta[++top]=(node){a[i],w+1};
}
}
int w=0;
while(top){
w+=sta[top].w;
cnt[w]+=sta[top].h-sta[top-1].h;--top;
}
int ans=m;
for(int i=n;i;--i){
// cout<<i<<' '<<cnt[i]<<" matix\n";
if(m>cnt[i]*i)m-=cnt[i]*i,ans-=cnt[i];
else{
ans-=(m+i-1)/i;
break;
}
}
cout<<ans<<"\n";
}
}
CF1824B2
首先，设 \(f_i\) 为第 \(i\) 个点在所有的方案中，有 \(f_i\) 种选点方案，使得点 \(i\) 作为好点
则 \(Ans=\frac{\sum_{i=1}^nf_i}{{n\choose k}}\)
考虑如何求出 \(f\)
我们回到定义，考虑一个点是好点的充分必要条件是什么。
树是无根树，这就能带来一个条件：将一棵树中任意一个点当做根来考虑不会影响最终结果，且一般会使得思考过程更加简单
求解一个最优化问题的充要条件，我们常常会使用比较两个决策的方法
假设在当前方案中，存在一个好点 \(u\)。
我们考虑将点 \(u\) 提成根，考虑设 \(v_1,v_2,v_3\dots v_m\) 为其子节点，设 \(g_i\) 表示当前方案里节点 \(i\) 及其子树里的人数
如果 \(u\) 移动到 \(v_x\)，则 \(dis'=dis-g_{v_x}+(k-g_{v_x})\)
答案不会变劣，当且仅当 \(k-g_{v_x}=g_{v_x}\implies g_{v_x}=\frac{k}{2}\)
显然当 \(k\) 为奇数时，不存在这样的点 \(v\)，则在当前方案中，好点 \(u\) 唯一，所以 \(\sum_{i=1}^nf_i={n\choose k}\)，此时答案为 \(1\)
考虑当 \(k\) 为偶数时，我们同样可以分讨，设 \(k'=\frac{k}{2}\)。
我们首先来讨论不存在 \(g_{v_x}=k'\) 的情况
这显然等价于 \(k\) 为奇数的情况，则对答案贡献为 \(1\)
我们更改 \(f_i\) 的定义，定义为：点 \(i\) 为好点，在把点 \(i\) 提为根时，存在 \(g_{v_x}=k'\) 的情况总数，那么 \(Ans=\frac{\sum_{i=1}^nf_i}{{n\choose k}}+1\)
这个情况，怎么看呢？
显然就是强制性令其中一个 \(v\) 的 \(g=k'\)，剩下 \(k'\) 自己选。
这个方案数是什么？显然可以列出式子：
对的吗？不对，会重复统计
这一步，我们以退为进，去掉我们的假想条件
我们考虑 \(u\) 在以 \(1\) 为根的子树里怎么统计。
其实我们可以在 \(siz_u\) 中选出 \(k'\) 个，在子树外再选出 \(k'\) 个，这个方案数即为答案的方案数。
为什么，根据 \(u\) 到 \(v_x\) 的转移，扩展一下，就可以看出，事实上这些好点构成一条链，根据我们讨论的问题，这个链长度大于1
因为如果在这条链中间，插入一个虚点作为根，则必定会存在两个节点，他们的 \(siz\) 都等于 \(k'\)
这两个节点的路径上的点，全部都是好点
所以 \(f_u={siz_u\choose k'}{n-siz_u\choose k'}\)
到最后就有：
CF1824C
这个题，难度主要在算法上
不难想到设 \(f_i\) 为在 \(i\) 的子树中，每一个叶子结点到 \(i\) 的异或和相等的最小操作次数
\(f_u=d+\sum_{v\in Son(u)}f_v\)
其中 \(d\) 是将所有 \(v_i\) 变为相等的最小操作数
显然，我们应该让众数不变，其他变成众数，这样的 \(d\) 是最小的——用 \(v\) 的个数减去众数的个数即可
然后最后只保留一个众数即可
注意到如果有多个众数，将数保留，但是代价仍然只计算 \(cnt-mx\)，这是因为这个众数可能在后面会继续更新到，此时就有用了
那么我们如何实现求众数的操作呢？
考虑暴力解决这个问题
设集合 \(T_u\) 为 \(u\) 子树中各个数的出现次数，我们要求区间众数的话，将所有的 \(T_v\) 暴力合并为 \(T_u\) 并记录当前众数的出现次数，最后保留所有可能的众数，其他删去即可
这样的数据结构，不难想到map<int,int>，用迭代器遍历暴力合并即可。
这样肯定会TLE……，因为复杂度可以卡到 \(O(n^2)\)
发现这个问题可以使用启发式合并优化，我们每次在合并集合 \(T'_u=(T_u,T_v)\) 的时候，如果 \(|T_v|>|T_u|\)，那么交换 \(T_u,T_v\) (一个指针的事)即可，最终复杂度 \(O(n\log n)\)
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
#define N 505050
map<int,int>cnt[N],tmp;
int ans,n,id[N],a[N],head[N],ver[N<<1],nxt[N<<1],tot;
void dfs(int u,int fa){
int res=0,mx=1;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(v==fa)continue;
a[v]^=a[u];++res;
dfs(v,u);
if(cnt[id[v]].size()>cnt[id[u]].size())swap(id[v],id[u]);//important
for(auto x:cnt[id[v]]){
cnt[id[u]][x.first]+=x.second;
mx=max(mx,cnt[id[u]][x.first]);
}
}
if(!res){
cnt[id[u]][a[u]]++;return ;
}
ans+=res-mx;
tmp.clear();
if(mx>1){
for(auto x:cnt[id[u]]){
if(x.second==mx){
tmp[x.first]=1;
}
}
swap(tmp,cnt[id[u]]);
}
}
void add(int u,int v){
nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)id[i]=i;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
add(u,v);add(v,u);
}
dfs(1,0);
cout<<ans+(cnt[id[1]][0]==0);
}