Codeforces Round #415 Div. 1

2023-08-23 13:29:52

　　A：考虑每对最大值最小值的贡献即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 300010

#define P 1000000007

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],p[N],x,ans;

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();

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

	p[0]=1;for (int i=1;i<=n;i++) p[i]=2ll*p[i-1]%P;

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

	{

		ans=(ans+1ll*a[i]*(p[i-1]-1))%P;

		x=(2ll*x+a[i-1])%P;

		ans=(ans-x+P)%P;

	}

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　B：考虑每次都询问x=i y=i+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 n,k;

char s[10];

bool ask(int x,int y)

{

	cout<<1<<' '<<x<<' '<<y<<endl;

	scanf("%s",s);

	return s[0]=='T';

}

bool check(int x)

{

	if (x<=0||x>n) return 0;

	if (x==1)

	{

		return ask(1,2);

	}

	if (x==n)

	{

		return ask(n,n-1);

	}

	if (ask(x,x-1)&&ask(x,x+1)) return 1;else return 0;

}

signed main()

{

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

	int x=0;

	if (ask(n,n-1)) x=n;

	else

	{

		int l=1,r=n-1;

		while (l<r)

		{

			int mid=l+r>>1;

			if (ask(mid,mid+1))

			{

				r=mid;

			}

			else

			{

				l=mid+1;

			}

		}

		x=l;

	}

	int l=1,r=x-1;

	while (l<r)

	{

		int mid=l+r>>1;

		if (ask(mid,mid+1)) r=mid;

		else l=mid+1;

	}

	if (check(l)&&x!=l) cout<<2<<' '<<l<<' '<<x<<endl;

	else

	{

		int l=x+1,r=n;

		while (l<r)

		{

			int mid=l+r>>1;

			if (ask(mid+1,mid)) l=mid+1;

			else r=mid;

		}

		if (check(x)&&x!=l) cout<<2<<' '<<x<<' '<<l<<endl;

		else

		{

			if (x>1) if (ask(x-1,x)) {cout<<2<<' '<<x-1<<' '<<x<<endl;return 0;}

			if (x<n) if (ask(x+1,x)) {cout<<2<<' '<<x<<' '<<x+1<<endl;return 0;}

		}

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：打表可以发现，对于2^k*2^k的矩阵，将其分成左上左下右上右下四部分，其中左上和右下相同，左下和右上相同，且左下是左上+2^k-1复制而来。于是直接记搜即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

#define ll long long

#define N 100010

#define P 1000000007

#define mp(x,y) make_pair((x),(y))

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;

}

typedef pair<int,int> pii;

struct data

{

	int x,y,k;

	bool operator <(const data&a) const

	{

		return x<a.x||x==a.x&&y<a.y||x==a.x&&y==a.y&&k<a.k;

	}

	bool operator ==(const data&a) const

	{

		return x==a.x&&y==a.y&&k==a.k;

	}

};

map<data,pii> f;

pii operator +(pii a,pii b)

{

	return mp((a.first+b.first)%P,(a.second+b.second)%P);

}

pii calc(int x,int y,int k)

{

	if (x==0||y==0||k<=0) return mp(0,0);

	if (x==1&&y==1) return mp(1,1);

	k=min(k,x+y-1);

	if (x>y) swap(x,y);

	data qwq=(data){x,y,k};

	if (f.find(qwq)!=f.end()) return f[qwq];

	int u=1;

	while ((u<<1)<y) u<<=1;

	pii ans;

	if (x<=u)

	{

		ans=calc(x,u,k);

		pii tmp=calc(x,y-u,k-u);

		ans=ans+tmp;ans.first=(ans.first+1ll*tmp.second*u)%P;

	}

	else

	{

		ans=calc(u,u,k);

		ans=ans+calc(x-u,y-u,k);

		pii tmp=calc(x-u,u,k-u);

		ans=ans+tmp;ans.first=(ans.first+1ll*tmp.second*u)%P;

		tmp=calc(u,y-u,k-u);

		ans=ans+tmp;ans.first=(ans.first+1ll*tmp.second*u)%P;

	}

	return f[qwq]=ans;

}

int bruteforce(int x1,int y1,int x2,int y2,int k)

{

	int ans=0;

	for (int i=x1;i<=x2;i++)

		for (int j=y1;j<=y2;j++)

		if ((i-1^j-1)+1<=k) ans=(ans+(i-1^j-1)+1)%P;

	return ans;

}

signed main()

{

	int q=read();

	while (q--)

	{

		int x1=read(),y1=read(),x2=read(),y2=read(),k=read();

		int ans=0;

		ans=(ans+calc(x2,y2,k).first)%P;

		ans=(ans-calc(x1-1,y2,k).first+P)%P;

		ans=(ans-calc(x2,y1-1,k).first+P)%P;

		ans=(ans+calc(x1-1,y1-1,k).first)%P;

		printf("%d\n",ans);

		//printf("%d\n",bruteforce(x1,y1,x2,y2,k));

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：搬上LIS的单调队列做法，设f[j]为前i位长度为j的单增序列的最后一位的最小值。考虑转移，显然f[j]=min(f[j],max(f[j-1]+1,l[i])) (f[j-1]<r[i])。注意到显然有f[j]<f[j+1]，所以不考虑l[i]限制的话，上述转移不需要取min，符合条件就可以直接赋值。那么二分找到l[i]和r[i]对应的边界，就相当于将区间平移并+1，然后区间内对l[i]取max。可以用splay维护。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

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

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

#define N 300010

#define inf 1000000001

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

struct data{int ch[2],fa,x,lazymax,lazyadd,s;

}tree[N<<1];

void up(int k){tree[k].s=tree[lson].s+tree[rson].s+1;}

void access(int k){while (k) up(k),k=tree[k].fa;}

int newnode(int v)

{

	int k=++cnt;

	tree[k].s=1;

	tree[k].x=v;

	return k;

}

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

{

	if (l>r) return;

	int mid=l+(r-l)/2;

	if (mid<=0) k=newnode(mid);

	else k=newnode(inf+mid);

	build(lson,l,mid-1);

	build(rson,mid+1,r);

	tree[lson].fa=tree[rson].fa=k;

	up(k);

}

int whichson(int k){return tree[tree[k].fa].ch[1]==k;}

void update(int k,int lazymax,int lazyadd)

{

	tree[k].x+=lazyadd;

	tree[k].x=max(tree[k].x,lazymax);

	tree[k].lazyadd+=lazyadd;

	tree[k].lazymax+=lazyadd;

	tree[k].lazymax=max(tree[k].lazymax,lazymax);

}

void down(int k)

{

	update(lson,tree[k].lazymax,tree[k].lazyadd);

	update(rson,tree[k].lazymax,tree[k].lazyadd);

	tree[k].lazymax=tree[k].lazyadd=0;

}

void push(int k){if (k!=root) push(tree[k].fa);down(k);}

void move(int k)

{

	int fa=tree[k].fa,gf=tree[fa].fa,p=whichson(k);

	if (fa!=root) tree[gf].ch[whichson(fa)]=k;tree[k].fa=gf;

	tree[fa].ch[p]=tree[k].ch[!p];tree[tree[k].ch[!p]].fa=fa;

	tree[k].ch[!p]=fa,tree[fa].fa=k;

	up(fa),up(k);

}

void splay(int k,int rt)

{

	push(k);

	while (tree[k].fa!=rt)

	{

		int fa=tree[k].fa;

		if (tree[fa].fa!=rt)

			if (whichson(fa)^whichson(k)) move(k);

			else move(fa);

		move(k);

	}

	if (rt==0) root=k;

}

int find(int k,int x)

{

	if (tree[lson].s-1==x) return k;

	if (tree[lson].s-1>x) return find(lson,x);

	else return find(rson,x-tree[lson].s-1);

}

int findsuf(int k,int x)

{

    if (k==0) return -2;

    down(k);

    if (tree[k].x<=x) return findsuf(rson,x);

    else

    {

        int t=findsuf(lson,x);

        if (t==-2) return k;

        else return t;

    }

}

int findpre(int k,int x)

{

    if (k==0) return -2;

    down(k);

    if (tree[k].x>=x) return findpre(lson,x);

    else

    {

        int t=findpre(rson,x);

        if (t==-2) return k;

        else return t;

    }

}

int getrank(int k)

{

    splay(k,0);

    return tree[lson].s-1;

}

int split(int l,int r)

{

	int p=find(root,l-1),q=find(root,r+1);

	splay(p,0);splay(q,p);

	return tree[q].ch[0];

}

void del(int x)

{

	int k=split(x,x);

	tree[tree[k].fa].ch[0]=0;

	access(tree[k].fa);

}

void ins(int x,int v)

{

	int k=split(x,x);

	lson=newnode(v);

	tree[lson].fa=k;

	access(lson);

}

int query(int x)

{

	return tree[split(x,x)].x;

}

void add(int l,int r)

{

	int k=split(l,r);

	update(k,0,1);

}

void getmax(int l,int r,int x)

{

	if (l>r) return;

	int k=split(l,r);

	update(k,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(),b[i]=read();

	build(root,-1,n+1);

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

	{

	    int l=getrank(findsuf(root,a[i]));

	    int r=getrank(findpre(root,b[i]))+1;

	    if (l>r) continue;

	    del(r);ins(l-1,query(l-1));add(l,r);getmax(l,r,a[i]);

	}

	for (int i=n;i>=1;i--) if (query(i)<inf) {cout<<i;break;}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　E：众所周知φ(nm)=φ(n)*φ(m)*gcd(n,m)/φ(gcd(n,m))，于是莫比乌斯反演一下，最后大约要求f(D)=Σdis(u,v)*φ(a_u)*φ(a_v) (D|a_u,a_v)。考虑点分，可以转化为对每个点u求g(D,u)=2deep_u*φ(a_u)*φ(a_v) (D|a_u,a_v)，每个点对所有因子加一下贡献即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define N 200010

#define P 1000000007

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

int prime[N],phi[N],mobius[N],inv[N],cnt;

int deep[N],size[N],val[N],f[N],ans;

bool flag[N];

vector<int> factor[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;}

inline void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

void make(int k,int from)

{

	size[k]=1;

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

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

	{

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

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

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

	}

}

int findroot(int k,int from,int s)

{

	int mx=0;

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

	if (!flag[edge[i].to]&&edge[i].to!=from&&size[edge[i].to]>size[mx]) mx=edge[i].to;

	if ((size[mx]<<1)>s) return findroot(mx,k,s);

	else return k;

}

void work(int k,int from,int op)

{

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

	if (op==1) inc(val[factor[a[k]][i]],phi[a[k]]);

	else inc(val[factor[a[k]][i]],P-phi[a[k]]);

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

	if (!flag[edge[i].to]&&edge[i].to!=from) work(edge[i].to,k,op);

}

void update(int k,int from)

{

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

	inc(f[factor[a[k]][i]],2ll*deep[k]*phi[a[k]]%P*val[factor[a[k]][i]]%P);

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

	if (!flag[edge[i].to]&&edge[i].to!=from) update(edge[i].to,k);

}

void solve(int k)

{

	make(k,k);

	k=findroot(k,k,size[k]);

	flag[k]=1;deep[k]=0;make(k,k);

	work(k,k,1);

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

	if (!flag[edge[i].to])

	{

		work(edge[i].to,edge[i].to,-1);

		update(edge[i].to,edge[i].to);

		work(edge[i].to,edge[i].to,1);

	}

	work(k,k,-1);

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

	if (!flag[edge[i].to]) solve(edge[i].to);

}

//f(D)=��2deepu*��(au)*��(av) (D|au,D|av)

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++)

	{

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

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

	}

	flag[1]=1;mobius[1]=phi[1]=1;

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

	{

		if (!flag[i]) prime[++cnt]=i,mobius[i]=-1,phi[i]=i-1;

		for (int j=1;j<=cnt&&prime[j]*i<=n;j++)

		{

			flag[prime[j]*i]=1;

			if (i%prime[j]==0) {phi[prime[j]*i]=phi[i]*prime[j];break;}

			mobius[prime[j]*i]=-mobius[i];

			phi[prime[j]*i]=phi[i]*(prime[j]-1);

		}

	}

	inv[1]=1;for (int i=2;i<=n;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;

	memset(flag,0,sizeof(flag));

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

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

		factor[j].push_back(i);

	solve(1);

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

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

		ans=(ans+1ll*f[j]*(P+mobius[j/i])%P*i%P*inv[phi[i]])%P;

	cout<<1ll*ans*inv[n]%P*inv[n-1]%P;

	return 0;

	//NOTICE LONG LONG!!!!!

}

码农公寓

相关文章