| Solved | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 6/6 | Ø | Ø | Ø | Ø | Ø | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
给一个$n\times m(1\leq n,m\leq 500)$的字符矩阵，问从左上角到右下角的路径（只能往右或者下走）中，有多少个路径得到的字符串为回文串。
解题思路
考虑从左上和右下角同时向中间走，记录走的步数和两端对应的横坐标。$dp[i][j][k]$表示走了$i$步，左上角走到横坐标为$x$的位置，右下角走到横坐标为$y$的位置，处理一下边界即可递推解决。（怕超空间用了一下滚动数组）
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
using namespace std;
typedef long long ll;
char a[N][N];
ll dp[2][N][N];
int main(){
int n,m,i,j,k;
scanf("%d%d",&n,&m);
int mx=(n+m-2)/2,p=0;
for(i=1;i<=n;i++)scanf("%s",a[i]+1);
dp[0][1][n]=(a[1][1]==a[n][m]);
for(i=1;i<=mx;i++){
p^=1;
memset(dp[p],0,sizeof(dp[p]));
for(j=max(1,i+2-m);j<=n&&j<=i+1;j++){
int x1=j,y1=i-j+2;
for(k=max(1,n-i);k<=n&&k<=n+m-i;k++){
int x2=k,y2=n+m-i-k;
if(a[x1][y1]==a[x2][y2])
dp[p][j][k]=(dp[p^1][j-1][k]+dp[p^1][j-1][k+1]+dp[p^1][j][k]+dp[p^1][j][k+1])%w;
}
}
}
ll ans=0;
if((n+m)&1)for(i=1;i<=n;i++)ans+=dp[p][i][i]+dp[p][i][i+1];
else for(i=1;i<=n;i++)ans+=dp[p][i][i];
printf("%I64d\n",ans%w);
return 0;
}
B
题目描述
给出长度为$n\leq 500000$的数组$a_i$，可以连续或间断输出，每连续输出一串$[l,r]$，它的费用是$\sum_{i=l}^{r}a_i^2+M$，求最小花费。
解题思路
观察状态转移方程$f[i]=min(f[j]+(s[i]-s[j])^2+M)=M+S[i]^2+min(f[j]+s[j]^2-s[j]*s[i])$，尝试对该方程进行优化。从前向后递推，尝试用一种方法保证每次能够$O(1)$地查询到$min$所要求的$j$。对于任意在$j$前面出现的$k$，如果$j$比$k$优，则可以彻底移除$k$。
如果$j$比$k$优：$\frac{f[j]+s[j]^2-f[k]-s[k]^2}{2(f[j]-f[k])}\leq s[i]$，考虑对任意一个位置$i$构造点$(x_i,y_i)=(f[i]+s[i]^2,2f[i])$，则$k$到$j$的线段斜率如果小于$s[i]$则必然会被排除（因为$s[i]$会越变越大，随着$i$的增加$k$永远不如$j$优）。故维护一个单调队列，这个队列的单调性在于把这些位置对应的点连接起来的斜率严格单调增。每次取队首元素，添加队尾元素，即可保证复杂度的线性。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef long long ll;
using namespace std;
ll s[N],f[N];
int q[N],hd,tl;
ll getup(int x,int y){return f[x]+s[x]*s[x]-f[y]-s[y]*s[y];}
ll getdown(int x,int y){return 2*s[x]-2*s[y];}
int main(){
int i,n,m;
while(~scanf("%d%d",&n,&m)){
hd=0;tl=1;
for(i=1;i<=n;i++)scanf("%d",&s[i]),s[i]+=s[i-1];
for(i=1;i<=n;i++){
while(hd+1<tl&&getup(q[hd+1],q[hd])<=s[i]*getdown(q[hd+1],q[hd]))hd++;
f[i]=f[q[hd]]+m+(s[i]-s[q[hd]])*(s[i]-s[q[hd]]);
while(hd+1<tl&&getup(q[tl-1],q[tl-2])*getdown(i,q[tl-1])>=getup(i,q[tl-1])*getdown(q[tl-1],q[tl-2]))tl--;
q[tl++]=i;
}
printf("%lld\n",f[n]);
}
return 0;
}
C
题目描述
给一个$n\times m(1\leq n,m\leq 12)$的玉米田，每一行只能选择有肥料的地方种植，行之间、列之间不允许有相邻的玉米种植，问总共有多少种种法。
解题思路
一看数据范围这么小肯定是状态压缩$dp[i][S]$表示填到第$i$行，这一行状态为$S$的时候有多少种方法。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef long long ll;
ll ans,f[N][1<<N]={1};
int m,n,state[N];
int main(){
int i,j,k,x;
scanf("%d%d",&m,&n);
int S=1<<n;
for(i=1;i<=m;i++)for(j=1;j<=n;j++)
scanf("%d",&x),state[i]=(state[i]<<1)+x;
for(i=1;i<=m;i++)for(j=0;j<S;j++)
if(!(j&(j>>1))&&!(j&(j<<1))&&!(j&(~state[i])))
for(k=0;k<S;k++)if(!(k&j))(f[i][j]+=f[i-1][k])%=w;
for(i=0;i<S;i++)(ans+=f[m][i])%=w;
printf("%I64d",ans);
return 0;
}
D
题目描述
一群人编号为$1-n$坐成一圈，一个人当且仅当坐在其编号左右两个位置时是高兴的。问$n(3\leq n\leq 2000)$个人中至少让$k$个人高兴有多少种方法。
解题思路
先考虑求确定有$p$个人高兴的（可重复）方法$r[p]$，则恰好有$i$个人高兴的方法用容斥可以求出：
$sum[i]=\sum_{j=i}^{n}r[j]\times (n-j)!\times C_j^i\times (-1)^{i-j}$
那么答案即为$ans=\sum_{i=k}^{n}sum[i]$。这里为什么不直接令$ans=r[k]$呢？因为$r[p]$使用动归递推得出，可能会有重复计算，具体请看下文。
第一感构造$dp[i][j]$表示填了$i$个人，有$j$个高兴的个数，但发现极难转化。
这时候本题最巧妙的地方到了。
构造一个长度为$N$的环，一个个往里面填人$i$，记录下来$n,1,i$三个点是否高兴的状态进行转移。
最后统计答案的时候应当在某处断开构成一个环，所以需要记录第$i+1$个人的状态，以方便与$n,1$比较，方便去重。故$dp[bit(n)bit(1)][bit(i+1)bit(i)][i][j]$表示状态分别为表示之时，填到第$i$个人，已经有$j$个人高兴的方法。
于是$r[i]=\sum_{a=0}^{3}\sum_{b=0}^{3}(!(a&1,b&2)\quad and\quad!(a&2,b&1))dp[a][b][n][i]$。（判断条件是为了去重）
边界：$i=1$的时候，$bit(1)=bit(i)$，故$dp[0][0][1][0]=1$（都不高兴），$dp[2][0][1][1]=1$（第$n$个人高兴），$dp[0][2][1][1]=1$（第$i+1$个人高兴），$dp[1][1][1][1]=1$（第$1$个人高兴）。
转移：
$dp[a][b][i][j]$可以加一个人什么都不做转移到$dp[a][b>>1][i+1][j]$
$dp[a][b][i][j]$可以加一个人使得第$i+2$个人高兴，转移到$dp[a][(1<<1)|(b>>1)][i+1][j+1]$
如果第$i$个人没有确定高兴，则$dp[a][b][i][j]$可以加一个人使得第$i$个人高兴，转移到$dp[a][b>>1][i+1][j+1]$，这里特判一下$i=1$的情况即可。
如果第$i+1$个人没有确定高兴，则$dp[a][b][i][j]$可以加一个人使得第$i+1$个人高兴，转移到$dp[a][1][i+1][j+1]$
就结束了。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
typedef long long ll;
ll w=1000000007,inv[N]={1},fac[N]={1};
ll qp(ll a,ll b){
ll ans=1;
for(;b;b>>=1,a=a*a%w)if(b&1)ans=ans*a%w;
return ans;
}
ll c(int n,int m){return fac[n]*inv[m]%w*inv[n-m]%w;}
ll dp[4][4][N][N];
void add(ll &a,ll b){(a+=b)%=w;if(a<0)a+=w;}
void init(){
int i,j,a,b;
for(i=1;i<2001;i++)fac[i]=fac[i-1]*i%w,inv[i]=qp(fac[i],w-2);
dp[0][0][1][0]=dp[2][0][1][1]=dp[1][1][1][1]=dp[0][2][1][1]=1;
for(i=1;i<2001;i++){
for(j=0;j<=i;j++){
for(a=0;a<4;a++){
for(b=0;b<4;b++){
ll t=dp[a][b][i][j];if(!t)continue;
add(dp[a][b>>1][i+1][j],t);
if((b&1)==0){
if(i==1)add(dp[a|1][b>>1][i+1][j+1],t);
else add(dp[a][b>>1][i+1][j+1],t);
}
if((b&2)==0)add(dp[a][1][i+1][j+1],t);
add(dp[a][2|(b>>1)][i+1][j+1],t);
}
}
}
}
}
ll r[N];
int main(){
int i,j,a,b,T,n,k,cas=0;
scanf("%d",&T);
init();
while(~scanf("%d%d",&n,&k)){
ll ans=0;
for(j=k;j<=n;j++){
r[j]=0;
for(a=0;a<4;a++)for(b=0;b<4;b++)
if((a&1)&&(b&2)||(a&2)&&(b&1));
else add(r[j],dp[a][b][n][j]);
}
for(i=k;i<=n;i++){
for(j=i;j<=n;j++)
add(ans,((j-i)&1?-1:1)*(r[j]*fac[n-j]%w*c(j,i)%w));
}
printf("Case %d: %lld\n",++cas,ans);
}
return 0;
}
E
题目描述
定义一个区间的价值为该区间中两两相等的元素个数。给一个长度为$n(2\leq n\leq 10^5)$的序列，把它分成$k(2\leq k\leq min(n,20))$段，求最小总价值。
解题思路
设$dp[i][j]$表示选了前$i$个数，分成$j$段的最小总价值。则$dp[i][j]=min(dp[k][j-1]+w(k+1,i))$，$w(l,r)$表示$[l,r]$区间内的价值总和。
很明显，$i_1>i_2$时，设决策点分别为$k_1,k_2$，则有$k_1\geq k_2$，即有决策单调性。
于是考虑分治求$dp$，从小到大枚举分成的段数进行$dp$，记当前计算区间为$[l,r]$，决策所在区间为$[L,R]$ ，则枚举$[L,R]$中的元素找到决策值$nxt$，分别计算$[l,mid-1]$（对应决策区间$[L,nxt]$）和$[mid+1,r]$（对应决策区间$[nxt,R]$）即可。时间复杂度$O(nklogn)$。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
typedef long long ll;
using namespace std;
int n,k,a[N];
ll dp[N][22];
int buc[N],pL,pR;
ll nowans;
void upd(int x,ll f){
nowans+=f*buc[x]*(buc[x]-1)/2;
}
ll calc(int l,int r){
while(pL<l){
upd(a[pL],-1);buc[a[pL]]--;
upd(a[pL],1);pL++;
}
while(r<pR){
upd(a[pR],-1);buc[a[pR]]--;
upd(a[pR],1);pR--;
}
while(l<pL){
pL--;
upd(a[pL],-1);buc[a[pL]]++;
upd(a[pL],1);
}
while(pR<r){
pR++;
upd(a[pR],-1);buc[a[pR]]++;
upd(a[pR],1);
}
return nowans;
}
void solve(int p,int L,int R,int l,int r){
if(l>r||L>R)return;
int i,mid=(l+r)>>1,nxt=0;
ll &ans=dp[mid][p];
for(i=L;i<=R;i++){
ll tmp=calc(i+1,mid);
if(tmp+dp[i][p-1]<ans)ans=tmp+dp[i][p-1],nxt=i;
}
solve(p,L,nxt,l,mid-1);
solve(p,nxt,R,mid+1,r);
}
int main(){
int i;
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
buc[a[1]]++;pL=pR=1;
for(i=1;i<=k;i++)solve(i,0,n-1,1,n);
printf("%lld",dp[n][k]);
return 0;
}
F
题目描述
给一个树每一个节点染黑白色，问恰好染$k$个黑色之后黑色点两两之间距离之和与白色点两两之间距离之和的和最大为多少。
解题思路
这个树形$DP$很妙，可以找每一条边的贡献。用$f[i][j]$表示节点$i$的子树当前已经选择了$j$个黑色节点时当前节点已枚举子树中所有边对答案的贡献之和。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
typedef long long ll;
using namespace std;
struct Edge{
int e,n;ll l;
}e[N<<1];
int hd[N],cnt;
void add(int a,int b,ll l){
e[++cnt]=(Edge){b,hd[a],l};hd[a]=cnt;
}
int siz[N],n,k;
ll f[N][N];
void dfs(int x,int fa){
int i,j,l;
siz[x]=1;
for(i=hd[x];i;i=e[i].n){
int q=e[i].e;
if(q==fa)continue;
dfs(q,x);
for(j=min(siz[x],k);j>=0;j--)
for(l=min(k-j,siz[q]);l>=0;l--)
f[x][j+l]=max(f[x][j+l],f[x][j]+f[q][l]+e[i].l*(1LL*(siz[q]-l)*(n-k+l-siz[q])+1LL*l*(k-l)));
siz[x]+=siz[q];
}
}
int main(){
int i,u,v;ll w;
scanf("%d%d",&n,&k);
for(i=1;i<n;i++)scanf("%d%d%lld",&u,&v,&w),add(u,v,w),add(v,u,w);
dfs(1,0);
printf("%lld",f[1][k]);
return 0;
}