Contest 8

时间:2022-04-04 03:33:31

  A:做法应该很多,比较好想的是每个点都往上倍增找到其能更新到的点。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 200010
int n,fa[N][],ans[][N];
struct data{int x,ch[];
}tree[N];
int whichson(int k){return tree[fa[k][]].ch[]==k;}
int main()
{
freopen("node.in","r",stdin);
freopen("node.out","w",stdout);
n=read();
for (int i=;i<=n;i++) tree[i].x=read();
for (int i=;i<=n;i++)
fa[tree[i].ch[]=read()][]=i,fa[tree[i].ch[]=read()][]=i;
fa[][]=;
for (int j=;j<;j++)
for (int i=;i<=n;i++)
fa[i][j]=fa[fa[i][j-]][j-];
for (int i=;i<=n;i++)
{
int k=tree[i].x,x=i;
for (int j=;~j;j--) if (k>(<<j)) x=fa[x][j],k-=(<<j);
ans[whichson(x)][fa[x][]]++;
}
for (int i=;i<=n;i++) printf("%d %d\n",ans[][i],ans[][i]);
return ;
}

  B:直接模拟即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define P 1000000007
int n,m,a,b,c,x,y,ansx,ansy;
long long f;
bool flag[];
void inc(int &x,int y){x+=y;if (x>=P) x-=P;}
int main()
{
freopen("schedule.in","r",stdin);
freopen("schedule.out","w",stdout);
n=read(),m=read(),a=read(),b=read(),c=read();
for (int i=;i<=m;i++)
{
f=(1ll*a*f+b)%(2ll*n*c);
if (f<1ll*n*c)
{
int t=f/c+;
if (!flag[t])
{
flag[t]=;
inc(x,),inc(y,t);
}
}
else
{
int t=f/c-n+;
if (flag[t])
{
flag[t]=;
inc(x,P-),inc(y,P-t);
}
}
inc(ansx,x),inc(ansy,y);
}
cout<<ansx<<' '<<ansy<<endl;
return ;
}

  C:考虑扩展最大独立集的做法:设f[i][j]为i子树中离i最近的被选点与i的距离至少为j时的最优解,转移时枚举与根最近的点在哪棵子树及与根的距离即可转移。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 10010
#define M 110
int n,m,a[N],p[N],f[N][M],t=;
struct data{int to,nxt;
}edge[N<<];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
void dfs(int k,int from)
{
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=from) dfs(edge[i].to,k);
for (int j=;j<=m;j++)
{
int tot=;
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=from) tot+=f[edge[i].to][max(j,m-j-)];
if (j==m) f[k][]=tot+a[k];
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=from) f[k][j+]=max(f[k][j+],f[edge[i].to][j]+tot-f[edge[i].to][max(j,m-j-)]);
}
for (int i=m;~i;i--)
f[k][i]=max(f[k][i+],f[k][i]);
}
int main()
{
freopen("score.in","r",stdin);
freopen("score.out","w",stdout);
n=read(),m=read();
for (int i=;i<=n;i++) a[i]=read();
for (int i=;i<n;i++)
{
int x=read(),y=read();
addedge(x,y),addedge(y,x);
}
dfs(,);
cout<<f[][];
return ;
}

  result:300 rank1