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