CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » wangzai_milk » educational_codeforces_round_94_rated_for_div._2_zars19
2020-2021:teams:wangzai_milk:educational_codeforces_round_94_rated_for_div._2_zars19

目录

A. String Similarity

间隔输出即可，达到的效果是对于第 $i$ 个 $n$ 长度子串对齐第 $i$ 个 $0/1$ 字符。

点击以显示 ⇲

点击以隐藏 ⇱ 

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=105;
char s[N];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d%s",&n,s);
		for(int i=0;i<2*n-1;i+=2)putchar(s[i]);
		puts("");
	}
	return 0;
}


B. RPG Protagonist

优先填充重量更小的武器，至于自己和跟从者各取多少可以枚举，然后另一种武器补满。

点击以显示 ⇲

点击以隐藏 ⇱ 

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		ll p,f,cnts,cntw,s,w,res=0;
		scanf("%lld%lld%lld%lld%lld%lld",&p,&f,&cnts,&cntw,&s,&w);
		if(s>w)swap(s,w),swap(cnts,cntw);
		for(int i=0;i<=cnts;i++)
		{
			if(i*s>p)break;
			ll cs=cnts,cw=cntw,pp=p,ff=f,ans=0;
			pp-=i*s,cs-=i,ans+=i;
			ll t1=min(cs,ff/s);
			ff-=t1*s,ans+=t1+min(pp/w+ff/w,cw);
			res=max(res,ans);
		}
		printf("%d\n",res);
	}
	return 0;
}


C. Binary String Reconstruction

相当于如果 $s_i$ 为 $1$ ， $w_{i-x}$ 和 $w_{i+x}$ 中至少一个为 $1$ ， $s_i$ 为 $ 0 $ ， $w_{i-x}$ 和 $w_{i+x}$ 均为 $ 0 $ 。贪心填一下就好

点击以显示 ⇲

点击以隐藏 ⇱ 

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=1e5+10;
char s[N],t[N];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(t,0,sizeof(t));
		scanf("%s",s);
		int n=strlen(s),f=1,x;
		scanf("%d",&x);
		for(int i=0;i<n;i++)
		if(s[i]=='0')
		{
			if(i-x>=0)t[i-x]='0';
			if(i+x<n)t[i+x]='0';
		}
		for(int i=0;i<n;i++)
		if(s[i]=='1')
		{
			if(i-x>=0&&t[i-x]!='0')t[i-x]='1';
			else if(i+x<n&&t[i+x]!='0')t[i+x]='1';
			else f=0;
		}
		if(!f)puts("-1");
		else
		{
			for(int i=0;i<n;i++)if(!t[i])t[i]='0';
			puts(t);
		}
	}
	return 0;
}


D. Zigzags

给定数组，统计满足 $1 \le i < j < k < l \le n,a_j = a_l,a_i = a_k$ 的四元组 $(i, j, k, l)$ 。

大概就是注释这样。

点击以显示 ⇲

点击以隐藏 ⇱ 

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=3005;
int a[N];
ll f[N][N];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;ll res=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)for(int j=n;j;j--)
		f[i][j]=f[i][j+1]+(a[i]==a[j]);				//大于等于j的位置有多少等于a[i]
		for(int j=1;j<=n;j++)
		for(int i=1;i<=n;i++)f[i][j]+=f[i-1][j];	//前缀和
		for(int i=1;i<=n;i++)
		for(int j=i+2;j<=n;j++)
		if(a[i]==a[j])res+=f[j-1][j+1]-f[i][j+1];	//大于j的位置等于a[i+1]...a[j-1]的
		printf("%lld\n",res);
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=0;
	}
	return 0;
}


E. Clear the Multiset

给定数组 $a_i$ ，每次操作可以把某个都不为零的区间全部减一或者把某个位置清零，问使得整个数组清零的最少操作次数。

两种操作的次序对结果无影响，那可以先做所有的区间减一操作，如果要做肯定要选值最小的 $a_k$ ，把所有值减去 $a_k$ ，递归的去做 $[l,k-1],[k+1,r]$ ，否则我们就只能把 $[l,r]$ 区间每个位置手动分别清零。 $O(n^2)$ 就可以过了，不过用RMQ等等可以做到更好。

点击以显示 ⇲

点击以隐藏 ⇱ 

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=5005;
int a[N];
int solve(int l,int r)
{
	if(l>r)return 0;
	int k=l,t=a[l];
	for(int i=l;i<=r;i++)if(a[i]<a[k])k=i,t=a[i];
	for(int i=l;i<=r;i++)a[i]-=t;
	return min(r-l+1,solve(l,k-1)+solve(k+1,r)+t);
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	printf("%d\n",solve(1,n));
	return 0;
}


F. x-prime Substrings

$x$ -prime其实非常的少可以先dfs出来放进ac自动机，然后简单dp一下停在自动机某节点不动删除字符要加一，否则转移向nxt[i]，作字符串结尾的节点要ban掉。

点击以显示 ⇲

