晚上睡不着就来总结一下叭~（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...
感谢补充！！！
解释如下：Orz...
把范围缩小到50也可以过，经过测试可以把范围缩小到43，再减小就过不了了。。。这要怎么解释啊啊啊！！！
#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)(已补。。)
感谢dalao的思路~
思路：
总的思路还是将所有数都转化为整数或者负数。。
记所有数的最大值和最小值以及位置，按照最大值和最小值的正负分四种情况进行考虑(排除了一种情况)，如下图。。。
1、当最大值大于0且最小值小于0时，可以将整个序列分别全化为正的或负的，最后答案取操作数较少的一个
2、当最小值大于0时，所有数都是正数
3、当最大值小于0时，所有数都是负数文章来源：https://www.toymoban.com/news/detail-617525.html
将所有书都转化为正数或负数之后，正数取前缀和(因正数前缀和后面的数总不小于前面的数)，负数取后缀和(因负数后缀和后面的数总不小于前面的数)文章来源地址https://www.toymoban.com/news/detail-617525.html
#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],b[N];
signed main(){
IOS;
int T; cin>>T;
while(T--){
int f;
vector<PII> vz;
vector<PII> vf;
int n,nmax=-inf,dn,nmin=inf,xn; cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
if(a[i]>nmax){
dn=i;
nmax=a[i];
}
if(a[i]<nmin){
xn=i;
nmin=a[i];
}
}
if(nmax>0&&nmin<0){
while(a[dn]<abs(a[xn])){
a[dn]+=a[dn];
vz.push_back({dn,dn});
}
for(int i=1;i<=n;i++){
if(a[i]<0){
a[i]+=a[dn];
vz.push_back({i,dn});
}
}
for(int i=2;i<=n;i++){
if(a[i-1]>a[i]){
a[i]+=a[i-1];
vz.push_back({i,i-1});
}
}
while(abs(b[xn])<b[dn]){
b[xn]+=b[xn];
vf.push_back({xn,xn});
}
for(int i=1;i<=n;i++){
if(b[i]>0){
b[i]+=b[xn];
vf.push_back({i,xn});
}
}
for(int i=n;i>1;i--){
if(b[i-1]>b[i]){
b[i-1]+=b[i];
vf.push_back({i-1,i});
}
}
if(vz.size()>=vf.size()){
f=2;
}else{
f=1;
}
}else if(nmin>=0){
for(int i=2;i<=n;i++){
if(a[i-1]>a[i]){
a[i]+=a[i-1];
vz.push_back({i,i-1});
}
}
f=1;
}else{
for(int i=n;i>1;i--){
if(b[i-1]>b[i]){
b[i-1]+=b[i];
vf.push_back({i-1,i});
}
}
f=2;
}
if(f==1){
cout<<vz.size()<<'\n';
for(auto u:vz){
cout<<u.first<<' '<<u.second<<'\n';
}
}else{
cout<<vf.size()<<'\n';
for(auto u:vf){
cout<<u.first<<' '<<u.second<<'\n';
}
}
}
return 0;
}Orz......
到了这里，关于Codeforces Round 889 (Div. 2) 题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
