CSP-S模拟30
垃圾场
A. 灯若辰星 (light)
打表题。
题意就是求第一类、第二类斯特林数 \(\mod 2\) 意义下的值。
Code：
#include<bits/stdc++.h>
#define int long long using namespace std;const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar() \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt) \? EOF \: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{int x=0,c=getchar(),f=0;for(;c>'9'||c<'0';f=c=='-',c=getchar());for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);return f?-x:x;
}
inline void write(int x)
{if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar(x%10+'0');
}int q;
int op,n,m;inline int f(int n,int m)
{int a=n/2,b=m-(n+1)/2;if((!n*m)||m>n) return 0;if(b<0||b>a) return 0;return ((a&b)==b);
}
inline int g(int n,int m)
{int a=n-1-m/2,b=n-m;if((!n*m)||m>n) return 0;if(b<0||b>a) return 0;return ((a&b)==b);
}inline void solve()
{op=read();n=read();m=read();if(n==0&&m==0) cout<<"1";else if(op==1) cout<<f(n,m);else cout<<g(n,m);
}signed main()
{freopen("light.in","r",stdin);freopen("light.out","w",stdout);q=read();while(q--) solve();
}
B. 彻天之火 (fire)
异或哈希。
答案 \(= n − 1−\) 交集的最大值。
对于每条边 \(i\)，假设覆盖它的路径集合是 \(S_i\)，那么出现次数最多的 \(S_i\) 的出现次数就是交集的最大值。
给每条路径随机一个 \([0, 2^63)\) 内的权值，每条边的权值取成覆盖它的路径权值的异或和，就可以大概率表示出不同的覆盖集合。
异或差分甚至不需要求出 lca，复杂度 \(O(n + m)\)。
证明是对的很难。但手模发现这样做可以覆盖所有情况。
Code：
#include<bits/stdc++.h>
#define int long longusing namespace std;const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar() \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt) \? EOF \: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{int x=0,c=getchar(),f=0;for(;c>'9'||c<'0';f=c=='-',c=getchar());for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);return f?-x:x;
}
inline void write(int x)
{if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar(x%10+'0');
}int n,m;
const int N=1<<20;
vector<int> E[1<<20];
int u[N],v[N];// int bcj[1<<20];
// int f[1<<20];
// int dep[1<<20];
// int find(int x)
// {
// if(x==bcj[x]) return x;
// return bcj[x]=find(bcj[x]);
// }int cntt;
mt19937_64 rnd(time(0));
// int val[N];
int pval[N];unordered_map<int,int> mp;void dfs(int p,int fa)
{// int nw=0;for(int to:E[p]){if(to==fa) continue;dfs(to,p);pval[p]^=pval[to];}if(p==1) return;// cout<<p<<" "<<pval[p]<<"\n";// mp[pval[p]]++;// cntt=max(cntt,mp[pval[p]]);// nw^=pval[p];mp[pval[p]]++;cntt=max(cntt,mp[pval[p]]);// pval[p]=nw;// f[p]=fa;// dep[p]=dep[fa]+1;// for(int to:E[p])// {// if(to==fa) continue;// dfs(to,p);// }
}// void init()
// {
// for(int i=1;i<=n;i++) bcj[i]=i;
// dfs(1,0);
// }// int Lca(int u,int v)
// {
// int cnt=0;
// while(bcj[u]!=bcj[v])
// {
// if(dep[u]<dep[v]) swap(u,v);
// cnt++;
// int top=find(u);
// bcj[top]=find(f[top]);
// u=bcj[top];
// }
// return cnt;
// }int solve1()
{return 0;// init();// int cnt=0;// for(int i=1;i<=m;i++)// {// cnt+=Lca(u[i],v[i]);// }// return cnt;
}int solve2()
{for(int i=1;i<=m;i++){int nw=(rnd()>>1);// cout<<nw<<"\n";pval[u[i]]^=nw;pval[v[i]]^=nw;}dfs(1,0);// cout<<cntt<<"\n";return cntt;
}signed main()
{// #ifndef ONLINE_JUDGEfreopen("fire.in","r",stdin);freopen("fire.out","w",stdout);n=read();m=read();for(int i=1;i<n;i++){int u=read(),v=read();E[u].push_back(v);E[v].push_back(u);}for(int i=1;i<=m;i++){u[i]=read();v[i]=read();// if(u[i]==v[i]) { i--,m--; }}int ans=max(solve1(),solve2());cout<<max(0ll,n-1-ans)<<"\n";// #endif//mt19937_64 myrand(time(0));return 0;
}