Codeforces Round #483 Div. 1

2022-08-13 15:28:55

　　A：首先将p和q约分。容易发现相当于要求存在k满足b^k mod q=0，也即b包含q的所有质因子。当然不能直接分解质因数，考虑每次给q除掉gcd(b,q)，若能将q除至1则说明合法。但这个辣鸡题卡常，每求一次gcd都除干净就可以了。

#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;}

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

ll read()

{

	ll 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;

ll p,q,b;

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

	n=read();

	while (n--)

	{

		p=read(),q=read(),b=read();

		q/=gcd(p,q);

		ll u=gcd(b,q);

		while (u>1&&q>1)

		{

			while (q%u==0) q/=u;

			u=gcd(b,q);

		}

		if (q==1) puts("Finite");else puts("Infinite");

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　B：先考虑求出每个区间的f值。可以发现若区间长度为x，对于区间内第i个元素，其对最后答案是否产生贡献仅与C(x,i)是否为奇数有关。直接计算仍然是O(n³)的，由于C(i,j)=C(i-1,j-1)+C(i-1,j)，f值我们也可以类似地递推得到，即f[i][j]=f[i+1][j]^f[i][j-1]，考虑其中每个元素被计算的次数容易证明。然后再预处理正方形最大值，同样递推一下即可。于是就O(1)回答询问了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 5010

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

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

ll read()

{

	ll 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],f[N][N],ans[N][N];

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

	n=read();

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

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

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

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

		f[j][j+i-1]=f[j][j+i-2]^f[j+1][j+i-1];

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

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

		ans[j][j+i-1]=max(max(ans[j][j+i-2],ans[j+1][j+i-1]),f[j][j+i-1]);

	q=read();

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

	{

		int l=read(),r=read();

		printf("%d\n",ans[l][r]);

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：f[i][j][k]表示当前已经i个人进入过电梯，电梯在第j层，电梯内的人要到达的楼层状态为k，连边bfs即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<bitset>

#include<map>

using namespace std;

#define ll long long

#define N 10000010

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;

}

map<int,int> id;

int n,a[2010],b[2010],cnt;

bitset<2010> f[10000][10];

struct data{int d,cur,S,nxt,s;

}q[N];

void check(int &k)

{

	if (id.find(q[k].S)==id.end()) id[q[k].S]=++cnt;

	if (f[id[q[k].S]][q[k].cur][q[k].nxt]) {k--;return;}

	f[id[q[k].S]][q[k].cur][q[k].nxt]=1;

}

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

	n=read();

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

	int head=0,tail=1;

	q[1].d=0;q[1].cur=1;q[1].S=0;q[1].nxt=1;q[1].s=0;check(tail);

	do

	{

		data x=q[++head];if (x.S==0&&x.nxt>n) {cout<<x.d;return 0;}x.d++;

		if (x.cur>1) q[++tail]=x,q[tail].cur--,check(tail);

		if (x.cur<9) q[++tail]=x,q[tail].cur++,check(tail);

		int u=(x.S>>3*x.cur-3)&7;

		if (u) q[++tail]=x,q[tail].S=x.S^(u<<3*x.cur-3)^(u-1<<3*x.cur-3),q[tail].s--,check(tail);

		if (x.s<4&&a[x.nxt]==x.cur) u=(x.S>>3*b[x.nxt]-3)&7,q[++tail]=x,q[tail].S=x.S^(u<<3*b[x.nxt]-3)^(u+1<<3*b[x.nxt]-3),q[tail].s++,q[tail].nxt++,check(tail);

	}while (head<tail);

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　E：显然每次贪心的选择能坐的尽量久的公交车即可。考虑倍增，对每个点预处理向上坐2^k辆公交车能到的最高点。初始值通过子树查询得到。然后只需要考虑是否能通过某辆公交车跨越lca，这是一个矩形区域查询。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define N 200010

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][20],p[N],t,dfn[N],size[N],root[N],deep[N],reach[N][20],cnt,tot;

vector<int> a[N];

struct data{int to,nxt;

}edge[N<<1];

struct data2{int l,r,x;

}tree[N<<6];

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

void dfs(int k)

{

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

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

	{

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

		dfs(edge[i].to);

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

	}

}

int lca(int x,int y)

{

	if (deep[x]<deep[y]) swap(x,y);

	for (int j=19;~j;j--) if (deep[fa[x][j]]>=deep[y]) x=fa[x][j];

	if (x==y) return x;

	for (int j=19;~j;j--) if (fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];

	return fa[x][0];

}

void ins(int &k,int l,int r,int x)

{

	tree[++tot]=tree[k];k=tot;tree[k].x++;

	if (l==r) return;

	int mid=l+r>>1;

	if (x<=mid) ins(tree[k].l,l,mid,x);

	else ins(tree[k].r,mid+1,r,x);

}

void dfs2(int k)

{

	cnt++;root[cnt]=root[cnt-1];

	for (int i=0;i<a[k].size();i++) ins(root[cnt],1,n,dfn[a[k][i]]);

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

	{

		dfs2(edge[i].to);

		if (deep[reach[edge[i].to][0]]<deep[reach[k][0]]) reach[k][0]=reach[edge[i].to][0];

	}

}

int query(int x,int y,int l,int r,int p,int q)

{

	if (!y) return 0;

	if (l==p&&r==q) return tree[y].x-tree[x].x;

	int mid=l+r>>1;

	if (q<=mid) return query(tree[x].l,tree[y].l,l,mid,p,q);

	else if (p>mid) return query(tree[x].r,tree[y].r,mid+1,r,p,q);

	else return query(tree[x].l,tree[y].l,l,mid,p,mid)+query(tree[x].r,tree[y].r,mid+1,r,mid+1,q);

}

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

	n=read();

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

	{

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

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

	}

	fa[1][0]=1;dfs(1);

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

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

		fa[i][j]=fa[fa[i][j-1]][j-1];

	m=read();

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

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

	{

		int from=read(),to=read(),key=lca(from,to);

		if (deep[key]<deep[reach[from][0]]) reach[from][0]=key;

		if (deep[key]<deep[reach[to][0]]) reach[to][0]=key;

		a[from].push_back(to),a[to].push_back(from);

	}

	cnt=0;dfs2(1);

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

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

		reach[i][j]=reach[reach[i][j-1]][j-1];

	int q=read();

	while (q--)

	{

		int x=read(),y=read(),key=lca(x,y),ans=0;if (deep[x]<deep[y]) swap(x,y);

		for (int j=19;~j;j--) if (deep[reach[x][j]]>deep[key]) ans+=1<<j,x=reach[x][j];

		for (int j=19;~j;j--) if (deep[reach[y][j]]>deep[key]) ans+=1<<j,y=reach[y][j];

		if (deep[reach[x][0]]>deep[key]||deep[reach[y][0]]>deep[key]) {printf("-1\n");continue;}

		if (key==y||query(root[dfn[x]-1],root[dfn[x]+size[x]-1],1,n,dfn[y],dfn[y]+size[y]-1)) printf("%d\n",ans+1);

		else printf("%d\n",ans+2);

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D好像没看懂题解，自闭了。

码农公寓

相关文章