\(55+42+50=147,rk2\)。
T1 序列
直接上吉司机线段树，特判 \(+\ 0\) 情况即可。
我猜测时间复杂度是 \(O(n\log^2n)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+5;
int n,m,mn[N],nn[N],ad[N];
int adn[N],chg[N],chgn[N];
void push_up(int x){
mn[x]=min(mn[x*2],mn[x*2+1]);
nn[x]=min(nn[x*2],nn[x*2+1]);
if(mn[x]!=mn[x*2])
nn[x]=min(nn[x],mn[x*2]);
if(mn[x]!=mn[x*2+1])
nn[x]=min(nn[x],mn[x*2+1]);
}void down(int x,int d,int dn,int g,int gn){
mn[x]+=dn,nn[x]+=d,adn[x]+=dn,ad[x]+=d,chgn[x]+=gn,chg[x]+=g;
}void push_down(int x){
int minn=min(mn[x*2],mn[x*2+1]);
if(mn[x*2]!=minn) down(x*2,ad[x],ad[x],chg[x],chg[x]);
else down(x*2,ad[x],adn[x],chg[x],chgn[x]);
if(mn[x*2+1]!=minn) down(x*2+1,ad[x],ad[x],chg[x],chg[x]);
else down(x*2+1,ad[x],adn[x],chg[x],chgn[x]);
ad[x]=adn[x]=chg[x]=chgn[x]=0;
}void build(int x,int l,int r){
if(l==r) return cin>>mn[x],nn[x]=1e18,void();
int mid=(l+r)/2;build(x*2,l,mid);
build(x*2+1,mid+1,r),push_up(x);
}void add(int x,int l,int r,int L,int R,int v){
if(!v) return;
if(L<=l&&r<=R) return down(x,v,v,1,1);
int mid=(l+r)/2;push_down(x);
if(L<=mid) add(x*2,l,mid,L,R,v);
if(R>mid) add(x*2+1,mid+1,r,L,R,v);
push_up(x);
}void minn(int x,int l,int r,int L,int R,int v){
if(v<=mn[x]) return;
if(L<=l&&r<=R&&v<nn[x])
return down(x,0,v-mn[x],0,1);
int mid=(l+r)/2;push_down(x);
if(L<=mid) minn(x*2,l,mid,L,R,v);
if(R>mid) minn(x*2+1,mid+1,r,L,R,v);
push_up(x);
}pair<int,int>ans(int x,int l,int r,int k){
if(l==r) return {mn[x],chgn[x]};
int mid=(l+r)/2;push_down(x);
if(k<=mid) return ans(x*2,l,mid,k);
return ans(x*2+1,mid+1,r,k);
}signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n,build(1,1,n),cin>>m;
while(m--){
char c;int l,r,d;cin>>c>>l;
if(c=='Q'){
pair<int,int>p=ans(1,1,n,l);
cout<<p.first<<" "<<p.second<<"\n";
}if(c=='A') cin>>r>>d,add(1,1,n,l,r,d);
if(c=='M') cin>>r>>d,minn(1,1,n,l,r,d);
}return 0;
}
T2 旅行计划
第一眼线性基，然后发现根本没有异或操作。
考场上想到奇环能调节奇偶性，但是没想清楚。
考虑设联通块内所有边的 \(\gcd\) 为 \(x\)，则我们可以先对所有边 \(\times\frac 1{\gcd(x,k)}\)，最后再 \(\times\gcd(x,k)\)，相当于我们只需要考虑 \(\gcd(x,k)=1\) 的情况了。
假如 \(k\) 为奇数，在 \((u,v)\) 的一条路径上来回走 \(k\) 次一定可以。
假如 \(k\) 为偶数，如果有一条 \((u,v)\) 路径长在 \(\times\frac 1{\gcd(x,k)}\) 后为偶数，我们就可以通过反复走一条边将答案改为 \(0\)；假如有一个奇环，那我们可以通过走奇环来改变奇偶性，同样也可以将答案改为 \(0\)。容易发现，假如 \((u,v)\) 间的一条路径为奇路径，那么要么有奇环，要么没有 \((u,v)\) 间的偶路径。证明显然。我们也很容易观察到，若不满足上述两种情况，答案一定不为 \(0\)。于是我们得到如下结论：
当 \(k\) 为偶数时，联通块内有奇环，或有一条 \((u,v)\) 间的路径长度为偶数，为 \((u,v)\) 答案为 \(0\) 的充要条件。
但这样显然不好预处理，考虑通过预处理关于 \(x\) 的值来推导答案。我们分两种情况（下文 \(w\) 表示联通块内任意一条边的原先边权）：
-
\(\frac w{\gcd(x,k)}\bmod 2=\frac wx\bmod 2\)。此时直接预处理，由于不动奇偶性，所以问题不大。
-
\(\frac w{\gcd(x,k)}\bmod 2\ne\frac wx\bmod 2\)。很明显，一定是前项为偶数，后项为奇数。相当于给原图所有边权 \(\times 2\)，那么所有路径就都是偶路径，那么答案必为 \(0\)，不影响。
出题人似乎根本没有意识到第二种情况特判的重要性。
当然，上述所有情况都建立在 \(u,v\) 在同一联通块内，若不在同一联通块内，输出 \(NIE\) 即可。
时间复杂度 \(O(n\log n)\)，\(\log\) 是计算 \(\gcd\) 的时间。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,q,d[N],ft[N];
int dis[N],id[N],vs[N];
struct edge{int to,cs;};
vector<edge>g[N];
int gcd(int x,int y){
return !y?x:gcd(y,x%y);
}int dfs1(int x){
int re=0;vs[x]=1;
for(auto y:g[x])
re=gcd(re,gcd(y.cs,(!vs[y.to])?dfs1(y.to):0));
return re;
}void dfs(int x,int zx,int gc){
ft[x]=zx;
for(auto y:g[x]){
int to=y.to,cs=(y.cs/gc)&1;
if(ft[to]) id[zx]|=dis[to]^dis[x]^cs;
else dis[to]=dis[x]^cs,dfs(to,zx,gc);
}
}signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m>>q;
for(int i=1,x,y,z;i<=m;i++)
cin>>x>>y>>z,g[x].push_back({y,z}),g[y].push_back({x,z});
for(int i=1;i<=n;i++) if(!ft[i])
dfs(i,i,d[i]=dfs1(i));
while(q--){
int x,y,k;cin>>x>>y>>k;
if(ft[x]!=ft[y]) cout<<"NIE\n";
else if(id[ft[x]]||k%2) cout<<"0\n";
else if(dis[x]^dis[y]==0) cout<<"0\n";
else if(!(d[ft[x]]/gcd(d[ft[x]],k)%2)) cout<<"0\n";
else cout<<gcd(d[ft[x]],k)<<"\n";
}return 0;
}
T3 Hack
有趣的网络流如期而至。
容易看出原题是一个最小割问题，但是在最大流时，不能走回头路。
所以先 \(tarjan\) 缩点，再按题目中给的数据连边。为了保证不走回头路，还需要再建反边，长度为 \(inf\)。
这样的思路仍然有 \(bug\)。考虑当一条边的 \(u\) 无法从 \(1\) 到达，或者 \(v\) 无法到达 \(n\)，此时这条边都不能连。特判即可。
时间复杂度 \(O(n^2m)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=205,M=10005;
int n,dfn[N],low[N],tot,id,tp,k=1;
int h[N],nxt[M],to[M],cs[M],st[N];
int m,idx[N],u[M],v[M],w[M],vs[N];
vector<int>g1[N],g2[N];int c[N],d[N];
vector<int>g[N];int v1[N],v2[N];
void tarjan(int x){
dfn[x]=low[x]=++id;
st[++tp]=x,vs[x]=1;
for(auto y:g[x]){
if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
else if(vs[y]) low[x]=min(low[x],dfn[y]);
}if(low[x]!=dfn[x]) return;
++tot;while(st[tp+1]!=x)
vs[st[tp]]=0,idx[st[tp--]]=tot;
}void add(int x,int y,int z){
if(x==y) return;
cs[++k]=z,to[k]=y,nxt[k]=h[x],h[x]=k;
cs[++k]=0,to[k]=x,nxt[k]=h[y],h[y]=k;
}int bfs(int s,int t){
memset(c,-1,sizeof(c));queue<int>q;
c[s]=0,q.push(s),d[s]=h[s];
while(q.size()){
int x=q.front();q.pop();
for(int i=h[x];i;i=nxt[i]){
int y=to[i],lv=cs[i];
if(!lv||~c[y]) continue;
c[y]=c[x]+1,d[y]=h[y],q.push(y);
if(y==t) return 1;
}
}return 0;
}int dfs(int x,int ans,int t){
if(x==t) return ans;
int sum=ans;
for(int i=d[x];i&∑i=nxt[i]){
d[x]=i;int y=to[i],lv=cs[i];
if(lv<1||c[y]!=c[x]+1) continue;
int zjy=dfs(y,min(sum,lv),t);
sum-=zjy,cs[i]-=zjy,cs[i^1]+=zjy;
}return ans-sum;
}int dinic(int s,int t){
int re=0;
while(bfs(s,t))
re+=dfs(s,1e18,t);
return re;
}void dfs1(int x){
v1[x]=1;for(auto y:g1[x])
if(!v1[y]) dfs1(y);
}void dfs2(int x){
v2[x]=1;for(auto y:g2[x])
if(!v2[y]) dfs2(y);
}signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u[i]>>v[i]>>w[i];
g[++u[i]].push_back(++v[i]);
}tarjan(1);
if(idx[1]==idx[n]) return cout<<-1,0;
for(int i=1;i<=m;i++)
if(idx[u[i]]&&idx[v[i]]&&idx[u[i]]!=idx[v[i]]){
g1[idx[v[i]]].push_back(idx[u[i]]);
g2[idx[u[i]]].push_back(idx[v[i]]);
}
dfs1(idx[n]),dfs2(idx[1]);
for(int i=1;i<=m;i++)
if(v2[idx[u[i]]]&&v1[idx[v[i]]]&&idx[u[i]]&&idx[v[i]])
add(idx[u[i]],idx[v[i]],w[i]),add(idx[v[i]],idx[u[i]],1e18);
cout<<dinic(idx[1],idx[n]);
return 0;
}