21牛客多校第三场
21牛客多校第三场
这场好难 dls下手也太狠了
A
好奇怪的题 弃了
B
将每个点认为是边和列之间的边，容易发现题意即为求最小生成树
因为边权不会太大，桶排序后kruskal即可
#include<bits/stdc++.h>#define inf 2139062143#define ll long long#define db double#define ld long double#define ull unsigned long long#define MAXN 100100#define MOD 998244353#define Fill(a,x) memset(a,x,sizeof(a))#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)#define ren for(int i=fst[x];i;i=nxt[i])#define pls(a,b) (a+b)%p#define mul(a,b) (1LL*(a)*(b))%p#define pii pair<int,int>#define fi first#define se second#define pb push_backusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} return x*f;
}int n,m,a,b,c,d,p,las,fa[MAXN],ans;vector<pii> e[MAXN];int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}inline int merge(int u,int v){ int fu=find(u),fv=find(v); if(fu!=fv) return fa[fu]=fv;return 0;
}int main(){
n=read(),m=read(),las=a=read(),b=read(),c=read(),d=read(),p=read();
rep(i,1,n) rep(j,1,m)
{
las=pls(pls(mul(mul(las,las),b),mul(las,c)),d);
e[las].pb({i,j+n});
}
rep(i,1,n+m) fa[i]=i;
rep(i,0,p-1) for(auto t:e[i]) if(merge(t.fi,t.se)) ans+=i; printf("%d\n",ans);
}C
至多2n个点就一定可以满足要求，而能减小答案的点一定满足该点所在行和列限制相同
这样的话对于这种点行与列连边，做最大费用流即可
#include<bits/stdc++.h>#define inf 213906214300000LL#define ll long long#define db double#define ld long double#define ull unsigned long long#define MAXN 1001001#define MAXM 1001001#define Fill(a,x) memset(a,x,sizeof(a))#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)#define ren for(int i=fst[x];i;i=nxt[i])#define pls(a,b) (a+b)%MOD#define mns(a,b) (a-b+MOD)%MOD#define mul(a,b) (1LL*(a)*(b))%MOD#define pii pair<int,int>#define fi first#define se second#define pb push_backusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} return x*f;
}int n,m,k,a[MAXN],b[MAXN];
ll ans;struct ZKW{
int nxt[MAXM<<1],to[MAXM<<1],val[MAXM<<1],cnt,fst[MAXN]; int vis[MAXN],S,T;queue<int> q;
ll cst[MAXM<<1],dis[MAXN],res; void mem(){Fill(fst,0);cnt=1,res=0;} void add(int u,int v,int w,int c) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w,cst[cnt]=c;} void ins(int u,int v,int w,int c) {add(u,v,w,c),add(v,u,0,-c);} int spfa()
{ int x;rep(i,1,n*2+2) dis[i]=-inf,vis[i]=0;
dis[T]=0,vis[T]=1;q.push(T);while(!q.empty())
{
x=q.front(),q.pop();vis[x]=0;ren if(dis[to[i]]<dis[x]-cst[i]&&val[i^1])
{dis[to[i]]=dis[x]-cst[i];if(!vis[to[i]]) vis[to[i]]=1,q.push(to[i]);}
} return dis[S]!=-inf;
} int dfs(int x,int a)
{ if(vis[x]) return 0;vis[x]=1;if(x==T||!a) {res+=a*dis[S];return a;} int f,flw=0;ren if(val[i]&&dis[to[i]]==dis[x]-cst[i]&&(f=dfs(to[i],min(a,val[i]))))
a-=f,val[i]-=f,val[i^1]+=f,flw+=f; return flw;
} int solve()
{ int f,flw=0;while(spfa())
do{memset(vis,0,sizeof(vis));f=dfs(S,inf),flw+=f;}while(f); return res;
}
}Z;int main(){
n=read(),m=read(),k=read();int x,y;
rep(i,1,n) a[i]=read(),ans+=a[i];
rep(i,1,n) b[i]=read(),ans+=b[i];
Z.mem();Z.S=2*n+1,Z.T=2*n+2;
rep(i,1,n) Z.ins(Z.S,i,1,0),Z.ins(n+i,Z.T,1,0);
rep(i,1,m) {x=read(),y=read();if(a[x]==b[y]) Z.ins(x,y+n,1,a[x]);} printf("%d\n",ans-Z.solve());
}D
容斥+三维背包 咕了
E
打表题（bushi
不难发现每一对数对是连续的，且ai=x2ai−1−ai−2，其中(x,x3)为这一条链的起始数对
最后upper_bound即可
（也可以正经做，但是懒得再推一遍了，反正结论就是这个
#include<bits/stdc++.h>#define inf 2139062143#define ll long long#define db double#define ld long double#define ull unsigned long long#define MAXN 10010010#define MOD 998244353#define Fill(a,x) memset(a,x,sizeof(a))#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)#define ren for(int i=fst[x];i;i=nxt[i])#define pls(a,b) (a+b)%MOD#define mns(a,b) (a-b+MOD)%MOD#define mul(a,b) (1LL*(a)*(b))%MOD#define pii pair<int,int>#define fi first#define se second#define pb push_backusing namespace std;inline ll read(){
ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} return x*f;
}
ll g[MAXN],n,ans;int tot;void mem(int n=1e6,ll lim=1e18){
__int128 x,y,z;g[++tot]=1;
rep(i,2,n)
{
x=i,y=1LL*i*i*i; while(y<=lim)
g[++tot]=y,z=y*i*i-x,x=y,y=z;
}
sort(g+1,g+tot+1);
}int main(){
mem();rep(T,1,read())
{
n=read();ans=upper_bound(g+1,g+tot+1,n)-g-1; printf("%d\n",ans);
}
}F
爆搜题
可以发现n≤3时显然不可能所有操作出现分数，直接判断
先搜出4个数的组合，再排列后枚举所有的符号组合
判断能凑出答案的所有方案是否都出现分数即可
#include<bits/stdc++.h>#define inf 2139062143#define ll long long#define db double#define ld long double#define ull unsigned long long#define MAXN 100100#define MOD 998244353#define Fill(a,x) memset(a,x,sizeof(a))#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)#define ren for(int i=fst[x];i;i=nxt[i])#define pls(a,b) (a+b)%MOD#define mns(a,b) (a-b+MOD)%MOD#define mul(a,b) (1LL*(a)*(b))%MOD#define pii pair<int,int>#define fi first#define se second#define pb push_backusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} return x*f;
}const db eps=1e-6;int n,m,op[10],p,w[10],res=0;vector<int> ans[5];inline int isz(db x){return (-eps<x&&x<eps);}int isd(db x){return fabs(x-(int)x)>=eps;}db calc(db a,db b,int c){ if(c==1) return a+b; if(c==2) return a-b; if(c==3) return a*b; if(isz(b)) return inf; return a/b;
}int cheq(){ int ret=0,rett=0;db res=0; if(p==1)
{
db t1=calc(w[1],w[2],op[1]); if(isz(t1-inf)){ret=0;return ret;} if(isd(t1)) rett=1;
db t2=calc(t1,w[3],op[2]); if(isz(t2-inf)){ret=0;return ret;} if(isd(t2)) rett=1;
res=calc(t2,w[4],op[3]); if(isz(res-m)) ret=1; else {ret=0;return ret;}
} else if(p==2)
{
db t1=calc(w[1],w[2],op[1]); if(isz(t1-inf)){ret=0;return ret;} if(isd(t1)) rett=1;
db t2=calc(w[3],w[4],op[3]); if(isz(t2-inf)){ret=0;return ret;} if(isd(t2)) rett=1;
res=calc(t1,t2,op[2]); if(isz(res-m)) ret=1; else {ret=0;return ret;}
} else if(p==3)
{
db t1=calc(w[2],w[3],op[2]); if(isz(t1-inf)){ret=0;return ret;} if(isd(t1)) rett=1;
db t2=calc(w[1],t1,op[1]); if(isz(t2-inf)){ret=0;return ret;} if(isd(t2)) rett=1;
res=calc(t2,w[4],op[3]); if(isz(res-m)) ret=1; else {ret=0;return ret;}
} else if(p==4)
{
db t1=calc(w[2],w[3],op[2]); if(isz(t1-inf)){ret=0;return ret;} if(isd(t1)) rett=1;
db t2=calc(t1,w[4],op[3]); if(isz(t2-inf)){ret=0;return ret;} if(isd(t2)) rett=1;
res=calc(w[1],t2,op[1]); if(isz(res-m)) ret=1; else {ret=0;return ret;}
} else if(p==5)
{
db t1=calc(w[3],w[4],op[3]); if(isz(t1-inf)){ret=0;return ret;} if(isd(t1)) rett=1;
db t2=calc(w[1],w[2],op[1]); if(isz(t2-inf)){ret=0;return ret;} if(isd(t2)) rett=1;
res=calc(t1,t2,op[2]); if(isz(res-m)) ret=1; else {ret=0;return ret;}
} else
{
db t1=calc(w[3],w[4],op[3]); if(isz(t1-inf)){ret=0;return ret;} if(isd(t1)) rett=1;
db t2=calc(w[2],t1,op[2]); if(isz(t2-inf)){ret=0;return ret;} if(isd(t2)) rett=1;
res=calc(w[1],t2,op[1]); if(isz(res-m)) ret=1; else {ret=0;return ret;}
}
return ret+rett;
}
void dfs2(int i,int &jud){ if(!jud) return; if(i>n-1)
{ int ok=jud,flg; for(p=1;p<=6;++p)
{
flg=cheq(); if(flg==1) ok=0; else if(flg==2&&ok) ok=1;
}
jud=ok;return;
}
rep(j,1,4){op[i]=j;dfs2(i+1,jud);}
}void dfs(int i,int las){ if(i>n)
{ int jud=-1; do {dfs2(1,jud);} while(next_permutation(w+1,w+n+1)); if(jud>0) {res++;rep(j,1,n) ans[j].pb(w[j]);} return;
}
rep(j,las,13) {w[i]=j;dfs(i+1,j);} return;
}int main(){
n=read(),m=read();if(n<=3) return puts("0"),0;
dfs(1,1);printf("%d\n",res);
rep(i,0,res-1) {rep(j,1,n) cout<<ans[j][i]<<" ";puts("");}
}G
首先可以把每次修改放到所有d|x里面，这样可以单独处理所有有关i的询问
对每个i的一个询问来说，若我们可以快速知道每个点到根的路径上有多少个符合条件的颜色，则可以在这个点到根的链上二分，直到找到答案和查询点相同的深度最浅的点，即为所求的最近祖先
这个二分过程可以用树链剖分简单实现
对于到根路径颜色数量的查询，考虑维护一个二维平面，横坐标为dfs序，纵坐标为颜色
每次修改操作会影响子树内的点，相当于添加一条平行的直线
查询即查询该点对应垂直的直线段[l,r]内有多少与平行直线的交点
使用树套树，横坐标用树状数组，纵坐标动态开点线段树
注意每次处理完所有i之后清空所有标记
#include<bits/stdc++.h>#define inf 2139062143#define ll long long#define db double#define ld long double#define ull unsigned long long#define MAXN 150100#define MOD 998244353#define Fill(a,x) memset(a,x,sizeof(a))#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)#define ren for(int i=fst[x];i;i=nxt[i])#define pls(a,b) (a+b)%MOD#define mns(a,b) (a-(b)+MOD)%MOD#define mul(a,b) (1LL*(a)*(b))%MOD#define pii pair<int,int>#define fi first#define se second#define pb push_backusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} return x*f;
}int n,Q,m,nxt[MAXN<<1],fst[MAXN],to[MAXN<<1],cnt,val[MAXN<<1],hsh[MAXN],cntq[MAXN];int sz[MAXN],dep[MAXN],fa[MAXN],hvs[MAXN],bl[MAXN],in[MAXN],out[MAXN],dfn;
ll dis[MAXN],ans[MAXN];struct Data{int id,l,r,x;};vector<int> d[MAXN],Del;vector<Data> q[MAXN];void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}void dfs(int x,int pa){
sz[x]=1,fa[x]=pa; ren if(to[i]^pa)
{
dep[to[i]]=dep[x]+1;dis[to[i]]=dis[x]+val[i];dfs(to[i],x);
sz[x]+=sz[to[i]],hvs[x]=sz[to[i]]>sz[hvs[x]]?to[i]:hvs[x];
}
}void Dfs(int x,int anc){
bl[x]=anc,in[x]=out[x]=++dfn,hsh[dfn]=x; if(!hvs[x]) return ;Dfs(hvs[x],anc); ren if(to[i]^fa[x]&&to[i]^hvs[x]) Dfs(to[i],to[i]);out[x]=dfn;
}int tot,rt[MAXN],sum[MAXN<<7],ls[MAXN<<7],rs[MAXN<<7];void mdf(int &k,int l,int r,int x,int w){ if(!k) k=++tot;sum[k]+=w;if(l==r) return ;int mid=l+r>>1;
x<=mid?mdf(ls[k],l,mid,x,w):mdf(rs[k],mid+1,r,x,w);
}int query(int k,int l,int r,int a,int b){ if(!k) return 0;if(a<=l&&r<=b) return sum[k];int mid=l+r>>1,res=0; if(a<=mid) res=query(ls[k],l,mid,a,b); if(b>mid) res+=query(rs[k],mid+1,r,a,b); return res;
}inline void ins(int x,int w,int v){
Del.pb(x);for(;x<=n;x+=x&-x) mdf(rt[x],1,n,w,v);
}inline int query(int x,int l,int r,int res=0){ for(;x;x-=x&-x) res+=query(rt[x],1,n,l,r);return res;
}inline void erase(int x){ for(;x<=n;x+=x&-x) if(rt[x]) rt[x]=0;else break;
}inline int calc(int l,int r,int a,int b,int x){ int res=0;for(int mid=l+r>>1;l<=r;mid=l+r>>1) if(query(mid,a,b)==x) res=mid,r=mid-1; else l=mid+1; return hsh[res];
}inline void work(int num){ for(auto t:q[num]) if(!t.id){ins(in[t.l],t.x,1);ins(out[t.l]+1,t.x,-1);} else
{ int mx=query(in[t.x],t.l,t.r),x=t.x,tmp,las; if(!mx) {ans[t.id]=-1;goto End;}
tmp=query(in[bl[x]],t.l,t.r); if(tmp!=mx)
{ans[t.id]=calc(in[bl[x]],in[x],t.l,t.r,mx);goto End;} for(las=bl[x],x=fa[bl[x]];x;las=bl[x],x=fa[bl[x]])
{
tmp=query(in[x],t.l,t.r); if(tmp<mx) {ans[t.id]=las;goto End;}
tmp=query(in[bl[x]],t.l,t.r); if(tmp<mx) {ans[t.id]=calc(in[bl[x]],in[x],t.l,t.r,mx);goto End;}
}
End:if(~ans[t.id]) ans[t.id]=dis[t.x]-dis[ans[t.id]]; if(!(--cntq[num])) break;
}
rep(i,1,tot) ls[i]=rs[i]=sum[i]=0;tot=0; for(auto x:Del) erase(x);Del.clear();
}int main(){
n=read(),Q=read();int a,b,c,e;
rep(i,1,n) for(int j=i;j<=n;j+=i) d[j].pb(i);
rep(i,2,n) a=read(),b=read(),c=read(),add(a,b,c),add(b,a,c);
dfs(1,0);Dfs(1,0);
rep(i,1,Q)
{
c=read(),a=read(),b=read(); if(!c) for(auto x:d[b]) q[x].pb({0,a,0,b}); else {c=read(),e=read();cntq[e]++;q[e].pb({++m,b,c,a});}
}
rep(i,1,n) work(i);
rep(i,1,m)
if(ans[i]<0) puts("Impossible!"); else printf("%lld\n",ans[i]);
}H
题解写了3整页 过于害怕于是弃了
I
0操作直接差分即可
对于1操作，先拆成[l,n]和[r+1,n]两段异或等差数列
容易发现对每一位来说，异或上的数一定是…11100001111…的一部分，连续2i个0/1交错出现
因此在这一位上的所有修改的周期是一样的，考虑二阶差分
对于每个从t位置开始异或以x开始的等差数列，可以先将x加入到一阶差分中
然后只需要找到每一位第一个和x不一样的位置，每过2i之后改变一次，放进二阶差分中
最后先将二阶差分数组按周期性整合tag，得到一阶差分数组，再直接求前缀和即可
#include<bits/stdc++.h>#define inf 2139062143#define ll long long#define db double#define ld long double#define ull unsigned long long#define MAXN 600100#define MOD 998244353#define Fill(a,x) memset(a,x,sizeof(a))#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)#define ren for(int i=fst[x];i;i=nxt[i])#define pls(a,b) (a+b)%MOD#define mns(a,b) (a-(b)+MOD)%MOD#define mul(a,b) (1LL*(a)*(b))%MOD#define pii pair<int,int>#define fi first#define se second#define pb push_backusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} return x*f;
}int n,q,g[MAXN],s[MAXN];bool tag[MAXN][30];void work(int x,int w){
s[x]^=w;rep(i,0,29)
{ int t=(((w>>i)+1)<<i)-w+x; if(t<=n) tag[t][i]^=1;
}
}int main(){
n=read(),q=read();rep(i,1,n) g[i]=read();int x,a,b;
rep(i,1,q)
{
x=read(); if(!x) {a=read(),b=read(),x=read();s[a]^=x,s[b+1]^=x;} else {a=read(),b=read(),x=read();work(a,x),work(b+1,x+b-a+1);}
}
rep(i,1,n) rep(j,0,29) if(tag[i][j])
{
s[i]^=(1<<j); if(i+(1<<j)<=n) tag[i+(1<<j)][j]^=1;
}
rep(i,1,n) {s[i]^=s[i-1];printf("%d%c",g[i]^s[i],i==n?'\n':' ');}
}J
签到题，同色三元环并不好计算，考虑计算异色三元环
异色三元环一定有两个角是异色的，则只需统计有多少个异色角再
对每个点来说，异色角个数即 黑边×白边
#include<bits/stdc++.h>#define inf 2139062143#define ll long long#define db double#define ld long double#define ull unsigned long long#define MAXN 100100#define MOD 998244353#define Fill(a,x) memset(a,x,sizeof(a))#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)#define ren for(int i=fst[x];i;i=nxt[i])#define pls(a,b) (a+b)%MOD#define mns(a,b) (a-b+MOD)%MOD#define mul(a,b) (1LL*(a)*(b))%MOD#define pii pair<int,int>#define fi first#define se second#define pb push_backusing namespace std;namespace GenHelper
{ unsigned z1,z2,z3,z4,b,u; unsigned get()
{
b=((z1<<6)^z1)>>13;
z1=((z1&4294967294U)<<18)^b;
b=((z2<<2)^z2)>>27;
z2=((z2&4294967288U)<<2)^b;
b=((z3<<13)^z3)>>21;
z3=((z3&4294967280U)<<7)^b;
b=((z4<<3)^z4)>>12;
z4=((z4&4294967168U)<<13)^b; return (z1^z2^z3^z4);
} bool read() { while (!u) u = get(); bool res = u & 1;
u >>= 1; return res;
} void srand(int x)
{
z1=x;
z2=(~x)^0x233333333U;
z3=x^0x1234598766U;
z4=(~x)+51;
u = 0;
}
}using namespace GenHelper;int n,seed,d[8080];
ll ans,res;int main(){ cin>>n>>seed;srand(seed);int x;
rep(i,1,n) rep(j,i+1,n) x=read(),d[i]+=x,d[j]+=x;
ans=1LL*n*(n-1)*(n-2)/6;
rep(i,1,n) ans-=1LL*d[i]*(n-1-d[i])/2; printf("%lld\n",ans);
}来源https://www.cnblogs.com/yyc-jack-0920/p/15081056.html