Link:
ARC060 传送门
C:
由于难以维护和更新平均数的值：
$Average->Sum/Num$
这样我们只要用$dp[i][j][sum]$维护前$i$个数中取$j$个，且和为$sum$的个数
最后统计$dp[n][k][k*a]$即可
这样就得到了$O(n^4)$的解法
#include <bits/stdc++.h>using namespace std; typedef long long ll; const int MAXN=55; int n,a,sum,dat[MAXN]; ll dp[MAXN][MAXN][MAXN*MAXN],res=0;int main() {scanf("%d%d",&n,&a);for(int i=1;i<=n;i++) scanf("%d",&dat[i]);dp[1][1][dat[1]]=1;sum=dat[1]+dat[2];for(int i=1;i<=n;i++) dp[i][0][0]=1;for(int i=2;i<=n;i++,sum+=dat[i])for(int j=1;j<=i;j++)for(int k=1;k<=sum;k++){dp[i][j][k]=dp[i-1][j][k];if(k>=dat[i]) dp[i][j][k]+=dp[i-1][j-1][k-dat[i]];}for(int i=1;i<=n;i++) res+=dp[n][i][i*a];printf("%lld",res);return 0; }
不过真的需要同时记录个数与和吗？
如果将$dat[i]->a-dat[i]$，只要维护最终和为0的情况即可
于是将复杂度降到了$O(n^3)$
#include <bits/stdc++.h>using namespace std; const int MAXN=51,ZERO=2550; typedef long long ll; int n,a,x,cur; ll dp[2][2*ZERO];int main() {scanf("%d%d",&n,&a);dp[cur^1][ZERO]=1;for (int i=1;i<=n;i++,cur^=1){scanf("%d",&x);x-=a;for (int j=MAXN;j+MAXN<2*ZERO;j++)dp[cur][j]=dp[cur^1][j]+dp[cur^1][j-x];}printf ("%lld\n",dp[cur^1][ZERO]-1); }
D:
遇到多次取模问题时，有以下对数据的典型分类：
1、$base\le sqrt(n)$，此时直接枚举即可
2、$base>sqrt(n)$，此时由$n=p*base+q$和$p+q=s$可得$n-s=p(base-1)$
从小到大枚举$n-s$的所有约数算出$base$再验证
#include <bits/stdc++.h>using namespace std; typedef long long ll; ll n,s,sq;bool check(ll b) {ll ret=0,t=n;for(;t;t/=b) ret+=t%b;return (ret==s); }ll solve() {if(s==n) return n+1; //s=1时不特殊处理 if(s>n) return -1;for(int i=2;i<=sq;i++)if(check(i)) return i;for(int i=sq;i;i--) //注意枚举顺序 if((n-s)%i==0&&check((n-s)/i+1)) return ((n-s)/i+1);return -1; }int main() {scanf("%lld%lld",&n,&s);sq=sqrt(n);printf("%lld",solve());return 0; }
很多题目都是暴力枚举$k\le sqrt(n)$，对$k>sqrt(n)$进行分块等处理来保证$O(nlog(n))$的复杂度
E:
比较明显的序列上倍增裸题
记录每个点能达到的最大距离再倍增即可
可以用假设法证明$dist(i,j)=dist(j,i)$
#include <bits/stdc++.h>using namespace std; const int MAXN=1e5+10; int n,l,q,a,b,dat[MAXN],nxt[MAXN][25];int main() {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&dat[i]);scanf("%d",&l);for(int i=1;i<=n;i++)nxt[i][0]=upper_bound(dat+1,dat+n+1,dat[i]+l)-dat-1;for(int i=n;i;i--)for(int j=1;j<=20;j++)nxt[i][j]=nxt[nxt[i][j-1]][j-1];scanf("%d",&q);while(q--){scanf("%d%d",&a,&b);if(a>b) swap(a,b);int res=0;for(int i=20;i>=0;i--)if(nxt[a][i]&&nxt[a][i]<b) a=nxt[a][i],res+=(1<<i);printf("%d\n",res+1);}return 0; }
F:
首先要在对小数据尝试后得到结论：
分成的组数只可能为$1 / 2 / len(s)(当每个字符都相同时)$
接下来只要判断任意一个$s$的前缀/后缀是否有循环节即可
%陈主力的代码后找到了最简易的判断方式：$KMP$算法中的$nxt$数组！
由画图可知：一个字符串最长相同的前/后缀有重叠部分且剩余部分为$len$的约数则其有循环节
因此$pos\% (pos-nxt[pos])==0$时则$pos$为有循环节的前缀/后缀
正反求一次$nxt$数组枚举每一个分割点判断就好啦
#include <bits/stdc++.h>using namespace std; const int MAXN=5e5+10; char s[MAXN]; int len,res=0,nxt1[MAXN],nxt2[MAXN];void cal_nxt(int* nxt) {int k=0;for(int i=2;i<=len;i++){while(k&&s[k+1]!=s[i]) k=nxt[k];if(s[k+1]==s[i]) k++;nxt[i]=k;} }bool check(int* nxt,int pos) {if(!nxt[pos]) return false;return (pos%(pos-nxt[pos])==0); }int main() {scanf("%s",s+1);len=strlen(s+1);cal_nxt(nxt1);if(!check(nxt1,len)) printf("1\n1");else if(nxt1[len]==len-1) printf("%d\n1",len);else{reverse(s+1,s+len+1);cal_nxt(nxt2);for(int i=1;i<=len;i++)res+=(!check(nxt1,i))&(!check(nxt2,len-i));printf("2\n%d",res);}return 0; }
Review:
感觉$Atcoder$里的题目对推断能力要求比较高
还是要多尝试小数据，大胆猜结论再证明