2019牛客暑期多校训练营（第五场）（A、B、C题待补、E、F、G、H、I题待补）

于 2022-10-03 17:04:06 发布
阅读量455 收藏 1
点赞数 1
分类专栏： # 牛客多校 文章标签： 牛客多校 图论 思维题 BSGS 矩阵快速幂
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/Code92007/article/details/98122120
版权

心得

感觉下午还是很不稳吧，很多基础东西都不会或不熟

dreammoon出的题还是很有水平，便于巩固一些知识

自己通过

A digits 2(思维题)

T(T<=100)组样例，每次给出一个n(1<=n<=100)，

输出一个不超过1e4位的数，满足这个数能被n整除，且数位和能被n整除

像拼接字符串一样，输出n个n即可，数位和为n*sum(n)，

且这个数能整除n，商为10101……10101……的形式

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n;
int sum(int n)
{
	int ans=0;
	for(;n;n/=10)
	ans+=n%10;
	return ans;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;++i)
		printf("%d",n);
		puts("");
	}
	return 0;
}

H subsequence 2(拓扑排序)

给你小写字母的前m(2<=m<=10)个，每次取出两个，声明其C(m,2)种在原串中的位置

也就是原串中，只取出包含这两个字母的子序列(0<=|len|<=n)，子序列是什么样子的

问是否能在满足这些限制条件的情况下，将串还原为长度恰为n(1<=n<=1e4)的串，

若可以，输出原串

对每个子序列第几个出现的某一字母动态开点，在别的子序列中出现时就导向到其位置

这样对于每个字母，其位置都是唯一的，相邻字母之间前向后连边，拓扑排序，

无环且所有字母个数恰为n则有解，否则无解；

可以证明，由于给出了所有字母两两之间的关系，则若有解，则解唯一

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#define pb push_back
using namespace std;
const int N=1e6+10;
int n,m,cnt[26],now[26],len,tot,last,v;
int ch[N],ans[N],num;
vector<int>pos[26]; 
char s[N],t[3];
int p,q,ver,in[N];
vector<int>E[N];
bool vis[N];
void add(int u,int v)//u->v
{
	E[u].pb(v);
	in[v]++;
}
bool topo()
{
	queue<int>q;
	for(int i=1;i<=tot;++i)
	{
		if(in[i]==0)
		{
			q.push(i);
			vis[i]=1; 
		} 
	}
	while(!q.empty())
	{
		int t=q.front(); 
		q.pop();
		ans[num++]=ch[t];
		int len=E[t].size();
		for(int i=0;i<len;++i)
		{
			if((--in[E[t][i]])==0)
			{
				q.push(E[t][i]);
				vis[E[t][i]]=1;
			}
		}
	}
	for(int i=1;i<=tot;++i)
	if(!vis[i])return 0;
	return 1;
}
int main()
{
	for(int i=0;i<26;++i)
	{
		pos[i].pb(0);
	}
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m*(m-1)/2;++i)
	{
		scanf("%s%d",t,&len);
		if(len)scanf("%s",s);
		memset(now,0,sizeof now);
		last=0;
		for(int j=0;j<len;++j)
		{
			v=s[j]-'a';
			now[v]++;
			if(cnt[v]>=now[v])ver=pos[v][now[v]];
			else
			{
				pos[v].pb(++tot);
				ch[tot]=v;
				cnt[v]++;
				ver=pos[v][now[v]];
			}
			if(last)add(last,ver);
			last=ver;
		}
	}
	if(!topo())puts("-1");
	else
	{
		if(num!=n)puts("-1");
		else
		{
			for(int i=0;i<num;++i)
			putchar(ans[i]+'a');
			puts("");
		}
	}
	return 0;
}

队友通过

G subsequence 1(计数dp/子序列dp)

长度为n的字符串s和长度为m的字符串t，保证1<=m<=n<=3e3，且s和t的首字母不为'0'

求当成为十进制数字时，s的子序列代表的十进制数字比t代表的十进制数字大的个数，答案mod998244353

首先，如果s串比t串长且s串首字母不为0，那么一定比t大，组合数计算一下即可，

要统计的是，当s取s[i]为首字母时，后面的字母取不少于m位的方案数

再考虑s和t等长的情况，考虑s取的和t等长，该状态一定要从s取的和t-1等长的子状态转移

所以d[i][j]代表s中前i个字母选j个，和t中的前j个字母比较时，s大的方案数，

那这种情况，也有可能从前缀相等的情况转移而来，

