Codeforces 1029 Div3（ABCDE）

前言

芜湖～这次状态可以的！！赛时前四个题都过了，积分也上了一千！E题最后思路基本已经出来了，可惜时间不够了，感觉再给十几分钟也能过哈哈哈！再接再厉！！

A. False Alarm

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;void solve()
{int n,x;cin>>n>>x;vector<int>door(n+1);for(int i=1;i<=n;i++){cin>>door[i];}//跳过前导0int open=1;while(open<=n&&door[open]==0){open++;}int end=open+x;while(end<=n&&door[end]==0){end++;}if(end>n){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();    }return 0;
}

这个题难度不大，就是上来先一直怼到第一个关着的门，然后按按钮冲过这x个门，之后能冲到最后就是Yes，不能就是No。

B. Shrink

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;void solve()
{int n;cin>>n;cout<<1<<" ";for(int i=n;i>=2;i--){cout<<i<<" ";}cout<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();    }return 0;
}

这个题还是贪心，怎么感觉cf一半都是贪心…

因为可以每次把极大值删除，且要求删的次数最多，首先可以考虑先打个表找找规律。从最基本的看起，当n等于3时，可以构造132，这样就是先删3，然后剩12结束。当n等于4时，可以构造1432，这样就是先删4，然后情况就跟n等于3时一样。当n等于5时，可以构造15432，然后先删5，之后和n等于4时一样……所以规律就是先输出一个1，然后从n开始倒着输出即可。

C. Cool Partition

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;void solve()
{int n;cin>>n;vector<int>a(n+1);for(int i=1;i<=n;i++){cin>>a[i];}int ans=2;set<int>cur;cur.insert(a[1]);set<int>next;for(int i=2;i<=n;i++){if(cur.find(a[i])!=cur.end()){cur.erase(a[i]);}next.insert(a[i]);if(cur.empty()){ans++;cur=next;next.clear();}}if(!cur.empty()){ans--;}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();    }return 0;
}

这个题也是贪心，但这个思路就不太好想了。

贪心的思路就是从前往后遍历，首先上来让第一个数单独一组。然后在往后遍历的过程中，只要凑齐了前面一组的所有数，就直接划分出一组，然后去之后看是否满足。因为凑齐了就划分这种策略，保证了前一组数都出现的情况下当前组大小最小。这样可以留更多的数给之后的组，所以只会导致后续更有可能划出更多的组，而不会导致可能性减少。

所以代码就是设置两个set去滑，出现了就在上一个set里删除，空了就说明该划分了。最后要注意，若set不为空，说明没收集齐，即上次划分不成功，所以上次划分的一组要跟着后续一直到最后作为最后一组，答案要减一个。

D. Retaliation

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;//幽默高斯消元
void solve1()
{ll n;cin>>n;vector<ll>a(n+1);for(int i=1;i<=n;i++){cin>>a[i];}ll p,r;bool flag=false;ll start=2;for(ll i=2;i<=n;i++){p=n-i+1-i*n;r=a[i]-i*a[1];if(p==0){if(r!=0){cout<<"NO"<<endl;return ;}}else{flag=true;start=i;break;}}if(!flag){cout<<"YES"<<endl;return ;}if(r%p!=0){cout<<"NO"<<endl;return ;}ll s=r/p;if(s<0){cout<<"NO"<<endl;return ;}for(ll i=start+1;i<=n;i++){ll res=a[i]-i*a[1];ll p=n-i+1-i*n;if(res-s*p!=0){cout<<"NO"<<endl;return ;}}if(a[1]-n*s<0){cout<<"NO"<<endl;return ;}cout<<"YES"<<endl;
}//饭老师正解
void solve2()
{int n;cin>>n;vector<ll>a(n);for(int i=0;i<n;i++){cin>>a[i];}//两种操作减的数值加起来均为n+1 -> 不改变数字之间的相对差值//所以可以合并起来看，则减去n+1的次数为min(x,y)//所以abs(x-y)就是改变数字之间相对差值的次数//所以就是先补上某两个数字的差值，然后考察是否剩余的所有数字都一样且是n+1的倍数//判断是否数组里每个数都相等且是n+1的倍数auto check=[&]()->bool{if(a[0]<0){return false;}if(a[0]%(n+1)!=0){return false;}for(int i=0;i<n;i++){if(a[i]!=a[0]){return false;}}return true;};bool ans=true;if(a[0]==a[1]){ans=check();}else if(a[0]<a[1]){ll cut=a[1]-a[0];for(int i=0;i<n;i++){a[i]-=cut*(i+1);}ans=check();}else{ll cut=a[n-2]-a[n-1];for(int i=0;i<n;i++){a[i]-=cut*(n-i);}ans=check();}   cout<<(ans?"YES":"NO")<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve2();    }return 0;
}

