xiaoh's Blog

Practise like you never won, Perform like you never lost!

USACO FEB 2020 参赛总结

发布于 2020-02-24 | 分类于 参赛总结 | 29分钟 | 5985字数

USACO FEB 2020 参赛总结(2020-2-21~2020-2-24)

2020-2-24 xiaoh

铜组Bronze

A-Triangles

题意

平面上给定nn个点(1≤n≤100,∣xi∣,∣yi∣≤1041\leq n\leq 100,|x_i|,|y_i|\leq 10^4),求满足三条边中两条边分别平行于xx轴和yy轴的三角形中面积最大的面积的22倍.

题解

注意到数据较小,因此考虑O(n3)O(n^3) 的枚举点,判断是否合法并更新答案.除了实现起来细节较多,且比较麻烦,没什么难点.计算面积时分类讨论比较麻烦,但是不难发现平行于xx轴的边的长度的两倍就是三个点两两横坐标差的绝对值之和,纵坐标同理,因此可以将这两个和乘起来除以44便是面积,用这种做法即可避免分类讨论,稍微的减小代码的复杂度.时间复杂度O(n3)O(n^3)

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=110;
int n;
struct node{
    int x,y;
}a[MAXN];
int ans=0;
bool isok(node x,node y,node z)
{
    int u=(x.x==y.x)+(y.x==z.x)+(z.x==x.x);
    int v=(x.y==y.y)+(y.y==z.y)+(z.y==x.y);
    return (u==1)&&(v==1);
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++) read(a[i].x),read(a[i].y);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++)
    if(i!=j&&j!=k&&i!=k&&isok(a[i],a[j],a[k]))
    ans=max(ans,(abs(a[i].x-a[j].x)+abs(a[j].x-a[k].x)+abs(a[k].x-a[i].x))*(abs(a[i].y-a[j].y)+abs(a[j].y-a[k].y)+abs(a[k].y-a[i].y))/4);
    write(ans),putchar('\n');
	return 0;
}

B-Mad Scientist

题意

给定两个仅含有M和HM和H字符串a,ba,b,两者的长度都为n(1≤n≤1000)n(1\leq n\leq 1000),每次可以选定一个区间,翻转这个区间内所有的M和HM和H(即M变H,H变MM变H,H变M),求最小的操作次数是bb串变成aa串.

题解

首先证明:对于一种满足条件的最小的操作序列,一定有一种操作方法使所有操作的区间不相交.证明方法很简单,对于任何两个重叠的区间,将两者的范围都减去重叠的部分,显然不影响最终的结果.不停地把相交的区间做这样的减法,就可以使所有区间不相交.
这样一来,问题就很简单了.我们只要扫一遍bb串,对于每一个连续的两者对应位置字母都不同的段,我们使用一次翻转即可.时间复杂度O(n)O(n).

Code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1010;
int n;
char a[MAXN],b[MAXN];
int ans=0;
int main()
{
    scanf("%d",&n);
    scanf("%s",a+1),scanf("%s",b+1);
    bool flag=0;
    for(int i=1;i<=n;i++)
    if(a[i]!=b[i]&&!flag) ans++,flag=1;
    else if(a[i]==b[i]&&flag) flag=0;
    printf("%d\n",ans);
	return 0;
}

C-Swapity Swap

注:此题的进阶版在Silver  A−Swapity  Swapity  SwapSilver\;A-Swapity\;Swapity\;Swap中有,笔者没有对此题更好的解法,所以请各位移步至SilverASilver A查看此题题解QAQ

银组Silver

A-Swapity Swapity Swap

题意

初始情况下有nn头牛(1≤n≤1051\leq n\leq 10^5),第ii头牛在ii号位置上.接下来有mm个操作(1≤m≤1001\leq m\leq 100),每个操作给定一个区间 [l,r][l,r],表示翻转这个区间的所有的牛(例如1,2,31,2,3反转后为3,2,13,2,1).然后给定一个kk(1≤k≤1091\leq k\leq 10^9),按顺序执行kk轮(注意:不是kk次)操作,求最后所有牛所构成的序列.

