CF2200D Portal
题意：
给定一个排列p，在任意两个位置放两个传送门
可以进行任意次“传送”操作
求操作后能得到的字典序最小的序列
传送操作定义为：
将一个传送门紧左边的元素移除，并插入到另一个传送门的紧右边或将一个传送门紧右边的元素移除，并插入到另一个传送门的紧左边
解法：
手玩样例发现对于传送门内部的数字形成了一个环
找到破环成链的最小值即可
而对于传送门外部的数字，相当于将传送门中所有数字整体左右挪动
于是字典序最小当且仅当左传送点大于其左侧数字而再向右挪一下就不满足该条件
代码非常好写
#include<bits/stdc++.h>
#define jiaa(a,b) {a+=b;if(a>=MOD) a-=MOD;}
#define jian(a,b) {a-=b;if(a<0) a+=MOD;}
using namespace std;
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
int s[200005],q[200005],qq[200005],cn1,cn2;
signed main()
{//freopen("filename.in", "r", stdin);//freopen("filename.out", "w", stdout);int T=read();while(T--){int n=read(),x=read(),y=read();for(int i=1;i<=n;i++) s[i]=read();int minn=n+1;for(int i=x+1;i<=y;i++){minn=min(minn,s[i]);}cn1=cn2=0;int ff=0;for(int i=1;i<=x;i++){if(s[i]>minn) ff=1;if(ff) qq[++cn2]=s[i];else q[++cn1]=s[i];}for(int i=y+1;i<=n;i++){if(s[i]>minn) ff=1;if(ff) qq[++cn2]=s[i];else q[++cn1]=s[i];}for(int i=1;i<=cn1;i++) cout<<q[i]<<' ';int nw=0;for(int i=x+1;i<=y;i++){if(s[i]==minn){nw=i;break;} }for(int i=nw;i<=y;i++) cout<<s[i]<<' ';for(int i=x+1;i<nw;i++) cout<<s[i]<<' ';for(int i=1;i<=cn2;i++) cout<<qq[i]<<' ';cout<<'\n';}return 0;
}
CF2200E Divisive Battle
题意：
给定一个数组a
Alice和Bob轮流进行以下操作：
每次操作可以选择数组中的一个元素x，将其分解成x=y*z并将x替换成y,z(y,z顺序任意且1<y,z<x)
最后游戏结束当且仅当a单调不降或无法继续进行操作
Bob目标是使得a单调不降，Alice反之
求双方最优策略前提下谁会赢
解法：
首先将原序列单调不降的情况判掉
容易发现无法进行操作当且仅当x为质数
由于Alice先手，那么若存在一个数x，能分解成多个质因数，则Alice必胜
否则将x替换成该唯一质因数，再次判断序列是否单调不降即可
具体实现容易发现即使最暴力的做法先将所有质数筛出来然后对每个数排着考虑可能的最小质因数复杂度也不会太高
加上CF机子特别快
所以直接暴力就行啦
#include<bits/stdc++.h>
#define jiaa(a,b) {a+=b;if(a>=MOD) a-=MOD;}
#define jian(a,b) {a-=b;if(a<0) a+=MOD;}
using namespace std;
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
bool is[1000005];
int prim[1000005];
int cnt,a[100005];
void Oprime(int n){is[1]=1;for(int i=2;i<=n;i++){if(!is[i]){prim[++cnt]=i;}for(int j=1;j<=cnt&&prim[j]*i<=n;j++){is[prim[j]*i]=1;if(i%prim[j]==0) break;}}
}
signed main()
{//freopen("filename.in", "r", stdin);//freopen("filename.out", "w", stdout);Oprime(1000000);int T=read();while(T--){int n=read();for(int i=1;i<=n;i++) a[i]=read();int fl=0;for(int i=1;i<n;i++){if(a[i]>a[i+1]){fl=1;break;}}if(!fl){cout<<"Bob"<<'\n';continue;}fl=0;for(int i=1;i<=n;i++){if(fl) break;if(!is[a[i]]||a[i]==1) continue;for(int j=1;j<=cnt;j++){if(a[i]%prim[j]==0){int jj=a[i];while(jj%prim[j]==0) jj/=prim[j];if(jj>1) fl=1;else a[i]=prim[j];break;}}}if(fl) cout<<"Alice"<<'\n';else{fl=0;for(int i=1;i<n;i++){if(a[i]>a[i+1]){fl=1;break;}}if(!fl) cout<<"Bob"<<'\n';else cout<<"Alice"<<'\n';}}return 0;
}
CF2200F Mooclear Reactor 2
题意：
给定n个粒子，每个粒子有一个二元组(x,y)其中x表示能量，y表示做多能与y个粒子一同反应
给定m组询问，每次再给定一个粒子，求这n+1个粒子产生能量的最大值
解法：
首先考虑没有询问怎么做
发现若用k个粒子，则一定选y>=k-1中前k大的x
考虑将粒子按照y排序，倒着选择粒子
同时优先队列维护x前k大的粒子（有点类似于反悔贪心的思想）
考虑若加上一组询问，答案要么不选该粒子（即为上述答案），要么选择该粒子
考虑再维护一个ansk表示要选择k个数但实际上只选了k-1个数，剩下一个要选择的数是询问时的最大能量
对ans做前缀max后选择该粒子的答案即为该粒子的x+ans[y+1]
#include<bits/stdc++.h>
#define int long long//十年OI一场空，____________
#define jiaa(a,b) {a+=b;if(a>=MOD) a-=MOD;}
#define jian(a,b) {a-=b;if(a<0) a+=MOD;}
using namespace std;
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
pair<int,int> shu[200005];
priority_queue<int> hp;
int ans[200005];
signed main()
{//freopen("filename.in", "r", stdin);//freopen("filename.out", "w", stdout);int T=read();while(T--){int n=read(),m=read();for(int i=0;i<=n+1;i++) ans[i]=0;while(!hp.empty()) hp.pop();for(int i=1;i<=n;i++){shu[i].second=read();shu[i].first=read();} sort(shu+1,shu+n+1);int r=n,sum=0,maxx=0;for(int i=n+1;i;i--){while(shu[r].first>=i-1&&r){hp.push(-shu[r].second);sum+=shu[r].second;r--;}int nsiz=hp.size();while(nsiz>i){sum+=hp.top();hp.pop();nsiz--;}maxx=max(maxx,sum);}r=n,sum=0;while(!hp.empty()) hp.pop();for(int i=n+1;i;i--){while(shu[r].first>=i-1&&r){hp.push(-shu[r].second);sum+=shu[r].second;r--;}int nsiz=hp.size();while(nsiz>(i-1)){sum+=hp.top();hp.pop();nsiz--;}ans[i]=sum;}for(int i=1;i<=n+1;i++) ans[i]=max(ans[i],ans[i-1]);while(m--){int x=read(),y=read();cout<<max(x+ans[y+1],maxx)<<' ';}cout<<'\n';}return 0;
}