本场总结:
题目类型：
A.签到
B.广义斐波那契数列求第n项----十进制倍增
C.BSGS基础题 ---预处理打表
E.位元状压dp
F.二分图求解最大独立集
G.基础dp
H.拓扑排序
D.I.J 留坑暂时不填
小结:
----广义斐波那契 可以先找最小循环节加速，然后用十进制倍增取模
----学习了一下BSGS，对于多组询问可以先预处理a^i*m来降低复杂度. 学了 手写hash
----再次复习状压dp 哎,又是智商差距
----学习了一下二分图，这道题转换是在巧妙,最大团转化为二分图求最大独立集.---还有独立集元素求取方法
----基础dp就是补想法吧
----转化拓扑思想学一学.
A. digits 2
题目大意:t组，每组输入一个n，求构造一个数字x,x是n的倍数并且x的位数之和也是n的倍数.(n<10^400)
分析:显然我们输出n个n即可。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while( t-- )
{
int n;
cin>>n;
string s;
for( int i=1;i<=n;i++ )cout<<n;
cout<<endl;
}
}B. generator 1
题目大意:直接上图(题意显然)
分析:求广义斐波那契数列第n项,我们可以先处理出模数的循环节，然后对底数进行十进制位逐位取模，然后套用矩阵快速幂板子即可.
#include<bits/stdc++.h>
using namespace std;
struct node {
long long a[2][2];
};
const int maxn = 1e6 + 5;
int ans, pri[maxn];
void init()
{
long long limit;
for ( int i = 2; i <= 100000; i++ )
{
if (!pri[i])pri[ans++] = i;
for ( int j = 0; j < ans; j++ )
{
limit = 1ll * i * pri[j];
if (limit > 100000)break;
pri[limit] = 1;
if (i % pri[j] == 0)break;
}
}
}
long long getmod( long long n )
{
long long ans1 = 1, ans2 = 1,nn = n;
for (int i = 0; i < ans; i++)
{
if (pri[i] * pri[i] > n)break;
if (n%pri[i] == 0)
{
ans1 *= (pri[i] - 1) * (pri[i] + 1);
ans2 *= pri[i];
while (n%pri[i] == 0)n /= pri[i];
}
}
if ( n > 1 )
{
ans1 *= (n - 1) *(n + 1);
ans2 *= n;
}
return nn / ans2 * ans1;
}
node mul( node a, node b, long long mod )
{
node ans;
memset(ans.a, 0, sizeof(ans.a));
for ( int i = 0; i < 2; i++ )
{
for ( int j = 0; j < 2; j++ )
{
for ( int k = 0; k < 2; k++ )
{
ans.a[i][j] = (ans.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;
}
}
}
return ans;
}
node ksm( node a, long long b, long long mod )
{
node ans; // 单位矩阵
ans.a[0][0] = 1;ans.a[0][1] = 0;
ans.a[1][0] = 0;ans.a[1][1] = 1;
while ( b )
{
if (b & 1) ans = mul(ans, a, mod);
a = mul(a, a, mod);
b >>= 1;
}
return ans;
}
char s[maxn];
long long ksc( long long x, long long y, long long mod ) // 防止溢出
{
long long tmp = (x*y - (long long)((long double)x / mod * y + 1.0e-8)*mod);
return tmp < 0 ? tmp + mod : tmp;
}
int main() {
ios::sync_with_stdio(false);
long long x, y, a, b, mod, m, n;
node ans, aa;
cin >> x >> y >> a >> b >> s>>mod;
init();
m = getmod(mod); // 找最小循环节
n = 0;
int t = strlen(s);
for ( int i = 0; i < t; i++ )
{
n = ksc(n, 10, m);
n = n + s[i] - '0';
if (n >= m) n -= m;
}
aa.a[0][0] = a;aa.a[0][1] = 1;
aa.a[1][0] = b;aa.a[1][1] = 0;
ans = ksm(aa, n, mod);
printf("%lld\n", (ans.a[1][1] * x + ans.a[0][1] * y) % mod );
return 0;
}C. generator 2
题目大意:
分析:对该式子进行化简，会发现就是一个BFGS的基础题.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
const int HashMod=1999997;
inline ll read()
{
ll f=1,x=0;char s=getchar();
for( ;!isdigit(s);s=='-' && (f=-1),s=getchar());
for( ;isdigit(s);x=x*10+s-48,s=getchar());
return x*f;
}
ll qpow( ll a,ll b,ll mod )
{
ll ans=1;
while( b )
{
if( b&1 ) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
namespace BSGS
{
ll tt,m,lim;
struct HashTable // 手写hash
{
struct node{
ll u,v,next;
}e[1000005];
ll head[HashMod],cnt;
void add( ll u,ll v,ll w )
{
e[++cnt]=(node){ w,v,head[u] };
head[u]=cnt;
}
void Clear()
{
memset(head,0,sizeof(head));
cnt=0;
}
void Hash( ll x,ll k )
{
ll s=x%HashMod;
add(s,k,x);
}
ll query( ll x )
{
ll s=x%HashMod;
for( ll i=head[s];i;i=e[i].next )
{
if( e[i].u==x ) return e[i].v;
}
return -1;
}
}Hash;
void init( ll y,ll p )
{
m=(ll)pow(p,2.0/3);Hash.Clear(); // 适当更改块的大小和Hash的块的大小
tt=qpow( qpow(y,m,p),p-2,p); // 1/a^m
lim=p/m+1;
Hash.Hash(1,0);
ll t=1;
for( int i=1;i<m;i++ )
{
t=t*y%p;
if( Hash.query(t)==-1 ) Hash.Hash(t,i);
}
}
ll cal( ll b,ll p )
{
if( b==1 ) return 0;
for( int i=0;i<lim;i++ )
{
int k=Hash.query(b);
if( k!=-1 ) return 1ll*i*m+k;
b=tt*b%p;
}
return -1;
}
}
ll n;
// a ^ n = ( a - 1 ) * v + b / ( ( a - 1 ) * x0 + b )
void print( ll x )
{
printf("%lld\n", x<n ? x : -1 );
}
void solve()
{
ll x0,a,b,p,q,v;
n=read();x0=read();a=read();b=read();p=read();
q=read();
if( a==0 ) //如果a=0，看v与x0和b的值
{
while( q-- )
{
v=read();
if( v==x0 ) print(0);
else if( v==b ) print(1);
else print(-1);
}
return;
}
else if( a==1 ) //如果a=1，分b=0和b!=0两种情况讨论
{
if( b==0 )
{
while( q-- )
{
v=read();
if( v==x0 ) print(0);
else print(-1);
}
}
else
{
while( q-- ) // x0 + n*b = v ---> n=( v - x0 )/ b
{
v=read();
v=(v-x0+p)%p*qpow(b,p-2,p)%p;
print(v);
}
}
return;
}
ll inv=( (a-1)*x0+b )%p;
if( inv==0 ) //左边为 0，如果右边也为 0则是 0，否则是-1
{
while( q-- )
{
while( q-- )
{
v=read();
if( ( (a-1)*v+b )%p==0 ) print(0);
else print(-1);
}
}
return;
}
inv=qpow(inv,p-2,p);
BSGS::init(a,p); // 预处理a^(m*t1)
while( q-- )
{
v=read();
if( v==x0 ) print(0);
else
{
ll res=( (a-1)%p*v%p+b )%p*inv%p; // a^n=((a-1)*v+b)/((a-1)*x0+b) 设res=((a-1)*v+b)/((a-1)*x0+b)
ll ans=BSGS::cal(res,p);
print(ans);
}
}
}
int main()
{
int t;
t=read();
while( t-- ) solve();
return 0;
}E. independent set 1
题目大意:n个点,m条边,求所有点集的最大独立点集之和. ( n<26 , m<n*(n-1)/2 )
最大独立点集的定义:给定点集中，选取最多的点(满足两个互异的点不相连)构成的点集，集合元素个数即为值.
分析:显然我们必须枚举所有的点集,去求对应的最大独立点集. 用位元状压dp.注意:这题有个坑点，内存限制只能用char类型.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1<<26;
int val[27];
char dp[maxn];
char max( char a,char b ){ return a > b ? a : b; }
int main()
{
int n,m;
cin>>n>>m;
for( int i=1;i<=m;i++ )
{
int a,b;cin>>a>>b;
val[a]|=(1<<b);
val[b]|=(1<<a);
}
for( int i=0;i<n;i++ )
{
val[i]|=(1<<i);
val[i]=~val[i];
}
ll ans=0;
for( int i=1;i<(1<<n);i++ )
{
int pos;
for( int j=0;j<26;j++ )
{
if( i>>j & 1 )
{
pos=j;
break;
}
}
dp[i]=max( dp[i^(1<<pos)],dp[ ( i & val[pos] ) ]+1 );
ans+=dp[i];
}
cout<<ans<<endl;
}F.maximum clique 1
题目大意:给一个集合(大小5e3),由于是集合,所以每个元素都不同，求一个最大子集合使得子集合内每两个点最少有2个二进制bit位不同
分析：对于集合内每对bit位最少2个不同的,在两点之间连一条边,于是题目就变成了在图论中求一个最大团,但是最大团不是NPC问题么，只能指数级别算呀，这可不行。于是可以看这个边有什么性质,图里的边要满足bit差异至少有2个,那么由于元素不同,它反过来就是bit位差异为1,那么补图的某一边存在当且仅当bit差异为1,相当于就是求补图的最大独立集，再想想，bit差异为1？？？？,那岂不是可以根据二进制中1的个数划分为二分图,求二分图的最大独立集.
如何求二分图的最大独立集: 点数 - 二分图最大匹配数 ( 证明自己琢磨 )
我们规定 二进制中1个数为偶数的 数集合为二分图的一边，我们从这个集合入手( 另一边情况算法相同).
- 先跑一遍二分图匹配，会有不相关的点和失配点 不会被匹配.
- 再用失配点和不相关的点跑一遍二分图匹配，就可以得二进制中1个数为偶数的 数集合的最大独立集，然后再加上非匹配 二进制中1个数为奇数结点，即为答案
#include<bits/stdc++.h>
using namespace std;
const int maxn=5002;
int p[maxn];
bool vis[maxn],jud[maxn],used[maxn];
int master[maxn];
vector<int>g[maxn];
bool check( int x,int y )
{
return __builtin_popcount(p[x]^p[y])==1 ;
}
bool find( int x )
{
vis[x]=1;
for( auto v:g[x] )
{
if( used[v] ) continue;
used[v]=1;
if( !master[v] || find(master[v]) )
{
master[v]=x;
return 1;
}
}
return 0;
}
int main()
{
int n;
scanf("%d",&n);
for( int i=1;i<=n;i++ ) scanf("%d",&p[i]);
for( int i=1;i<=n;i++ )
{
for( int j=i+1;j<=n;j++ )
{
if( check(i,j) )
{
g[i].push_back(j);
g[j].push_back(i);
}
}
}
for( int i=1;i<=n;i++ )
{
memset(used,0,sizeof(used));
if( __builtin_parity(p[i])==1 ) //规定 二进制下1的个数为偶数的数 进行 二分图匹配
{
if( find(i) ) jud[i]=1; // 该点可以匹配
}
}
memset(used,0,sizeof(used));
memset(vis,0,sizeof(vis));
for( int i=1;i<=n;i++ )
{
if( __builtin_parity(p[i])==1 && !jud[i] ) // 失配元素 匹配
{
find(i);
}
}
vector<int> ans;
for( int i=1;i<=n;i++ )
{
if( __builtin_parity(p[i])==1 && vis[i] ) ans.push_back(p[i]);
if( __builtin_parity(p[i])==0 && !used[i] ) ans.push_back(p[i]);
}
cout<<ans.size()<<endl;
for( auto v:ans ) cout<<v<<" ";
return 0;
}G. subsequence 1
题目大意：给定t组样例，每组样例输入n,m,字符串s,t(都由数字构成).求s中的子序列构成的数字大于t的方案数.
分析:此题两个解法.
解法一: (题解方法)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e3+10;
const int mod=998244353;
char s[maxn],t[maxn];
ll C[maxn][maxn],dp[maxn][maxn];
void init()
{
for( int i=0;i<maxn;i++ ) C[i][0]=C[i][i]=1;
for( int i=2;i<maxn;i++ )
{
for( int j=1;j<i;j++ ) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
}
int main()
{
init();
int T,n,m;
cin>>T;
while( T-- )
{
cin>>n>>m;
cin>>(s+1);
cin>>(t+1);
ll ans=0;
for( int i=1;i<=n-m;i++ )
{
if( s[i]!='0' )
{
for( int j=m;j+i<=n;j++ ) ans=(ans+C[n-i][j])%mod;
}
}
for( int i=1;i<=m;i++ ) // t 的 i个后缀
{
for( int j=i;j<=n;j++ ) // s 的 j 个后缀
{
if( t[m-i+1]==s[n-j+1] ) dp[i][j]=( dp[i-1][j-1]+dp[i][j-1] )%mod;
if( t[m-i+1]<s[n-j+1] ) dp[i][j]=( C[j-1][i-1]+dp[i][j-1] )%mod;
if( t[m-i+1]>s[n-j+1] ) dp[i][j]=dp[i][j-1];
}
}
// for( int i=1;i<=m;i++ )
// {
// for( int j=1;j<=n;j++ ) printf("(%d)(%d) -%d- ",i,j,dp[i][j]);cout<<endl;
// }
ans=(ans+dp[m][n])%mod;
cout<<ans<<endl;
}
}解法二:我们要找的序列的长度分两种，一种大于t的长度，一种等于t的长度.大于t的长度的序列贡献可以用组合数求得.
等于t的长度的序列贡献,分为两种,一个是前i个字符与t对应相同,一个是第一个字符就大于t[0]两种贡献,用个g[]维护即可.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e3+10;
const int mod=998244353;
char s[maxn],t[maxn];
ll g[maxn],f[maxn][maxn]; // g 维护 前i位相同的 方案数
void init() // 组合数打表
{
for( int i=0;i<maxn;i++ ) f[i][0]=f[i][i]=1;
for( int i=2;i<maxn;i++ )
{
for( int j=1;j<i;j++ ) f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
}
}
int main()
{
init();
int T,n,m;
cin>>T;
while( T-- )
{
cin>>n>>m;
cin>>(s+1);
cin>>(t+1);
g[0]=1;
for( int i=1;i<=m;i++ ) g[i]=0;
ll ans=0;
for( int i=1;i<=n;i++ )
{
if( s[i]!='0' ) //求 以 s[i]为首字符 len>len(t) 贡献
{
for( int j=m;j<=n-i;j++ ) ans=(ans+f[n-i][j])%mod;
}
for( int j=1;j<=min(i,m);j++ ) // 前j-1位相等 第j位为 i len=len(t) 的贡献
{
if( s[i]>t[j] ) ans=(ans+f[n-i][m-j]*g[j-1])%mod;
}
for( int j=min(i,m);j;j-- ) // 更新g数组
{
if( s[i]==t[j] ) g[j]=(g[j]+g[j-1])%mod;
}
}
cout<<ans<<endl;
}
}H. subsequence 2
**题目大意:https://ac.nowcoder.com/acm/contest/885/H 自行读题叭
分析:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
vector<int> g[maxn];
int d[maxn];
char str[maxn];
char num[maxn];
int ch[12][maxn];
int idd[maxn]; //编号 对应 字符
int cnt;
int get_id( int id,int num ) // 获取当前 第num个字符 的 编号
{
if( ch[id][num]==0 )
{
ch[id][num]=++cnt;
idd[cnt]=id;
}
return ch[id][num];
}
int main()
{
int n,m;
cin>>n>>m;
for( int i=1;i<=m*(m-1)/2;i++ )
{
char s[3];
int len;
cin>>s>>len;
if( len )
{
cin>>str;
int num1=0,num2=0;
int pre=-1;
for( int j=0;j<len;j++ )
{
int id;
if( str[j]==s[0] )
{
id=get_id(str[j]-'a',num1);
num1++;
}
else
{
id=get_id(str[j]-'a',num2);
num2++;
}
if( pre!=-1 ) // 相邻字符建边
{
d[id]++;
g[pre].push_back(id);
}
pre=id;
}
}
}
if( cnt!=n )
{
puts("-1");
return 0;
}
queue<int> que;
vector<int> ans;
for( int i=1;i<=n;i++ ) if( d[i]==0 ) que.push(i); // 拓扑排序
while( !que.empty() )
{
int u=que.front();que.pop();
ans.push_back(u);
for( auto v:g[u] )
{
d[v]--;
if( d[v]==0 ) que.push(v);
}
}
if( ans.size()!=n )
{
puts("-1");
return 0;
}
for( auto v:ans ) putchar( 'a'+idd[v] );
}
京公网安备 11010502036488号