总结
(T1) 应该可以说是吉司机线段树的板子题，但是看到变化次数就不知道怎么维护了
交了一个假的线段树上去，本来能得 (80)，但是没判 (0)，没数据点分治，直接挂到 (20)
(T2) 的思维性比较强，貌似除了凯爹大家都是 (13) 分
(T3) 也是人均 (50) 分
基本上差距还是在 (T1)，以后还是要多注意一些细节的东西
A. 序列
分析
看到区间和某一个数取最值的操作就想到吉司机线段树
但是不会维护变化次数
所以就写了一个复杂度很假的维护最大值和最小值进行剪枝的线段树
但是被出题人卡了，不仅卡了时限，还卡了区间加 (0)
正解很多，最后还是写了吉司机线段树
考虑维护四个懒惰标记，一个是修改最小值的标记，一个是区间加的标记，一个是区间修改次数的标记，一个是最小值修改次数的标记
注意一下更新顺序就行了
代码
#include<cstdio>
#include<algorithm>
#include<cmath>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e5+5;
#define Min(a,b) (a)<(b)?(a):(b)
int a[maxn],n,q;
struct trr{
int l,r,cnt,laz2,laz3;
long long sum,laz1,mmin,sec;
}tr[maxn<<2];
void push_up(rg int da){
tr[da].mmin=Min(tr[da<<1].mmin,tr[da<<1|1].mmin);
if(tr[da<<1].mmin<tr[da<<1|1].mmin){
tr[da].sec=Min(tr[da<<1|1].mmin,tr[da<<1].sec);
} else if(tr[da<<1|1].mmin<tr[da<<1].mmin){
tr[da].sec=Min(tr[da<<1].mmin,tr[da<<1|1].sec);
} else {
tr[da].sec=Min(tr[da<<1].sec,tr[da<<1|1].sec);
}
}
inline void updat1(rg int da,rg long long val){
tr[da].laz1+=val,tr[da].mmin+=val,tr[da].sec+=val,tr[da].sum+=val;
}
inline void push_down1(rg int da){
if(!tr[da].laz1) return;
updat1(da<<1,tr[da].laz1),updat1(da<<1|1,tr[da].laz1);
tr[da].laz1=0;
}
inline void updat2(rg int da,rg int val){
tr[da].laz2+=val,tr[da].cnt+=val;
}
inline void push_down2(rg int da){
if(!tr[da].laz2) return;
updat2(da<<1,tr[da].laz2),updat2(da<<1|1,tr[da].laz2);
tr[da].laz2=0;
}
inline void updat3(rg int da,rg int val){
tr[da].laz3+=val;
if(tr[da].l==tr[da].r) tr[da].cnt+=val;
}
inline void push_down3(rg int da){
if(tr[da].laz3==0) return;
if(tr[da<<1].mmin==tr[da].mmin) updat3(da<<1,tr[da].laz3);
if(tr[da<<1|1].mmin==tr[da].mmin) updat3(da<<1|1,tr[da].laz3);
tr[da].laz3=0;
}
inline void updat4(rg int da,rg long long val){
if(tr[da].mmin<val){
tr[da].mmin=val;
if(tr[da].l==tr[da].r) tr[da].sum=val;
}
}
inline void push_down4(rg int da){
updat4(da<<1,tr[da].mmin),updat4(da<<1|1,tr[da].mmin);
}
inline void push_down(rg int da){
push_down1(da),push_down4(da),push_down3(da);
}
void build(rg int da,rg int l,rg int r){
tr[da].l=l,tr[da].r=r;
if(l==r){
tr[da].sum=tr[da].mmin=a[l];
tr[da].sec=0x3f3f3f3f3f3f3f3f;
return;
}
rg int mids=(l+r)>>1;
build(da<<1,l,mids);
build(da<<1|1,mids+1,r);
push_up(da);
}
void xg1(rg int da,rg int l,rg int r,rg int val){
if(tr[da].l>=l && tr[da].r<=r){
updat1(da,val);
updat2(da,1);
return;
}
push_down(da);
rg int mids=(tr[da].l+tr[da].r)>>1;
if(l<=mids) xg1(da<<1,l,r,val);
if(r>mids) xg1(da<<1|1,l,r,val);
push_up(da);
}
void xg2(rg int da,rg int l,rg int r,rg int val){
if(tr[da].mmin>=val) return;
if(tr[da].l>=l && tr[da].r<=r && tr[da].sec>val){
updat4(da,val),updat3(da,1);
return;
}
push_down(da);
rg int mids=(tr[da].l+tr[da].r)>>1;
if(l<=mids) xg2(da<<1,l,r,val);
if(r>mids) xg2(da<<1|1,l,r,val);
push_up(da);
}
int cx1(rg int da,rg int wz){
if(tr[da].l==tr[da].r) return tr[da].cnt;
push_down(da),push_down2(da);
rg int mids=(tr[da].l+tr[da].r)>>1;
if(wz<=mids) return cx1(da<<1,wz);
else return cx1(da<<1|1,wz);
}
long long cx2(rg int da,rg int wz){
if(tr[da].l==tr[da].r) return tr[da].sum;
push_down(da);
rg int mids=(tr[da].l+tr[da].r)>>1;
if(wz<=mids) return cx2(da<<1,wz);
else return cx2(da<<1|1,wz);
}
int main(){
n=read();
for(rg int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
rg int aa,bb,cc;
rg char ch;
q=read();
for(rg int i=1;i<=q;i++){
scanf(" %c",&ch);
if(ch=='A'){
aa=read(),bb=read(),cc=read();
if(cc==0) continue;
xg1(1,aa,bb,cc);
} else if(ch=='M'){
aa=read(),bb=read(),cc=read();
xg2(1,aa,bb,cc);
} else {
aa=read();
printf("%lld %d
",cx2(1,aa),cx1(1,aa));
}
}
return 0;
}
B. 旅行计划
分析
设 (d=gcd(K,l_1,l_2,cdots l_e)) 显然答案一定是 (d) 的倍数
那么把所有都除以 (d) 再乘回去答案也是对的
此时 (gcd(K,l_1,l_2...l_e)=1)，那么存在 (a_K+bl_1+cl_2+....+el_e=1)
这个可以用归纳法证
因为根据裴蜀定理，存在 (al_1+bl_2=k imes gcd(l_1,l_2))
把 (k) 看成新的系数，把 (gcd(l_1,l_2)) 看成新的值就可以了
那么就有 (2a_K+2bl_1+2cl_2+....+2el_e=2)
也就是说可以通过每条边回去 (a,b,c,d cdots e) 次使答案加 (2)
我们先把每一个边权和 (k) 都除以它们的最小公倍数，那么问题就转化为奇偶性判定问题
因为你可以一直使答案加 (2)，影响答案的就只有奇偶性了
对原图进行奇偶染色
先判一下不联通的情况
如果此时 (k) 为奇数，那么在模 (k) 意义下价值一定会变成 (0)
如果原图中存在奇环，那么我们可以走这个奇环来改变答案的奇偶性，答案也为 (0)
如果两个端点染色后颜色相同，那么它们之间的距离一定为偶数，答案仍然为 (0)
如果 (gcd) 等于 (k),因为答案是 (k) 的倍数，那么答案还是 (0)
剩下的情况直接输出 (gcd) 就可以了
但是每一次都对所有的边和 (k) 求一次 (gcd) 复杂度是 (O(n)) 的
所以我们可以提前把一个联通块中所有边的 (gcd) 预处理出来
这样做之所以正确的是因为 (k) 为奇数的情况被特判掉了
用到奇偶性的一定是 (k) 为偶数的情况
此时是不影响边权的奇偶性的
代码
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=2e5+5;
int h[maxn],tot=2,n,m,q;
struct asd{
int to,nxt,val;
}b[maxn];
void ad(rg int aa,rg int bb,rg int cc){
b[tot].to=bb;
b[tot].nxt=h[aa];
b[tot].val=cc;
h[aa]=tot++;
}
int shuyu[maxn],pre[maxn],col[maxn],cnt;
bool jud[maxn];
int gcd(rg int aa,rg int bb){
return bb==0?aa:gcd(bb,aa%bb);
}
int get(rg int val){
if(val&1) return 1;
else return 2;
}
void dfs(rg int now,rg int ncol){
shuyu[now]=cnt;
col[now]=ncol;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(!col[u]){
dfs(u,get(ncol+(b[i].val&1)));
} else if(col[u]!=get(ncol+(b[i].val&1))){
jud[cnt]=1;
}
}
}
int main(){
memset(h,-1,sizeof(h));
n=read(),m=read(),q=read();
rg int aa,bb,cc;
for(rg int i=1;i<=m;i++){
aa=read(),bb=read(),cc=read();
ad(aa,bb,cc);
ad(bb,aa,cc);
}
for(rg int i=1;i<=n;i++){
if(!col[i]){
cnt++;
dfs(i,2);
}
}
for(rg int i=1;i<=n;i++){
for(rg int j=h[i];j!=-1;j=b[j].nxt){
pre[shuyu[i]]=gcd(pre[shuyu[i]],b[j].val);
}
}
for(rg int i=1;i<=n;i++){
for(rg int j=h[i];j!=-1;j=b[j].nxt){
b[j].val/=pre[shuyu[i]];
}
}
memset(col,0,sizeof(col));
memset(shuyu,0,sizeof(shuyu));
memset(jud,0,sizeof(jud));
cnt=0;
for(rg int i=1;i<=n;i++){
if(!col[i]){
cnt++;
dfs(i,2);
}
}
rg int now;
for(rg int i=1;i<=q;i++){
aa=read(),bb=read(),cc=read();
if(shuyu[aa]!=shuyu[bb]) printf("NIE
");
else {
now=gcd(pre[shuyu[aa]],cc);
if(now==cc || jud[shuyu[aa]] || col[aa]==col[bb] || (cc/now)&1) printf("0
");
else {
printf("%d
",now);
}
}
}
return 0;
}
C. Hack
分析
如果没有恰好选择一次的限制就是一个裸的最小割
经过多于一次的方案就是走某些路径由最小割后 (T) 点集走回了 (S)点集
于是我们把反向边开成 (inf) 就好了
这样就保证了即使它可以往回走的路径也被割断
要注意起点不会经过的边不要建图
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=5e3+5;
int n,h[maxn],m,h2[maxn],s,t,tot=2;
struct asd{
int to,nxt;
long long val;
}b[maxn<<1];
void ad(rg int aa,rg int bb,rg long long cc){
b[tot].to=bb;
b[tot].nxt=h[aa];
b[tot].val=cc;
h[aa]=tot++;
}
int que[maxn],head,tail,dep[maxn];
long long ans;
bool bfs(){
for(rg int i=1;i<=n;i++) dep[i]=0;
for(rg int i=1;i<=n;i++) h[i]=h2[i];
head=tail=1;
que[1]=s;
dep[s]=1;
while(head<=tail){
rg int now=que[head++];
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(b[i].val && !dep[u]){
dep[u]=dep[now]+1;
que[++tail]=u;
}
}
}
return dep[t]!=0;
}
long long dfs(rg int now,rg long long ac1){
if(now==t) return ac1;
rg long long ac2=0;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
h[now]=i;
rg int u=b[i].to;
if(b[i].val && dep[u]==dep[now]+1){
rg long long nans=dfs(u,std::min(ac1,1LL*b[i].val));
b[i].val-=nans;
b[i^1].val+=nans;
ac1-=nans;
ac2+=nans;
}
if(!ac1) break;
}
if(!ac2) dep[now]=0;
return ac2;
}
bool vis[maxn];
void dfs(rg int now){
vis[now]=1;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(vis[u]) continue;
dfs(u);
}
}
int jla[maxn],jlb[maxn],jlc[maxn];
int main(){
memset(h,-1,sizeof(h));
n=read(),m=read();
for(rg int i=1;i<=m;i++){
jla[i]=read(),jlb[i]=read(),jlc[i]=read();
jla[i]++,jlb[i]++;
ad(jla[i],jlb[i],jlc[i]);
}
dfs(1);
memset(h,-1,sizeof(h));
tot=2;
for(rg int i=1;i<=m;i++){
if(vis[jla[i]] && vis[jlb[i]]){
ad(jla[i],jlb[i],jlc[i]);
ad(jlb[i],jla[i],0x3f3f3f3f3f3f3f3f);
}
}
s=1,t=n;
for(rg int i=1;i<=n;i++) h2[i]=h[i];
while(bfs()){
ans+=dfs(s,0x3f3f3f3f3f3f3f3f);
}
if(ans>=0x3f3f3f3f3f3f3f3f) ans=-1;
printf("%lld
",ans);
return 0;
}