Codeforces Global Round 1 自闭记

时间：2022-04-28 07:04:21

　　A：签到。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll 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 b,k,a[100010];

signed main()

{

/*#ifndef ONLINE_JUDGE

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

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

	const char LL[]="%I64d\n";

#endif*/

	b=read(),k=read();b&=1;

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

	if (b==0)

	{

		if (a[k]&1) cout<<"odd";

		else cout<<"even";

	}

	else

	{

		int s=0;

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

		if (s&1) cout<<"odd";

		else cout<<"even";

	}

	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 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,m,k,a[N],b[N],ans;

signed main()

{

/*#ifndef ONLINE_JUDGE

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

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

	const char LL[]="%I64d\n";

#endif*/

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

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

	ans=a[n]-a[1]+1;

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

	sort(b+2,b+n+1);reverse(b+2,b+n+1);

	for (int i=2;i<=k;i++) ans-=b[i]-1;

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：当a!=2k-1时，令k为满足2k-1>a的最小正整数，显然可以令b=2k-1^a使答案成为2k-1，并且显然不可能更优。a=2k-1时直接暴力打表。

#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 q,ans[1<<25];

signed main()

{

/*#ifndef ONLINE_JUDGE

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

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

	const char LL[]="%I64d\n";

#endif*/

	q=read();

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

	{

		for (int j=1;j<(1<<i)-1;j++)

		ans[(1<<i)-1]=max(ans[(1<<i)-1],gcd((1<<i)-1&j,(1<<i)-1^j));

	}

	ans[(1<<23)-1]=178481;

	ans[(1<<24)-1]=5592405;

	ans[(1<<25)-1]=1082401;

	while (q--)

	{

		int x=read();

		if (ans[x]>0) printf("%d\n",ans[x]);

		else

		{

			while (x!=(x&-x)) x^=x&-x;

			printf("%d\n",(x<<1)-1);

		}

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　E：https://www.cnblogs.com/Gloid/p/10060025.html 作为一个做过所谓原题的选手看了1h这个题感到十分自闭。事实上第一眼就想到了这个原题，发现并不一样之后就去梦游了。毕竟当时也不是用前缀和的做法做的，而是自己想了半天搞了个做法还觉得挺nb，反应不过来也挺正常。但现在感觉我这做法好像也能类似的搬过来？自闭了啊？

　　比较差分集合是否相同即可，因为每次操作相当于交换差分数组中相邻两数。注意特判首尾。

#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[N<<4],head,tail,cnt;

ll a[N],b[N];

bool flag[N];

signed main()

{

/*#ifndef ONLINE_JUDGE

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

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

	const char LL[]="%I64d\n";

#endif*/

	n=read();

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

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

	if (a[1]!=b[1]||a[n]!=b[n]) {cout<<"No";return 0;}

	for (int i=n;i>=1;i--) a[i]-=a[i-1];

	for (int i=n;i>=1;i--) b[i]-=b[i-1];

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

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

	for (int i=1;i<=n;i++) if (a[i]!=b[i]) {cout<<"No";return 0;}

	cout<<"Yes";

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：注意到一定存在最优方案使得同种顺子最多出两次。然后就是普及组dp了。我这种弱智怎么可能注意的到啊。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#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,u,a[N],f[N][3][3];

signed main()

{

#ifndef ONLINE_JUDGE

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

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

	const char LL[]="%I64d\n";

#endif

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

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

	memset(f,200,sizeof(f));

	f[0][0][0]=0;

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

		for (int j=0;j<=2;j++)

			for (int k=0;k<=2;k++)

				for (int x=0;x<=2;x++)

				if (k<=a[i]&&j+k<=a[i-1]&&j+k+x<=a[i-2])

				f[i][j][k]=max(f[i][j][k],f[i-1][x][j]+x+(a[i-2]-j-k-x)/3);

	cout<<f[m+2][0][0];

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　F：对dfs序建线段树维护当前点到每个点的距离（非叶子设为inf），询问按dfs序离线，然后整棵树dfs一遍并维护距离即可，这个维护仅仅是线段树上的区间加和区间减。我觉得比D简单多了！算了云选手没资格说话。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define N 500010

#define inf 100000000000000000ll

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,fa[N],p[N],len[N],dfn[N],id[N],L[N<<2],R[N<<2],size[N],t,cnt,cur;

ll deep[N],ans[N],tree[N<<2],lazy[N<<2];

struct data

{

	int to,len;

	bool operator <(const data&a) const

	{

		return to<a.to;

	}

};

vector<data> edge[N];

struct data2

{

	int x,l,r,i;

	bool operator <(const data2&a) const

	{

		return dfn[x]<dfn[a.x];

	}

}q[N];

void addedge(int x,int y,int z){edge[x].push_back((data){y,z});}

void dfs(int k)

{

	dfn[k]=++cnt;id[cnt]=k;size[k]=1;

	for (int i=0;i<edge[k].size();i++)

	{

		deep[edge[k][i].to]=deep[k]+edge[k][i].len;

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

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

	}

	if (edge[k].size()) deep[k]=inf;

}

void up(int k){tree[k]=min(tree[k<<1],tree[k<<1|1]);}

void build(int k,int l,int r)

{

	L[k]=l,R[k]=r;

	if (l==r)

	{

		tree[k]=deep[id[l]];

		return;

	}

	int mid=l+r>>1;

	build(k<<1,l,mid);

	build(k<<1|1,mid+1,r);

	up(k);

}

void update(int k,ll x){tree[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)

{

	if (l>r) return;

	if (L[k]==l&&R[k]==r) {update(k,x);return;}

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

	int mid=L[k]+R[k]>>1;

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

	else if (l>mid) add(k<<1|1,l,r,x);

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

	up(k);

}

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

{

	if (L[k]==l&&R[k]==r) return tree[k];

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

	int mid=L[k]+R[k]>>1;

	if (r<=mid) return query(k<<1,l,r);

	else if (l>mid) return query(k<<1|1,l,r);

	else return min(query(k<<1,l,mid),query(k<<1|1,mid+1,r));

}

void work(int k)

{

	while (k==q[cur+1].x) cur++,ans[q[cur].i]=query(1,q[cur].l,q[cur].r);

	for (int i=0;i<edge[k].size();i++)

	{

		int to=edge[k][i].to;

		add(1,dfn[to],dfn[to]+size[to]-1,-edge[k][i].len);

		add(1,1,dfn[to]-1,edge[k][i].len);

		add(1,dfn[to]+size[to],n,edge[k][i].len);

		work(to);

		add(1,dfn[to],dfn[to]+size[to]-1,edge[k][i].len);

		add(1,1,dfn[to]-1,-edge[k][i].len);

		add(1,dfn[to]+size[to],n,-edge[k][i].len);

	}

}

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

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

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

	{

		fa[i]=read();len[i]=read();

		addedge(fa[i],i,len[i]);

	}

	for (int i=1;i<=n;i++) sort(edge[i].begin(),edge[i].end());

	dfs(1);

	for (int i=1;i<=m;i++) q[i].x=read(),q[i].l=read(),q[i].r=read(),q[i].i=i;

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

	build(1,1,n);

	work(1);

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

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　div1+div2的场从来没进过前400，自闭了。

　　result：rank 420 rating +22

相关文章