点击以隐藏 ⇱ 

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=5005;
int x,sz,pre[N],w[N],q[N],dp[N][2];
char s[N];
struct Node{int nxt[10],vis,fail;}tr[N];
void insert()
{
	int p=0,i=1;
	while(w[i])
	{
		if(!tr[p].nxt[w[i]])tr[p].nxt[w[i]]=++sz;
		p=tr[p].nxt[w[i]],i++;
	}
	tr[p].vis=1;
}
void dfs(int d)
{
	if(pre[d-1]>x)return;
	if(pre[d-1]==x)
	{
		for(int i=1;i<d;i++)
		for(int j=i;j<d;j++)
		if(pre[j]-pre[i-1]!=x&&x%(pre[j]-pre[i-1])==0)return;
		w[d]=0,insert();return;
	}
	for(int i=1;i<10;i++)w[d]=i,pre[d]=pre[d-1]+i,dfs(d+1);
}
void build()
{
	int head=0,tail=-1;
	for(int i=1;i<10;i++)if(tr[0].nxt[i])q[++tail]=tr[0].nxt[i];
	while(head<=tail)
	{
		int p=q[head++];
		tr[p].vis|=tr[tr[p].fail].vis;
		for(int i=1;i<10;i++)
		if(!tr[p].nxt[i])tr[p].nxt[i]=tr[tr[p].fail].nxt[i];
		else tr[tr[p].nxt[i]].fail=tr[tr[p].fail].nxt[i],q[++tail]=tr[p].nxt[i];
	}
}
int main()
{
	scanf("%s%d",s,&x);
	dfs(1),build();
	dp[0][1]=0;for(int j=1;j<=sz;j++)dp[j][1]=N;
	for(int i=0,k=0;s[i];i++,k^=1)
	{
		for(int j=0;j<=sz;j++)dp[j][k]=N;
		for(int j=0;j<=sz;j++)
		{
			if(tr[j].vis)continue;
			dp[j][k]=min(dp[j][k],dp[j][k^1]+1);
			int p=tr[j].nxt[s[i]-'0'];
			if(!tr[p].vis)dp[p][k]=min(dp[p][k],dp[j][k^1]);
		}
		if(!s[i+1])
		{
			int res=N;
			for(int j=0;j<=sz;j++)res=min(res,dp[j][k]);
			printf("%d\n",res);
		}
	}
	return 0;
}


G. Mercenaries

$n$ 个雇佣兵， $m$ 条限制关系。只有满足总选择人数在 $[l_i,r_i]$ 间，雇佣兵 $i$ 被选择才是合法的。限制关系限制 $a_i,b_i$ 不能被同时选择。问可行的选择方案数。

考虑容斥，设 $a_i$ 为选择某 $i$ 条限制被固定打破时人数满足区间条件的方案数量的和，则答案是 $\sum\limits_{i=0}^m(-1)^ia_i$ 。

观察到 $m$ 比较小，限制关系是可以按位枚举的。当前选取某 $s$ 条限制违反，即每条限制中的 $a,b$ 必选，可以得到此时固定了 $cnt$ 个雇佣兵，而总人数一定在这些固定选取者的区间的并 $[L,R]$ 中。我们可以通过差分再前缀和得到人数为 $i$ 时满足区间条件的人数 $num_i$ 。则这个限制子集对答案的贡献为 $(-1)^s\sum\limits_{i=L}^R{num_i-cnt\choose i-cnt}$ ，而为了降低复杂度可以对每个 $cnt$ 做前缀和预处理（只有 $2m$ 个）。

点击以显示 ⇲

点击以隐藏 ⇱ 

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=3e5+10,M=25;
const ll mod=998244353;
ll num[N],fac[N],inv[N],res,pre[2*M][N];
int l[N],r[N],a[M],b[M],used[N];
void init()
{
    fac[0]=1,inv[1]=inv[0]=1;
    for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
    for(int i=2;i<N;i++)inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    for(int i=1;i<N;i++)inv[i]=inv[i-1]*inv[i]%mod;
}
ll C(int m,int n){return (m<n||n<0)?0:fac[m]*inv[n]%mod*inv[m-n]%mod;}
int main()
{
	int n,m;
	init(),scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]),num[l[i]]++,num[r[i]+1]--;
	for(int i=1;i<=n;i++)num[i]+=num[i-1];
	for(int i=1;i<=m;i++)scanf("%d%d",&a[i],&b[i]);
	for(int i=0;i<=2*m;i++)for(int j=1;j<=n;j++)
	pre[i][j]=(C(num[j]-i,j-i)+pre[i][j-1])%mod;
	for(int i=0;i<(1<<m);i++)
	{
		int x=i,j=1,cnt=0,L=1,R=n,sz=0;
		while(x)
		{
			if(x&1)
			{
				cnt+=(used[a[j]]==0)+(used[b[j]]==0),sz++;
				used[a[j]]=1,used[b[j]]=1;
				L=max(L,max(l[a[j]],l[b[j]])),R=min(R,min(r[a[j]],r[b[j]]));
			}
			x>>=1,j++;
		}
		for(int j=1;j<=2*m;j++)used[a[j]]=used[b[j]]=0;
		if(L>R)continue;
		ll t=(pre[cnt][R]-pre[cnt][L-1]+mod)%mod;
		if(sz&1)res=(res-t+mod)%mod;else res=(res+t)%mod;
	}
	printf("%lld\n",res);
	return 0;
}


2020-2021/teams/wangzai_milk/educational_codeforces_round_94_rated_for_div._2_zars19.txt · 最后更改: 2020/08/28 13:08 由 zars19

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3