所以e[i][j]代表s中前i个字母选j个，和t中的前j个字母比较时，完全相等的方案数

子序列dp，注意枚举j==1时的情况，这时子状态除了j-1外，单个字母也可新增一个状态

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int N=3e3+5;
int T,n,m,d[N][N],e[N][N];//d[i][j]s里前i个选j个比t里的前j个大 e[i][j]s里前i个选j个和t里的前j个相等 
int c[N][N],sum[N][N];//c[n][m],sum[n][m] n个里选m个,n个里选不少于m个 
int ans;
char s[N],t[N];
void add(int &x,int y)
{
	x=(x+y)%mod;
	if(x<0)x+=mod; 
}
int main()
{
	for(int i=1;i<N;++i)
	{
		c[i][0]=c[i][i]=1;
		for(int j=1;j<i;++j)
		add(c[i][j],c[i-1][j]+c[i-1][j-1]);
		for(int j=i;j>=0;--j)
		add(sum[i][j],sum[i][j+1]+c[i][j]);
	}
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		scanf("%s%s",s+1,t+1);
		for(int i=1;i<=n;++i)
		{
			memset(d[i],0,sizeof d[i]); 
			memset(e[i],0,sizeof e[i]);
		}
		for(int i=1;i<=n;++i)
		{
			d[i][1]=d[i-1][1];
			e[i][1]=e[i-1][1];
			if(s[i]>t[1])d[i][1]++;
			else if(s[i]==t[1]&&s[i]!='0')e[i][1]++;
			for(int j=2;j<=m;++j)
			{
				add(d[i][j],d[i-1][j]+d[i-1][j-1]);
				add(e[i][j],e[i-1][j]);
				if(s[i]>t[j])add(d[i][j],e[i-1][j-1]);
				else if(s[i]==t[j])add(e[i][j],e[i-1][j-1]);
			}
		} 	
		ans=d[n][m];
		for(int i=1;i<=n-m;++i)
		{
			if(s[i]!='0')//n-i个里至少取m个
			add(ans,sum[n-i][m]);
		}
		printf("%d\n",ans);
	}
	return 0;
}

I three points 1(平面几何)

补题

B generator 1(十进制矩阵快速幂or广义斐波那契数列循环节)

给定x0,x1,a,b(均<=1e9)，xn=a*xn-1+b*xn-2，为广义Fibonacci数列

求广义Fibonacci数列的第n(n<=1e(1e6))项%mod的值，mod在(1e9,2e9]之间

法一：变二进制矩阵快速幂为十进制矩阵快速幂，每一位进行一次快速幂

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 2;
const int N=1e6+10;
typedef long long ll;
int MOD;
char s[N];
ll x0,x1,a,b;
struct mat {
    ll c[MAXN][MAXN];
    int m, n;
    mat(){
    	memset(c, 0, sizeof(c));
    	m=n=MAXN;
    } 
    mat(int a, int b) : m(a), n(b) {
        memset(c, 0, sizeof(c));
    }
    void clear(){
		memset(c, 0, sizeof(c)); 
    }
    mat operator * (const mat& temp) {
        mat ans(m, temp.n);
        for (int i = 0; i < m; i ++)
            for (int j = 0; j < temp.n; j ++)
            {
                for (int k = 0; k < n; k ++)
                    ans.c[i][j] += c[i][k] * temp.c[k][j];
                ans.c[i][j]%=MOD;
            }
        return ans;
    }
    friend mat operator ^(mat M, int n) 
	{
   		 mat ans(M.m, M.m);
    	for (int i = 0; i < M.m; i ++)
        ans.c[i][i] = 1; 
   		 while (n > 0) {
        if (n & 1) ans = ans * M;
        M = M * M;
        n >>= 1;
    	}
    return ans;
	}
}bs,res;

int main()
{
	scanf("%lld%lld%lld%lld",&x0,&x1,&a,&b);
	scanf("%s%d",s,&MOD);
	bs.c[0][0]=a;bs.c[0][1]=b;
	bs.c[1][0]=1;
	res.c[0][0]=res.c[1][1]=1;
	int len=strlen(s);
	ll now=0;
	for(int i=len-1;i>=0;--i)
	{
		int v=s[i]-'0';
		res=res*(bs^v);//res*s[i]倍的基底 
		bs=bs^10;//基底扩大为原来10次方的基底 
	}
	printf("%lld\n",(res.c[1][0]*x1%MOD+res.c[1][1]*x0%MOD)%MOD); 
	return 0;
}

