CodeforcesRound#771（Div.2）A-E不完整题解（努⼒更新中）A. Rever
字典序最⼩的是1 2 3……n排列，故找到第⼀个a[i]!=i的地⽅，然后把这个地⽅换成i即可。普通地去模拟。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
int a[N];
int main(){
int t;cin>>t;
while(t--){
int n,bj=-1,bj2=-1;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
if(a[i]!=i){
bj=i;break;
}
}
if(bj!=-1){
for(int i=1;i<=n;i++)if(a[i]==bj){bj2=i;break;}
}
if(bj!=-1&&bj2!=-1) {
for (int i = 1; i < bj; i++)cout << a[i] << '';
for (int i = bj2; i >= bj; i--)cout << a[i] << '';
for (int i = bj2 + 1; i <= n; i++)cout << a[i] << '';
cout << '\n';
} el for (int i = 1; i <=n; i++)cout<<a[i]<<'';
}
return0;
}
B. Odd Swap Sort
换⾔之，奇数之间可以互相交换，偶数之间可以互相交换；
换⾔之，如果NO，说明某个奇数和偶数形成逆序对……当然这⾥我们只要On扫⼀遍数组就⾏了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
int a[N];
int q0,q1;
int main(){
int t;cin>>t;
while(t--){int flg=1;
int n;cin>>n;
for(int i=1,x;i<=n;i++){cin>>x;
if(q0==0&&x%2==0)q0=x;
if(q1==0&&x%2==1)q1=x;
if(q0!=0&&x%2==0&&q0>x)flg=0;
if(q0!=0&&x%2==0&&q0<x)q0=x;
if(q1!=0&&x%2==1&&q1>x)flg=0;
if(q1!=0&&x%2==1&&q1<x)q1=x;
}
if(flg)cout<<"YES"<<'\n';
el cout<<"NO"<<'\n';
q0=q1=0;
}
return0;
}
C. Inversion Graph
当时卡了许久，想了很多复杂度极其垃圾的⽅法没想出来，才发现这题是On的
题意：给⼀串1-n的排列，在所有逆序对之间连⼀条边，求⼀共有多少个连通块
劣解：我们从1到n扫这个排列，若i和a[i]之间连了⼀条边，则i到a[i]之间的所有数都是连通的这是因为：在这区间之中的数，要么⼩于a[i]且⼤于i，要么⼤于a[i]，要么⼩于i，这三种情况都保证它会和前⾯的某个点连上⼀条边；考虑当连通块的最⼤值等于扫过数字个数时⾃动从排列中形成连通块“脱落”。实战中我的代码写得很劣。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
int a[N];
int main(){
int t;cin>>t;
while(t--){int ans=1,mx=1,cnt=0;
int n;cin>>n;
for(int i=1;i<=n;i++){cin>>a[i];
if(a[i]>=mx&&cnt==mx){mx=a[i],ans++;}
if(a[i]>=mx&&cnt!=mx){mx=a[i];}
if(a[i]<=mx)cnt++;
}
cout<<ans<<'\n';
}
return0;
}
劣解
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
b[i] = a[i];
if (i > 0) {
a[i] = std::max(a[i], a[i - 1]);
}
}
for (int i = n - 2; i >= 0; i--) {
b[i] = std::min(b[i], b[i + 1]);
}
int ans = 1;
for (int i = 0; i < n - 1; i++) {
ans += (a[i] < b[i + 1]);
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(fal);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return0;
}
Jiangly的⼈类⾼质量代码
D. Big Brush
恶臭bfs模拟题。考虑“正难则反”，我们从结束状态反推，若有⽅形⾊块则将其保存为答案。然后去除⽅形⾊块，并关于原来的⽅形⾊块⼀圈圈向外作bfs。
最后，若⾊块没有被去⼲净则输出-1，否则输出答案
#include <bits/stdc++.h>
using namespace std;
int mp[1010][1010],mp2[1010][1010],vis[1010][1010];
queue<pair<int,int> >q;
stack<pair<int,int> >ans;
bool chk(int i,int j){
int k=max(mp[i][j],mp[i+1][j+1]);
k=max(k,max(mp[i][j+1],mp[i+1][j]));
if(k!=0){mp2[i][j]=k;return ((mp[i][j]==k||mp[i][j]==0)&&(mp[i+1][j]==k||mp[i+1][j]==0)&&(mp[i][j+1]==k||mp[i][j+1]==0)&&(mp[i+1][j+1]==k||mp[i+1][j+1]==0));} return0;
}
int fx[8]={0,1,0,-1,1,1,-1,-1},fy[8]={1,0,-1,0,1,-1,1,-1};
int main(){cin.tie(0);ios::sync_with_stdio(fal);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
mp2[i][j]=mp[i][j];
if((j!=1&&i!=1)&&chk(i-1,j-1)){q.push({i-1,j-1}),vis[i-1][j-1]=1;}
}
}
while(!q.empty()){
int sz=q.size();
for(int i=1;i<=sz;i++){
int f=q.front().first,s=q.front().cond;
if(f==0||s==0||f==n||s==m){q.pop();continue;}
mp[f][s]=mp[f+1][s]=mp[f][s+1]=mp[f+1][s+1]=0;
for(int j=0;j<8;j++){
if(f+fx[j]==0||f+fx[j]==n||s+fy[j]==0||s+fy[j]==m)continue;
if(chk(f+fx[j],s+fy[j])&&vis[f+fx[j]][s+fy[j]]==0){
vis[f+fx[j]][s+fy[j]]=1;
q.push({f+fx[j],s+fy[j]});
}
}
ans.push(q.front());
q.pop();
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]!=0){cout<<-1<<'\n';return0;}
}
}
cout<<ans.size()<<endl;
while(!pty()){
int p().first,p().cond;
cout<<f<<''<<s<<''<<mp2[f][s]<<'\n';
ans.pop();
}
return0;
}
或许是世界上最丑的D题代码
E.Colorful Operations
题意：⼀串数组，初始状态为颜⾊1和值0；
有两种操作，⼀是对区间染⾊，⼆是相同颜⾊的数加上值c。
以及⾄多1e6次的在线询问
对于染⾊题，我们考虑神(暴)奇(⼒)的ODT，由于出题⼈没有卡，所以能够AC。
显然Color就是odt中的assign，qry则访问t中的下标即可。
⾄于add，我们考虑使⽤树状数组保存区间和/单点求值，即在每⼀次assign时，将被推平的区间加上c。
博主数据结构很弱，有⼀定参考他⼈代码QWQ
#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
#define int long long
int n,tr[N],col[N];
char c[6];
#define sit t<odt>::iterator
struct odt{
int l,r;
mutable int val;
odt(int l,int r=0,int val=0):l(l),r(r),val(val){}
bool operator<(const odt&a)const{return l<a.l;}
};
t<odt>s;
sit split(int pos){
auto it=s.lower_bound(odt(pos));
if(it!=s.end()&&it->l==pos)return it;
-
-it;
int l=it->l,r=it->r,val=it->val;
s.inrt(odt(l,pos-1,val));
return s.inrt(odt(pos,r,val)).first;
}
int sum(int x){
int ans=0;
for(;x;x-=x&-x)ans+=tr[x];
return ans;
}
void add(int a ,int x){
for(;a<=n;a+=a&-a)tr[a]+=x;
}
void assign(int l,int r,int x){
sit rit=split(r+1);sit lit=split(l);
for(auto it=lit;it!=rit;++it){
add(it->r+1,-col[it->val]);
add(it->l,col[it->val]);
}
add(r+1,col[x]),add(l,-col[x]);
}
int qry(int x){
int ans=sum(x);
auto it=s.upper_bound(x);
--it;
return ans+col[it->val];
}
signed main() {ios::sync_with_stdio(fal);cin.tie(nullptr);cout.tie(nullptr);
int q;cin>>n>>q;
s.inrt(odt(1,n,1));
while(q--){
cin>>c;
if(c[0]=='A'){int co,x;cin>>co>>x;
col[co]+=x;
}
if(c[0]=='Q'){int x;cin>>x;
cout<<qry(x)<<'\n';
}
if(c[0]=='C'){int l,r,x;cin>>l>>r>>x;
assign(l,r,x);
}
}
}
烂烂代码，别看QWQ
F. Two Posters
看⼀眼tags：brute force,data structures,greedy,two pointers，好像很基础的样⼦？再看⼀眼，3200
噔噔咚
（这题暂时放着，等我强点再来更新）
