The 2021 CCPC Weihai Onsite A,D,J

A - Goodbye, Ziyin!

题意:

给定一个树的点数和边,问以每个点为根节点,有多少个树为二叉树

思路:

按照入度来算,但凡出现入度>=4的一定不能形成二叉树,入度<=2的拎起来之后可以作为根

int n,m,k,q[N];
void solve(){cin>>n;_for(i,n-1){cin>>k;q[k]++;cin>>k;q[k]++;}int res=0;_rep(i,1,n){if(q[i]<=2)res++;if(q[i]>=4){cout<<0;return ;}}cout<<res;
}

D - Period

题意:

给定一个字符串(仅小写),每次查询尝试把i号修改成‘#',问修改之后有多少个不同的周期

思路:

显然把一个字符变成'#'之后,这个字符串就算有周期,'#'也是处于第一个周期

比如“ccpc"变为“c#pc”之后只能以"c#p"为周期

下一步就可以发现,能形成周期的条件当且仅当前k个字符等于后k个字符(公共前后缀)

例如ABCDAB 以ABCD为一个周期,那么此时CD两个位置都可以容许变成"#"

然后手玩一下就可以发现,AAACDAAA这种样例,公共前后缀长度分别为1 2 3,那么‘#’

放在1号位,三种周期都用不了

放在2号位,可以用公共前后缀长度为1的周期

放在3号位,可以用公共前后缀长度为1，2的周期

放在4号位,可以用公共前后缀长度为1，2，3的周期

放在5号位,可以用公共前后缀长度为1，2，3的周期

放在6号位,可以用公共前后缀长度为1，2的周期

放在7号位,可以用公共前后缀长度为1的周期

放在8号位,三种周期都用不了

只需要观察当前'#‘不能使用哪些周期就可以计算出来当前可以容纳的不同周期数

#include<iostream>
#include<map>
#include<cmath>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#define pb push_back
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(),(x).end()
#define _for(i, a) for(int i = 0; i < (a); ++i) 
#define _rep(i, a, b) for(int i = (a);i <= (b); ++i)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define u1 (u<<1)
#define u2 (u<<1|1)
using namespace std;
typedef pair<int,int> PII;
const int INF=4e18;
const int P1 = 998244353,P2=13331;
const int N=1e6+20;
typedef unsigned long long ULL;
int n,m,k,q[N];
ULL h1[N], p1[N];
ULL h2[N], p2[N];
string s;
ULL get1(int l, int r)
{return h1[r] - h1[l - 1] * p1[r - l + 1];
}
ULL get2(int l, int r)
{return h2[r] - h2[l - 1] * p2[r - l + 1];
}
void init()
{p1[0] = 1;for (int i = 1; i <= n; i ++ ){h1[i] = h1[i - 1] * P1 + s[i];p1[i] = p1[i - 1] * P1;}p2[0] = 1;for (int i = 1; i <= n; i ++ ){h2[i] = h2[i - 1] * P2 + s[i];p2[i] = p2[i - 1] * P2;}
}
void solve(){cin>>s;n=s.size();s=" "+s;init();int res=INF;vector<int>v1,v2;_rep(i,1,n/2){if(get1(1,i)==get1(n-i+1,n)&&get2(1,i)==get2(n-i+1,n)){res=i;v1.pb(i);v2.pb(n-i+1);}}if(v2.size())reverse(all(v2));cin>>m;while(m--){int x;cin>>x;int a=lower_bound(all(v1),x)-v1.begin();//合法int b=v2.size()-(upper_bound(all(v2),x)-v2.begin());//非法cout<<min(a,b)<<'\n';}
}
signed main(){IOS;int T=1;_rep(i,1,T){solve();}return 0;
}