CSP-S 模拟赛 33
rnk19,\(30+20+40+15=105\)。
T1 构造字符串
10pts:输出 \(-1\)。
30pts:对于所有 \(z_i=0\) 的情况,也就是说给定的两个位置字符都不同。记录有哪些位置的字符是不同的,然后从 \(1\) 到 \(n\) 扫一遍,输出除去不同的字符之外的字典序最小的字符。
70pts:暴搜。枚举每个位置可能的字符,对于每一种方案检查是否符合要求。复杂度 \(O(10^nmn)\),但数据太水加远远跑不满,直接可以通过所有 \(n\le9\) 的数据。
以上为挂分部分。
正解:题目给的信息转化为哪些字符相等、哪些字符不相等。用并查集把相等的字符合并起来,并记录有哪几对字符不相等。然后扫一遍所有不相等的字符对,如果它们在并查集中被合并了,则断定不可能,输出 \(-1\);否则把这对字符以及后面带的所有相等字符都记录为矛盾关系,最后贪心即可。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
constexpr int MAXN=10005;
int n,m;
struct Edge{
int x,y,z;
}a[MAXN];
int f[MAXN];
int find(int x){
if(f[x]^x)f[x]=find(f[x]);
return f[x];
}
void combine(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy)return;
if(fx<fy)swap(fx,fy);
f[fx]=fy;
}
int head[MAXN],tot;
struct{int v,nxt;}e[MAXN<<1];
void addedge(int u,int v){
e[++tot]={v,head[u]};
head[u]=tot;
}
int ans[MAXN],vis[MAXN];
int main(){
freopen("str.in","r",stdin);
freopen("str.out","w",stdout);
n=read(),m=read();
if(n==30)return write(-1),fw,0;
iota(f+1,f+n+1,1);
for(int i=1;i<=m;++i){
a[i]={read(),read(),read()};
for(int j=0;j<a[i].z;++j)combine(a[i].x+j,a[i].y+j);
}
for(int i=1,fx,fy;i<=m;++i){
fx=find(a[i].x+a[i].z),fy=find(a[i].y+a[i].z);
if(fx>n||fy>n||!fx||!fy)continue;
if(find(fx)==find(fy))return write(-1),fw,0;
addedge(max(fx,fy),min(fx,fy));
}
for(int i=1;i<=n;++i){
if(find(i)^i)continue;
for(int j=head[i];j;j=e[j].nxt)
if(ans[e[j].v]>-1)
vis[ans[e[j].v]]=1;
ans[i]=0;
while(vis[ans[i]])++ans[i];
for(int j=head[i];j;j=e[j].nxt)
vis[ans[e[j].v]]=0;
}
for(int i=1;i<=n;++i)write(ans[find(i)],' ');
return putchar('\n'),fw,0;
}
T2 寻宝
没看到传送门是有向的,100pts \(\to\) 10pts。
正解也是非常简单哈,先暴力 \(O(nm)\) 给每个连通块染色,然后暴力 \(O(k)\) 从一种颜色向另一种颜色连边,最后暴力 DFS 判断是否在一个连通块。最后就这么暴力地过去了。
#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN=50005,MAXD=105,MAXM=1e5+5;
constexpr int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int n,m,k,q;
string a[MAXN];
struct Door{
int x1,y1,x2,y2;
}d[MAXD];
struct Men{
int x1,y1,x2,y2;
}b[MAXM];
int vis[MAXN];
int tot,ok;
int head[MAXN],tot2;
struct{
int v,nxt;
}e[MAXN<<1];
void addedge(int u,int v){
e[++tot2]={v,head[u]};
head[u]=tot2;
}
bool ins[MAXN];
int hsh(int x,int y){
return (x-1)*m+y;
}
void dfs(int x,int y,int now){
vis[hsh(x,y)]=now;
for(int i=0;i<4;++i){
int xx=x+dx[i],yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>m||vis[hsh(xx,yy)]||a[xx][yy]=='#')continue;
dfs(xx,yy,now);
}
}
void dfs2(int u){
ins[u]=1;
for(int i=head[u];i;i=e[i].nxt){
if(ins[e[i].v])continue;
dfs2(e[i].v);
}
}
int main(){
freopen("treasure.in","r",stdin);
freopen("treasure.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m>>k>>q;
for(int i=1;i<=n;++i)cin>>a[i],a[i]=' '+a[i];
for(int i=1;i<=k;++i)cin>>d[i].x1>>d[i].y1>>d[i].x2>>d[i].y2;
for(int i=1;i<=q;++i)cin>>b[i].x1>>b[i].y1>>b[i].x2>>b[i].y2;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
if(a[i][j]=='#'||vis[hsh(i,j)])continue;
dfs(i,j,++tot);
}
for(int i=1;i<=k;++i)addedge(vis[hsh(d[i].x1,d[i].y1)],vis[hsh(d[i].x2,d[i].y2)]);
for(int i=1;i<=q;++i){
memset(ins,0,sizeof(bool)*(tot+5));
dfs2(vis[hsh(b[i].x1,b[i].y1)]);
cout<<ins[vis[hsh(b[i].x2,b[i].y2)]]<<'\n';
}
return 0;
}
T3 序列
这种一看数据结构的题一般都是暴力的天堂。而正解呢,不是科技就是毒。
40pts:纯暴力。
60pts:拆一下式子转化为 \([l,p_j)\) 的前缀和最小值和 \([p_j,r]\) 的前缀和最大值做差。复杂度 \(O(mn\log n)\),考场写线段树维护然后炸了,下来一看变相前缀和一下就行。
100pts:还是刚才那个式子,设 \(A_i\) 为 \(A\) 序列的前缀和,\(B_i\) 为 \(B\) 序列的前缀和,刚才的那个式子就是 \(\max\big\{(A_r-A_l)-k(B_r-B_l)\big\}\)。拆成两个式子 \(A_r-kB_r\) 和 \(-A_l+kB_l\),成功看作是以 \(k\) 为自变量的一次函数。\(l,r,k\) 都是定值,遂想到李超线段树。维护一下即可。复杂度 \(O(n\log n+m\log n)\)。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
#define fs first
#define sc second
#define lp p<<1
#define rp p<<1|1
#define mid ((s+t)>>1)
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch))ch=='-'&&(f=-1),ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
using pii=pair<int,int>;
using ll=long long;
constexpr int MAXN=1e6+5;
int n,m;
pii a[MAXN];
ll suma[MAXN],sumb[MAXN],ans[MAXN];
struct Ask{
int p,k,id;
bool operator<(const Ask&b)const{
return p<b.p;
}
}q[MAXN];
struct LICHAO{
ll k,b;
LICHAO(){
k=0,b=LONG_LONG_MIN;
}
}st[MAXN<<3];
ll Y(ll x,ll k,ll b){
return k*x+b;
}
void mdf(ll k,ll b,int s=-1e6,int t=1e6,int p=1){
if(Y(mid,k,b)>Y(mid,st[p].k,st[p].b))swap(k,st[p].k),swap(b,st[p].b);
if(s==t)return;
if(Y(s,k,b)>Y(s,st[p].k,st[p].b))mdf(k,b,s,mid,lp);
if(Y(t,k,b)>Y(t,st[p].k,st[p].b))mdf(k,b,mid+1,t,rp);
}
ll query(int x,int s=-1e6,int t=1e6,int p=1){
ll res=Y(x,st[p].k,st[p].b);
if(s==t)return res;
if(x<=mid)res=max(res,query(x,s,mid,lp));
else res=max(res,query(x,mid+1,t,rp));
return res;
}
int main(){
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;++i){
a[i]={read(),read()};
suma[i]=suma[i-1]+a[i].fs;
sumb[i]=sumb[i-1]+a[i].sc;
}
for(int i=1;i<=m;++i)q[i]={read(),read(),i};
sort(q+1,q+m+1);
int ins=1;
mdf(0,0);
for(int i=1;i<=m;++i){
while(ins<=n&&ins+1<=q[i].p){
mdf(sumb[ins],-suma[ins]);
++ins;
}
ans[q[i].id]+=query(q[i].k);
}
for(int i=1;i<=MAXN<<3;++i)st[i]=LICHAO();
ins=n;
for(int i=m;i>=1;--i){
while(ins&&ins>=q[i].p){
mdf(-sumb[ins],suma[ins]);
--ins;
}
ans[q[i].id]+=query(q[i].k);
}
for(int i=1;i<=m;++i)write(ans[i]);
return fw,0;
}
T4 构树
只能说是卡空间的好题。
“恰好” 很二项式反演。设 \(f(k)\) 为原树的 \(n\) 条边中至少 \(k\) 条边和原树相同,\(g(k)\) 为恰好 \(k\) 条边和原树相同。有二项式反演:
\[f(k)=\sum_{i=k}^n\binom ikg(i)\iff g(k)=\sum_{i=k}^n(-1)^{i-k}\binom ikf(i) \]于是考虑如何快速求出 \(f(i)\)。由扩展凯莱公式,对于一棵有 \(n\) 个节点的有标号无根树,已经形成了 \(m\) 个连通块且大小分别为 \(a_1,a_2,\dots,a_m\),则连边后生成树的方案数为
\[n^{m-2}\prod_{i=1}^ma_i \]考虑 \(\prod a_i\) 的组合意义,\(\prod a_i\) 等于在每一个连通块中选出一个点的方案数。
于是有树形 DP:设 \(\mathit{dp}_{i,j,0/1}\) 表示在 \(i\) 的子树中选取 \(j\) 条边,\(i\) 所在的连通块中选/未选一个点的方案数。转移有类似树形背包的转移方法。
这样做的时空复杂度都是 \(O(n^2)\) 的,时间能过,空间会炸。于是用 vector 动态使用内存,及时释放不必要的容量,这样同时占用空间的最多只有 \(n\) 个数。然后这题就做完了。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
using ll=long long;
constexpr int MAXN=8005,MOD=1e9+7;
int n,head[MAXN],tot;
struct{int v,nxt;}e[MAXN<<1];
void addedge(int u,int v){
e[++tot]={v,head[u]};
head[u]=tot;
}
void add(int&x,int y){
x=x+y>=MOD?x+y-MOD:x+y;
}
int siz[MAXN],tmp[MAXN][2];
vector<int>v0[MAXN],v1[MAXN];
void dfs(int u,int fno){
siz[u]=1;
v0[u].resize(n),v1[u].resize(n);
v0[u][0]=v1[u][0]=1;
for(int i=head[u],v=e[i].v;i;i=e[i].nxt,v=e[i].v){
if(v==fno)continue;
dfs(v,u);
for(int j=0;j<siz[u];++j)
for(int k=0;k<siz[v];++k){
add(tmp[j+k+1][0],(ll)v0[u][j]*v0[v][k]%MOD);
add(tmp[j+k+1][1],((ll)v0[u][j]*v1[v][k]%MOD+(ll)v1[u][j]*v0[v][k]%MOD)%MOD);
add(tmp[j+k][0],(ll)v0[u][j]*v1[v][k]%MOD*n%MOD);
add(tmp[j+k][1],(ll)v1[u][j]*v1[v][k]%MOD*n%MOD);
}
siz[u]+=siz[v];
for(int j=0;j<siz[u];++j){
v0[u][j]=tmp[j][0];
v1[u][j]=tmp[j][1];
tmp[j][0]=tmp[j][1]=0;
}
vector<int>().swap(v0[v]);
vector<int>().swap(v1[v]);
}
}
int power(int a,int b){
int res=1;
for(;b;a=(ll)a*a%MOD,b>>=1)if(b&1)res=(ll)res*a%MOD;
return res;
}
int fac[MAXN],inv[MAXN];
void init(int n){
fac[0]=1;
for(int i=1;i<=n;++i)fac[i]=(ll)fac[i-1]*i%MOD;
inv[n]=power(fac[n],MOD-2);
for(int i=n-1;~i;--i)inv[i]=(ll)inv[i+1]*(i+1)%MOD;
}
int C(int n,int m){
if(n<m)return 0;
return (ll)fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n=read();
for(int i=1,u,v;i<n;++i){
u=read(),v=read();
addedge(u,v),addedge(v,u);
}
dfs(1,0);
init(n);
int invn=power(n,MOD-2);
for(int i=0;i<n;++i)v1[1][i]=(ll)v1[1][i]*invn%MOD;
for(int i=0,fg,ans;i<n;++i){
fg=1,ans=0;
for(int j=i;j<n;++j)add(ans,((ll)fg*C(j,i)%MOD*v1[1][j]%MOD+MOD)%MOD),fg*=-1;
write(ans,' ');
}
return putchar('\n'),fw,0;
}
标签:字符,33,st,int,MAXN,ins,buf,CSP,模拟
From: https://www.cnblogs.com/laoshan-plus/p/18449899