即可

即可

关注
发信
关注(28)粉丝(399)

Codeforces Global Round 2

　　A：答案一定包含首位或末位。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 300010

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,a[N];

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read();

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

	if (a[1]!=a[n]) cout<<n-1;

	else

	{

		int ans=0;

		for (int i=n;i>=1;i--) if (a[i]!=a[1]) ans=max(ans,i-1);

		for (int i=1;i<=n;i++) if (a[i]!=a[n]) ans=max(ans,n-i);

		cout<<ans;

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　B：二分答案，大的匹配大的即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 1010

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,h,a[N],b[N];

bool check(int k)

{

	for (int i=1;i<=k;i++) b[i]=a[i];

	sort(b+1,b+k+1);

	ll s=0;

	for (int i=k;i>0;i-=2) s+=b[i];

	return s<=h;

}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read(),h=read();

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

	int l=1,r=n,ans=1;

	while (l<=r)

	{

		int mid=l+r>>1;

		if (check(mid)) ans=mid,l=mid+1;

		else r=mid-1;

	}

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：显然将两矩阵xor一下后相当于将矩阵变为全0矩阵，大胆猜想要求每行每列都有偶数个1即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 510

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][N],b[N][N];

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

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

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

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

		a[i][j]=read();

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

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

		a[i][j]^=read();

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

	{

		int s=0;

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

		s^=a[i][j];

		if (s&1) {cout<<"NO";return 0;}

	}

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

	{

		int s=0;

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

		s^=a[j][i];

		if (s&1) {cout<<"NO";return 0;}

	}

	cout<<"YES";

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：显然询问的答案只与长度有关，离线按长度从小到大排序，相当于一个不断合并间隙的过程，将间隙长度排序记录已经有多少个被填满即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

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;

ll a[N],ans[N],d[N];

struct data

{

	ll k,i;

	bool operator <(const data&a) const

	{

		return k<a.k;

	}

}b[N];

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read();

	for (int i=1;i<=n;i++) scanf("%I64d",&a[i]);

	sort(a+1,a+n+1);

	for (int i=2;i<=n;i++) d[i]=a[i]-a[i-1];

	sort(d+2,d+n+1);

	q=read();

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

	{

		ll l,r;scanf("%I64d%I64d",&l,&r);

		b[i].k=r-l+1;b[i].i=i;

	}

	sort(b+1,b+q+1);

	int cnt=n,x=1;

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

	{

		ans[b[i].i]=ans[b[i-1].i];

		while (x<n&&d[x+1]<=b[i].k) ans[b[i].i]-=b[i-1].k,x++,cnt--,ans[b[i].i]+=d[x];

		ans[b[i].i]+=1ll*cnt*(b[i].k-b[i-1].k);

	}

	for (int i=1;i<=q;i++) printf("%I64d ",ans[i]);

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　E：显然三角形一定等腰且腰为最长边，瞎贪心，从小到大考虑边长，让其先尽量与之前的短边组成三角形，若有剩余则内部消化，最后留下的边留给更长的边匹配。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 300010

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,a[N];

ll ans,x=0;

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read();

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

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

	{

		if (a[i]>=x*2)

		{

			ans+=x,a[i]-=x*2,x=0;

			ans+=a[i]/3,x=a[i]%3;

		}

		else

		{

			ans+=a[i]/2,x-=a[i]/2,x+=a[i]%2;

		}

	}

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　F：考虑对于单次询问怎么做，显然有dpf[i][0/1]表示在i连向父亲的这条边是否切的情况下，i子树内所有点都满足条件的最小代价，转移将儿子按f[][0]-f[][1]排下序即可。注意到度数>=x的点的个数是O(n/x)的，所以对于所有询问，需要考虑的点的总数只有O(nlogn)个。但同时这些点还会与度数<x的点相连，这些边也可以提供贡献，这一部分可以用平衡树维护，dp时在平衡树上二分决定删除哪些边即可。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 250010

#define inf 10000000000000000ll

#define lson tree[k].ch[0]

#define rson tree[k].ch[1]

mt19937 rnd(20020509);

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],degree[N],root[N],id[N],t,cnt;

