2026牛客暑期多校训练营6 2026-8-5

MIngYaaa520

39人浏览 · 2026-08-09 10:00:00

MIngYaaa520 · 2026-08-09 10:00:00 发布

赛时没看到F的时限给了10s，扩展kmp后打完二进制状态压缩的拓扑解后感觉时间复杂度暴了，想了半天点分治。。。

最后赛时5k,AJ待补，有时间更新

好多题要补呀（划掉）

图论签到题基础bfs变种，分别维护奇偶最小值，判断时注意k为偶数而维护值为奇数无解

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define cans cout<<ans<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define lc p<<1
#define rc p<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define sp(x) fixed<<setprecision(x)
#define all(v) v.begin(),v.end()
#define fr(i,st,ed) for(int i=st;i<=ed;i++)
#define ffr(i,st,ed,dt) for(int i=st;i<=ed;i+=dt)
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
typedef pair<string,string>Pss;
const int N=5e5+10,mod=1e9+7,M=1e6+10;
int lowbit(int x){
return x&(-x);}
vector<int>g[N];
int dis[N][2];//01
int n,m,k;
int Get(int d,int op){
if(d==inf)return inf;
if(k%2==0){
if(op==1)return inf;
int x=(d+k-1)/k;
return x*k;
}
else{
int x=(d+k-1)/k;
if((x&1)!=op)x++;
return x*k;
}
}
void init(int n){
fr(i,1,n){
g[i].clear();
dis[i][0]=dis[i][1]=inf;
}
}
void solve(){
cin>>n>>m>>k;
init(n);
fr(i,1,m){
int u,v;
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
}
queue<Pii>q;
dis[1][0]=0;
q.push({1,0});
while(!q.empty()){
auto [u,op]=q.front();
q.pop();
for(auto v:g[u]){
if(dis[v][op^1]>dis[u][op]+1){
dis[v][op^1]=dis[u][op]+1;
q.push({v,op^1});
}
}
}
for(int i=1;i<=n;i++){
int ans=min(Get(dis[i][0],0),Get(dis[i][1],1));
if(ans>inf/2)cout<<-1<<" ";
else cout<<ans<<" ";
}
cout<<"\n";
}
signed main(){
GG;
int _t=1;
cin>>_t;
while(_t--){
solve();
}
}

题目翻译一下就是给出若干字母在特定字母表排序方法下的大小对应关系，这个关系通过每个后缀和前缀相同的第一个字母给出

