Codeforces Round #569 Div. 1

　　A：n-1次操作后最大值会被放到第一个，于是暴力模拟前n-1次，之后显然是循环的。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define inf 1000000010

#define N 300010

#define int long long

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,q,a[N],ans[N][2];

deque<int> Q;

signed main()

{

	n=read(),q=read();

	for (int i=1;i<=n;i++) a[i]=read();

	for (int i=1;i<=n;i++) Q.push_back(a[i]);

	for (int i=1;i<n;i++)

	{

		int x=Q.front();Q.pop_front();

		int y=Q.front();Q.pop_front();

		ans[i][0]=x,ans[i][1]=y;

		Q.push_front(max(x,y)),Q.push_back(min(x,y));

	}

	for (int i=1;i<=n;i++)

	{

		a[i]=Q.front(),Q.pop_front();

	}

	while (q--)

	{

		int x=read();

		if (x<n) printf("%I64d %I64d\n",ans[x][0],ans[x][1]);

		else printf("%I64d %I64d\n",a[1],a[(x-1)%(n-1)+2]);

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　B：考虑一维的构造，每次取两边端点即可。拓展到二维，对行仍然使用一维情况下的构造方法，当然端点需要交替重复几次以取遍所有点。对列的构造相当于这样一个问题：1~n每个数各给2个，找一个排列使得差分序列不存在相同的数。可以用类似的方法构造，即令前一半和后一半各取遍1~n，前一半与一维相同每次取两边端点，后一半为前一半的镜像。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define inf 1000000010

#define N 1000010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,a[N],b[N];

signed main()

{

	n=read(),m=read();

	int u=0;

	for (int i=1;i<=n/2;i++)

		for (int j=1;j<=2*m;j++)

		a[++u]=j&1?i:n-i+1;

	for (;u<=n*m;) a[++u]=n/2+1;

	u=0;

	for (int i=1;i<=n;i++)

	{

		int p=1;

		for (int j=1;j<=m;j++)

		{

			b[++u]=p;

			if (j&1) p=m-p+1;

			else p=m-p+2;

		}

	}

	for (int i=1;i<=n;i++)

	if (i%2==0) reverse(b+(i-1)*m+1,b+i*m+1);

	for (int i=1;i<=n*m;i++) printf("%d %d\n",a[i],b[i]);

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：容易想到顺序实际上无关紧要。考虑将所有菜的价格和每个人的财产放在数轴上，菜标+1人标-1，如果一道菜最后作为答案，那么显然只需要满足其是最后一个后缀和>0的菜。线段树维护最大后缀和并查询即可。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define inf 1000000010

#define N 300010

#define M 1000000

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,q,a[N],b[N],mx[M+10<<2],lazy[M+10<<2];

void up(int k)

{

	mx[k]=max(mx[k<<1],mx[k<<1|1]);

}

void update(int k,int x)

{

	mx[k]+=x;

	lazy[k]+=x;

}

void down(int k)

{

	update(k<<1,lazy[k]);

	update(k<<1|1,lazy[k]);

	lazy[k]=0;

}

void add(int k,int l,int r,int x,int y,int p)

{

	if (l==x&&r==y) {update(k,p);return;}

	if (lazy[k]) down(k);

	int mid=l+r>>1;

	if (y<=mid) add(k<<1,l,mid,x,y,p);

	else if (x>mid) add(k<<1|1,mid+1,r,x,y,p);

	else add(k<<1,l,mid,x,mid,p),add(k<<1|1,mid+1,r,mid+1,y,p);

	up(k);

}

int query(int k,int l,int r)

{

	if (l==r) return mx[k]>0?l:-1;

	if (lazy[k]) down(k);

	int mid=l+r>>1;

	if (mx[k<<1|1]>0) return query(k<<1|1,mid+1,r);

	else return query(k<<1,l,mid);

}

signed main()

{

	n=read(),m=read();

	for (int i=1;i<=n;i++) a[i]=read();

	for (int i=1;i<=m;i++) b[i]=read();

	for (int i=1;i<=n;i++) add(1,1,M,1,a[i],1);

	for (int i=1;i<=m;i++) add(1,1,M,1,b[i],-1);

	q=read();

	while (q--)

	{

		int op=read(),p=read(),x=read();

		if (op==1)

		{

			add(1,1,M,1,a[p],-1);

			a[p]=x;

			add(1,1,M,1,a[p],1);

		}

		else

		{

			add(1,1,M,1,b[p],1);

			b[p]=x;

			add(1,1,M,1,b[p],-1);

		}

		printf("%d\n",query(1,1,M));

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：稍作转化可以得到，相当于选择一条链，将链上边依次切开，最小化各部分大小的平方和。一个比较显然的dp是，设f[i]为只考虑i子树时，选择包含i的一条链，所能得到的最小平方和。暴力转移需要枚举链的两端各在哪个子树，显然菊花就退化了。但容易发现对于大小相同的子树，我们只需要取dp值最大和次大的，于是暴力的复杂度就显然不超过O(nsqrtn)了。

　　不过有一种并不会证的做法，即模仿两遍dfs求直径，随便钦定个端点找到能最优化答案的另一端点，所找到的端点就一定在答案所选的链中。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define inf 1000000010

#define N 500010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,p[N],size[N],t;

ll f[N];

struct data{int to,nxt;

}edge[N<<1];

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

void getsize(int k,int from)

{

	size[k]=1;

	for (int i=p[k];i;i=edge[i].nxt)

	if (edge[i].to!=from)

	{

		getsize(edge[i].to,k);

		size[k]+=size[edge[i].to];

	}

}

void dfs(int k,int from)

{

	for (int i=p[k];i;i=edge[i].nxt)

	if (edge[i].to!=from)

	{

		f[edge[i].to]=f[k]+1ll*(size[k]-size[edge[i].to])*size[edge[i].to];

		dfs(edge[i].to,k);

	}

}

signed main()

{

	n=read();

	for (int i=1;i<n;i++)

	{

		int x=read(),y=read();

		addedge(x,y),addedge(y,x);

	}

	getsize(1,1);

	f[1]=0;dfs(1,1);

	int root=0;for (int i=1;i<=n;i++) if (f[i]>f[root]) root=i;

	getsize(root,root);

	f[root]=0;dfs(root,root);

	ll ans=0;

	for (int i=1;i<=n;i++) ans=max(ans,f[i]);

	cout<<ans+1ll*n*(n-1)/2;;

	return 0;

	//NOTICE LONG LONG!!!!!

}

巴特西

Codeforces Round #569 Div. 1

最新文章

热门文章