0-1-Tree CodeForces - 1156D
https://cn.vjudge.net/problem/CodeForces-1156D
解法1：暴力dp，分情况讨论，难
代码参考：https://blog.csdn.net/Coldfresh/article/details/89792170

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (500+10)
#define max2 (1000+10)
#define maxn (1000000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n;
int head[maxn],pre[maxn<<1],to[maxn<<1],tot,t[maxn<<1];
void adde(int u,int v,int w){to[++tot]=v,pre[tot]=head[u],head[u]=tot,t[tot]=w;}
ll dp[maxn][4];
//dp[i][0] root i,all 0
//dp[i][1] root i,all 1
//dp[i][2] root i,000...111
//dp[i][3] root i,111...000
ll ans=0;
void dfs(int u,int fa)
{
    for(int i=head[u];i;i=pre[i])
    {
        int v=to[i];if(v==fa)continue;
        dfs(v,u);
        if(t[i]==1)
        {
            ans+=dp[u][1]*(dp[v][1]+1)*2;
            ans+=(dp[u][0]+dp[u][3])*(dp[v][1]+1);
            ans+=dp[u][1]*(dp[v][3]+dp[v][0]);
            
            dp[u][1]+=dp[v][1]+1;
            dp[u][3]+=dp[v][0];
            dp[u][3]+=dp[v][3];
        }
        else
        {
            ans+=dp[u][0]*(dp[v][0]+1)*2;
            ans+=(dp[u][1]+dp[u][2])*(dp[v][0]+1);
            ans+=dp[u][0]*(dp[v][1]+dp[v][2]);
            dp[u][2]+=dp[v][1];
            dp[u][0]+=dp[v][0]+1;
            dp[u][2]+=dp[v][2];
        }
    }
    ans+=(dp[u][0]+dp[u][1])*2+dp[u][2]+dp[u][3];
}
/*
2
1 2 1
*/
int main()
{
    RD1(n);for(int i=1;i<n;i++){int u,v,w;RD3(u,v,w);adde(v,u,w);adde(u,v,w);}
    dfs(1,0);printf("%lld",ans);
    return 0;
}





解法2：并查集，相对简单

精妙的代码实现：

https://blog.csdn.net/qq_41730082/article/details/89742810



A and B and Interesting Substrings CodeForces - 519D


#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (500+10)
#define max2 (1000+10)
#define maxn (100000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int val[200];
ll sum[maxn];
char s[maxn];
map<ll,int>m[26];
int main()
{
    for(int i='a';i<='z';i++)RD1(val[i]);
    scanf("%s",s);
    ll ans=0;
    m[s[0]-'a'][val[s[0]]]++;
    sum[0]=val[s[0]];
    for(int i=1;s[i];i++)
    {
        char cur=s[i];
        ans+=m[cur-'a'][sum[i-1]];
        sum[i]=sum[i-1]+val[cur];
        m[cur-'a'][sum[i]]++;
    }
    cout<<ans;
    return 0;
}





A and B and Lecture Rooms CodeForces - 519E

lca模板见:https://www.cnblogs.com/zhouzhendong/p/7256007.html


#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (500+10)
#define max2 (1000+10)
#define maxn (100000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n;
int head[maxn],tot,to[maxn<<1],pre[maxn<<1],dep[maxn],p[maxn],f[maxn][20],sz[maxn];
void adde(int u,int v)
{
    to[++tot]=v,pre[tot]=head[u],head[u]=tot;
}
void dfs(int u)
{
    dep[u]=dep[p[u]]+1;
    sz[u]=1;
    f[u][0]=p[u];
    for(int i=1;i<20;i++)
        f[u][i]=f[f[u][i-1]][i-1];
    
    for(int i=head[u];i;i=pre[i])
    {
        int v=to[i];if(v==p[u])continue;
        p[v]=u;dfs(v);
        sz[u]+=sz[v];
    }
}
int lca(int x,int y)
{
    for(int i=19;i>=0;i--)if(dep[x]-(1<<i)>=dep[y])
        x=f[x][i];
    if(x==y)return x;
    for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i])
        x=f[x][i],y=f[y][i];
    return f[x][0];
}
int query(int x,int y)
{
    if(x==y)return sz[1];
    if(dep[x]<dep[y])swap(x,y);
    int ast=lca(x,y);
    int len=dep[x]-dep[ast]+dep[y]-dep[ast];
    if(len%2)return 0;
    len>>=1;
    bool level=dep[x]==dep[y];
    if(level)
    {
        for(int i=1;i<len;i++)x=p[x],y=p[y];
        return sz[1]-sz[x]-sz[y];
    }
    else
    {
        for(int i=1;i<len;i++)x=p[x];
        return sz[p[x]]-sz[x];
    }
}
int main()
{
    RD1(n);for(int i=1;i<n;i++)
    {
        int u,v;RD2(u,v);adde(u,v),adde(v,u);    
    }
    dfs(1);
    int q;RD1(q);
    while(q--)
    {
        int u,v;RD2(u,v);
        printf("%d\n",query(u,v));
    }
    return 0;
}