扩展kmp(Z函数）：寻找每个后缀与前缀的最长公共长度

然后根据这个关系拓扑即可

#include<bits/stdc++.h>
#define int long long
using u32=uint32_t;
using u64=uint64_t;
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define cans cout<<ans<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define lc p<<1
#define rc p<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define sp(x) fixed<<setprecision(x)
#define all(v) v.begin(),v.end()
#define fr(i,st,ed) for(int i=st;i<=ed;i++)
#define ffr(i,st,ed,dt) for(int i=st;i<=ed;i+=dt)
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
typedef pair<string,string>Pss;
const int N=2e4+10,mod=1LL<<32,M=1e6+10;
int lowbit(int x){
return x&(-x);}
u32 msk[26];
u32 ot[26];
u32 eg[26];
u32 C[30][30];
void init(){
C[0][0]=1;
fr(i,1,26){
C[i][0]=1;
fr(j,1,i)C[i][j]=(C[i-1][j]+C[i-1][j-1]);
}
}
u32 dfs(u32 Mask){
if(Mask==0)return 1;
vector<u32>v;
u32 r=Mask;
while(r){
u32 q=lowbit(r);
u32 now=0;
while(q){
u32 p=lowbit(q);
q^=p;
if(now&p)continue;
now|=p;
int id=__builtin_ctz(p);
q|=(eg[id]&Mask&(~now));
}
r&=~now;
v.pb(now);
}
if(v.size()>1){
u32 ans=1;
int sum=0;
for(auto x:v){
int siz=__builtin_popcount(x);
ans=(u32)((u64)ans*dfs(x));
ans=(u32)((u64)ans*C[sum+siz][siz]);
sum+=siz;
}
return ans;
}
int cnt=0,pos=-1;
u32 tmp=Mask;
while(tmp){
u32 p=lowbit(tmp);
tmp^=p;
int id=__builtin_ctz(p);
if((msk[id]&Mask)==0){
cnt++;
pos=id;
}
}
if(cnt==0)return 0;
if(cnt==1){
return dfs(Mask^(1u<<pos));
}
int id[26];
vector<int>node;
memset(id,-1,sizeof(id));
tmp=Mask;
while(tmp){
u32 p=lowbit(tmp);
tmp^=p;
int x=__builtin_ctz(p);
id[x]=node.size();
node.pb(x);
}
int siz=node.size();
vector<int>dp(1<<siz,0);
dp[0]=1;
vector<u32>pre(siz,0);
for(int i=0;i<siz;i++){
int x=node[i];
u32 p=msk[x]&Mask;
while(p){
u32 b=lowbit(p);
p^=b;
int y=__builtin_ctz(b);
pre[i]|=(1u<<id[y]);
}
}
u32 Max=(1u<<siz)-1;
for(u32 mk=0;mk<=Max;mk++){
if(dp[mk]==0)continue;
u32 rest=Max^mk;
while(rest){
u32 p=lowbit(rest);
rest^=p;
int x=__builtin_ctz(p);
if((pre[x]&mk)==pre[x]){
dp[mk|p]+=dp[mk];
}
}
}
return dp[Max];
}
void solve(){
string s;
cin>>s;
int n=s.size();
vector<int>z(n);
int l=0,r=0;
fr(i,1,n-1){
if(i<=r)z[i]=min(r-i+1,z[i-l]);
while(i+z[i]<n&&s[z[i]]==s[i+z[i]])z[i]++;
if(i+z[i]-1>r)l=i,r=i+z[i]-1;
}
//vector<int>msk(26,0);
fr(i,1,n-1){
if(z[i]==n-i){
cout<<0<<"\n";
return;
}
//msk[s[z[i]]-'a']|=1<<(s[i+z[i]]-'a');
msk[s[i+z[i]]-'a']|=1<<(s[z[i]]-'a');
ot[s[z[i]]-'a']|=1<<(s[i+z[i]]-'a');
}
fr(i,0,25){
eg[i]=msk[i]|ot[i];
}
int ans=0;

vector<int>dp(1<<26,0);
   dp[0]=1;
/*
   for (int i=0;i<(1<<26);i++) {
       for (int j=0;j<26;j++) {
           if (!(i>>j&1)&&((msk[j]&i)==msk[j])) {
               dp[i^(1<<j)]+=dp[i];
               dp[i^(1<<j)]%=mod;
           }
       }
   }
cout<<dp.back()<<"\n";
*/

for(int i=0;i<(1<<26);i++){
for(int j=i;j;j-=lowbit(j)){
int k=__builtin_ctz(j);
if((msk[k]&i)==msk[k]){
dp[i]+=dp[i^(1<<k)];
dp[i]%=mod;
}
}
}
cout<<dp.back()<<"\n";

// cout<<dfs((1u<<26)-1)<<"\n";
}
signed main(){
GG;
int _t=1;
init();
//cin>>_t;
while(_t--){
solve();
}

}
os:代码能看出作者的心路历程。。

蛮好玩的图论博弈题；

一个点必胜的条件是它的边上存在sp点或存在一条通向必胜的边

一条必胜边的条件是 u->v v在除去这条边后还存在>=2的相邻sp点或必胜边

定义一个dfs过程为对于一个点u，遍历与它相邻的所有点，假设从该点走向u,判断这条边是否为必胜边，是则标记并将该边加入搜索队列

读入并编号所有边，先对相邻sp点增加cnt,接着尝试搜索所有点，得到部分必胜边，再用必胜边更新cnt

由度数不大于3可知该方法正确

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define cans cout<<ans<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define lc p<<1
#define rc p<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define sp(x) fixed<<setprecision(x)
#define all(v) v.begin(),v.end()
#define fr(i,st,ed) for(int i=st;i<=ed;i++)
#define ffr(i,st,ed,dt) for(int i=st;i<=ed;i+=dt)
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
typedef pair<string,string>Pss;
const int N=2e5+10,mod=1e9+7,M=4e5+10;
int lowbit(int x){
return x&(-x);}
int fr[M],to[M],re[M],cnt[N];
bool st[M],sp[N];
vector<Pii>g[N];
queue<int>q,qe;
int n,m,k;
void dfs(int u){
if(sp[u])return;
for(auto [v,id]:g[u]){
if(st[re[id]])continue;
int f=sp[v]|st[id];
if(cnt[u]-f>=2){
st[re[id]]=1;
q.push(re[id]);
}
}
}
void init(int n,int m){
fr(i,1,n){
g[i].clear();
sp[i]=0;
cnt[i]=0;
}
fr(i,1,m<<1){
fr[i]=0;
to[i]=0;
re[i]=0;
st[i]=0;
}
q=qe;
}
void solve(){
cin>>n>>m>>k;
init(n,m);
int tot=0;
fr(i,1,m){
int u,v;
cin>>u>>v;
int id1=++tot;
int id2=++tot;
g[u].pb({v,id1});
g[v].pb({u,id2});
fr[id1]=u;
to[id1]=v;
fr[id2]=v;
to[id2]=u;
re[id1]=id2;
re[id2]=id1;
}
fr(i,1,k){
int x;
cin>>x;
sp[x]=1;
/*
for(Pii p:g[x]){
int v=p.x0;
cnt[v]++;
}
*/
}
fr(i,1,n){
for(auto [v,id]:g[i]){
if(sp[v])cnt[i]++;
}
}
fr(i,1,n){
if(!sp[i])dfs(i);
}
while(!q.empty()){
int id=q.front();
q.pop();
int u=fr[id];
int v=to[id];
cnt[u]++;
dfs(u);
}
vector<int>ans;
fr(i,1,n){
if(sp[i])continue;
bool f=0;
for(auto [v,id]:g[i]){
if(sp[v]||st[id]){
f=1;
break;
}
}
if(f)ans.pb(i);
}
cout<<ans.size()<<"\n";
for(int x:ans)cout<<x<<" ";
cout<<"\n";
}
signed main(){
GG;
int _t=1;
cin>>_t;
while(_t--){
solve();
}

}
H

签到

打个表即可

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define cans cout<<ans<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define lc p<<1
#define rc p<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define sp(x) fixed<<setprecision(x)
#define all(v) v.begin(),v.end()
#define fr(i,st,ed) for(int i=st;i<=ed;i++)
#define ffr(i,st,ed,dt) for(int i=st;i<=ed;i+=dt)
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
typedef pair<string,string>Pss;
const int N=2e5+10,mod=1e9+7,M=1e6+10;
int lowbit(int x){
return x&(-x);}
/*
bool Prm(int x){
if(x==1)return 0;
for(int i=2;i*i<=x;i++){
if(x%i==0)return 0;
}
return 1;
}
bool ok(const vector<int>&a,int n){
fr(i,0,n-1){
if(Prm(abs(a[i]-a[i%n+1])))return 0;
}
return 1;
}
*/
bool st[N];
int prime[N],cnt;
void init(){
st[0]=st[1]=1;
for(int i=2;i<N;i++){
if(!st[i])prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<N;j++){
st[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
void solve(){
/*
vector<int>a;
for(int i=1;i<=10;i++){
a.pb(i);
do {
if(ok(a,a.size())){
for(auto x:a)cout<<x<<" ";
cout<<"\n";
}
} while (next_permutation(a.begin(), a.end()));
}
*/
int n;
cin>>n;
if(n==3||n==4||n==6){
cout<<-1<<"\n";
return;
}
if(st[n-1]){
fr(i,1,n)cout<<i<<" ";
cout<<"\n";
return;
}
if(n==8){
cout<<"1 2 3 4 8 7 6 5\n";
return;
}
fr(i,1,n-4){
cout<<i<<" ";
}
cout<<n<<" "<<n-1<<" "<<n-2<<" "<<n-3<<"\n";
}
signed main(){
GG;
init();
int _t=1;
cin>>_t;
while(_t--){
solve();
}

}
I

数位dp,

一个小check是，加法的数位dp存在从低位到高位的情况（毕竟要向高位进位嘛）

维护一个Mask,记录当前位的 i 是否存在进位已经当前的 n-(i+d) 是否存在退位

它的意义是保证状态合法，最终的合法状态为0 0 即不存在进位/退位

我们假定fi=A,fi+d=B,在当前位i为x(0|1),i+d为y(0|1)

(A+x)*(B+y)=AB+A*y+B*x+x*y

维护每一种状态的 i的1总数 i+d的1总数状态数（i的1个数)*(i+d的1个数）

状态数的意义是每个可能会产生1贡献时，总贡献为1*状态数

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define cans cout<<ans<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define lc p<<1
#define rc p<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
#define sp(x) fixed<<setprecision(x)
#define all(v) v.begin(),v.end()
#define fr(i,st,ed) for(int i=st;i<=ed;i++)
#define ffr(i,st,ed,dt) for(int i=st;i<=ed;i+=dt)
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
typedef pair<string,string>Pss;
const int N=2e4+10,mod=998244353,M=1e6+10;
int lowbit(int x){
return x&(-x);}
struct Node{
int cnt,sx,sy,sxy;
};
void solve(){
int n,d;
cin>>n>>d;
Node dp[4],ndp[4];
memset(dp,0,sizeof(dp));
dp[0].cnt=1;
fr(i,0,60){
memset(ndp,0,sizeof(ndp));
int bitn=(n>>i)&1;
int bitd=(d>>i)&1;
fr(j,0,3){
int up=j&1;
int dow=(j>>1)&1;
Node cur=dp[j];
if(cur.cnt==0)continue;
int D=0,U=(i<60);
fr(x,D,U){
int y=(x+bitd+up)&1;
int nxty=(x+bitd+up)>>1;
int nxtn=((bitn-x-dow)<0);
int Nxt=(nxtn<<1)|nxty;
Node &nxt=ndp[Nxt];
nxt.cnt=(nxt.cnt+cur.cnt+mod)%mod;
nxt.sx=(nxt.sx+cur.sx+mod)%mod;
if(x)nxt.sx=(nxt.sx+cur.cnt+mod)%mod;
nxt.sy=(nxt.sy+cur.sy+mod)%mod;
if(y)nxt.sy=(nxt.sy+cur.cnt+mod)%mod;
nxt.sxy=(nxt.sxy+cur.sxy+mod)%mod;
if(x)nxt.sxy=(nxt.sxy+cur.sy+mod)%mod;
if(y)nxt.sxy=(nxt.sxy+cur.sx+mod)%mod;
if(x&y)nxt.sxy=(nxt.sxy+cur.cnt+mod)%mod;
}
}
//dp=ndp;
swap(dp,ndp);
}
//cout<<dp[0].cnt<<"\n";
cout<<dp[0].sxy<<"\n";
}
signed main(){
GG;
int _t=1;
cin>>_t;
while(_t--){
solve();
}

}

EazyDevelop社区

一站式 AI 云服务平台

更多推荐

没有AI项目经验，大学生还有必要考AI证书吗

EazyDevelop社区

零基础转行数字化，如何挑选高含金量 AI 证书？

EazyDevelop社区

多端商城怎么做？一套代码 vs 各端各写，4 个开源项目的实现路线对比

工程结构上，移动端是独立的 app/ 目录，PC 管理端是独立的 admin/（Vue + Element UI），后端 API 按管理端和前台端拆成两个服务：这个拆分对多端场景有实际意义：管理端 API 和 C 端 API 分离，意味着两边的鉴权、限流、发布节奏可以独立，C 端流量高峰不会影响后台操作。各端独立：改 3 个前端工程，3 次提测，3 次发版（小程序还要等审核）跨端框架：改 1 处，