题解

首先,不难发现O(nm)的时间复杂度是可以被接受的.所以我们先暴力的处理出一轮mm次操作后的序列,不妨设其为aa.我们考虑建一张有向图,有nn个点和nn条边,第ii条边从ii指向aia_i.不难发现这张图是一个基环树森林,且为内向树森林(一棵树加一条边后会有一个环,我们称之为基环树,内向树就是不论从任何一个点出发都可以走到环中,且无法离开环的基环树,实在不懂自己度娘或画一画就懂了).且每延基环树的边走一步就代表一轮操作后这个数的位置.
我们知道,在树上我们可以利用LCA的倍增思想LCA的倍增思想来求走了kk步后到达的位置(如果你不会用倍增求LCALCA,请戳这里),那么我们会发现这个思路在基环树上依旧可行.所以我们利用倍增的思想,求出走了2t2^t步后到达的节点,然后就可以用nlog⁡kn\log k的时间预处理,并用 log⁡k\log k的时间内算出每个节点的位置,时间复杂度O(nm+nlog⁡k)O(nm+n\log k).
进阶&优化
可以考虑一下,当1≤m≤1061\leq m\leq 10^6时,此时O(nm)O(nm) 的复杂度计算一轮操作后的序列已经在时间上不能承受了.这个时候,我们可以考虑使用平衡树来维护区间反转,从而将O(nm)O(nm)的翻转预处理变成O(mlogn)O(mlogn)的处理,就可以过啦.由于代码量不小且仅仅是暴力的将两段代码在一起在此就不赘述了,如果不会平衡树维护区间反转请戳这里.

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=100010,LOGK=32;
int n,m,k;
int a[MAXN],b[MAXN];
struct node{
    int l,r;
}op[MAXN];
int f[MAXN][LOGK];
int main()
{
    read(n),read(m),read(k);
    for(int i=1;i<=n;i++) b[i]=i;
    for(int i=1;i<=m;i++) read(op[i].l),read(op[i].r),reverse(b+op[i].l,b+op[i].r+1);
    for(int i=1;i<=n;i++) f[i][0]=b[i];
    for(int j=1;j<=log2(k)+1;j++)
    for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
    for(int i=1;i<=n;i++)
	{
		int tmp=k,cur=i;
		for(int j=log2(k)+1;j>=0;j--)
		if(tmp>=(1<<j)) tmp-=(1<<j),cur=f[cur][j];
		a[i]=cur;
	}
	for(int i=1;i<=n;i++) write(a[i]),putchar('\n');
	return 0;
}

B-Triangles

题意

平面上给定nn个点(3≤n≤105,∣xi∣,∣yi∣≤1043\leq n\leq 10^5,|x_i|,|y_i|\leq 10^4),求所有满足三条边中一条边平行于xx轴,一条边平行于yy轴的三角形的面积和的22倍.

题解

对于一个点A(x0,y0)A(x_0,y_0),我们不妨将其定为直角顶点,那么需要找到与它横,纵坐标分别相同的两个点B(x0,y1)B(x_0,y_1) 和C(x1,y0)C(x_1,y_0),构成一个满足条件的三角形.那么假设所有与AA横坐标相同的点为 (x0,y1),(x0,y2),……,(x0,yp)(x_0,y_1),(x_0,y_2),……,(x_0,y_p),与其纵坐标相同的点为 (x1,y0),(x2,y0),……,(xq,y0)(x_1,y_0),(x_2,y_0),……,(x_q,y_0),那么以AA为直角顶点的所有三角形的面积和的22倍为

S=∑i=1p∣y0−yi∣×∑i=0q∣x0−xi∣.S=\sum_{i=1}^p|y_0-y_i|\times\sum_{i=0}^q|x_0-x_i|.

