暂时只做了B题，所以只放一下B的题解
A-SOUL!
求公差为k的最长的等差数列长度
将数组排序去重
int n,k,ans; int a[maxn],dp[maxn]; void solve() { sdd(n,k); rep(i,1,n)sd(a[i]); sort(a+1,a+1+n); n=unique(a+1,a+1+n)-a-1; rep(i,1,n) { int p=lower_bound(a+1,a+1+n,a[i]-k)-a; if(a[p]!=a[i]-k)dp[i]=1; else dp[i]=dp[p]+1; ans=max(ans,dp[i]); } pd(ans); }
Bheith i ngra le
题意：
有一个m*n的网格，网格要么是黑色要么是白色。
1、所有的黑色网格连通
2、如果某一列有黑色网格，那么黑色必须是从最下面开始堆积
hi代表第i列的黑色网格个数
要求：
存在l,r使得
1、1≤l≤r≤n
2、hi在区间[1,l]非递减
3、hi在区间[r,n]非递增
4、hi在区间[l,r]相等
问共有多少种染色方法
题解：
动态规划呀！
都只考虑前面的非递减区域
dp[i][j]代表当第i列的hi为j时，前i-1列的可能涂色个数
sum[i][j]代表前i行最大的hi为j时的可能涂色个数
我想的是对于x这个位置，枚举它的高度hx，那么前面区间[1,x-1]的最高h小于hx的可能涂色个数即sum[x-1][hx-1]，然后后面区间[x+1,n]的最高h小于等于hx的可能涂色个数即sum[n-x][hx]，答案即sum[x-1][hx-1]*sum[n-x][hx]
int n,m,tmp[maxn]; int dp[maxn][maxn],sum[maxn][maxn]; int ans; void solve() { sdd(n,m); tmp[0]=ans=1; rep(i,0,n)sum[i][0]=1; rep(i,0,m)sum[0][i]=1; rep(i,1,n) { rep(j,1,m)tmp[j]=(tmp[j-1]+dp[i-1][j])%mod; rep(j,1,m) { dp[i][j]=tmp[j]; sum[i][j]=(sum[i][j-1]+tmp[j])%mod; } } rep(i,1,n)rep(j,1,m)ans=(ans+1ll*sum[i-1][j-1]*sum[n-i][j]%mod)%mod; pd(ans); }
Identical Day
优先队列保存长度为len的1串分成cnt+1段比分成cnt段能减少的分值
int n; char s[maxn]; priority_queue<PLII >pq; ll get_val(int len,int c)//长度为n去掉c个能得到的最大值 { if(c>=len)return 0; if(c>=len/2)return len-c; len-=c; c++; //转化为长度为len的1串要分成c段的最大值 int cnt=len%c,l=len/c+1; // cout<<len<<' '<<c<<' '<<1ll*cnt*l*(l+1)/2+1ll*(c-cnt)*l*(l-1)/2<<endl; return 1ll*cnt*l*(l+1)/2+1ll*(c-cnt)*l*(l-1)/2; } ll cur,k; void solve() { scanf("%d%lld",&n,&k); sc(s+1); s[n+1]='0'; int cnt=0; rep(i,1,n+1) { if(s[i]=='1')cnt++; else if(cnt) { cur+=get_val(cnt,0); pq.push(mk(get_val(cnt,0)-get_val(cnt,1),mk(cnt,0))); cnt=0; } } int ans=0; while(cur>k) { ans++; cur-=pq.top().fi; int len=pq.top().se.fi,cntt=pq.top().se.se; pq.pop(); pq.push(mk(get_val(len,cntt+1)-get_val(len,cntt+2),mk(len,cntt+1))); } pd(ans); }
JXC&amp;Jesus
暴力
先预处理出每个数对应的最小的质因子
int n,m,L; int pri[maxn],cnt; bool vis[maxn]; int val[maxn]; ll ans; void init() { for(int i=2;i<maxn;i++) { if(!vis[i])pri[++cnt]=val[i]=i; for(int j=1;j<=cnt&&pri[j]*i<maxn;j++) { vis[i*pri[j]]=1; val[i*pri[j]]=pri[j]; if(i%pri[j]==0)break; } } } void solve() { scanf("%d%d%d",&n,&m,&L); init(); ans=1ll*n*(L+1+L+n)/2; rep(i,L+1,L+n) { int cnt=0,x=i,v=1; while(x%val[i]==0) { x/=val[i]; cnt++; if(cnt%m==0)v*=val[i]; } ans-=1ll*x*v; } plld(ans); }
Minecraft
拓扑排序
int h,n,m; char s[35][35][35]; int in[30]; bool vis[30]; vector<int>vec[30]; void solve() { scanf("%d%d%d",&n,&m,&h); rep(i,0,25)vec[i].clear(),in[i]=vis[i]=0; rep(i,1,h)rep(j,1,n) { sc(s[i][j]+1); rep(k,1,m) { s[i][j][k]-='A'; vis[s[i][j][k]]=1; if(i==1||s[i][j][k]==s[i-1][j][k])continue; in[s[i-1][j][k]]++; vec[s[i][j][k]].pb(s[i-1][j][k]); } } priority_queue<int>pq; queue<int>ans; rep(i,0,25)if(vis[i]&&!in[i])pq.push(i); while(!pq.empty()) { int p=pq.top();pq.pop(); ans.push(p); for(int j:vec[p]) { in[j]--; if(!in[j])pq.push(j); } } int cnt=0; rep(i,0,25)if(vis[i])cnt++; if(cnt!=ans.size()) { puts("-1"); return; } while(!ans.empty())printf("%c",ans.front()+'A'),ans.pop(); puts(""); }