这次终于没有垫底了。。。
本来是预计有280分的，但是第三题的DP写炸了，后来发现答案加一就可以拿到50分了。。。
T1:
因为是求最小步数，可以考虑用贪心或DP来解决，但是由于DP不会，所以就贪心吧。。。
贪心思想：
用桶记录下1的个数，2的个数，然后考虑要给1留多少空间，给2留多少空间，再进行贪心的交换
code:
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]==1) b[1]++;
if(a[i]==2) b[2]++;
}
for(int i=1;i<=b[1];i++)
if(a[i]==3){
for(int j=n;j>b[1];j--)
if(a[j]==1){
swap(a[i],a[j]);
ans++;
break;
}
}
else if(a[i]==2){
for(int j=b[1]+1;j<=n;j++)
if(a[j]==1){
swap(a[i],a[j]);
ans++;
break;
}
}
for(int i=b[1]+1;i<=b[1]+b[2];i++)
if(a[i]==3){
for(int j=n;j>=b[1]+b[2]+1;j--)
if(a[j]==2){
swap(a[i],a[j]);
ans++;
break;
}
}
printf("%lld",ans);T2:
这题主要的瓶颈在于掌握O(n log n)的艾式筛法或者O(n)的欧拉筛，求出1`n之间的所有质数后进行二分判断，更新答案
code:
for(int i=2;i<=1000000;i++){
if(!h[i]) p[++m]=i;
for(int j=1;j<=m&&p[j]*i<=1000000;j++){
h[i*p[j]]=true;
if(!i%p[j]) break;
}
}
for(int i=1;i<=m;i++) s[i]=s[i-1]+p[i];
read(t);
while(t--){
read(n),read(k);
l=1;r=m-k+2;ans=0;
if(r<2){puts("-1");continue;}
while(l<=r){
int mid=l+r>>1;
if(s[mid+k-1]-s[mid-1]<=n) l=mid+1,ans=mid;
else r=mid-1;
}
if(s[ans+k-1]-s[ans-1]<=n&&ans) printf("%lld\n",s[ans+k-1]-s[ans-1]);
else puts("-1");
}T3:
这道题目初见以为是最长下降子序列，后来发现有c[i]值，可以用另外一种DP来解决。。。
骗分：
我也不知道这是怎么想到的。。
设f[i][j]为从i跳到j（有中转）的最多次数（漏洞百出。。。），c[i][j]为从i跳到j（有中转）的最小代价（符合f数组），
然后设g[i][j]为从i直接跳到j的代价，可以得出方程：
f[i][j]=max(f[i][j],f[i][x]+f[x+1][j]+1);
c[i][j]=min(g[i][x]+g[x+1][j]+g[x][x],c[i][j]);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i].c);
for(int i=1;i<=n;i++)scanf("%d",&a[i].h);
scanf("%d",&v);
int flag=1;
for(int i=1;i<=n;i++)if(a[i].h!=a[i+1].h) flag=0;
if(flag){
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
v-=a[i].c;
if(!v) break;
ans++;
}
printf("%d",ans);
}
else{
memset(c,127,sizeof(c));
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)g[i][j]=a[i].c+i!=j?a[j].c:0+abs(a[i].h-a[j].h);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
for(int x=i;x<=j;x++){
f[i][j]=max(f[i][j],f[i][x]+f[x+1][j]+1);
c[i][j]=min(g[i][x]+g[x+1][j]+g[x][x],c[i][j]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
if(c[i][j]<=v) ans=max(ans,f[i][j]);
}
printf("%d",ans/2+1);
} 然后问一下大佬：为什么这个DP是对的(虽然只有50分）。。
T4：
这道题本来应该是水题，结果由于数论太差了。。（辗转相减是什么都不知道。。）没做出来
由于辗转相减与辗转相除其实是一样的，所以其实可以用辗转相除法来求gcd来得到答案
code:
scanf("%lld%lld",&a,&b);
if(a<b) swap(a,b);
while(b){
ans+=a/b;
a%=b;
swap(a,b);
}
printf("%lld",ans+1);T5：
这是一道模拟题，但是作为模拟的铺垫的思维比较繁琐，我很懒，就不想写算了。。。
T6：
这道题我只拿到了30分，剩下来的70分有30分是我这个水平的选手能拿到的。。。
这个30分就是说每次给出的模数p相同，那么可以用vector来预处理出每个a[i] mod p所得的数所处的位置（下标）
然后就可以开始二分，但是要注意二分不能二分整个区间，而是先二分出左边界（>=l）然后再二分右边界（<=r）就可以O(log n)求出答案
需要注意的是，由于vector可能为空（或者其他特殊情况），所以第一次二分ans=vector[v].size()，第二次ans=-1，这样使得区间最鬼畜化，就可以避免爆炸。。。
code:
int check1(int x){return ve[v][x]>=l;}
int check2(int x){return ve[v][x]<=r;}
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
if(n<=1e3&&m<=1e3){
while(m--){
ans=0;
scanf("%d%d%d%d",&l,&r,&p,&v);
for(int i=l;i<=r;i++)if(a[i]%p==v) ans++;
printf("%d\n",ans);
}
return 0;
}
scanf("%d%d%d%d",&l,&r,&p,&v);
for(int i=1;i<=n;i++){
a[i]%=p;
ve[a[i]].push_back(i);
}
for(int i=l;i<=r;i++)if(a[i]==v) ans++;
printf("%d\n",ans);
m--;
while(m--){
ans=0;
scanf("%d%d%d%d",&l,&r,&p,&v);
int l1=0,r1=(int)ve[v].size()-1;ans=ve[v].size();
while(l1<=r1){
int mid=l1+r1>>1;
if(check1(mid)) r1=mid-1,ans=mid;
else l1=mid+1;
}
int cnt=ans;ans=-1;
l1=0;r1=(int)ve[v].size()-1;
while(l1<=r1){
int mid=l1+r1>>1;
if(check2(mid)) l1=mid+1,ans=mid;
else r1=mid-1;
}
printf("%d\n",ans-cnt+1);
}完结。。。
最后问大佬一个问题：
为什么t4的鬼畜DP能拿50分啊。。。
而且听说zjh大佬用我的DP方程做到了AC。。。我也是颜面扫地啊。。。我提出的算法，别人A了，我没有。。。