那么我们可以考虑使用一种数据结构来维护所有横坐标或纵坐标相同的点集,并且支持查询与一个值的绝对值之和.不难想到我们可以使用平衡树来进行维护.我这里使用fhq−Treapfhq-Treap来进行维护,并在树上多维护一个值:子树和.对于横坐标相同的点集,维护其纵坐标;反之则维护横坐标.对于一个与tt的绝对值的查询,我们将整棵树按照与tt进行权值分裂splitsplit成两颗,那么左边的子树(权值小的那棵)所有值拆开绝对值后都是负号,而右边那棵则都是正号,就可以拆掉绝对值,直接计算.具体地,设左子树的大小为mm,子树和为ll;右子树的大小为nn,子树和为rr,那么结果就为m×t−l+r−n×t=r−l+(m−n)×tm\times t-l+r-n\times t=r-l+(m-n)\times t.接下来的只需要用平衡树维护和查询即可.时间复杂度O(nlog⁡n)O(n\log n).

Code

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=100010,MAXL=10010;
int n;
int tot=0;
struct node{
    int l,r;
    long long val,sum;
    int sz,dat;
}f[MAXN*2];
inline void pushup(int p)
{
    f[p].sz=f[f[p].l].sz+f[f[p].r].sz+1;
    f[p].sum=f[f[p].l].sum+f[f[p].r].sum+f[p].val,f[p].sum%=mod;
}
void split(int p,int k,int &x,int &y)
{
    if(!p)
    {
        x=y=0;
        return;
    }
    if(f[p].val<=k)
    {
        x=p;
        split(f[p].r,k,f[p].r,y);
    }
    else
    {
        y=p;
        split(f[p].l,k,x,f[p].l);
    }
    pushup(p);
}
int merge(int a,int b)
{
    if(!a||!b) return a+b;
    if(f[a].dat<f[b].dat)
    {
        f[a].r=merge(f[a].r,b);
        pushup(a);
        return a;
    }
    else
    {
        f[b].l=merge(a,f[b].l);
        pushup(b);
        return b;
    }
}
inline int New(int val)
{
    tot++;
    f[tot].val=f[tot].sum=val,f[tot].dat=rand();
    f[tot].sz=1;
    return tot;
}
inline void insert(int &p,int val)
{
    int x,y;
    split(p,val,x,y);
    p=merge(merge(x,New(val)),y);
    return;
}
struct node2{
    long long x,y;
}a[MAXN];
int rtx[MAXL*2],rty[MAXL*2];
long long ans=0;
int main()
{
    read(n);
    for(int i=1;i<=n;i++)
    read(a[i].x),read(a[i].y),a[i].x+=MAXL,a[i].y+=MAXL;
    for(int i=1;i<=n;i++) insert(rtx[a[i].x],a[i].y),insert(rty[a[i].y],a[i].x);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        long long tmp=0;
        split(rtx[a[i].x],a[i].y,x,y);
        tmp=f[x].sz*a[i].y-f[x].sum+f[y].sum-f[y].sz*a[i].y;
        tmp%=mod;
        rtx[a[i].x]=merge(x,y);
        split(rty[a[i].y],a[i].x,x,y);
        tmp*=(f[x].sz*a[i].x-f[x].sum+f[y].sum-f[y].sz*a[i].x);
        tmp%=mod;
        rty[a[i].y]=merge(x,y);
        ans+=tmp,ans%=mod;
    }
    ans=(ans%mod+mod)%mod;
    write(ans),putchar('\n');
	return 0;
}

C-Clock Tree

题意

有一棵含有nn个节点的树(1≤n≤25001\leq n\leq 2500),每个节点上都有一个钟,第ii个钟指向的是aia_i的时间(1≤ai≤121\leq a_i\leq 12),你可以任选一个节点出发,每走到一个节点,就把那个节点的钟往后拨11个小时(从起点出发时除外).问你从哪些点出发能够使所有节点上的钟都指向1212.

题解

