ARC157
A
简单分讨即可
#include<bits/stdc++.h>
using namespace std;
int Abs(int x)
{
return x>0?x:-x;
}
int n;
int A,B,C,D;
int main()
{
scanf("%d %d %d %d %d",&n,&A,&B,&C,&D);
if(Abs(B-C)>1)
{
printf("No");
return 0;
}
if(B==0&&C==0)
{
if(A&&D)
{
printf("No");
return 0;
}
}
printf("Yes");
}
B
做法有点复杂,似乎是先把\(X\)变为\(Y\),如果变完了再把\(Y\)变\(X\),这里注意填完连续段的贡献会多一点
#include<bits/stdc++.h>
using namespace std;
int n,k;
string s;
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&k);
cin>>s;
int Res=0;
vector<int>Pos;
for(int i=0;i<n;i++)
{
if(s[i]=='Y')
{
Pos.push_back(i);
}
}
if(Pos.size()==n)
{
printf("%d\n",max(0,n-1-k));
return 0;
}
vector<int>si;
for(int i=1;i<Pos.size();i++)
{
int L=Pos[i-1]+1;
int R=Pos[i]-1;
si.push_back(R-L+1);
}
if(Pos.size()>=1)
{
//printf("ufkc\n");
int Po=Pos[0]+((n-1)-Pos.back());
sort(si.begin(),si.end());
for(int i=0;i<si.size();i++)
{
if(k>=si[i])
{
k-=si[i];
Res+=si[i]+1;
}
else
{
Res+=k;
k=0;
break;
}
}
if(k)
{
if(k<=Po)
{
Res+=k;
}
else
{
Res+=Po;
k-=Po;
if(k>0)
{
vector<int>Si;
Si.clear();
int Len=1;
int Op=0;
vector<int>BE;
BE.clear();
for(int i=1;i<Pos.size();i++)
{
if(Pos[i]==Pos[i-1]+1)
{
Len++;
}
else
{
if(Op)
{
Si.push_back(Len);
}
else
{
Op=1;
if(Len==Pos[i-1]+1)
{
BE.push_back(Len);
}
else
{
Si.push_back(Len);
}
}
Len=1;
}
}
if(Pos.back()==n-1)
{
BE.push_back(Len);
// printf("fuck\n");
}
else
{
if(Len==Pos.back()+1)
{
BE.push_back(Len);
}
else
{
Si.push_back(Len);
}
}
// printf("%d\n",BE.size());
if(BE.size())
{
for(int i=0;i<BE.size();i++)
{
int Lp=BE[i];
// printf("%d?\n",BE[i]);
if(Lp<k)
{
k-=Lp;
Res-=Lp;
}
else
{
Res-=k;
k=0;
break;
}
}
}
sort(Si.begin(),Si.end());
for(int i=Si.size()-1;i>=0;i--)
{
if(!k)
{
break;
}
int Lp=Si[i];
if(Lp<k)
{
k-=Lp;
Res-=(Lp+1);
}
else
{
Res-=(k+1);
k=0;
break;
}
}
}
}
}
printf("%d\n",Res);
}
else
{
printf("%d",max(0,k-1));
}
}
C
简单DP
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int MAXN=2e3+5;
int n,m;
string s[MAXN];
int dp1[MAXN][MAXN];
int dp2[MAXN][MAXN];
int dp3[MAXN][MAXN];
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
{
cin>>s[i];
}
dp1[0][0]=0;
dp2[0][0]=0;
dp3[0][0]=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(i==0&&j==0)
{
continue;
}
int nx=i-1;
int ny=j;
if(nx>=0&&ny>=0)
{
if(s[nx][ny]=='Y'&&s[i][j]=='Y')
{
dp1[i][j]=((long long)dp1[i][j]+((long long)2*dp2[nx][ny])%MOD)%MOD;
dp1[i][j]=((long long)dp1[i][j]+dp3[nx][ny])%MOD;
dp2[i][j]=((long long)dp2[i][j]+dp3[nx][ny])%MOD;
}
dp1[i][j]=((long long)dp1[i][j]+dp1[nx][ny])%MOD;
dp2[i][j]=((long long)dp2[i][j]+dp2[nx][ny])%MOD;
dp3[i][j]=((long long)dp3[i][j]+dp3[nx][ny])%MOD;
}
nx=i;
ny=j-1;
if(nx>=0&&ny>=0)
{
if(s[nx][ny]=='Y'&&s[i][j]=='Y')
{
dp1[i][j]=((long long)dp1[i][j]+((long long)2*dp2[nx][ny])%MOD)%MOD;
dp1[i][j]=((long long)dp1[i][j]+dp3[nx][ny])%MOD;
dp2[i][j]=((long long)dp2[i][j]+dp3[nx][ny])%MOD;
}
dp1[i][j]=((long long)dp1[i][j]+dp1[nx][ny])%MOD;
dp2[i][j]=((long long)dp2[i][j]+dp2[nx][ny])%MOD;
dp3[i][j]=((long long)dp3[i][j]+dp3[nx][ny])%MOD;
}
}
}
printf("%d",dp1[n-1][m-1]);
}
//2 2
//YY
//YY
D
之前一直往\(dp\)的方向想,结果就是个暴力、
实际上这玩意我们横着切一刀分出来的每一块的\(Y\)个数是一样的
直接枚举横着切了多少刀,这个时间复杂度感觉是\(n\),但实际上大概不超过\(100\)个比较玄学
然后我们就可以得到每一刀切的范围
对于竖着切一刀,其实差不多,注意要满足每横着的一块分到两个即可
实现起来有点细节,时间复杂度也很玄学
// LUOGU_RID: 118421079
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int MAXN=2005;
int n,m;
char s[MAXN][MAXN];
int Sum[MAXN][MAXN];
int PointL[MAXN];
int PointR[MAXN];/////
int PL[MAXN][MAXN];
int PR[MAXN][MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&m);
int Tot=0;
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]+1);
for(int j=1;j<=m;j++)
{
Sum[i][j]=Sum[i-1][j]+Sum[i][j-1]-Sum[i-1][j-1];
if(s[i][j]=='Y')
{
++Tot;
Sum[i][j]++;
}
}
}
if((Tot&1)||(!Tot))
{
printf("0");
}
else
{
int Res=0;
for(int x=1;x<=(n*m)/2&&x<=n;x++)
{
if((Tot/2)%x==0)
{
int Lix=(Tot/x);
int y=Lix/2;
int Liy=x*2;
int Last=0;
int Cx=0;
int res=1;
int i=1;
int Cp=1;
Last=i-1;
res=((long long)res*Cp)%MOD;
for(;i<=n;)
{
if(Sum[i][m]-Sum[Last][m]==Lix)
{
PointL[++Cx]=i;
Cp=1;
i++;
while(i<=n&&Sum[i][m]-Sum[i-1][m]==0)
{
++Cp;
i++;
}
if(Cx!=x)
{
res=((long long)res*Cp)%MOD;
}
Last=i-1;
PointR[Cx]=i-1;
}
else if(Sum[i][m]-Sum[Last][m]>Lix)
{
res=0;
break;
}
else
{
++i;
}
}
if(Cx!=x)
{
res=0;
//printf("???\n");
}
for(int i=1;i<=x;i++)
{
int j=1;
int Cy=0;
Last=j-1;
for(;j<=m;)
{
if((Sum[PointR[i]][j]-Sum[PointR[i-1]][j])-(Sum[PointR[i]][Last]-Sum[PointR[i-1]][Last])==2)
{
PL[i][++Cy]=j;
j++;
while(j<=m&&(Sum[PointR[i]][j]-Sum[PointR[i-1]][j])-(Sum[PointR[i]][j-1]-Sum[PointR[i-1]][j-1])==0)
{
j++;
}
Last=j-1;
PR[i][Cy]=j-1;
if(Cy==y)
{
PL[i][Cy]=m;
PR[i][Cy]=m;
}
}
else if((Sum[PointR[i]][j]-Sum[PointR[i-1]][j])-(Sum[PointR[i]][Last]-Sum[PointR[i-1]][Last])>2)
{
res=0;
break;
}
else
{
++j;
}
}
if(Cy!=y)
{
res=0;
//printf("%d %d???\n",x,Cy);
}
}
// printf("%d %d %d:::\n",x,y,res);
// for(int i=1;i<=x+1;i++)
// {
// for(int j=1;j<=y+1;j++)
// {
// printf("%d %d %d %d\n",i,j,PL[i][j],PR[i][j]);
// }
// }
for(int i=1;i<=y;i++)
{
int L=0;
int R=m;
for(int j=1;j<=x;j++)
{
L=max(PL[j][i],L);
R=min(PR[j][i],R);
}
if(L>R)
{
res=0;
}
else
{
res=((long long)res*(R-L+1))%MOD;
}
}
//printf("%d %d???\n",res,x);
Res=((long long)Res+res)%MOD;
}
}
printf("%d\n",Res);
}
}
E
没看到完全二叉树/kk
注意到是二叉树就简单了,可以发现\(C\)类的\(Y\)可以确定非叶子\(Y\)的个数是\(\dfrac{C}{2}\)
考虑如果根是\(Y\),那叶子上\(Y\)的个数就是\(B-\dfrac{C}{2}+1\),不是就是\(B-\dfrac{C}{2}\)
可以发现除了这些点都选\(X\)就满足条件了
然后可以发现\(Y\)就是最大独立集,可以设\(dp_{i,j,0/1}\)表示\(i\)为\(X/Y\)有\(j\)个叶子被选为\(Y\)时非叶子选为\(Y\)的最大个数
树上背包即可,\(1e8\)有点卡常
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
int T;
int n,A,B,C;
int x,y;
vector<int>g[MAXN];
int dp[MAXN][2][MAXN/2+15];
int Leaf[MAXN];
void dfs(int x)
{
if(!((int)g[x].size()))
{
Leaf[x]=1;
dp[x][1][1]=0;
dp[x][0][0]=0;
return;
}
dp[x][0][0]=0;
dp[x][1][0]=1;
Leaf[x]=0;
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
dfs(v);
for(int j=Leaf[x];j>=0;j--)
{
for(int k=Leaf[v];k>=0;k--)
{
dp[x][0][j+k]=max(dp[x][0][j+k],dp[x][0][j]+max(dp[v][0][k],dp[v][1][k]));
dp[x][1][j+k]=max(dp[x][1][j+k],dp[x][1][j]+dp[v][0][k]);
}
}
Leaf[x]+=Leaf[v];
}
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d %d %d %d",&n,&A,&B,&C);
for(int i=1;i<=n;i++)
{
g[i].clear();
for(int j=0;j<=max(n/2,B-C/2+1);j++)
{
dp[i][0][j]=-0x3f3f3f3f;
dp[i][1][j]=-0x3f3f3f3f;
}
}
for(int i=2;i<=n;i++)
{
scanf("%d",&x);
g[x].push_back(i);
}
if(C&1)
{
printf("No\n");
}
else
{
int Q=C/2;
int P=B-Q;
dfs(1);
if((P>=0&&dp[1][0][P]>=Q)||((P+1)>=0&&dp[1][1][P+1]>=Q))
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}
}