法二：求循环节，将1e(1e6)模循环节化为ll可表示的幂次，再进行快速幂

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 45000
typedef __int128 LL;
const int M=1e6+10;
LL f0,f1,a,b;
LL N,P;
LL prime[maxn];
LL fac[maxn];
char s[M];
inline __int128 read()
{
   long long X=0,w=0; char ch=0;
   while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
   while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
   return w?-X:X;
}
inline void print(__int128 x)
{  
   if(x<0){putchar('-');x=-x;}
   if(x>9) print(x/10);
   putchar(x%10+'0');
}
void Prime(){
    memset(prime,0,sizeof(prime));
    for(int i=2;i<maxn;i++){
        if(!prime[i]) prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&prime[j]<maxn/i;j++){
            prime[prime[j]*i]=1;
            if(i%prime[j]==0){
                break;
            }
        }
    }
}
LL factor[130][2];
int fatcnt;
int get_factors(LL n){
    fatcnt=0;
    LL tmp=n;
    for(int i=1;prime[i]<=tmp/prime[i];i++){
        factor[fatcnt][1]=0;
        if(tmp%prime[i]==0){
            factor[fatcnt][0]=prime[i];
            while(tmp%prime[i]==0){
                tmp/=prime[i];
                factor[fatcnt][1]++;
            }
            fatcnt++;
        }
    }
    if(tmp!=1){
        factor[fatcnt][0]=tmp;
        factor[fatcnt][1]=1;
        fatcnt++;
    }
    return fatcnt;
}
LL gcd(LL a,LL b){
    if(b==0){
        return a;
    }
    else{
        return gcd(b,a%b);
    }
}
LL lcm(LL a,LL b){
    return a/gcd(a,b)*b;
}
struct Matrix{
    LL m[2][2];
}E,D;
Matrix Multi(Matrix A,Matrix B,LL mod){
    Matrix ans;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            ans.m[i][j]=0;
            for(int k=0;k<2;k++){
                ans.m[i][j]+=(A.m[i][k]*B.m[k][j])%mod;
                if(ans.m[i][j]>=mod){
                    ans.m[i][j]-=mod;
                }
            }
        }
    }
    return ans;
}
void init(){
    memset(E.m,0,sizeof(E.m));
    memset(D.m,0,sizeof(D.m));
    D.m[0][0]=a;D.m[0][1]=b;
    D.m[1][0]=1;
    for(int i=0;i<2;i++){
        E.m[i][i]=1;
    }
    Prime();
}
Matrix Pow(Matrix A,LL e,LL mod){
    Matrix ans=E;
    while(e){
        if(e&1){
            ans=Multi(ans,A,mod);
        }
        A=Multi(A,A,mod);
        e>>=1;
    }
    return ans;
}
LL Pow(LL a,LL b,LL mod){
    LL ans=1;
    while(b){
        if(b&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
LL get_fib(LL n,LL mod)
{
    if(mod==1) return 0;
    if(n==0)return f0%mod;
    Matrix ans=Pow(D,n-1,mod);
    return (ans.m[0][0]*f1%mod+ans.m[0][1]*f0%mod)%mod;
}
LL find_loop(LL n)
{
    get_factors(n);
    LL ans=1;
    for(int i=0;i<fatcnt;i++)
    {
        LL record=(factor[i][0]+1)*(factor[i][0]-1);
        for(int j=1;j<factor[i][1];j++)
        record*=factor[i][0];
        //printf("record:");print(record);puts("");
        if(record)ans=ans*record;
    }
    //printf("ans:");print(ans);puts("");
    return ans;
}
int main()
{
        f0=read();//print(f0);puts("");
        f1=read();//print(f1);puts("");
        a=read();//print(a);puts("");
        b=read();//print(b);puts("");
        init();
        scanf("%s",s);
        P=read();
        LL mod2=find_loop(P);
        //printf("mod2:");print(mod2);puts("");
        int len=strlen(s);
        for(int i=0;i<len;++i)
        N=(N*10+(s[i]-'0'))%mod2;
        N=get_fib(N,P);
        print(N);
        puts("");
        return 0;
}
/*
1315 521 20185 5452831
999 1000000008
 */

E independent set 1(状压dp)

给你一张n(2<=n<=26)个点，m(0<=m<=n*(n-1)/2)条边的图，

每个图的贡献定义为这个图的最大独立集的点的个数，求该图的所有导出子图的贡献和

导出子图定义为，子图点是图中点的一部分，边只有在点都出现在子图的时候才保留在子图中

经典状压dp，然而几个月不做状压又不会了……

先处理出，每个点可以和哪些点放在一个图的集合，对有边的集合，取一下反即可

然后，考虑转移，放入最低位1的过程中，要么不放，要么只能放在和最后一个点构成独立集的集合中

__builtin_ffs(i)还是好用啊，卡空间，所以int改成char才能过

#include<bits/stdc++.h>
using namespace std;
int E[26];//记录能和哪些点放在一个独立集里
char dp[1<<26];
int n,m,u,v,mx,ans; 
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i)
	{
		scanf("%d%d",&u,&v);
		E[u]|=(1<<v);
		E[v]|=(1<<u);
	}
	mx=(1<<n)-1;
	for(int i=0;i<n;++i)
	E[i]=mx^(E[i]|(1<<i));
	for(int i=1;i<=mx;++i)
	{
		int pos=__builtin_ffs(i);//i从右起的第一个1是第几位 
		pos--;
		dp[i]=max(dp[i^(1<<pos)],(char)(dp[i&E[pos]]+1));
		ans+=dp[i];
	}
	printf("%d\n",ans);
	return 0;
}

F maximum clique 1(二分图最大独立集)

n(n<=5e3)个不同的数，第i个数为ai(1<=ai<=1e9)

找出最大的集合，使得这个集合内的元素两两之间，

在二进制表示下，都有至少两位不同

考虑如果至少两个二进制位不同，就连一条边，相当于找图中最大团

而如果建补图，相当于，找补图的最大独立集，且补图中如果二进制位恰有一位不同才会连边

而补图显然是一个二分图，二进制表示下，奇数个1，和偶数个1，分别是二分图的左边和右边

结论：二分图最大独立集=两边的点的个数和-二分图最小点覆盖

二分图最小点覆盖=最大匹配，故二分图最大独立集=两边的点的个数和-最大匹配

输出最大独立集方案，即相当于输出最小点覆盖方案的补集
 

#include <iostream>
#include <algorithm> 
#include <cstring>
#include <cstdio>
#include <map>
const int N=5e3+5; 
using namespace std;
map<int,int>mp;
int head[N],cnt;
int tot,n,m,cx[N],cy[N];
int a[N],b[N],v;
bool vis[N];
struct edge{int to,nex,w;}e[N*N];
void init()
{
	cnt=0;
	memset(head,-1,sizeof head);
}
void add(int u,int v)
{
	e[cnt].to=v;
	e[cnt].nex=head[u];
	head[u]=cnt++;
}
bool dfs(int u)
{
	vis[u]=1;
	for(int i=head[u];~i;i=e[i].nex)
	{
		int v=e[i].to;
		if(!vis[v])
		{
			vis[v]=1;
			if(cy[v-n]==-1||dfs(cy[v-n]))
			{
				cx[u]=v-n;
				cy[v-n]=u;
				return 1;
			}
		}
	}
	return 0;
}
int hungary()
{
	int res=0;
	memset(vis,0,sizeof vis);
	memset(cx,-1,sizeof cx);
	memset(cy,-1,sizeof cy);
	for(int u=1;u<=n;++u)
	{
		memset(vis,0,sizeof vis);
		res+=dfs(u);
	}
	return res;
} 
void MaxIndependentSet()
{
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;++i)
	if(cx[i]==-1)dfs(i);
	for(int i=1;i<=n;++i)
	if(vis[i])printf("%d ",a[i]);
	for(int i=n+1;i<=n+m;++i)
	if(!vis[i])printf("%d ",b[i-n]);
	puts("");
}
int main()
{ 
    init();
    scanf("%d",&tot);
    for(int i=1;i<=tot;++i)
    {
    	scanf("%d",&v);
    	int num=0,tmp=v;
    	for(;tmp;tmp>>=1)
		if(tmp&1)num++;
    	if(num&1)a[++n]=v;
    	else b[++m]=v;
    }
    for(int i=1;i<=m;++i)
	mp[b[i]]=n+i;//b[i]的实际点为n+i
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<32;++j)
		{
			if(mp.count(a[i]^(1<<j)))
			{
				add(i,mp[a[i]^(1<<j)]);
				//printf("%d->%d\n",a[i],a[i]^(1<<j));
			}
		}
	}
	printf("%d\n",n+m-hungary());
	MaxIndependentSet();
	return 0;
}

评论 1
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

小衣同学

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值