Educational Codeforces Round 62 Div. 2

2022-09-14 10:27:49

　　突然发现上一场edu忘记写了（

　　A：签到。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 10010

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],ans;

bool flag[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();

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

	{

		int x=a[i];

		ans++;

		while (i<x)

		{

			i++;

			x=max(x,a[i]);

		}

	}

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　B：显然仅当最左为>或最右为<时才能消去整个字符串。于是找到最左的>和最右的<取min即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 110

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 T,n;

char s[N];

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

	T=read();

	while (T--)

	{

		n=read();

		scanf("%s",s+1);

		int ans=n-1;

		int last=0;

		for (int i=n;i>=1;i--) if (s[i]=='<') {last=i;break;}

		ans=min(ans,n-last);

		int first=n;

		for (int i=1;i<=n;i++) if (s[i]=='>') {first=i;break;}

		ans=min(ans,first-1);

		cout<<ans<<endl;

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：枚举beauty最小值，则显然应该选择beauty不小于该数的前k大。堆维护。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

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,m;

struct data

{

	int x,y;

	bool operator <(const data&a) const

	{

		return y<a.y;

	}

}a[N];

priority_queue<int,vector<int>,greater<int> > q;

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

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

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

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

	ll tot=0,ans=0;

	for (int i=n;i>=1;i--)

	{

		q.push(a[i].x);tot+=a[i].x;

		if (n-i+1>m) tot-=q.top(),q.pop();

		ans=max(ans,tot*a[i].y);

	}

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：大胆猜想不用证明。即让1与所有相邻点配对。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

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

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

	n=read();

	int ans=0;

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

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　E：不存在奇回文串的充要条件是不存在长度为3的回文串。黑白染色（也就是奇偶分开考虑），则相当于相邻数不同。已确定的数将序列分割成若干区间，显然这些区间之间无关。然后随便dp一发。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define int long long

#define N 200010

#define P 998244353

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

int ksm(int a,int k)

{

	int s=1;

	for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;

	return s;

}

int calc(int *a,int n)

{

	int ans=1;

	bool flag=0;

	for (int i=1;i<=n;i++) if (a[i]!=-1) {flag=1;break;}

	if (!flag)

	{

		ans=m;for (int i=2;i<=n;i++) ans=1ll*ans*(m-1)%P;return ans;

	}

	int l=1,r=n;

	if (a[1]==-1)

	{

		while (a[l+1]==-1) l++;

		for (int i=1;i<=l;i++) ans=1ll*ans*(m-1)%P;

		l++;

	}

	if (a[n]==-1)

	{

		while (a[r-1]==-1) r--;

		for (int i=n;i>=r;i--) ans=1ll*ans*(m-1)%P;

		r--;

	}

	for (int i=l;i<=r;i++)

	{

		if (i==r) break;

		int t=i+1;

		while (a[t]==-1) t++;

		if (a[i]==a[t]) ans=1ll*ans*f[t-i]%P;

		else ans=1ll*ans*g[t-i]%P;

		i=t-1;

	}

	return ans;

}

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

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

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

	f[0]=1;for (int i=1;i<=n;i++) f[i]=(ksm(m-1,i-1)+P-f[i-1])%P;

	g[0]=0;for (int i=1;i<=n;i++) g[i]=(ksm(m-1,i-1)+P-g[i-1])%P;

	int u=0,v=0;

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

	if (i&1) b[++u]=a[i];

	else c[++v]=a[i];

	ans=1ll*calc(b,u)*calc(c,v)%P;

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　F：https://www.cnblogs.com/Gloid/p/9392532.html 用上这一场的D的结论（woc怎么看着这么羞耻），然后相当于动态图连通性问题，码了个线段树分治+带撤销并查集，得卡卡常。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<map>

#include<vector>

using namespace std;

#define ll long long

#define int long long

#define N 300010

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

#define left(x) (x)

#define right(x) ((x)+n)

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;

int n,t,fa[N<<1],lsize[N<<1],rsize[N<<1],L[N<<2],R[N<<2],lazy[N<<2];

ll ans,Q[N];

map<int,int> id[N];

vector<pii> edge[N<<2];

struct data{int x,y,z,l,r;

}a[N];

vector<data> stk[N<<2];

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

{

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

	if (l==r) return;

	int mid=l+r>>1;

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

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

}

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

{

	if (L[k]==l&&R[k]==r) {edge[k].push_back(mp(x,y));return;}

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

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

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

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

}

int find(int x){return fa[x]==x?x:find(fa[x]);}

ll calc(int x){return 1ll*lsize[x]*rsize[x];}

void solve(int k)

{

	lazy[k]=ans;

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

	{

		int x=edge[k][i].first,y=edge[k][i].second;

		int p=find(left(x)),q=find(right(y));

		if (p!=q)

		{

		ans-=calc(p);ans-=calc(q);

		if (lsize[p]+rsize[p]<rsize[p]+rsize[q]) swap(p,q);

		stk[k].push_back((data){q,p,fa[q],lsize[p],rsize[p]});

		fa[q]=p;lsize[p]+=lsize[q];rsize[p]+=rsize[q];

		ans+=calc(p);

		}

	}

	if (L[k]==R[k]) Q[L[k]]=ans;

	if (L[k]<R[k]) solve(k<<1),solve(k<<1|1);

	ans=lazy[k];

	for (int i=((int)stk[k].size())-1;i>=0;i--)

	{

		fa[stk[k][i].x]=stk[k][i].z;

		lsize[stk[k][i].y]=stk[k][i].l;

		rsize[stk[k][i].y]=stk[k][i].r;

	}

}

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

	n=read();

	for (int i=1;i<=n;i++) fa[left(i)]=left(i),fa[right(i)]=right(i),lsize[left(i)]=1,rsize[right(i)]=1;

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

	{

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

		if (id[x][y]==0)

		{

			id[x][y]=++t;

			a[t].x=x,a[t].y=y,a[t].l=i;

		}

		else

		{

			a[id[x][y]].r=i-1;

			id[x][y]=0;

		}

	}

	for (int i=1;i<=t;i++) if (a[i].r==0) a[i].r=n;

	build(1,1,n);

	for (int i=1;i<=t;i++) add(1,a[i].l,a[i].r,a[i].x,a[i].y);

	solve(1);

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

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　G：没补。

　　小小号的第一场。因为E一直wa非常自闭。result：rank 98 rating +214

码农公寓

相关文章