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均摊在所有叶子结点上就行了
京公网安备 11010502036488号