1-2-K Game CodeForces - 1194D

https://cn.vjudge.net/problem/CodeForces-1194D

打表找规律


#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (500+10)
#define max2 (1000+10)
#define maxn (100000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int sg[maxn];
int brute(int n,int k)
{
    CLR(sg);sg[1]=sg[2]=1;
    for(int i=1;i<=n;i++)
    {
        if(!sg[i-1]){sg[i]=1;continue;}
        if(!sg[i-2]){sg[i]=1;continue;}
        if(i-k>=0&&!sg[i-k]){sg[i]=1;continue;}
    }
    for(int i=0;i<=n;i++)see(i),see(sg[i]),NL;
    NL;
}
int main()
{
    //brute(100,10);
    int ttt;RD1(ttt);while(ttt--)
    {
        int n,k;RD2(n,k);
        if(n==k)printf("Alice\n");
        else if(k%3)
        {
            if(n%3)printf("Alice\n");
            else printf("Bob\n");    
        }
        else
        {
            n%=(k+1);
            if(n==k)printf("Alice\n");
            else if(n%3)printf("Alice\n");
            else printf("Bob\n");
        }
    }
    return 0;
}






"Or" Game CodeForces - 579D

https://cn.vjudge.net/problem/CodeForces-579D



暴力正解：https://www.cnblogs.com/zhangchengc919/p/5572966.html

想到了就很简单





Prefixes and Suffixes CodeForces - 432D

https://cn.vjudge.net/problem/CodeForces-432D

kmp+dp的思路不好想，

一般的dp是以当前状态为目标态，用多个之前的状态依次更新

而这里用当前态直接更新'未来'状态

还有一种冷门的z算法，反正自己是想不到这么做的

思路见https://blog.csdn.net/weixin_44031744/article/details/86693545

代码虽短，理解不易


#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (500+10)
#define max2 (1000+10)
#define maxn (100000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int pre[maxn];
//pre[i]:the end pos of the max prefix,equals the suffix ,of the substring[1,i];
char s[maxn];
int rec[maxn],pr;
int dp[maxn];
void getpre(int len)
{
    int fail=pre[0]=-1,pos=0;
    while(pos<len)
    {
        //see(pos),see(pre[pos]),NL;
        while(fail!=-1&&s[fail]!=s[pos]) fail=pre[fail];
        pre[++pos]=++fail;
    }
}
int main()
{
    scanf("%s",s);int len=strlen(s);getpre(len);
    int pt=len;
    while(pt)
        rec[pr++]=pt,pt=pre[pt];
    for(int i=len;i>=0;i--)dp[i]=1;
    for(int i=len;i;i--)
    {
    //    see(i),see(pre[i]),see(dp[i]),see(dp[pre[i]]),NL;
        dp[pre[i]]+=dp[i];
    }
    printf("%d\n",pr);
    while(pr--)
        printf("%d %d\n",rec[pr],dp[rec[pr]]);
    return 0;
}







Peculiar apple-tree CodeForces - 931D 

https://cn.vjudge.net/problem/CodeForces-931D

求出每个深度有多少个节点并mod2，最后求和，得到答案


#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define max1 (500+10)
#define max2 (1000+10)
#define maxn (100000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL cout<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int head[maxn],to[maxn<<1],pre[maxn<<1],tot,dep[maxn];
int n;
void adde(int u,int v)
{
    to[++tot]=v,pre[tot]=head[u],head[u]=tot;
}
void dfs(int u,int f,int d)
{
    dep[d]++;
    for(int i=head[u];i;i=pre[i])
    {
        int v=to[i];if(v==f)continue;
        dfs(v,u,d+1);
    }
}
int main()
{
    RD1(n);for(int i=2;i<=n;i++)
    {
        int u;RD1(u);adde(i,u),adde(u,i); 
    }
    int ans=0;
    dfs(1,0,0);for(int i=0;i<=n;i++)ans+=dep[i]&1;
    cout<<ans;
    return 0;
}





	Minimum Diameter Tree


https://cn.vjudge.net/problem/CodeForces-1087D 


	思维题，一旦想到就很简单




	直径必经过两个叶子节点，中间路径上的边全部置0，将s均摊在所有叶子结点上就行了