联合省选2020A题解 d1t1 d1t2 d1t3 d2t1 d2t2 d2t3
不知道怎么想的写了线段树维护最小最大值来找分界点
实际上维护双方的和，然后树状数组二分即可
树状数组二分：从高往低位确定，新加的部分就是tr[s+i^k]
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define low(x) ((x)&-(x))
#define ll long long
#define file
using namespace std;
struct type{
int x,id;
} A[2000001];
int p[21],a[2000001][3],b[2000001],Q,n,i,j,k,l,tp,tot;
ll tr[2][2000001],s1,s2,ans;
char st[21],ch;
void Read(int &x) {x=0;ch=getchar(); while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();}
void Write(ll x) {int i=0; if (!x) {putchar('0');return;} while (x) st[++i]=x%10+'0',x/=10; while (i) putchar(st[i--]);}
bool cmp(type a,type b) {return a.x<b.x;}
void init()
{
fo(i,1,Q) A[i]={a[i][1],i};
sort(A+1,A+Q+1,cmp);
tot=0;
fo(i,1,Q)
{
tot+=i==1 || A[i].x!=A[i-1].x;b[tot]=A[i].x;
a[A[i].id][1]=tot;
}
}
void change(int T,int t,ll s) {while (t<=tot) tr[T][t]+=s,t+=low(t);}
ll get(int T,int t) {ll s=0; while (t) s+=tr[T][t],t-=low(t); return s;}
int main()
{
freopen("icefire.in","r",stdin);
#ifdef file
freopen("icefire.out","w",stdout);
#endif
p[0]=1;
fo(i,1,20) p[i]=p[i-1]*2;
Read(Q);
fo(i,1,Q)
{
Read(tp);
if (tp==1) Read(a[i][0]),Read(a[i][1]),Read(a[i][2]);
else Read(j),a[i][0]=a[j][0],a[i][1]=a[j][1],a[i][2]=-a[j][2];
}
init();
fo(i,1,Q)
{
if (a[i][0]==0)
change(0,a[i][1],a[i][2]);
else
change(1,1,a[i][2]),change(1,a[i][1]+1,-a[i][2]);
if (i==4)
n=n;
l=s1=s2=0;
fd(j,20,0)
if (l+p[j]<=tot && s1+tr[0][l+p[j]]<=s2+tr[1][l+p[j]])
s1+=tr[0][l+p[j]],s2+=tr[1][l+p[j]],l+=p[j];
ans=min(s1,s2);
if (l<tot)
{
s2=get(1,l+1);
if (ans<=s2)
{
ans=s2,s2=l=0;
fd(j,20,0)
if (l+p[j]<=tot && ans<=s2+tr[1][l+p[j]])
s2+=tr[1][l+p[j]],l+=p[j];
}
}
if (!ans) printf("Peace
");
else Write(b[l]),putchar(' '),Write(ans*2),putchar('
');
}
fclose(stdin);
fclose(stdout);
return 0;
}
d1t2
https://www.cnblogs.com/gmh77/p/13170198.html
d1t3
线性基找约束条件，一个数和表示它的数连边（可任意换）
保序回归+网络流
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define inf 10000000000000000ll
#define ull unsigned long long
#define min(a,b) (a<b?a:b)
#define ll long long
#define file
using namespace std;
int v[1001],nx[1001],a[65],b[65],n,m,i,j,k,l;
ull c[1001],p[64],a2[1001],b2[1001];
ll Ans[1001],ans;
struct xxj{
ull a[65],b[65];
int f[65],i,j,k,l;
void build()
{
fo(i,1,m)
{
fo(j,1,64)
if (a[i]&p[j-1])
{
if (!f[j]) {f[j]=i;break;}
else
a[i]^=a[f[j]],b[i]^=b[f[j]];
}
}
}
ull get(ull t)
{
ull s=0;
fo(i,1,64)
if (t&p[i-1])
t^=a[f[i]],s^=b[f[i]];
return s;
}
} A,B;
struct G{
int a[300001][2],ls[1002],cur[1002],b[1001],s1[1001],s2[1001],f[1003],g[1003],tot,len,i,j,k,l,t1,t2;
bool bz[1002],Bz[1002];
ll A[300001],mid;
void NEW(int x,int y,ll z) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;A[len]=z;}
void New(int x,int y,ll z) {NEW(x,y,z),NEW(y,x,0);}
ll dfs(int t,ll flow)
{
ll use=0,w;
int i;
if (t==n+1) return flow;
for (i=cur[t]; i; i=a[i][1])
if (A[i] && f[t]==f[a[i][0]]+1)
{
cur[t]=i;
w=dfs(a[i][0],min(flow-use,A[i]));
A[i]-=w,A[i^1]+=w;
use+=w;
if (flow==use) return use;
}
cur[t]=ls[t];
--g[f[t]];
if (!g[f[t]]) {f[0]=tot+2;return use;}
++f[t];++g[f[t]];
return use;
}
void find()
{
int d[1012],h=0,t=1,i;
d[1]=0;Bz[0]=1;
while (h<t)
{
for (i=ls[d[++h]]; i; i=a[i][1])
if (A[i] && !Bz[a[i][0]])
Bz[a[i][0]]=1,d[++t]=a[i][0];
}
t1=t2=0;
fo(i,1,tot) if (!Bz[b[i]]) s1[++t1]=b[i]; else s2[++t2]=b[i];
}
void work()
{
int i,j;
len=1;
fo(i,1,tot) New(0,b[i],(mid-v[b[i]])*(mid-v[b[i]])),New(b[i],n+1,(mid+1-v[b[i]])*(mid+1-v[b[i]]));
fo(i,1,tot)
{
fo(j,1,m)
{
if (bz[::a[j]] && (a2[b[i]]&p[j-1])) New(::a[j],b[i],inf);
if (bz[::b[j]] && (b2[b[i]]&p[j-1])) New(b[i],::b[j],inf);
}
}
g[0]=tot+2;
while (f[0]<=tot+1)
dfs(0,inf);
find();
bz[0]=ls[0]=cur[0]=g[0]=f[0]=Bz[0]=bz[n+1]=ls[n+1]=cur[n+1]=g[n+1]=f[n+1]=Bz[n+1]=0;
fo(i,1,tot) bz[b[i]]=ls[b[i]]=cur[b[i]]=g[i]=f[b[i]]=Bz[b[i]]=0;tot=0;
}
} G;
void work(int x,int y,int st,int ed)
{
int d[1001],tot=0,mid=(x+y)/2,i,st1,ed1,st2,ed2;
for (i=st; i!=ed; i=nx[i]) d[++tot]=i;d[++tot]=ed;
if (x==y) return;
fo(i,1,tot) G.b[++G.tot]=d[i],G.bz[d[i]]=1;G.mid=mid;
G.work();
fo(i,1,G.t1-1) nx[G.s1[i]]=G.s1[i+1],Ans[G.s1[i]]=mid;Ans[G.s1[G.t1]]=mid;
fo(i,1,G.t2-1) nx[G.s2[i]]=G.s2[i+1],Ans[G.s2[i]]=mid+1;Ans[G.s2[G.t2]]=mid+1;
st1=(G.t1)?G.s1[1]:-1;ed1=G.s1[G.t1];
st2=(G.t2)?G.s2[1]:-1;ed2=G.s2[G.t2];
if (st1>0) work(x,mid,st1,ed1);
if (st2>0) work(mid+1,y,st2,ed2);
}
int main()
{
freopen("shop.in","r",stdin);
#ifdef file
freopen("shop.out","w",stdout);
#endif
p[0]=1;
fo(i,1,63) p[i]=p[i-1]*2;
scanf("%d%d",&n,&m);
fo(i,1,n) scanf("%llu",&c[i]);
fo(i,1,n) scanf("%d",&v[i]);
fo(i,1,m) scanf("%d",&a[i]),A.a[i]=c[a[i]],A.b[i]=p[i-1];A.build();
fo(i,1,m) scanf("%d",&b[i]),B.a[i]=c[b[i]],B.b[i]=p[i-1];B.build();
fo(i,1,n) a2[i]=A.get(c[i]),b2[i]=B.get(c[i]);
fo(i,1,n) nx[i]=i+1;
work(0,1000000,1,n);
fo(i,1,n) ans+=1ll*(v[i]-Ans[i])*(v[i]-Ans[i]);
printf("%lld
",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
d2t1
状压设f[s]表示已放s的代价，把代价拆开+预处理即可，预处理可以少掉自己那一位变成2^22
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) ((a)<(b)?(a):(b))
#define low(x) ((x)&-(x))
#define inf 2000000000
#define ll long long
#define file
using namespace std;
int p[24],a[24][24],A[24][24],b[8388609],f[8388608],F[24][4194304],num[8388608],n,m,K,i,j,k,l,L,L2,ans,s;
char ch;
void Read(int &x) {x=0; ch=getchar(); while (ch<'0' || ch>'9') ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();}
int main()
{
freopen("transfer.in","r",stdin);
#ifdef file
freopen("transfer.out","w",stdout);
#endif
p[0]=1;b[1]=0;
fo(i,1,23) p[i]=p[i-1]*2,b[p[i]]=i;
Read(n);Read(m);Read(K);L=p[m]-1,L2=p[m-1]-1;l=0;
fo(i,1,n) Read(j),++a[l][j],l=j;
fo(i,1,L) num[i]=num[i-low(i)]+1;
fo(i,1,m) fo(j,1,m) A[i][j]=a[i][j]*K;
fo(i,1,m)
{
fo(j,1,m)
if (i!=j)
F[i][0]+=-a[i][j]+A[j][i];
}
fo(i,1,m)
{
fo(j,1,L2)
k=b[low(j)]+1,k+=k>=i,F[i][j]=F[i][j-low(j)]-(-a[i][k]+A[k][i])+(a[k][i]+A[i][k]);
}
memset(f,127,sizeof(f)),f[0]=0;
fo(j,1,L)
{
for (k=j; k; k-=low(k))
{
i=b[low(k)]+1;
f[j]=min(f[j],f[j^p[i-1]]+F[i][(j&(p[i-1]-1))|(((j^p[i-1])^(j&(p[i-1]-1)))>>1)]*num[j]);
}
}
printf("%d
",f[L]);
fclose(stdin);
fclose(stdout);
return 0;
}
d2t2
AGC的题，反过来建trie合并
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define ll long long
#define N 21
#define file
using namespace std;
int tr[12000001][2],a[525011][2],ls[525011],v[525011],p[22],n,i,j,k,l,Len,len;
bool Tr[12000001],Ans[525011][22];
char ch;
ll ans;
void Read(int &x) {x=0;ch=getchar(); while (ch<'0' || ch>'9') ch=getchar(); while (ch>='0' && ch<='9') x=x*10+(ch-'0'),ch=getchar();}
void NEW(int x,int y) {++Len;a[Len][0]=y;a[Len][1]=ls[x];ls[x]=Len;}
void New(int t,int x) {if (!tr[t][x]) tr[t][x]=++len;}
void change(int st,int T,int t,int s)
{
Tr[t]^=1;
if (T==N) return;
Ans[st][T+1]^=s&1;
New(t,s&1),change(st,T+1,tr[t][s&1],s>>1);
}
void swap(int &x,int &y) {int z=x;x=y;y=z;}
void Change(int st,int T,int t)
{
if (tr[t][0]) Ans[st][T+1]^=Tr[tr[t][0]];
if (tr[t][1]) Ans[st][T+1]^=Tr[tr[t][1]];
swap(tr[t][0],tr[t][1]);
if (tr[t][0]) Change(st,T+1,tr[t][0]);
}
void merge(int t1,int t2)
{
Tr[t1]^=Tr[t2];
if (tr[t1][0] && tr[t2][0])
merge(tr[t1][0],tr[t2][0]);
else
if (tr[t2][0]) tr[t1][0]=tr[t2][0];
if (tr[t1][1] && tr[t2][1])
merge(tr[t1][1],tr[t2][1]);
else
if (tr[t2][1]) tr[t1][1]=tr[t2][1];
}
void dfs(int t)
{
int i,j;
for (i=ls[t]; i; i=a[i][1])
{
dfs(a[i][0]);
merge(t,a[i][0]);
fo(j,1,N) Ans[t][j]^=Ans[a[i][0]][j];
}
Change(t,0,t);
change(t,0,t,v[t]);
fo(i,1,N) ans=ans+Ans[t][i]*p[i-1];
}
int main()
{
freopen("tree.in","r",stdin);
#ifdef file
freopen("tree.out","w",stdout);
#endif
p[0]=1;fo(i,1,N) p[i]=p[i-1]*2;
Read(n);
fo(i,1,n) Read(v[i]);
fo(i,2,n) Read(j),NEW(j,i);
len=n;
dfs(1);
printf("%lld
",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
d2t3
用(n=sum_{d|n} varphi(d))拆开，把每条边设做1+w[i][j]x的多项式，做矩阵树后的x项系数就是答案
二项式求逆很简单
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define mod 998244353
#define Mod 998244351
#define ll long long
#define N 152501
#define file
using namespace std;
struct type{ll x,y;} a[31][31],s,Ans;
int A[31][31],b[31],p[N+1],n,m,i,j,k,l,x,y,z,d,len;
ll phi[N+1],ans,Ans2;
bool bz[N+1],f[N+1];
ll qpower(ll a,int b) {ll ans=1; while (b) {if (b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;} return ans;}
type ny(type a) {return {-a.x*qpower(a.y*a.y%mod,Mod)%mod,qpower(a.y,Mod)};}
type operator + (type a,type b) {return {(a.x+b.x)%mod,(a.y+b.y)%mod};}
type operator - (type a,type b) {return {(a.x-b.x)%mod,(a.y-b.y)%mod};}
type operator * (type a,type b) {return {(a.x*b.y+a.y*b.x)%mod,(a.y*b.y)%mod};}
type operator / (type a,type b) {return a*ny(b);}
void init()
{
phi[1]=f[1]=1;
fo(i,2,N)
{
if (!f[i]) p[++len]=i,phi[i]=i-1;
fo(j,1,len)
if (1ll*i*p[j]<=N)
{
f[i*p[j]]=1;
if (!(i%p[j])) {phi[i*p[j]]=phi[i]*p[j];break;}
phi[i*p[j]]=phi[i]*(p[j]-1);
}
else break;
}
}
int main()
{
freopen("count.in","r",stdin);
#ifdef file
freopen("count.out","w",stdout);
#endif
init();
scanf("%d%d",&n,&m);
fo(i,1,m)
{
scanf("%d%d%d",&x,&y,&z),A[x][y]=A[y][x]=z;
j=floor(sqrt(z));
fo(k,1,j) if (!(z%k)) bz[k]=bz[z/k]=1;
}
fo(d,1,N)
if (bz[d])
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
fo(i,1,n)
{
fo(j,1,n)
if (A[i][j] && !(A[i][j]%d))
a[i][j]={-A[i][j],-1},a[i][i]=a[i][i]+type{A[i][j],1};
}
Ans={0,1};
fo(i,1,n-1)
{
fo(j,1,n-1)
if (a[i][j].x || a[i][j].y)
{
if (!b[j])
{
Ans=Ans*a[i][j],a[i][j]=ny(a[i][j]);
fo(k,j+1,n-1) a[i][k]=a[i][k]*a[i][j];
a[i][j]={0,1},b[j]=i;
break;
}
fo(k,j+1,n-1) a[i][k]=a[i][k]-(a[i][j]*a[b[j]][k]);a[i][j]={0,0};
}
}
fo(i,1,n-1) if (!b[i]) break;
if (i<=n-1) continue;
Ans2=Ans.x;
fo(i,2,n-1)
{
fo(j,1,i-1)
if (b[j]>b[i])
Ans2=-Ans2;
}
ans=(ans+Ans2*phi[d])%mod;
}
printf("%lld
",(ans+mod)%mod);
fclose(stdin);
fclose(stdout);
return 0;
}