今天又文件错误了一道A的题，真是不长教训；

题解：

第一题：

每一层 k很小，考虑对路径数的奇偶性状压。

令 dp[i][S]表示第i 层奇偶状态为 S 的方案数，由于连边是固定的，转移显然。

注意到 O(k^2)转移需要优化成 O(k)，可以先把每一个点及与之相连的点对应的状态先 DP 出来，用位运算做到对每一个点 O(1) 转移，从而总的是 O(k)

我开始想到了这个做法，但觉得搞路径太麻烦，就放弃了，后来向轩哥学习了一波；

把前后两个状态压成二进制，在并起来就好了；因为只有后面是奇数并且边联通才有贡献，其他情况没有贡献，并起来是0；

用记搜跑起来挺快的；

 

#include
      
       using namespace std;const long long mod=998244353;int fg[10005][11], g[10005][11], n, a[1005], bin[(1<<10)+1], dp[10005][(1<<10)+1], pre, ed, k;#define RG registerint ksm(long long a,int b){    long long ret=1;    for(;b;b>>=1,a=a*a%mod)    if(b&1)ret=ret*a%mod;    return (int)ret;}int dfs(int now, int sta){    if(now==2){        return ( (bin[sta&pre]&1) == 0 );    }    if(dp[now][sta] != -1) return dp[now][sta];    if(sta == 0){        return dp[now][sta] = ksm(2, now-2);    }    int ret=0,tmp=0;    for(RG int i=0;i
       
        =mod)ret-=mod;    return dp[now][sta]=ret;}int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int main(){    freopen("adore.in","r",stdin);    freopen("adore.out","w",stdout);    scanf("%d%d",&n,&k);    int x;    memset(dp, -1, sizeof(dp));    for(int s=1;s<(1<
        
         >1]+(s&1);    for(int i=0;i
        
       
      

 

 

 

第二题：这题暴力搞就可以了，又froepen了；

#include
      
       using namespace std;const int M = 10000005;char s[6005][2005];int n, lim, res, cnt[6005], k, bin[(1<<6) + 1];bool uni(int x, int y){    int now=0;    for(int i=0;i
       
        =(n>>1))return 1;    }    if(res){        int t=(s[x][lim]-33)&(s[y][lim]-33);        for(int j=5,p=1;p<=res;p++,j--)            if(t&(1<
        
         =(n>>1);    }inline int up(int x){    int tot=0;    for(int i=0;i
         
          >1) + (s&1) : 0;}int main(){    freopen("confess.in","r",stdin);    freopen("confess.out","w",stdout);    int fg = 0, a1, a2;    scanf("%d", &n);    scanf("%s", s[1]);        k = strlen(s[1]);    lim = n*2/6, res=n*2%6;        for(int i=0;i<(1<<6);i++)bin[i]=go(i);    cnt[1]=up(1);            for(int i = 2; i <= n+1; i++){        scanf("%s", s[i]);        if(fg)continue;        cnt[i]=up(i);        if(cnt[i]<(n>>1)) continue;        for(int j = 1; j < i; j++){            if(cnt[j]>=(n>>1) && uni(i, j)) {a1=j, a2=i; fg = 1;break;}        }            }    fg ? printf("%d %d\n", a1, a2) : printf("NO Solution\n");}
         
        
       
      

 

 

 

第三题：贪心，考虑之前将军令的做法，从度数最深的跳k级father，再将father管辖的儿子放入优先队列，把当时同一层的儿子覆盖，如果s还有剩余，就覆盖上一层的儿子（这一层的儿子本来可以是更上面的节点管）；

就这样一直做下去就好了；

 

#include
      
       using namespace std;#define ex(i, u) for(register int i = h[u]; i; i = G[i].nxt)const int M = 1e5 + 5;int h[M], fg, tot, n, k, s, dep[M], anc[M][7], vis[M], id[M], que[M];struct edge{
    int v, nxt;}G[M<<1];void add(int u, int v){G[++tot].v = v, G[tot].nxt = h[u], h[u] = tot;}inline bool cmp(int a, int b){
    return dep[a]>dep[b];}void dfs(int u, int faa){    anc[u][0]=faa;    for(int p=1;p<=5;p++)        anc[u][p]=anc[anc[u][p-1]][p-1];    dep[u]=dep[faa]+1;    ex(i, u){        int v=G[i].v;        if(v==faa)continue;        dfs(v, u);    }}int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}#define RG registerint cnt;inline void col(int u,int f, int now){    if(now > k) return ;    que[++cnt]=u;    ex(i, u){        int v=G[i].v;        if(v==f||vis[v]) continue;        col(v, u, now+1);    }    } int main(){    freopen("repulsed.in","r",stdin);    freopen("repulsed.out","w",stdout);    n = read(), s = read(), k = read();     for(RG int i = 1; i < n; i++){        int u = read(), v = read();        add(u, v); add(v, u);    }    if(s == 1) {        printf("%d\n", n); return 0;    }    else {        int ans=0,vor=0;        dfs(1, 0);        for(RG int i=1;i<=n;i++)id[i]=i;        sort(id+1, id+1+n, cmp);                        for(RG int i=1;i<=n;i++){            RG int u=id[i], dd=dep[id[i]];            if(vis[u])continue;            int tp=k;            for(RG int p=0;tp;p++,tp>>=1)                if((tp&1) && anc[u][p]) u=anc[u][p];            cnt=0;            col(u, 0, 0);            sort(que+1, que+1+cnt, cmp);            RG int j;            for(j=1;j<=cnt&&dep[que[j]]==dd;j++){                vis[que[j]]=1;            }            int tmp=(j+s-2)/s;            RG int res=tmp*s-(j-1);            ans+=tmp;            for(j;res;res--,j++)vis[que[j]]=1;            //for(int j=1;j<=n;j++)printf("%d",vis[j]);printf("\n");                    }        printf("%d\n",ans);    }    }