【A:最大的K-偏差排列】：
第一次在hiho卡一题，所以暴力了搜索了一下，70分，后面回来打表找规律，规律是有和K有关的周期。
当K<=N/2时，成周期交叉变化，最后尾部部分单独考虑。
当K>N/2时，有三个序列，分别是[K+1...N] [K...N-K+1 ] [1..N-K]
自己的代码：
#include<bits/stdc++.h> using namespace std; int ans[110],N,K; int main(){ int pos=0,i,j; scanf("%d%d",&N,&K); if(K>=N-1) { for(i=N;i>=1;i--) ans[++pos]=i; } else if(K<=N/2){ //A int tmp=N/(K*2); for(i=1;i<=tmp;i++){ for(j=(i-1)*2*K+1;j<=(i-1)*2*K+K;j++) ans[++pos]=j+K; for(j=(i-1)*2*K+1;j<=(i-1)*2*K+K;j++) ans[++pos]=j; } if(K>=N-tmp*2*K-1) for(i=N;i>=tmp*2*K+1;i--) ans[++pos]=i; //a //最后一部分同理。 else { //b for(i=K+1;i<=N-tmp*2*K;i++) ans[++pos]=i+2*tmp*K; for(i=K;i>N-tmp*2*K-K;i--) ans[++pos]=i+2*tmp*K; for(i=1;i<=N-tmp*2*K-K;i++) ans[++pos]=i+2*tmp*K; } } else { //B for(i=K+1;i<=N;i++) ans[++pos]=i; for(i=K;i>N-K;i--) ans[++pos]=i; for(i=1;i<=N-K;i++) ans[++pos]=i; } for(i=1;i<=N;i++) printf("%d ",ans[i]); return 0; }
别人的段代码：
#include<bits/stdc++.h> using namespace std; int used[110]; int main(){ int N,K; scanf("%d%d",&N,&K); for (int i=1;i<=N;i++){ int j=max(1,i-K),up=min(N,i+K); while(used[up]) up--; while(j<up&&(used[j]||(i<N&&j>=i+1-K))) j++; used[j]=1; printf("%d ",j); } return 0; }
【B:孤独的字符】：
水题一个：对于每个字符，找到它做出贡献的范围，分别记录左边界L和右边界R，然后累计乘积。
#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=100010; ll L[maxn],R[maxn],Laxt[30],ans; char c[maxn]; int main() { int N,i,j; scanf("%s",c+1); N=strlen(c+1); for(i=0;i<26;i++) Laxt[i]=0; for(i=1;i<=N;i++) { L[i]=Laxt[c[i]-'a']; Laxt[c[i]-'a']=i; } for(i=0;i<26;i++) Laxt[i]=N+1; for(i=N;i>=1;i--) { R[i]=Laxt[c[i]-'a']; Laxt[c[i]-'a']=i; } for(i=1;i<=N;i++) ans+=(ll)(i-L[i])*(R[i]-i); cout<<ans<<endl; return 0; }
【C：秋天来了】：
一眼感觉是差分约束题，但是发现由于每个条件的(L,R)之间的点都要加限制，限制条件过多，不行。
所以直接暴力一点去更新区间(L,R)；很明显可以加优化：如果(L,R)之间的最大值都比Ai小，那就没必要更新了。
所以实际上暴力区间(L,R)的次数不会太多。（但是比赛后验证了一下，直接把线段树部分去掉，暴力就可以过。。。。）
#include<bits/stdc++.h> using namespace std; const int maxn=100001; int h[maxn],x[maxn],y[maxn]; int Max[maxn<<2]; void build(int Now,int L,int R){ if(L==R) { Max[Now]=h[L]; return ; } int Mid=(L+R)>>1; build(Now<<1,L,Mid); build(Now<<1|1,Mid+1,R); Max[Now]=max(Max[Now<<1],Max[Now<<1|1]); } void update(int Now,int L,int R,int pos,int val){ if(L==R) { Max[Now]=val; return ; } int Mid=(L+R)>>1; if(Mid>=pos) update(Now<<1,L,Mid,pos,val); else update(Now<<1|1,Mid+1,R,pos,val); Max[Now]=max(Max[Now<<1],Max[Now<<1|1]); } int qmax(int Now,int L,int R,int l,int r){ if(l<=L&&r>=R) return Max[Now]; int tmp=0,Mid=(L+R)>>1; if(l<=Mid) tmp=max(tmp,qmax(Now<<1,L,Mid,l,r)); if(r>Mid) tmp=max(tmp,qmax(Now<<1|1,Mid+1,R,l,r)); return tmp; } int main() { int N,L,H,M,i,j; scanf("%d%d%d%d",&N,&L,&H,&M); for(i=1;i<=N;i++) h[i]=H; build(1,1,N); for(i=1;i<=M;i++) scanf("%d%d",&x[i],&y[i]); bool Flag=true; while(Flag){ Flag=false; for(i=1;i<=M;i++){ if(x[i]==y[i]) continue; if(x[i]<y[i]){ if(qmax(1,1,N,x[i]+1,y[i]-1)>=h[x[i]]) { for(j=x[i]+1;j<y[i];j++) if(h[j]>=h[x[i]]){ h[j]=h[x[i]]-1;Flag=true; update(1,1,N,j,h[j]); } } } else { if(qmax(1,1,N,y[i]+1,x[i]-1)>=h[x[i]]){ for(j=x[i]-1;j>y[i];j--) if(h[j]>=h[x[i]]){ h[j]=h[x[i]]-1;Flag=true; update(1,1,N,j,h[j]); } } } } } for(i=1;i<=N;i++) printf("%d ",h[i]); return 0; }
【D：Nim森林】：
不如没有前面两步，就是最后一个石子输的Nim博弈类型。
忽略前面两步，输的情况是：
1，全部石子堆的石子个数都为1，而且石子堆数为奇。
2，至少有两堆大于1的石子堆，且石子堆的石子异或值为0。
根据两个情况，可以骗到一些分。。。（但是我手速慢了，最后慌慌张张提交，0分。。。输出“No”都有10分，妈蛋
1，假如只有一堆： 如果这一堆只有X=1个，那么必输；否则，胜利的代价是X-1。
2，假如全部堆都有Xi=1；那么胜利代价是N-2；
...