本题是一棵无根树,我们可以给它指定11作为它的根(注意此处,后面叙述中所有的深度都默认以11为根).不妨设did_i为第ii个节点的深度(其中d1=0d_1=0),以及fi,j为走了i步后第j个f_{i,j}为走了i步后第j个钟所指向的时间.那么我们考虑一下式子:

qi=∑j=1n(−1)djfi,j(mod12)q_i=\sum_{j=1}^n (-1)^{d_j}f_{i,j}\pmod {12}

即我们把所有的点按照深度的奇偶分成两类,将两类的时间相减并对1212取模.不难发现每一步都会从奇数深度的走向偶数深度的,所以q0=q1+1=q2=…q_0=q_1+1=q_2=\dots.而若要使所有钟都指向1212点,则此时必定会有一个qw=0q_w=0.所以只有当q0=0,1q_0=0,1时,从11出发才可能使某个qw=0q_w=0.接下来,可以证明若q0=0,1q_0=0,1,必定存在一种方法可以使所有钟指向1212.我们每次任意选择一个叶子kk,然后不停地重复1→k→11\to k\to 1,直到这个点的钟被拨到了1212点,然后删除这个叶子(即不再访问这个节点).所以当q0=0,1q_0=0,1时,节点11可行.那么发现对于所有深度为偶数的点,以这些点为根,qq的值都是不变的,所以所有度数为偶数的点都可行.那么接下来考虑度数为奇数的点,以这些点为根,则会发现所有的qi′=−qiq_i'=-q_i,所以当q0=−1,0q_0=-1,0时,选取深度为奇数的点可行.并在一起得出以下结论:
1.当q0=0q_0=0时,从所有点出发都可行;
2.当q0=1q_0=1时,从深度为偶数的点出发都可行;
3.当q0=−1q_0=-1时,从深度为奇数的点出发都可行;
4.否则都不可行.
复杂度很小,只有O(n)O(n),然鹅本题的数据水到连O(n2)O(n^2)都能轻松过去QAQ

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=2510;
int n;
int a[MAXN];
int tot=1;
int edge[MAXN*2],nxt[MAXN*2],hd[MAXN];
int odd,even;
int sum1,sum2;
inline void add_edge(int u,int v)
{
    edge[tot]=v,nxt[tot]=hd[u],hd[u]=tot++;
}
inline void dfs(int p,int dep,int fa)
{
    if(dep&1) odd++,sum1+=a[p];
    else even++,sum2+=a[p];
    for(int i=hd[p];i;i=nxt[i])
    if(edge[i]!=fa) dfs(edge[i],dep+1,p);
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        read(u),read(v);
        add_edge(u,v),add_edge(v,u);
    }
    dfs(1,0,-1);
    sum1%=12,sum2%=12;
    if(sum1==sum2) write(n),putchar('\n');
    else if((sum1+1)%12==sum2) write(even),putchar('\n');
    else if(sum1==(sum2+1)%12) write(odd),putchar('\n');
    else write(0),putchar('\n');
	return 0;
}

金组Gold

A-Timeline

题意

有nn个活动(1≤n≤1051\leq n\leq 10^5),发生在接下来的mm天(2≤m≤1092\leq m\leq 10^9).现在给定cc个限制条件(1≤c≤1051\leq c\leq 10^5),第ii个条件有三个参数 (a,b,x)(a,b,x),表示bb事件至少在aa时间xx天后发生.已知第ii件事至少在第sis_i天后发生.求满足上述条件的每件事发生的最早的日次.保证答案存在.

题解

