Educational Codeforces Round 81

Link

VP 了这场,做出了 ABCDE。

Educational Codeforces Round 81

B 题罚时四次是因为没想清楚就开冲,十分不冷静,甚至有一次忘记删调试就交了(但它能过第一个样例所以算罚时(哭))。

E 题想了个巨复杂的做法,差点没写完,但实际上有简单很多的做法,VP 的时候好像有一个瞬间这个做法一闪而过,不知道为啥没去往下想。

A

最终答案一定形如 7111.. 或者 111...,对 \(n\) 的奇偶性讨论一下即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cstdlib>
#include<ctime>
#include<ctime>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline 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;
}
void sol()
{
    int n=read();
    if(n==2)puts("1");
    else if(n==3)puts("7");
    else{
        if(n%2)putchar('7');
        else putchar('1');
        for(int i=1;i<n/2;i++)putchar(49);
        puts("");
    }
}
int main()
{
    int T=read();
    while(T--)sol();
}

B

令 \(0\) 的权值为 \(+1\),\(1\) 的权值为 \(-1\),那么就是问这个长度为无穷大的字符串有多少个权值前缀和为 \(x\)。开个桶记一下 \(s\) 前缀和的值的出现次数,那么一个值 \(v\) 能有贡献当且仅当 \(x\equiv v\pmod sum\),\(sum\) 表示 \(s\) 的权值总和。需要特判 \(sum=0\) 的情况。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cstdlib>
#include<ctime>
#include<ctime>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline 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;
}
const int N=2e5+10;
char s[N];
int cnt[N<<1];
void sol()
{
    int n=read(),x=read();
    scanf("%s",s+1);
    for(int i=0;i<=n*2;i++)cnt[i]=0;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='1')sum--;
        else sum++;
        cnt[sum+n]++;
    }
    if(sum==0)
    {
        if(x+n>=0&&x+n<=2*n&&cnt[x+n])puts("-1");
        else puts("0");
    }
    else
    {
        int ans=0;
        if(!x)ans++;
        for(int i=-n;i<=n;i++)
        {
            if(x<=i&&sum<0&&(i%(-sum)-sum)%(-sum)==(x%(-sum)-sum)%(-sum))ans+=cnt[n+i];
            if(x>=i&&sum>0&&(i%sum+sum)%sum==(x%sum+sum)%sum)ans+=cnt[n+i];
        }
        printf("%d\n",ans);
    }
}
int main()
{
    int T=read();
    while(T--)sol();
}

C

对 \(s\) 建出子序列自动机,\(t\) 在子序列自动机上匹配,计算匹配轮数。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cstdlib>
#include<ctime>
#include<ctime>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline 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;
}
const int N=1e5+10;
int nxt[N][26],pos[26];
char s[N],t[N];
void sol()
{
    scanf("%s%s",s+1,t+1);
    int n=strlen(s+1),m=strlen(t+1);
    memset(pos,0,sizeof(pos));
    for(int i=n;i;i--)
    {
        for(int j=0;j<26;j++)
            nxt[i][j]=pos[j];
        pos[s[i]-'a']=i;
    }
    for(int j=0;j<26;j++)nxt[0][j]=pos[j];
    int ans=0;
    for(int i=1;i<=m;)
    {
        ans++;
        int pre=i;
        int j=0;
        while(1)
        {
            // printf("i=%d\n",i);
            if(nxt[j][t[i]-'a'])j=nxt[j][t[i]-'a'],i++;
            else {break;}
            if(i>m)break;
            // printf("j=%d\n",j);
        }
        if(pre==i)return puts("-1"),void();
    }
    printf("%d\n",ans);
}
int main()
{
    int T=read();
    while(T--)sol();
    return 0;
}

D

设 \(g=\gcd(a,m)\),那么 \(\gcd(\frac{a}{g}+\frac{x}{g},\frac{m}{g})=1\),那这大概就是一个和 \(\varphi\) 有关的东西,结合样例大胆猜想答案是 \(\varphi(\frac{m}{g})\),然后就过了。

