本来是兴起，打算打一场div3录下来的，但是...这场div3真是把我的心态打崩了＞﹏＜ 刚开始pc上的chrome题面latex总是加载不出来；后来的E2贪心爆炸；改题整整改了两天，一道题改了十多遍...
A. Required Remainder
英文阅读理解题。先令ans=nx×x+y，如果ans>n 就令ans−=x 即可
#include <bits/stdc++.h>using namespace std;#define lor(a,b,c) for(register int a=b;a<=c;++a)#define ror(a,b,c) for(register int a=c;a>=b;--a)inline void work(){ int x,y,n; scanf("%d%d%d",&x,&y,&n); int res=(n/x)*x+y; if(res>n) res-=x; printf("%d\n",res);}int main(){ #ifndef ONLINE_JUDGE freopen("test.in","r",stdin); #endif int qwq=1; cin>>qwq; while(qwq--) work(); return 0;}
B. Multiply by 2, divide by 6
这道题也是很基础。如果n包含2和3以外的因数一定不合法；否则n=2a×3b，若a>b也是不合法的；否则答案是（b−a)+b
#include <bits/stdc++.h>using namespace std;#define lor(a,b,c) for(register int a=b;a<=c;++a)#define ror(a,b,c) for(register int a=c;a>=b;--a)inline void work(){ int n; cin>>n; int res2=0,res3=0; while(n%2==0) n/=2,res2++; while(n%3==0) n/=3,res3++; if(n!=1) {puts("-1"); return;} if(res2<=res3) printf("%d\n",(res3-res2)+res3); else puts("-1");}int main(){ #ifndef ONLINE_JUDGE freopen("test.in","r",stdin); #endif int qwq=1; cin>>qwq; while(qwq--) work(); return 0;}
Move Brackets
一道比较明显的贪心题，并没有太多可作记录的
#include <bits/stdc++.h>using namespace std;#define lor(a,b,c) for(register int a=b;a<=c;++a)#define ror(a,b,c) for(register int a=c;a>=b;--a)const int N=55;int n; char s[N];inline void work(){ cin>>n; cin>>s+1; int lef=0,cnt=0; lor(i,1,n){ if(s[i]=='('){ ++lef; } else{ if(lef) lef--; else cnt++; } } printf("%d\n",cnt);}int main(){ #ifndef ONLINE_JUDGE freopen("test.in","r",stdin); #endif int qwq=1; cin>>qwq; while(qwq--) work(); return 0;}
Zero Remainder Array
把握住同余的一些小性质，也是很也好做出来的。
#include <bits/stdc++.h>using namespace std;#define lor(a,b,c) for(register int a=b;a<=c;++a)#define ror(a,b,c) for(register int a=c;a>=b;--a)typedef long long ll;const int N=2e5+5;int n,k,a[N],b[N];inline void work(){ scanf("%d%d",&n,&k); lor(i,1,n) scanf("%d",&a[i]); lor(i,1,n) b[i]=(k-a[i]%k)%k; sort(b+1,b+1+n); ll ans=0; for(register int i=1;i<=n;){ register int j=i; while(j<n&&b[i]==b[j+1]) ++j; if(b[i]) ans=max(ans,1ll+(1ll*(j-i+1)-1)*(ll)k+(ll)b[i]); i=j+1; } printf("%lld\n",ans);}int main(){ #ifndef ONLINE_JUDGE freopen("test.in","r",stdin); #endif int qwq=1; cin>>qwq; while(qwq--) work(); return 0;}
E1 Reading Books (easy version)
这道题就是噩梦的开始...
本题是简易版本，可以发现：a=0,b=0的书一概没用；要么是一本a=b=1的书，要么是a=1,b=0和a=0,b=1的两本书。
观察完性质后，可以用优先队列实现，也可以用指针实现。我偷懒用的是priority_queue
#include <bits/stdc++.h>using namespace std;#define lor(a,b,c) for(register int a=b;a<=c;++a)#define ror(a,b,c) for(register int a=c;a>=b;--a)const int N=2e5+5,INF=0x3f3f3f3f;语言方法
455621gWu
r1BE7
抖音玩游戏赚钱「官方活动」月入万元56012010-05-09 18:43:54
int n,k;priority_queue <int,vector<int>,greater<int>> lis1,lis2,lis3;inline void work(){ scanf("%d%d",&n,&k); lor(i,1,n){ int t,a,b; scanf("%d%d%d",&t,&a,&b); if(a&&b) lis3.push(t); else if(a&&!b) lis1.push(t); else if(!a&&b) lis2.push(t); } int cnt=0; lor(i,1,k){ int f1=INF,f2=INF; if(!lis1.empty()&&!lis2.empty()) f1=lis1.top()+lis2.top(); if(!lis3.empty()) f2=lis3.top(); if(f1==INF&&f2==INF) {puts("-1"); return;} else if(f1<=f2) cnt+=f1,lis1.pop(),lis2.pop(); else cnt+=f2,lis3.pop(); } printf("%d\n",cnt);}int main(){ #ifndef ONLINE_JUDGE freopen("test.in","r",stdin); #endif int qwq=1; while(qwq--) work(); return 0;}
E2 Reading Books (hard version)
考场上的贪心思路是：先用11的书，再01和10的两本书凑对，最后从剩下的所有书中挑最小的，凑齐m本。
这个思路其实大体上对了，问题在于：没有枚举尽11的书所有的可能本数。直接贪心可能并不能准确地贪到正确的本数上。
怎么修改呢？其实也很简单：从大到小枚举可能的11本数，O(1)地对选择情况做微调。思路上不存在障碍，但代码实现上出现了很多降智错误。
#include <bits/stdc++.h>using namespace std;#define lor(a,b,c) for(register int a=b;a<=c;++a)#define ror(a,b,c) for(register int a=c;a>=b;--a)typedef pair<int,int> pi;#define fi first#define se second#define mp(a,b) make_pair(a,b)const int N=2e5+5,INF=2147483647;int n,m,k;pi lis[4][N]; int siz[4],pos[4],L,R,ans=INF,res=0,rec[4];inline int get(){ int t0=pos[0]<siz[0]?lis[0][pos[0]+1].fi:INF; int t1=pos[1]<siz[1]?lis[1][pos[1]+1].fi:INF; int t2=pos[2]<siz[2]?lis[2][pos[2]+1].fi:INF; if(t0==t1&&t1==t2&&t2==INF) return INF; if(t0<=t1&&t0<=t2) {++pos[0]; return t0;} else if(t1<=t2) {++pos[1]; return t1;} else {++pos[2]; return t2;}}inline int delate(int lim){ int t0=pos[0]?lis[0][pos[0]].fi:0; int t1=pos[1]>lim?lis[1][pos[1]].fi:0; int t2=pos[2]>lim?lis[2][pos[2]].fi:0; if(t0==t1&&t1==t2&&t2==0) return INF; if(t0>=t1&&t0>=t2) {--pos[0]; return t0;} else if(t1>=t2) {--pos[1]; return t1;} else {--pos[2]; return t2;}}inline void updata() {if(res<ans) {ans=res; lor(i,0,3) rec[i]=pos[i];}}inline void report() {printf("%d\n",ans); lor(j,0,3) lor(i,1,rec[j]) printf("%d ",lis[j][i].se); puts("");}int main(){ #ifndef ONLINE_JUDGE freopen("test.in","r",stdin); #endif scanf("%d%d%d",&n,&m,&k); lor(i,1,n){ int t,a,b; scanf("%d%d%d",&t,&a,&b); int ind=(a<<1)|b; lis[ind][++siz[ind]]=mp(t,i); } lor(i,0,3) sort(lis[i]+1,lis[i]+1+siz[i]); L=max(max(max(0,2*k-m),k-siz[1]),max(k-siz[2],m-siz[0]-siz[1]-siz[2])); R=siz[3]; if(L>R) return puts("-1"),0; lor(i,1,R) res+=lis[3][i].fi; pos[3]=R; lor(j,1,2) {lor(i,1,k-R) res+=lis[j][i].fi; pos[j]=k-R;} lor(i,k+k-R+1,m) res+=get(); updata(); ror(i,L,R-1){ int cnt=1; res-=lis[3][pos[3]--].fi; lor(j,1,2) if(pos[j]<k-i) res+=lis[j][++pos[j]].fi,--cnt; if(cnt==1) res+=get(); else if(cnt==-1) res-=delate(k-i); updata(); } report(); return 0;}
F Cyclic Shifts Sorting
先尝试强化一下条件：如果给定的序列是一个排列怎么做？
观察发现：“转换”无法更改逆序对的奇偶性。当为奇数时一定无解；当为偶数时，通过构造性证明其有解。
找到第一小，向前滚动，若不慎落在第二格，则两次“转换”[1,3]；接着找第二小，向前咕噜咕噜...；最后剩下的两个根据逆序对的奇偶性，一定是已排好序的。
回到原问题：如果是序列呢？
尝试按序列的大小关系，为序列对应一个相应的全排列。如果存在两个数大小一致，那么通过对换一定能使逆序对数的奇偶性调整到偶数；如果不存在的话..那不就和排列做法一模一样了嘛。
#include <bits/stdc++.h>using namespace std;#define lor(a,b,c) for(register int a=b;a<=c;++a)#define ror(a,b,c) for(register int a=c;a>=b;--a)typedef pair<int,int> pi;#define fi first#define se second#define mp(a,b) make_pair(a,b)const int N=505;int n,a[N],c[N]; pi b[N];int siz,lis[N*N];char buf[1<<21],*p1=buf,*p2=buf;template <typename T> inline T read(){ #define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin)),p1==p2?EOF:*p1++) char tmp=gc(); T sum=0; while(tmp<'0'||tmp>'9') tmp=gc(); while(tmp>='0'&&tmp<='9') sum=(sum<<1)+(sum<<3)+tmp-'0',tmp=gc(); return sum;}inline int op(int p) {lis[++siz]=p; swap(c[p],c[p+2]); swap(c[p+1],c[p+2]);}inline void work(){ n=read<int>(); lor(i,1,n) a[i]=read<int>(),b[i]=mp(a[i],i); sort(b+1,b+1+n); lor(i,1,n) c[b[i].se]=i; int cnt=0; lor(i,1,n) lor(j,1,i-1) if(c[j]>c[i]) ++cnt; if(cnt&1){ bool flag=false; lor(i,1,n-1) if(b[i].fi==b[i+1].fi) {swap(c[b[i].se],c[b[i+1].se]); flag=true; break;} if(!flag) {puts("-1"); return;} } siz=0; lor(i,1,n-2){ int minn=n+5,pos; lor(j,i,n) if(c[j]<minn) minn=c[j],pos=j; while(pos>i+1) op(pos-2),pos-=2; if(pos==i+1) op(i),op(i); } printf("%d\n",siz); lor(i,1,siz) printf("%d ",lis[i]); puts("");}int main(){ #ifndef ONLINE_JUDGE freopen("test.in","r",stdin); #endif int qwq=1; qwq=read<int>(); while(qwq--) work(); return 0;}
后记
诶，还是太菜了，打场div3还被教训了一顿...剩下的时间，你小子可得出质量啊！