记第ii件事发生的最早时间为tit_i.那么题意即为给定mm个不等式,每个不等式形如tb−ta≥xt_b-t_a\geq x.于是想到了差分约束系统.对于tb−ta≥xt_b-t_a\geq x,建一条从aa到bb,边权为cc的边.对于每个sis_i,我们新开一个00号点,建一条从00到ii,边权为 −si-s_i的边,跑最短路,最终答案取个符号即为最短时间.鉴于保证答案存在,即图中不存在负环,所以整张图是有向无环图.我们可以也跑DAGDAG上的DPDP来解决.笔者写的是SPFASPFA,复杂度是彻彻底底的的O(玄学)O(玄学).反正本题数据很水,只要不写Bellman−FordBellman-Ford应该都能过.

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=100010,MAXC=100010;
const int inf=1000000007;
int n,m,c;
int tot=1;
int edge[MAXC*2],nxt[MAXC*2],w[MAXC*2],hd[MAXN];
inline void add_edge(int u,int v,int c)
{
    edge[tot]=v,w[tot]=c,nxt[tot]=hd[u],hd[u]=tot++;
}
int s[MAXN];
int dis[MAXN];
queue<int> q;
bool book[MAXN];
inline void SPFA()
{
    for(int i=1;i<=n;i++) dis[i]=inf;
    q.push(n+1),book[n+1]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        book[x]=0;
        for(int i=hd[x];i;i=nxt[i])
        if(dis[edge[i]]>dis[x]+w[i])
        {
            dis[edge[i]]=dis[x]+w[i];
            if(!book[edge[i]]) book[edge[i]]=1,q.push(edge[i]);
        }
    }
}
int main()
{
    read(n),read(m),read(c);
    for(int i=1;i<=n;i++) read(s[i]),add_edge(n+1,i,-s[i]);
    for(int i=1;i<=c;i++)
    {
        int u,v,k;
        read(u),read(v),read(k);
        add_edge(u,v,-k);
    }
    SPFA();
    for(int i=1;i<=n;i++) write(-dis[i]),putchar('\n');
	return 0;
}

B-Help Yourself

题意

给定nn条线段(1≤n≤1051\leq n\leq 10^5),第ii条线段覆盖区间[li,ri][l_i,r_i],且所有线段的li与ril_i与r_i互不相等(即所有的li,ril_i,r_i构成一个11~2n2n的排列),我们可以从中选取任意多个线段构成一个子集(不能不选),求一个子集的复杂度为构成它的线段的联通区域的数量,求所有子集的复杂度之和对109+710^9+7取模的答案.

题解

显然,暴力枚举所有情况就算是天河二号也救不了你.所以考虑计算每一段的贡献.
首先,不难发现每存在一个连通区域ii,就会有一个kk,使区间 [k,k+1][k,k+1] 有线段覆盖,而区间 [k−1,k][k-1,k] 无线段覆盖.那么我们可以考虑枚举每一个连通区域的起始点.对于每一个线段 [l,r][l,r],它前面的 [l−1,l][l-1,l] 若被覆盖,则这个线段对总的答案没有贡献,否则强制断开区间 [l−1,l][l-1,l] 的所有线段(即不选取这些线段),其他的任意选择,这个线段对总的答案会有11的贡献.设区间 [l−1,l][l-1,l] 有tt个线段覆盖,则它对答案有 2n−1−k2^{n-1-k} 的贡献.先用前缀积计算出所有的22的指数幂,就可以用常数的时间算出所有的线段的贡献.而覆盖每一段小段区间[t,t+1][t,t+1]的线段数可以利用差分和前缀和用线性的时间算出来.所以时间复杂度O(n)O(n)

Code

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=100010;
int n;
struct node{
    int l,r;
}a[MAXN];
int f[MAXN*2];
long long p[MAXN];
long long ans=0;
int main()
{
    read(n);
    for(int i=1;i<=n;i++) read(a[i].l),read(a[i].r),f[a[i].l]++,f[a[i].r]--;
    p[0]=1;
    for(int i=1;i<=n;i++) p[i]=p[i-1]<<1,p[i]%=mod;
    for(int i=1;i<=2*n;i++) f[i]+=f[i-1];
    for(int i=1;i<=n;i++) ans+=p[n-1-f[a[i].l-1]],ans%=mod;
    write(ans),putchar('\n');
	return 0;
}

C-Delegation

