T1 100pts
大水题，特判即可过。。。
可是我写了gcd()
ri~~
#include<bits/stdc++.h>
#define R register int
#define ll long long
using namespace std;
namespace Luitaryi {
inline ll g() { register ll x=0,f=1;
register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*f;
}
int T,Caz; ll n,m,k,l;
inline ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
inline void main() {
g(); T=g(); while(T--) {
n=g(),m=g(),k=g(); l=2ll*(n+m);
printf("Case %d: ",++Caz);
if(m==0) {puts("Winter"); continue;}
if(k>n+m) {puts("Summer"); continue;}
if(k<=m&&(k/gcd(m,k))&1) {puts("Winter"); continue;}
for(register ll L=l,cnt=0,lim=2*k;cnt<=5&&L>=lim;++cnt,L-=2) {
register ll t=gcd(k,L);
if(m%t==0) {puts("Winter"); goto end;}
} puts("Summer"); end:;
}
}
} signed main() {Luitaryi::main(); return 0;}T2 0pts
并查集，不会。
答案 \(=qpow(2,cnt-1)\)
原因是我们可以将合法的连通块看成二分图。我们需要将所有的二分图合并起来(就是上下随便放，共两种情况)。但是有上下反转同构。
#include<bits/stdc++.h>
#define R register int
using namespace std;
const int N=100010,M=998244353;int n,m,T,fa[N],d[N];
inline int getf(int x) {if(x==fa[x]) return x;R f=getf(fa[x]); d[x]^=d[fa[x]]; return fa[x]=f;}
inline void merge(int u,int v,int w) {R uf=getf(u),vf=getf(v);fa[uf]=vf,d[uf]=d[u]^d[v]^w;}
inline int qpow(int a,int b) {R ret=1;for(;b;b>>=1,a=1ll*a*a%M)if(b&1)ret=1ll*ret*a%M;return ret;}
int main() {
scanf("%d%d",&n,&T);while(T--){bool flg=0;scanf("%d%d",&n,&m);memset(d,0,sizeof d);
for(R i=1;i<=n;++i)fa[i]=i;for(R i=1,u,v,w;i<=m;++i){scanf("%d%d%d",&u,&v,&w);
if(getf(u)!=getf(v))merge(u,v,w^1);else if(d[u]^d[v]^w^1)flg=true;
}if(flg){puts("0");continue;}m=0;for(R i=1;i<=n;++i)if(fa[i]==i)++m;printf("%d\n",qpow(2,m-1));
}
}T3 0pts
硬刚t3无果。
线段树优化建图。
网上的std有错，没有判掉在子树外的点。
连边时 \(s2\) 先连到一个点，另一个点再连到 \(s1\) .
#include<bits/stdc++.h>
#define R register int
#define ll long long
using namespace std;
namespace Luitaryi {
char BB[1<<15],*S=BB,*T=BB;
#define getchar() (S==T&&(T=(S=BB)+fread(BB,1,1<<15,stdin),S==T)?EOF:*S++)
inline ll g() { register ll x=0,f=1;
register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*f;
} const int N=100010,B=17,Y=20,F=5;
int n,m,cnt,tot,rt[2],t,W;
int vr[Y*N],nxt[Y*N],fir[F*N],rw[N],dfn[N],sz[N],w[Y*N],fa[N][B+1];
int ls[F*N],rs[F*N]; bool vis[F*N]; ll d[F*N];
struct node {int l,r; node() {} node(int _l,int _r) {l=_l,r=_r;}
inline bool operator < (const node& that) const
{return l<that.l||l==that.l&&r<that.r;}
}mem[N];
inline void dfs(int u) { dfn[u]=++tot,rw[tot]=u; sz[u]=1;
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(dfn[v]) continue; d[v]=d[u]+1,fa[v][0]=u;
dfs(v); sz[u]+=sz[v];
}
}
inline void add(int u,int v,int ww)
{vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt,w[cnt]=ww;}
inline void build(int& tr,int l,int r,int op) {
if(l==r) return void(tr=rw[l]);
if(!tr) tr=++tot; R md=l+r>>1;
build(ls[tr],l,md,op),build(rs[tr],md+1,r,op);
(op)?(add(ls[tr],tr,0)):(add(tr,ls[tr],0));
(op)?(add(rs[tr],tr,0)):(add(tr,rs[tr],0));
}
inline void change(int tr,int l,int r,int LL,int RR,int op) {
if(LL<=l&&r<=RR) return void((op)?add(tot,tr,W):add(tr,tot,0));
R md=l+r>>1; if(LL<=md) change(ls[tr],l,md,LL,RR,op);
if(RR>md) change(rs[tr],md+1,r,LL,RR,op);
}
inline int calc(int u,int v)
{for(R t=B;~t;--t) if(d[fa[u][t]]>d[v]) u=fa[u][t]; return u;}
inline void dijk() { memset(d,0x3f,sizeof d);
priority_queue<pair<ll,int> > q; d[1]=0; q.push(make_pair(0,1));
while(q.size()) { R u=q.top().second; q.pop();
if(vis[u]) continue; vis[u]=true;
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(d[v]>d[u]+w[i]) d[v]=d[u]+w[i],q.push(make_pair(-d[v],v));
}
}
}
inline void main() {
g(); n=g(),m=g(); for(R i=1,u,v,w;i<n;++i)
u=g(),v=g(),w=g(),add(u,v,w),add(v,u,w);
d[1]=1,dfs(1); for(R t=1;t<=B;++t) for(R i=1;i<=n;++i)
fa[i][t]=fa[fa[i][t-1]][t-1];
build(rt[0],1,n,0),build(rt[1],1,n,1);
R x1,k1,x2,k2,LL,RR,p;
for(R i=1;i<=m;++i) {
x1=g(),k1=g(),LL=1,RR=n,t=0; ++tot;
if(~k1) { p=0;
for(R i=1,u;i<=k1;++i) { u=g();
if(dfn[u]<=dfn[x1]&&dfn[x1]+sz[x1]-1<=dfn[u]+sz[u]-1)
d[u]>d[p]?p=u:0;
else mem[++t]=node(dfn[u],dfn[u]+sz[u]-1);
} sort(mem+1,mem+t+1); p=calc(x1,p);
LL=dfn[p],RR=dfn[p]+sz[p]-1;
for(R i=1;i<=t;++i) {
if(!(dfn[p]<=mem[i].l&&mem[i].r<=RR)) continue;
if(LL<mem[i].l) change(rt[1],1,n,LL,mem[i].l-1,0);
LL=max(LL,mem[i].r+1);
} if(LL<=RR) change(rt[1],1,n,LL,RR,0);
} else add(x1,tot,0);
x2=g(),k2=g(),LL=1,RR=n,t=0;
if(~k2) { p=0;
for(R i=1,u;i<=k2;++i) { u=g();
if(dfn[u]<=dfn[x2]&&dfn[x2]+sz[x2]-1<=dfn[u]+sz[u]-1)
d[u]>d[p]?p=u:0;
else mem[++t]=node(dfn[u],dfn[u]+sz[u]-1);
} sort(mem+1,mem+t+1); p=calc(x2,p);
W=g(); LL=dfn[p],RR=dfn[p]+sz[p]-1;
for(R i=1;i<=t;++i) {
if(!(dfn[p]<=mem[i].l&&mem[i].r<=RR)) continue;
if(LL<mem[i].l) change(rt[0],1,n,LL,mem[i].l-1,1);
LL=max(LL,mem[i].r+1);
} if(LL<=RR) change(rt[0],1,n,LL,RR,1);
} else W=g(),add(tot,x2,W);
} dijk(); for(R i=1;i<=n;++i) printf("%lld\n",d[i]);
}
} signed main() {Luitaryi::main(); return 0;}