Codeforces Round 889 (Div. 2) 题解

晚上睡不着就来总结一下叭~（OoO）

赛后榜(希望不要被Hack...Orz)

终榜！！！

瞬间的辉煌(呜呜呜~)

 

先不放图了。。怕被dalaoHack...呜呜呜~

总结

        7.29半夜比赛，本来是不想打的，感觉最近做的题太多了，什么牛客杭电以及CF上的题等等等，挺杂的，也来不及整理，本想梳理一下，而且也感觉今天状态不太好，但见他们都要打，我也就跟着一起打了。。。总体来说还可以吧(目前来说。。如果明天早上不会被Hack的话。。。。祈祷Orz...保佑...)但是A题出现一点小失误，考虑问题不完整，WA了一发，不应该，而且这题用时也比较长，8分钟，脑子当时没转过来啊啊啊啊啊啊。。。附加WA一发。B题实话实说有点傻逼。。。直接猜结论，开始不敢写，因为我自己都不等说服自己。。。但是想了十分钟左右，没有其他思路，直接莽了，没想到竟然过了。不敢相信，虽然我也不知道为什么过的。。Orz...C1大模拟，有点复杂，但是还可以。后接近一个半小时都在改C2，最后也没改对，需要注意的细节太多了。。。总有考虑到的。。直到最后就这样了。。。

题解

A. Dalton the Teacher

思路：计算学生的学号和椅子的编号相同的个数ans，若是奇数则相同的个数ans/2+1，若是偶数则相同的个数ans/2即可(其实就是两个人交换，如果最后还剩下一个人再交换一次)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;typedef pair<int,int> PII;
const int N=200005;
const int inf=0x3f3f3f3f;
int a[N];signed main(){IOS;int T;  cin>>T;while(T--){int n,ans=0;  cin>>n;for(int i=1;i<=n;i++){int p;  cin>>p;if(p==i){ans++;}}if(ans==0){cout<<0<<'\n';}else{if(ans%2){cout<<ans/2+1<<'\n';}else{cout<<ans/2<<'\n';}}}return 0;
}

B. Longest Divisors Interval

思路：用1-1000去类比1-10e18，虽然我也不知道原理是什么。。。随便猜的啊啊啊。。Orz...

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;typedef pair<int,int> PII;
const int N=200005;
const int inf=0x3f3f3f3f;
int a[N];signed main(){IOS;int T;  cin>>T;while(T--){int n,cnt=0,ans=-inf;  cin>>n;for(int i=1;i<=1000;i++){if(n%i==0){cnt++;}else{ans=max(ans,cnt);cnt=0;}}cout<<ans<<'\n';}return 0;
}

C1. Dual (Easy Version)

思路：模拟。。分别找最大的数nmax和最小的数nmin，比较谁的绝对值更大，如果最大的数nmax的绝对值更大，从前往后遍历，如果前一个数比当前数大，后一个数加nmax(nmax不可能是负的，如果最大的是负的那么最小的也是负的，两个都是负的一定是最小的数的绝对值较大)；如果最小的数nmin的绝对值更大，从后往前遍历，如果前一个数比当前数大，前一个数加nmin(nmin不可能是正的，如果最小的是正的那么最大的也是正的，两个都是正的一定是最大的数的绝对值较大)，将标号如队列即可

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;typedef pair<int,int> PII;
const int N=25;
const int inf=0x3f3f3f3f;
int a[N];signed main(){IOS;int T;  cin>>T;while(T--){vector<PII> v;int n,nmax=-inf,dn,nmin=inf,xn,ans=0;  cin>>n;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]>nmax){dn=i;nmax=a[i];}if(a[i]<nmin){xn=i;nmin=a[i];}}if(abs(nmax)>abs(nmin)){for(int i=2;i<=n;i++){while(a[i]<a[i-1]){a[i]+=nmax;ans++;v.push_back({i,dn});if(a[i]>nmax){dn=i;nmax=a[i];}}}}else{for(int i=n-1;i>0;i--){while(a[i]>a[i+1]){a[i]+=nmin;ans++;v.push_back({i,xn});if(a[i]<nmin){xn=i;nmin=a[i];}}}}cout<<ans<<'\n';for(auto u:v){cout<<u.first<<' '<<u.second<<'\n';}}return 0;
}

C2. Dual (Hard Version)(待补。。)

应该是全是负数的情况没有考虑。。MLE2了，而且一想这也不是最优的。也不对。。。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;typedef pair<int,int> PII;
const int N=25;
const int inf=0x3f3f3f3f;int a[N];
vector<PII> v;
int main(){IOS;int T;  cin>>T;while(T--){v.clear();int n,ans=0;  cin>>n;for(int i=0;i<n;i++){cin>>a[i];}for(int i=1;i<n;i++){if(a[i]<a[i-1]){int d=a[i-1]-a[i],zn=inf,zi;for(int j=0;j<n;j++){if(zn>=d&&a[j]<zn&&a[j]>=d){zn=a[j];zi=j;}}if(zn!=inf){v.push_back({i+1,zi+1});ans++;a[i]+=a[zi];}else{int nmax=-inf,dn;for(int j=0;j<n;j++){if(a[j]>nmax){nmax=a[j];dn=j;}}while(a[i-1]>a[i]){a[i]+=a[dn];v.push_back({i+1,dn+1});ans++;}}}}cout<<ans<<'\n';for(auto u:v){cout<<u.first<<' '<<u.second<<'\n';}}return 0;
}

Orz......