题意

给定一棵有nn个节点的树(1≤n≤1051\leq n\leq 10^5),问对于i∈[1,n−1]i\in [1,n-1],是否存在一种方法,能够用一些长度为ii的链覆盖整棵树.

题解

考虑使用树形DP来求解该问题.首先,若 (n−1) mod k≠0(n-1) \bmod k\neq 0,则显然不能配对.接下来考虑能整除的情况.对于一棵子树来说,会有一些链覆盖住子树中的点,且至多有一条链未完全覆盖住整颗子树,且其一定覆盖住这棵子树的根.我们可以考虑深搜遍历整棵树,若无法覆盖子树,则也无法覆盖整棵树,返回false即可.否则把所有子树多出来的那半条链两两配对,配对成长度为kk的链,若剩余的链超过一条,则无法覆盖,否则返回那条链的长度即可.但是这样有一个小小的问题,就是你无法用 O(1)O(1) 的时间检查是否有多余的链.当然,O(log⁡n)O(\log n) 的有很多,例如dsu  on  treedsu\;on\;tree,或者用平衡树维护等,但是这样复杂度中会多出一个 log⁡\log,这样就会被时限卡掉.所以我们不能采用递归式的算法,所以我们考虑使用非递归式的树形DP.显然,对于一棵子树,若它的大小确定,那么它多出来的链的长度也一定确定(由于树是一棵无根树,所以在我们假定跟之后,他父亲所在的那一"向上"部分也算作一棵子树),为该子树的大小去对kk取模.我们对每一个节点的所有子树进行配对,若有任何一个无法配对的,那么就不行,否则若对于所有点的所有子树都配对成功,就是可以.时间复杂度O(n×(n的约数个数))O(n\times (n的约数个数)).

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=100010;
int n;
int tot=1;
int edge[MAXN*2],nxt[MAXN*2],hd[MAXN];
inline void add_edge(int u,int v)
{
    edge[tot]=v,nxt[tot]=hd[u],hd[u]=tot++;
}
int mp[MAXN];
inline void init()
{
    memset(mp,0,sizeof(mp));
}
struct node2{//此处储存每个儿子的子树大小
    int tot=1;
    int edge[MAXN*2],nxt[MAXN*2],hd[MAXN];
    inline void add_edge(int u,int v)
    {
        edge[tot]=v,nxt[tot]=hd[u],hd[u]=tot++;
    }
}g;
int sz[MAXN];
void prework(int p,int fa)
{
    sz[p]=1;
	for(int i=hd[p];i;i=nxt[i])
	if(edge[i]!=fa)
	{
		prework(edge[i],p);
		g.add_edge(p,sz[edge[i]]);
		sz[p]+=sz[edge[i]];
	}
	if(sz[p]!=n) g.add_edge(p,n-sz[p]);
}
inline bool check(int k)
{
	if((n-1)%k!=0) return 0;
	init();
	for(int i=1;i<=n;i++)
	{
		int cnt=0;
		for(int j=g.hd[i];j;j=g.nxt[j])
		{
			int x=g.edge[j]%k;
			if(x==0) continue;
			if(mp[k-x]) mp[k-x]--,cnt--;
			else mp[x]++,cnt++;
		}
		if(cnt) return 0;
	}
	return 1;
}
int main()
{
    read(n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        read(u),read(v);
        add_edge(u,v),add_edge(v,u);
    }
	prework(1,-1);
    for(int i=1;i<n;i++)
    {
        if(check(i)) write(1);
		else write(0);
    }
	putchar('\n');
	return 0;
}
  • 本文作者： xiaoh's Blog
  • 本文链接： USACO FEB 2020 参赛总结
  • 版权声明： 本博客所有文章除特别声明外，转载请注明出处！
# 参赛总结
洛谷 P3745 【六省联考2017】期末考试 题解 上一篇
ABC156 Summary 下一篇
© 2019-2020 HsxyHao
Powered by Gridea
0%