A-C

直接放代码吧。

A

int n,k;

int main()

{

  n=read();k=read();

  puts(k<=(n+1)/2?"YES":"NO");

  return 0;

}

B

int d[N];pair<int,int>s[10];

int main()

{

  for(int i=1,u,v;i<=3;i++){

    u=read();v=read();

    s[i].first=u;s[i].second=v;

    d[u]++;d[v]++;

  }

  sort(s+1,s+3+1);

  for(int i=2;i<=3;i++)if(s[i]==s[i-1])return puts("NO"),0;

  for(int i=1;i<=4;i++)if(d[i]>=3)return puts("NO"),0;

  return puts("YES"),0;

}

C

int main()

{

  int k=read(),a=read(),b=read();ll ans=0;

  if(b<=a+2||k<=a-1)printf("%d\n",k+1);

  else{

    k-=a-1;ans=a;if(k&1)k--,ans++;

    printf("%lld\n",ans+1ll*(k/2)*(b-a));

  }

  return 0;

}

D - Ears

zsy在一条\([0,L]\)的数轴上来回走路。

zsy可以任选\([0,L]\)中的整点作为起点和终点,并且zsy走路时只能在整数位置(\(0,1,2,...,L\))调整方向。

每当zsy向左或向右经过一条\([i,i+1]\ (i\in[0,L))\)的线段时,zsy就会往这条线段的中间放上一个球。

当zsy走完路后,yyb会来到这条数轴。她会进行若干次操作:打爆一个球或在一条线段的中间放上一个球。

现在给出数轴每条线段中间最终球的个数\(a_1,...,a_n\),求出zsy的一种行走方式,使得yyb的操作次数最小。

因为zsy可以反复横跳来回地走,所以可以把\(a_i\)减去若干个2,最后只剩下\(0,1,2\)三种状态。

可以知道对应简化数组的一种最优方案里zsy不会重复走过一条路超过2次。

既然是回路问题,考虑插头dp。

设\(f[i][j][k]\)表示考虑轮廓线到达\(i\),插头有\(j\)个,已经用了\(k\)个单插头的最少代价,

直接转移即可。

int n,t[N];ll suft[N],dp[N][3][3],ans;

inline void upd(ll &a,ll b){a=a<b?a:b;}

inline int calc(int x,int r){

  if(r==0)return x;

  if(r==1)return x&1?0:1;

  if(r==2){if(!x)return 2;else return x&1?1:0;}

}

int main()

{

  n=read();for(int i=1;i<=n;i++)t[i]=read();

  for(int i=n;i;i--)suft[i]=suft[i+1]+t[i];ans=suft[1];

  memset(dp,63,sizeof(dp));dp[0][0][0]=0;

  for(int i=0;i<=n;i++)

    for(int a=0;a<3;a++)

      for(int b=0;b<3;b++){

    	if(a==0){

    	  upd(dp[i+1][a][b],dp[i][a][b]+t[i+1]);

    	  if(b!=2)upd(dp[i+1][a+1][b+1],dp[i][a][b]+calc(t[i+1],1));

    	  upd(dp[i+1][a+2][b],dp[i][a][b]+calc(t[i+1],2));

    	}

    	if(a==1){

    	  if(b!=2)upd(ans,dp[i][a][b]+suft[i+1]);

    	  upd(dp[i+1][a][b],dp[i][a][b]+calc(t[i+1],1));

    	  if(b!=2)upd(dp[i+1][a+1][b+1],dp[i][a][b]+calc(t[i+1],2));

    	}

    	if(a==2){

    	  upd(ans,dp[i][a][b]+suft[i+1]);

    	  if(b!=2)upd(dp[i+1][a-1][b+1],dp[i][a][b]+calc(t[i+1],1));

    	  upd(dp[i+1][a][b],dp[i][a][b]+calc(t[i+1],2));

    	}

      }

  printf("%lld\n",ans);

  return 0;

}

E - Odd Subrectangles

考虑给定行后选出列集合的方案数:

如果行的异或和不为0,那么总有一半的方案选出来异或和为1,另一半为0,因此方案为\(2^{m-1}\)

于是答案变成\(2^{m-1}S\),其中\(S\)表示行向量选出来的异或和不为\(0\)的方案数。

求解选取行向量集合,使其异或和不为0的方案数是一个经典问题:

考虑求出\(n\)个行向量的线性基,设其大小为\(r\)。

如果仅选取线性基中的元素,显然无法使得异或和为\(0\);

那么考虑先选取不在线性基中的元素:

对于这样的一组方案,在线性基中都有唯一的一种选取元素的方案,使得所有元素的异或和为0.

因此\(S=2^n-2^{n-r}\)。

int n,m,a[N][N],now[N],in[N],p[N][N],r;

inline int poww(int a,int b){

  int res=1;

  for(;b;b>>=1,a=1ll*a*a%mod)

    if(b&1)res=1ll*res*a%mod;

  return res;

}

int main()

{

  n=read();m=read();

  for(int i=1;i<=n;i++)

    for(int j=1;j<=m;j++)a[i][j]=read();

  for(int i=1;i<=n;i++){

    memcpy(now,a[i],sizeof(now));

    for(int j=1;j<=m;j++)

      if(now[j]){

	if(in[j])for(int k=j;k<=m;k++)now[k]^=p[j][k];

	else{in[j]=1;memcpy(p[j],now,sizeof(p[j]));r++;break;}

      }

  }

  printf("%lld\n",1ll*(poww(2,n)-poww(2,n-r)+mod)%mod*poww(2,m-1)%mod);

  return 0;

}

F - Pass

考虑直接构造最终序列。由传球方式可以知道,第\(i(i\le n)\)个球只会在\(1-i\)个人的手中出现,后\(n\)个求随意。

因此直接设\(f[i][j]\)dp,最后组合数乘一下即可。

char s[N];int n,dp[N][N],c[N][N],ans;

inline void upd(int &a,int b){a+=b;if(a>=mod)a-=mod;}

int main()

{

  scanf("%s",s+1);n=strlen(s+1);

  for(int i=0;i<=n;i++)

    for(int j=c[i][0]=1;j<=i;j++)upd(c[i][j]=c[i-1][j],c[i-1][j-1]);

  dp[0][0]=1;

  for(int i=1;i<=n;i++)

    for(int j=0,c=s[i]-48;j<=i;j++){

      if(j>=c-1)upd(dp[i][j],dp[i-1][j-c+1]);

      if(j>=c)upd(dp[i][j],dp[i-1][j-c]);

    }

  for(int i=0;i<=n;i++)upd(ans,1ll*dp[n][i]*c[n][i]%mod);

  printf("%d\n",ans);

  return 0;

}