幽默高斯消元…

赛时压根没观察出来相对差值这个点，只观察出来可以设x和y表示两种操作的次数，然后暴力解方程组……

所以这个暴力解的方法就是纯模拟高斯消元，注意矩阵要保证列满秩非奇异！！

正解是，观察两种操作，可以发现两种操作叠加起来每个数同样减去n+1，此时不改变数字之间的相对差值。所以思路就是先随便挑两个数考察他们的差值，然后先用第一种或第二种操作把差值抹掉，然后check一下剩下所有数是否均相等且是n+1的倍数即可。

代码就是先挑第一个和第二个数看两者差值，若第二个数大，就用第一种操作去抹差值；否则就挑最后两个数用第二种操作抹差值即可。

E. Lost Soul

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;void solve()
{int n;cin>>n;vector<int>a(n+1);for(int i=1;i<=n;i++){cin>>a[i];}vector<int>b(n+1);for(int i=1;i<=n;i++){cin>>b[i];}//basecase：Ai=Bi -> i个//          Ai=A(i+1)||Bi=B(i+1) -> i个//从后往前一上一下交错替换 -> 下标的奇偶性！！！//存在一个i，当j>=i+2，Ai=Bj或Aj || Bi=Aj或Bj //就可以通过删除或不删除一列来改变下标的奇偶关系//从而转化成某个basecaseint ans=0;//basecase1for(int i=1;i<=n;i++){if(a[i]==b[i]){ans=i;}}//basecase2for(int i=1;i<n;i++){if(a[i]==a[i+1]||b[i]==b[i+1]){ans=max(ans,i);}}set<int>s;for(int i=n;i>=2;i--){if(s.find(a[i-1])!=s.end()||s.find(b[i-1])!=s.end()){ans=max(ans,i-1);}s.insert(a[i]);s.insert(b[i]);}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();    }return 0;
}

赛时basecase和交错替换已经想出来了，感觉再给十分二十分钟就能写出来了。

首先basecase是，若a数组或b数组存在两个相同的数并列，则前面所有数都能刷成一样的；然后若ab数组同一位置的两个数相同，那前面依然都能刷成一样的。

之后思路是，观察修改的规律，可以发现，两个数组是从后往前一上一下交替修改的，所以对于每个下标，都能把前面和当前下标奇偶性相同的位置都刷成和当前位置相同的数。而因为有一次删除的操作，所以通过这个操作就可以修改前面所有下标的奇偶性。所以就是从后往前遍历，只要出现之前出现过的数，且两次位置隔了至少一个位置，即有删除的空间，那就可以把从当前位置开始往前的所有数都刷成一样的。

代码就是先遍历两遍求basecase，接着设置一个set，然后从后往前遍历。当来到每个位置i时，先检查i-1位置的数是否出现过。因为此时set中存的是i+1到最后的数，所以天然保证中间隔了一个位置。接着每次就把i位置的两数加入set即可。

总结

F和G听是听懂了，但不会求LCA和带权并查集……还是要加速学习啊！！

END