csp-s 模拟
ZROJ-NOIP二十连
CSP-S模拟 1
T1 喜剧的迷人之处在于
咕咕咕
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+9;
int T,cnt,mx,prime[maxn],v[maxn];
long long sqr[maxn];
inline long long read(){
long long res=0;char c=getchar();
for(;c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar()) res=(res<<3)+(res<<1)+(c^48);
return res;
}
int main(){
for(int i=2;i<=1000000;i++){
if(!v[i]) prime[++cnt]=i;
for(int j=1;prime[j]*i<=1000000;j++){
v[prime[j]*i]=1;
if(!(i%prime[j])) break;
}
sqr[i]=1ll*i*i;
}
scanf("%d",&T);
memset(v,0,sizeof v);
while(T--){
long long a=read(),b=1,L=read(),R=read();
for(int i=1;a>1;i++,mx=i) while(!(a%prime[i])) a/=prime[i],v[prime[i]]++;
for(int i=1;i<mx;i++){
if(v[prime[i]]&1) b*=prime[i];
v[prime[i]]=0;
}
long long sq=sqrt((L-1)/b)+1;
b*=sq*sq;
printf("%lld\n",b<=R?b:-1);
}
return 0;
}
T2 镜中的野兽
咕咕咕
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+9;
int n,m,p,cnt,ans;
int phi[maxn],v[maxn];
int f[29][1<<18];
void getprime(int lcm){
cnt=0;
for(int i=2;i<=lcm;i++){
if(lcm%i) continue;
phi[++cnt]=i,v[cnt]=0;
while(!(lcm%i)) lcm/=i,v[cnt]++;
}
}
void dfs(int pos,int now){
if(pos>cnt){
for(int i=n;i;i--){
for(int j=(1<<(cnt<<1))-1;~j;j--){
(f[i][j|now]+=f[i-1][j])%=p;
}
}
return;
}
dfs(pos+1,now|1<<pos>>1);
for(int i=1;i<v[pos];i++) dfs(pos+1,now);
dfs(pos+1,now|1<<(pos+cnt)>>1);
}
void solve(int gcd){
if(m<=gcd<<1) return;
memset(f,0,sizeof f),f[0][0]=1;
getprime((m-gcd)/gcd),dfs(1,0);
(ans+=f[n][(1<<(cnt<<1))-1])%=p;
}
int main(){
scanf("%d%d%d",&n,&m,&p);
int s=sqrt(m);
for(int i=1;i<=s;i++){
if(!(m%i)){
solve(i);
if(i*i^m) solve(m/i);
}
}
return printf("%d\n",ans),0;
}
T3 我愿相信由你所描述的童话
咕咕咕
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+9;
const int inf=1<<20;
const int mod=1e9+7;
int n,m,ans,f[1<<10][1<<10];
int s[maxn],up[maxn],low[maxn],las[inf];
void update(int x,int val){
int l=x>>m,r=x^(l<<m),u=(~r)^(~r>>m<<m);
for(int sb=u;;sb=(sb-1)&u){
(f[l][r|sb]+=val)%=mod;
if(!sb) return;
}
}
int query(int x){
int l=x>>m,r=x^(l<<m),res=1;
for(int sb=l;;sb=(sb-1)&l){
(res+=f[sb][r])%=mod;
if(!sb) return res;
}
}
int main(){
scanf("%d%d",&n,&m),m>>=1;
for(int i=1;i<=n;i++) scanf("%d",&s[i]);
for(int i=1;i<=n;i++) update(s[i],up[i]=query(s[i]));
memset(f,0,sizeof f);
for(int i=n;i;i--) update(s[i],low[i]=query(s[i]));
for(int i=1;i<=n;i++){
(ans+=1ll*up[i]*low[i]%mod)%=mod;
(ans-=1ll*las[s[i]]*low[i]%mod-mod)%=mod;
(las[s[i]]+=up[i])%=mod;
}
return printf("%d\n",ans),0;
}
T4 Baby Doll
咕咕咕
CSP-S模拟 2
T1 不相邻集合
咕咕咕
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int inf=5e5+9;
int n,die[inf],sz[inf],v[inf];
int findie(int x){return x==die[x]?x:die[x]=findie(die[x]);}
void merge(int x,int y){die[findie(x)]=findie(y);}
int main(){
scanf("%d",&n);
for(int i=1;i<inf;i++) die[i]=i,sz[i]=1;
for(int i=1,a,ans=0;i<=n;i++){
scanf("%d",&a);
if(!(v[a]++)){
int nsz=1;
if(v[a-1]){
int lsz=sz[findie(a-1)];
ans-=ceil(1.0*lsz/2);
nsz+=lsz;merge(a,a-1);
}
if(v[a+1]){
int rsz=sz[findie(a+1)];
ans-=ceil(1.0*rsz/2);
nsz+=rsz;merge(a,a+1);
}
ans+=ceil(1.0*(sz[findie(a)]=nsz)/2);
}
printf("%d ",ans);
}
return 0;
}
T2 线段树
subtask 1
直接建树查询，递归到每个区间内的叶子结点，对路径上所有合法根的编号求和。
时间复杂度 \(O(n)\) ，\(n\) 的范围是 \(1e18\) ，直接T飞。
暴力
#include<bits/stdc++.h>
#define lcs (rt<<1)
#define rcs (rt<<1|1)
using namespace std;
using ll=long long;
const int mod=1e9+7;
ll T,n,x,y;
int query(int rt,ll l,ll r,ll L,ll R){
int res=0;
if(L>r||R<l) return res;
if(l==r) return rt;
if(L<=l&&r<=R) res=rt;
ll mid=(l+r)>>1;
(res+=(query(lcs%mod,l,mid,L,R)+query(rcs%mod,mid+1,r,L,R))%mod)%=mod;
return res;
}
int main(){
scanf("%lld",&T);
while(T--){
scanf("%lld%lld%lld",&n,&x,&y);
printf("%d\n",query(1,1,n,x,y));
}
return 0;
}
subtask 别的
当这个节点代表的 \(l\) 和 \(r\) 刚好在要查询的区间之内时，整个子树内的节点均合法，此事无需继续递归，想办法求出子树内所有节点编号之和，作为这个根节点的贡献。
设 \(f(rt,n)\) 代表以 \(rt\) 为根且子树叶子结点数为 \(n\) 的节点的贡献
可以得出递推式 \(f(rt,n)=f(rt*2,\ulcorner{\frac{n}{2}}\urcorner)+f(rt*2+1,\llcorner{\frac{n}{2}}\lrcorner)+rt\)
发现 \(f(rt,n)\) 可以写成 \(k_{n}*rt+b_{n}\) 的一次函数形式，所以再把两边换一下：
\[k_{n}*rt+b_{n}=k_{\ulcorner{\frac{n}{2}}\urcorner}*(rt*2)+b_{\ulcorner{\frac{n}{2}}\urcorner}+k_{\llcorner{\frac{n}{2}}\lrcorner}*(rt*2+1)+b_{\llcorner{\frac{n}{2}}\lrcorner}+rt
\]
\[k_{n}*rt+b_{n}=(2*(k_{\ulcorner{\frac{n}{2}}\urcorner}+k_{\llcorner{\frac{n}{2}}\lrcorner})+1)*rt+b_{\ulcorner{\frac{n}{2}}\urcorner}+b_{\llcorner{\frac{n}{2}}\lrcorner}+k_{\llcorner{\frac{n}{2}}\lrcorner}
\]
所以就有了 \(k\) 和 \(b\) 的递推式：
\[k_{n}=2*(k_{\ulcorner{\frac{n}{2}}\urcorner}+k_{\llcorner{\frac{n}{2}}\lrcorner})+1
\]
\[b_{l,r}=b_{\ulcorner{\frac{n}{2}}\urcorner}+b_{\llcorner{\frac{n}{2}}\lrcorner}+k_{\llcorner{\frac{n}{2}}\lrcorner}
\]
最后再用map加个记搜把用到的 \(k\) 跟 \(b\) 记一下，把贡献 \(k_{n}*rt+b_{n}\) 累加到答案上，就过了。
点击查看代码
#include<bits/stdc++.h>
#define lcs (rt<<1)
#define rcs (rt<<1|1)
#define axe r-l+1
using namespace std;
using ll=long long;
const int mod=1e9+7;
ll T,n,x,y;map<ll,ll> k,b;
void dfs(ll n){
if(k[n]) return;
ll n1=ceil(1.0*n/2);dfs(n1);
ll n2=floor(1.0*n/2);dfs(n2);
k[n]=((k[n1]+k[n2])<<1|1)%mod;
b[n]=(b[n1]+b[n2]+k[n2])%mod;
}
int query(int rt,ll l,ll r,ll L,ll R){
if(L>r||R<l) return 0;
if(L<=l&&r<=R) return dfs(axe),(k[axe]*rt+b[axe])%mod;
ll mid=(l+r)>>1;
return (query(lcs%mod,l,mid,L,R)+query(rcs%mod,mid+1,r,L,R))%mod;
}
int main(){
scanf("%lld",&T);k[1]=1;
while(T--){
scanf("%lld%lld%lld",&n,&x,&y);
printf("%d\n",query(1,1,n,x,y));
}
return 0;
}
T3 魔法师
咕咕咕
点击查看代码
#include<bits/stdc++.h>
#define lcs (rt<<1)
#define rcs (rt<<1|1)
using namespace std;
const int inf=250000;
int Q,T,axe,op,t,a,b;
multiset<int> A[2][inf<<1];
multiset<int> B[2][inf<<1];
multiset<int>::iterator it;
struct segtree{
int mn,l,r,a[2],b[2];
segtree(){mn=a[0]=b[0]=a[1]=b[1]=0x3f3f3f3f;}
}tree[inf<<3];
void pushup(int rt){
tree[rt].a[0]=min(tree[lcs].a[0],tree[rcs].a[0]);
tree[rt].b[0]=min(tree[lcs].b[0],tree[rcs].b[0]);
tree[rt].a[1]=min(tree[lcs].a[1],tree[rcs].a[1]);
tree[rt].b[1]=min(tree[lcs].b[1],tree[rcs].b[1]);
tree[rt].mn=min(tree[lcs].a[1]+tree[rcs].a[0],tree[lcs].b[0]+tree[rcs].b[1]);
tree[rt].mn=min(tree[rt].mn,min(tree[lcs].mn,tree[rcs].mn));
}
void build(int rt,int l,int r){
tree[rt].l=l,tree[rt].r=r;
if(l==r) return;
int mid=(l+r)>>1;
build(lcs,l,mid),build(rcs,mid+1,r);
}
void update(int rt,int pos){
if(pos<tree[rt].l||pos>tree[rt].r) return;
if(tree[rt].l==tree[rt].r){
int now=tree[rt].l;
if(!A[0][now].size()){
A[0][now].insert(0x3f3f3f3f);
B[0][now].insert(0x3f3f3f3f);
A[1][now].insert(0x3f3f3f3f);
B[1][now].insert(0x3f3f3f3f);
}
if(op==1){
A[t][now].insert(a);
B[t][now].insert(b);
}
if(op==2){
it=A[t][now].lower_bound(a);
if(*it==a) A[t][now].erase(it);
it=B[t][now].lower_bound(b);
if(*it==b) B[t][now].erase(it);
}
tree[rt].a[0]=*A[0][now].begin();
tree[rt].b[0]=*B[0][now].begin();
tree[rt].a[1]=*A[1][now].begin();
tree[rt].b[1]=*B[1][now].begin();
tree[rt].mn=min(tree[rt].a[0]+tree[rt].a[1],tree[rt].b[0]+tree[rt].b[1]);
return;
}
update(lcs,pos),update(rcs,pos),pushup(rt);
}
int main(){
scanf("%d%d",&Q,&T);
build(1,1,inf<<1);
while(Q--){
scanf("%d%d%d%d",&op,&t,&a,&b);
if(T) a^=axe,b^=axe;
update(1,(t?b-a:a-b)+inf);
printf("%d\n",axe=tree[1].mn^0x3f3f3f3f?tree[1].mn:0);
}
return 0;
}
T4 园艺
咕咕咕
CSP-S模拟 3
T1 奇观
咕咕咕
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+9;
const int mod=998244353;
int n,m,u,v,sum,C,F;
int v1[maxn],v2[maxn];
vector<int> del[maxn];
int main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d%d",&n,&m);sum=1ll*n*(n-1)%mod;
for(int i=1;i<=n;i++) del[i].push_back(i),v1[i]=n-1;
while(m--){
scanf("%d%d",&u,&v);
del[u].push_back(v);
del[v].push_back(u);
v1[u]--,v1[v]--,sum-=2;
}
for(int i=1;i<=n;i++){
v2[i]=sum;
for(auto j:del[i]) (v2[i]-=v1[j]-mod)%=mod;
(C+=1ll*v1[i]*v2[i]%mod)%=mod;
(F+=1ll*v1[i]*v1[i]%mod*v2[i]%mod)%=mod;
}
return printf("%lld\n",1ll*C*C%mod*F%mod),0;
}
T2 铁路
咕咕咕
点击查看代码
#include<bits/stdc++.h>
#define lcs (rt<<1)
#define rcs (rt<<1|1)
using namespace std;
const int maxn=5e5+9;
int n,m,tot,cnt,u,v;
int h[maxn],nxt[maxn<<1],to[maxn<<1];
int ys[maxn],die[maxn],dep[maxn],siz[maxn];
int son[maxn],top[maxn],dfn[maxn],rnk[maxn];
struct segtree{
int sum,l,r,lz,bel;
}tree[maxn<<2];
void add(int x,int y){
tot++;
nxt[tot]=h[x];
to[tot]=y;
h[x]=tot;
}
inline void pushup(int rt){tree[rt].sum=tree[lcs].sum+tree[rcs].sum;}
void pushdown(int rt){
if(!tree[rt].lz) return;
tree[lcs].lz=tree[rcs].lz=1;
tree[lcs].bel=tree[rt].bel;
tree[rcs].bel=tree[rt].bel;
tree[lcs].sum=tree[rt].bel>=tree[lcs].l&&tree[rt].bel<=tree[lcs].r;
tree[rcs].sum=tree[rt].bel>=tree[rcs].l&&tree[rt].bel<=tree[rcs].r;
tree[rt].lz=0;
}
void build(int rt,int l,int r){
tree[rt].l=l,tree[rt].r=r;
if(l==r) return tree[rt].bel=l,tree[rt].sum=1,void(0);
int mid=(l+r)>>1;
build(lcs,l,mid),build(rcs,mid+1,r),pushup(rt);
}
void update(int rt,int l,int r,int y){
if(l>tree[rt].r||r<tree[rt].l) return;
if(l<=tree[rt].l&&tree[rt].r<=r){
tree[rt].sum=y>=tree[rt].l&&tree[rt].r>=y;
tree[rt].bel=y,tree[rt].lz=1;
return;
}
pushdown(rt),update(lcs,l,r,y),update(rcs,l,r,y),pushup(rt);
}
int query(int rt,int pos){
if(tree[rt].l==tree[rt].r) return tree[rt].bel;
int mid=(tree[rt].l+tree[rt].r)>>1;
return pushdown(rt),query(pos<=mid?lcs:rcs,pos);
}
void dfs1(int x,int fa){
siz[x]=1,die[x]=fa,dep[x]=dep[fa]+1;
for(int i=h[x];i;i=nxt[i]){
int y=to[i];
if(y==fa) continue;
dfs1(y,x),siz[x]+=siz[y];
if(siz[y]>siz[son[x]]) son[x]=y;
}
}
void dfs2(int x,int tp){
top[x]=tp,dfn[x]=++cnt,rnk[dfn[x]]=x;
if(!son[x]) return;
dfs2(son[x],tp);
for(int i=h[x];i;i=nxt[i]){
int y=to[i];
if(y^die[x]&&y^son[x]) dfs2(y,y);
}
}
int lca(int x,int y){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=die[top[x]];
}
if(dep[y]<dep[x]) swap(x,y);
return x;
}
void merge(int x,int y,int z){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
update(1,dfn[top[x]],dfn[x],z);
x=die[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
update(1,dfn[x],dfn[y],z);
}
int find(int x){
int tmp=query(1,dfn[x]);
return tmp==dfn[x]?x:find(rnk[tmp]);
}
int main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs1(1,0),dfs2(1,1),build(1,1,n);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
if(u>n) u=ys[u-n];
if(v>n) v=ys[v-n];
ys[i]=find(lca(u,v));
merge(u,v,dfn[ys[i]]);
printf("%d\n",tree[1].sum);
}
return 0;
}
T3 光纤
咕咕咕
T4 权值
咕咕咕
CSP-S模拟 4
T1 商品
咕咕咕
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+9;
int n,d,cnt,l,r;long long ans;
int num[maxn],big[maxn],small[maxn];
long long sa[maxn],sb[maxn];
map<int,int> t;
inline long long sua(int l,int r){return sa[r]-sa[l-1];}
inline long long sub(int l,int r){return sb[r]-sb[l-1];}
int main(){
freopen("goods.in","r",stdin);
freopen("goods.out","w",stdout);
scanf("%d%d",&n,&d);
for(int i=1,a[2];i<=n;i++){
scanf("%d",&a[i&1]);
if(!t[a[i&1]]) num[++cnt]=a[i&1];
t[a[i&1]]++;if(i==1) continue;
int mx=max(a[i&1],a[!(i&1)]),mn=min(a[i&1],a[!(i&1)]);
big[++big[0]]=mx,small[++small[0]]=mn;
}
sort(num+1,num+cnt+1);
sort(big+1,big+big[0]+1);
sort(small+1,small+small[0]+1);
for(int i=1;i<=n;i++) sa[i]=sa[i-1]+big[i],sb[i]=sb[i-1]+small[i];
for(int i=1,L,R;i<cnt;i++){
l=num[i],r=num[i]+d;
L=upper_bound(big+1,big+big[0]+1,l)-big-1;
R=lower_bound(big+1,big+big[0]+1,r)-big-1;
long long mx=1ll*L*l+1ll*(big[0]-R)*r+sua(L+1,R);
L=upper_bound(small+1,small+small[0]+1,l)-small-1;
R=lower_bound(small+1,small+small[0]+1,r)-small-1;
long long mn=1ll*L*l+1ll*(small[0]-R)*r+sub(L+1,R);
ans=max(ans,mx-mn);
}
for(int i=cnt,L,R;i>1;i--){
l=num[i]-d,r=num[i];
L=upper_bound(big+1,big+big[0]+1,l)-big-1;
R=lower_bound(big+1,big+big[0]+1,r)-big-1;
long long mx=1ll*L*l+1ll*(big[0]-R)*r+sua(L+1,R);
L=upper_bound(small+1,small+small[0]+1,l)-small-1;
R=lower_bound(small+1,small+small[0]+1,r)-small-1;
long long mn=1ll*L*l+1ll*(small[0]-R)*r+sub(L+1,R);
ans=max(ans,mx-mn);
}
return printf("%lld\n",ans),0;
}
T2 价值
咕咕咕
T3 货币
咕咕咕
T4 资本
咕咕咕