bool vis[N];

ll f[N][2],S[N],a[N];

struct data{int to,nxt,len;

}edge[N<<1];

struct data2{int ch[2],p,size,x;ll sum;

}tree[N<<1];

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

bool cmp(const int&a,const int&b)

{

	return degree[a]<degree[b];

}

ll query(int k,int x,int s)

{

	if (x==0) return 0;

	if (k==0) return x>s?inf:S[x];

	if (tree[lson].size>=x) return query(lson,x,s);

	if (x-tree[lson].size>s) return query(rson,x-tree[lson].size-1,s)+tree[lson].sum+tree[k].x;

	ll t=tree[lson].sum+tree[k].x+S[x-tree[lson].size-1];

	if (tree[k].x<=a[x-tree[lson].size]) return t=min(t,tree[lson].sum+tree[k].x+query(rson,x-tree[lson].size-1,s));

	else return t=min(t,query(lson,x,s));

	return t;

}

void up(int k)

{

	tree[k].size=tree[lson].size+tree[rson].size+1;

	tree[k].sum=tree[lson].sum+tree[rson].sum+tree[k].x;

}

void move(int &k,int p)

{

	int t=tree[k].ch[p];

	tree[k].ch[p]=tree[t].ch[!p],tree[t].ch[!p]=k,up(k),up(t),k=t;

}

void ins(int &k,int x)

{

	if (k==0) {k=++cnt;tree[k].p=rnd(),tree[k].size=1,tree[k].sum=tree[k].x=x;return;}

	if (tree[k].x<x) {ins(rson,x);if (tree[rson].p>tree[k].p) move(k,1);}

	else {ins(lson,x);if (tree[lson].p>tree[k].p) move(k,0);}

	up(k);

}

void dfs(int k,int from)

{

	vis[k]=1;int x=0;bool isroot=1;f[k][0]=f[k][1]=0;

	int last=0;

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

	if (degree[edge[i].to]>_)

	{

		if (!vis[edge[i].to]) dfs(edge[i].to,k),f[k][0]+=f[edge[i].to][1],f[k][1]+=f[edge[i].to][1];

		else f[k][0]+=edge[i].len,isroot=0;

		last=i;

	}

	else if (last) edge[last].nxt=edge[i].nxt;else p[k]=edge[i].nxt;

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

	if (degree[edge[i].to]>_&&edge[i].to!=from) a[++x]=f[edge[i].to][0]-f[edge[i].to][1];

	sort(a+1,a+x+1);

	for (int i=1;i<=x;i++) S[i]=S[i-1]+a[i];

	for (int i=x;i>=0;i--)

	if (a[i]<=0)

	{

		if (degree[k]-i<=_) f[k][1]+=S[i];

		else f[k][1]+=query(root[k],degree[k]-_,x);

		break;

	}

	if (!isroot)

	{

		for (int i=x;i>=0;i--)

		if (a[i]<=0)

		{

			if (degree[k]-1-i<=_) f[k][0]+=S[i];

			else f[k][0]+=query(root[k],degree[k]-1-_,x);

			break;

		}

	}

}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read();

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

	{

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

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

		degree[x]++,degree[y]++;

	}

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

	sort(id+1,id+n+1,cmp);

	int x=1;

	for (_=0;_<n;_++)

	{

		while (x<=n&&degree[id[x]]<=_)

		{

			for (int j=p[id[x]];j;j=edge[j].nxt)

			ins(root[edge[j].to],edge[j].len);

			x++;

		}

		for (int j=x;j<=n;j++) vis[id[j]]=0;

		ll ans=0;

		for (int j=x;j<=n;j++)

		if (!vis[id[j]])

		{

			dfs(id[j],id[j]);

			ans+=f[id[j]][1];

		}

		//for (int i=1;i<=n;i++) cout<<f[i][0]<<' '<<f[i][1]<<endl;

		printf("%I64d ",ans);

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　G、H：咕咕咕

　　小号打的。这种场真是不管打成什么样都能涨分。result：rank 310 rating +7

05-11 19:31
Powered by LMLPHP ©2024 即可 0.061784