证明并不困难,考虑到 \(0\le \frac xg<\frac mg\),那 \(\frac ag+\frac xg\) 一定会覆盖到模 \(\frac mg\) 意义下的所有值且每个值只覆盖一次。而根据辗转相除法 \(\gcd(\frac ag+\frac xg,\frac mg)=\gcd((\frac ag + \frac mg)\bmod \frac mg,\frac mg)\),也就是说上面要求的东西等价于 \(\sum_{i=0}^{\frac mg-1}[\gcd(i,\frac mg)=1]\),即 \(\varphi(\frac mg)\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cstdlib>
#include<ctime>
#include<ctime>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline 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 gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int phi(int n) 
{
    int ans=n;
    for(int i=2;i*i<=n;i++) 
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}
void sol()
{
    int a=read(),m=read();
    int g=gcd(a,m);
    printf("%lld\n",phi(m/g));
}
signed main()
{
    int T=read();
    while(T--)sol();
}

E

枚举最终左边集合的最大值 \(x\),考虑分界点 \(l\) 在哪里时 \(p_i\) 会产生代价。设 \(pos_i\) 表示数值 \(i\) 在排列中的位置,不难发现当 \(pos_i>l\) 且 \(i\le x\) 时或者 \(pos_i\le l\) 且 \(i>x\) 时会产生 \(a_i\) 的代价,线段树维护这个东西(详见代码),\(x\) 增加时单点修改,每次都取个全局 \(\min\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cstdlib>
#include<ctime>
#include<ctime>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline 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 gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int phi(int n) 
{
    int ans=n;
    for(int i=2;i*i<=n;i++) 
    {
        if(n%i==0)
	{
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}
void sol()
{
    int a=read(),m=read();
    int g=gcd(a,m);
    printf("%lld\n",phi(m/g));
}
signed main()
{
    int T=read();
    while(T--)sol();
}

F

基本上是从这里抄的

首先把期望转化为合法方案数除以总方案数。

把给定区间弄成左闭右开的,然后把端点离散化,设端点从小到大为 \(t_1,t_2,\cdots,t_m\),那么就有了 \(m-1\) 个区间 \([t_1,t_2),[t_2,t_3),\cdots,[t_{m-1},t_m)\)。设 \(f_{i,j}\) 表示考虑前 \(i\) 个数,第 \(i\) 个数放在第 \(j\) 个区间的方案数,枚举前面的区间放的数量 \(k\),有转移:

\[f_{i,j}=\sum_{k<i}\binom{t_{j+1}-t_j+i-k-1}{t_{j+1}-t_j-1}\sum_{s>j}f_{k,s} \]

其实就是个插板法。

答案就是:

\[\frac{\sum_{i=1}^{m-1} f_{n,i}}{\prod_{i=1}^n (r_i-l_i+1)} \]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
inline 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;
}
void write(int n)
{
	if(n<0){putchar('-');n=-n;}
	if(n>9)write(n/10);
	putchar(n%10^48);
}
const int N=110,mod=998244353;
int qpow(int a,int n)
{
	int ans=1;
	while(n){
		if(n&1)ans=1ll*a*ans%mod;
		a=1ll*a*a%mod;
		n>>=1;
	}
	return ans;
}
int binom(int n,int m)
{
	if(n<m)return 0;
	int ans=1;
	for(int i=1;i<=m;i++)ans=1ll*ans*qpow(i,mod-2)%mod*(n-i+1)%mod;
	return ans;
}
int f[N][N];
int l[N],r[N],t[N];
int main()
{
	int n=read(),m=0;
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=0;j<=i;j++)printf("%d ",binom(i,j));
//		puts("");
//	}
	for(int i=1;i<=n;i++)t[++m]=l[i]=read(),t[++m]=r[i]=read()+1;
//	for(int i=1;i<=n;i++)printf("[%d, %d)\n",l[i],r[i]);
	sort(t+1,t+m+1),m=unique(t+1,t+m+1)-t-1;
	for(int i=1;i<=n;i++)l[i]=lower_bound(t+1,t+m+1,l[i])-t,r[i]=lower_bound(t+1,t+m+1,r[i])-t;
//	for(int i=1;i<=m;i++)printf("t[%d]=%d\n",i,t[i]);
	f[0][m]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<m;j++)
		{
			for(int k=i-1;k>=0;k--)
			{
				if(l[k+1]>j||j>r[k+1]-1)break;
				int sum=0;
				for(int t=j+1;t<=m;t++)sum+=f[k][t],sum%=mod;
				f[i][j]+=binom(t[j+1]-t[j]+i-k-1,i-k)*1ll*sum%mod;
				f[i][j]%=mod;
			}
		}
	}
	int ans=0;
	for(int i=1;i<m;i++)ans+=f[n][i],ans%=mod;
	for(int i=1;i<=n;i++)ans=1ll*ans*qpow(t[r[i]]-t[l[i]],mod-2)%mod;
	printf("%d",ans);
	return 0;
}
上一篇:sequence


下一篇:《Java程序员面试笔试宝典》之Java与C/C++有什么异同