2018.12.1 Test
题目为2018.1.2雅礼集训。
时间：3.5h
期望得分：100+30+10
实际得分：100(0)+0+10
A 串string(思路)
如果一个串不是回文串，答案是1（我竟然漏了QAQ）。
否则，除了以下三种情况无解外，都能两次消掉：
aaaaa aabaa ababa
判一下就OK了。
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=1e5+5;
char s[N];
inline int read()
{
int now=0,f=1;register char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;
}
bool Check0(int n)
{
int mid=n>>1;
for(int i=1; i<=mid; ++i) if(s[i]!=s[n-i+1]) return puts("1"),0;
return 1;
}
bool Check1(int n)//All the same
{
const char c=s[1];
for(int i=2; i<=n; ++i) if(s[i]!=c) return 1;
puts("-1");
return 0;
}
bool Check2(int n)
{
if(!(n&1)) return 1;
const char c1=s[1],c2=s[2];
for(int i=3; i<n; i+=2) if(s[i]!=c1||s[i+1]!=c2) return 1;
if(s[n]!=c1) return 1;
puts("-1");
return 0;
}
bool Check3(int n)
{
if(!(n&1)) return 1;
s[(n+1)>>1]=s[1];
return Check1(n);
}
int main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
for(int T=read(); T--; )
{
int n=read(); scanf("%s",s+1);
if(Check0(n)&&Check1(n)&&Check2(n)&&Check3(n)) puts("2");
}
return 0;
}
B 变量variable(最小割ISAP)
我们发现一个点如果与它相邻的点取值不同，会造成一个系数*\(2W\)的代价。
想到网络流就好办了。。
比较显然的是拆点，然后建图跑最小费用最大流。但是这样对于限制\(a\leq b，b\leq c\)，有\(a\leq c\)这种传递性，我好像不会判/连边 QAQ。只会暴力搞但也不想写...
费用流做法里的流量其实没啥用，还是直接考虑最大流/最小割。
这样的话就不用拆点了，每个点向\(S\)连容量（即权值）为\(W\)的边，向\(T\)连容量\(-W\)的边，就可以了QAQ。那些\(系数和*w_i\)的代价也加到这两条边上（记它为\(x\)）。为了避免负边可以先让\(Ans\)减去\(|x|\)，然后根据\(x\)的正负确定连边（边权都加个\(|x|\)就消掉负边啦）。
对于代价\(a_i|w_x-w_y|\)，在\(x,y\)间连容量为\(a_i*2W\)的双向边（\(w_x,w_y\)取值不同就会加上这个值）。
对于限制，\(w_x\leq w_y\)就由\(x\)向\(y\)连一条容量\(INF\)的单向边（\(x\)选\(W\)时\(y\)不能选\(-W\)）；\(w_x=w_y\)就连一条\(x\)到\(y\)的双向边，容量同样为\(INF\)；\(w_x<w_y\)就由\(x\)向\(T\)连\(INF\)边，\(S\)向\(y\)连\(INF\)边好了（只能\(x\)取负\(y\)取正）。
另外边权可以都除个\(W\)，最后再乘个\(W\)。
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=507,M=12000;
const int INF=1e9;
int src,des,coef[N],cur[N],H[N],Enum,fr[M],to[M],nxt[M],cap[M],pre[N],lev[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline void AE(int u,int v,int w,int w2)
{
to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum, cap[Enum]=w;
to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum, cap[Enum]=w2;
}
bool BFS()
{
static int q[N];
for(int i=src; i<des; ++i) lev[i]=des+1;
int h=0,t=1; lev[des]=0, q[0]=des;
while(h<t)
{
int x=q[h++];
for(int i=H[x]; i; i=nxt[i])
if(cap[i^1] && lev[to[i]]==des+1) lev[to[i]]=lev[x]+1, q[t++]=to[i];
}
return lev[src]<=des;
}
inline int Augment()
{
int mn=123456789;
for(int i=des; i!=src; i=fr[pre[i]])
mn=std::min(mn,cap[pre[i]]);
for(int i=des; i!=src; i=fr[pre[i]])
cap[pre[i]]-=mn, cap[pre[i]^1]+=mn;
return mn;
}
int ISAP()
{
static int num[N];
if(!BFS()) return 0;
for(int i=src; i<=des; ++i) cur[i]=H[i],++num[lev[i]];
int x=src,res=0;
while(lev[x]<=des)
{
if(x==des) x=src,res+=Augment();
bool can=0;
for(int i=cur[x]; i; i=nxt[i])
if(cap[i] && lev[to[i]]==lev[x]-1)
{
can=1, cur[x]=i, pre[x=to[i]]=i;
break;
}
if(!can)
{
int mn=des;
for(int i=H[x]; i; i=nxt[i])
if(cap[i]) mn=std::min(mn,lev[to[i]]);
if(!--num[lev[x]]) break;
++num[lev[x]=mn+1], cur[x]=H[x];
if(x!=src) x=fr[pre[x]];
}
}
return res;
}
void Work()
{
int n=read(),W=read(),P=read(),Q=read();
//Clear
Enum=1, memset(H,0,sizeof H);
//Init
for(int i=1; i<=n; ++i) coef[i]=1;
for(int i=1,x,y,z,a,b,c,d,e,f; i<=P; ++i)
{//a:0 b:1 c:2 d:3 e:4 f:5
x=read(),y=read(),z=read(),a=read(),b=read(),c=read(),d=read(),e=read(),f=read();
AE(x,y,a<<1,a<<1), AE(y,z,b<<1,b<<1), AE(z,x,c<<1,c<<1);
coef[x]+=d-f, coef[y]+=e-d, coef[z]+=f-e;
}
//limit
src=0, des=n+1;
for(int i=1,x,y; i<=Q; ++i)
{
x=read(),y=read();
switch(read())
{
case 0: AE(x,y,INF,0); break;
case 1: AE(x,y,INF,INF); break;
case 2: AE(x,des,INF,0), AE(src,y,INF,0); break;
}
}
//AE
int ans=0;
for(int i=1; i<=n; ++i)
{
ans-=std::abs(coef[i]);
if(coef[i]>0) AE(i,des,coef[i]<<1,0);
else AE(src,i,-coef[i]<<1,0);
}
ans+=ISAP();
printf("%I64d\n",1ll*ans*W);
}
int main()
{
freopen("variable.in","r",stdin);
freopen("variable.out","w",stdout);
for(int T=read(); T--; Work());
return 0;
}
C 取石子stone(思路 博弈)
不妨假设\(a<b\)。
每堆石子先对\(a+b\)取模（\(≥a+b\)时先手取了后手接着取没有影响啊），然后可以分为4种：
\((1)\) \(x_i<a\)，没用。
\((2)\) \(a≤x_i<b\)，只要存在则\(A\)必胜。
\((3)\) \(b≤x_i<2a\)，只和奇偶性有关。
\((4)\) \(2a≤x_i<a+b\ (b≤x_i)\)，\((4)\)存在至少\(2\)个则\(A\)必胜，存在\(1\)个且\((3)\)为偶数则先手必胜，存在\(1\)个且\((3)\)为奇数则\(A\)必胜，不存在且\((3)\)为奇数则先手必胜，不存在且\((3)\)为偶数则后手必胜。
时间复杂度\(O(n)\)。
orz mjt差点想出正解。
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define mod 1000000007
typedef long long LL;
const int N=1e5+5;
inline int read()
{
int now=0,f=1;register char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;
}
int main()
{
static int pw[N];
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
int n=read(),A=read(),B=read();
bool Flag=0;
if(A>B) std::swap(A,B), Flag=1;
int t[5]={0,0,0,0,0},ans[5]={0,0,0,0,0};
for(int i=1; i<=n; ++i)
{
int x=read()%(A+B);
++t[1+(x>=A)+(x>=B)+(x>=A+A&&x>=B)];//2A<=x<B 就是(2)啊
}
pw[0]=1;
for(int i=1; i<=n; ++i) pw[i]=pw[i-1]<<1, pw[i]>=mod&&(pw[i]-=mod);
//其它任选的不要忘统计或者重复统计QAQ
ans[1]=(1ll*(pw[t[2]]-1)*pw[t[3]+t[4]]%mod+1ll*(pw[t[4]]-t[4]-1+mod)*pw[t[3]]%mod+1ll*t[4]*(t[3]?pw[t[3]-1]:0)%mod)%mod;
ans[3]=((t[3]?pw[t[3]-1]:0)+1ll*t[4]*(t[3]?pw[t[3]-1]:1)%mod)%mod;
ans[4]=t[3]?pw[t[3]-1]:1;
for(int i=1; i<=4; ++i) ans[i]=1ll*ans[i]*pw[t[1]]%mod;
if(Flag) std::swap(ans[1],ans[2]);
for(int i=1; i<=4; ++i) printf("%d ",ans[i]);
return 0;
}
考试代码
B
写了费用流。然而边都搞好了不会处理限制的传递性TAT
暴力也挂了TAT（for一遍限制不就行了...）
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int INF=1e9;
const LL INFll=0x3f3f3f3f3f3f3f3f;
inline int read()
{
int now=0,f=1;register char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;
}
namespace Subtask1
{
const int N=100;
int w[N],n,W,P,Q,Enum,H[N],nxt[N],to[N],opt[N];
LL Ans;
struct Node{
int x,y,z,a[6];
inline void Init() {x=read(),y=read(),z=read(); for(int i=0; i<6; ++i) a[i]=read();}
inline LL Calc()
{
int wx=w[x],wy=w[y],wz=w[z];
return 1ll*a[0]*std::abs(wx-wy)+a[1]*std::abs(wy-wz)+a[2]*std::abs(wz-wx)+a[3]*(wx-wy)+a[4]*(wy-wz)+a[5]*(wz-wx);
}
}A[N];
inline void AE(int o,int v,int u)
{
if(u<v) std::swap(u,v), o+=3;
to[++Enum]=v, opt[Enum]=o, nxt[Enum]=H[u], H[u]=Enum;
}
void DFS(int x,int sum)
{
if(x>n)
{
LL ans=0;
for(int i=1; i<=P; ++i) ans+=A[i].Calc();
// puts("Now:");
// for(int i=1; i<=n; ++i) printf("%d ",w[i]); puts("");
// printf("ans:%I64d sum:%d\n",ans,sum);
Ans=std::min(Ans,ans+sum);
return;
}
int need=0;
for(int i=H[x]; i; i=nxt[i])
{
int equ=0;
if(!opt[i])
if(w[to[i]]==-W) equ=-W;
else ;
else if(opt[i]==1) equ=w[to[i]];
else if(opt[i]==2)
if(w[to[i]]==-W) return;
else equ=-W;
else if(opt[i]==3)
if(w[to[i]]==W) equ=W;
else ;
else if(opt[i]==4) equ=w[to[i]];
else if(opt[i]==5)
if(w[to[i]]==W) return;
else equ=W;
// printf("%d->%d(%d) equ:%d need:%d\n",x,to[i],opt[i],equ,need);
if(!need) need=equ;
else if(equ&&equ!=need) return;
}
if(!need) w[x]=W, DFS(x+1,sum+W), w[x]=-W, DFS(x+1,sum-W);
else w[x]=need, DFS(x+1,sum+need);
}
void Main(int n,int W,int P,int Q)
{
Enum=0, memset(H,0,sizeof H);
Subtask1::n=n, Subtask1::W=W, Subtask1::P=P, Subtask1::Q=Q;
for(int i=1; i<=P; ++i) A[i].Init();
for(int i=1; i<=Q; ++i) AE(read(),read(),read());
Ans=1e15, DFS(1,0), printf("%I64d\n",Ans);
}
}
//-----
const int N=3005,M=1e5;
int src,des,val[N][N],coef[N],dgr[N],cur[N],H[N],Enum,to[M],nxt[M],cap[M];
LL cost[M],dis[N],Cost;
bool ban[N][N],vis[N];
//std::vector<int> b1[N],b2[N],s1[N],s2[N];//
inline void AE(int u,int v,int w,LL c)
{
// printf("%d->%d cap:%d cost:%I64d\n",u,v,w,c);
++dgr[u];
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, cap[Enum]=w, cost[Enum]=c;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, cap[Enum]=0, cost[Enum]=-c;
}
bool SPFA()
{
static std::queue<int> q;
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
dis[src]=0, q.push(src);
while(!q.empty())
{
int x=q.front(); q.pop(), vis[x]=0;
for(int i=H[x],v; i; i=nxt[i])
if(cap[i]&&dis[v=to[i]]>dis[x]+cost[i])
dis[v]=dis[x]+cost[i], !vis[v]&&(q.push(v),vis[v]=1);
}
return dis[des]<INFll;
}
bool DFS(int x)
{
if(x==des) return 1;
vis[x]=1;
for(int &i=cur[x]; i; i=nxt[i])
if(!vis[to[i]]&&cap[i]&&dis[to[i]]==dis[x]+cost[i])
if(DFS(to[i]))
return --cap[i],++cap[i^1],Cost+=cost[i],1;
return 0;
}
LL MCMF()//GG
{
Cost=0; int flow=0;
while(SPFA())
{
for(int i=src; i<=des; ++i) cur[i]=H[i];
while(DFS(src)) ++flow;
}
// printf("flow:%d ",flow);
return std::abs(Cost);
}
void Work()
{
int n=read(),W=read(),P=read(),Q=read();
if(n<=17) {Subtask1::Main(n,W,P,Q); return;}
//Clear
Enum=1, memset(H,0,sizeof H);
memset(dgr,0,sizeof dgr), memset(coef,0,sizeof coef), memset(val,0,sizeof val), memset(ban,0,sizeof ban);
//Init
for(int i=1,x,y,z,a,b,c,d,e,f; i<=P; ++i)
{//a:0 b:1 c:2 d:3 e:4 f:5
x=read(),y=read(),z=read(),a=read(),b=read(),c=read(),d=read(),e=read(),f=read();
val[x][y]+=a, val[y][x]+=a, val[y][z]+=b, val[z][y]+=b, val[x][z]+=c, val[z][x]+=c;
coef[x]+=d-f, coef[y]+=e-d, coef[z]+=f-e;
}
for(int i=1; i<=n; ++i) ++coef[i];
// for(int i=1; i<=n; ++i) printf("coef[%d]=%d\n",i,coef[i]);
//limit
int n2=n+n;//0:W n:-W 2n:origin
for(int i=1; i<=Q; ++i)
{
int x=read(),y=read(),opt=read();
if(x>y) std::swap(x,y), opt+=3;
switch(opt)
{
case 0: ban[x][y+n]=1; break;//x<=y
case 1: ban[x][y+n]=ban[x+n][y]=1; break;
case 2: ban[x][y]=ban[x][y+n]=ban[x+n][y+n]=1; break;
case 3: ban[x+n][y]=1; break;//x>=y
case 4: ban[x][y+n]=ban[x+n][y]=1; break;
case 5: ban[x][y]=ban[x+n][y]=ban[x+n][y+n]=1; break;
}
}
//AE
int src=0,des=n+n2+2; ::src=src, ::des=des;
LL W2=W<<1;
for(int i=1; i<=n; ++i)
for(int j=i+1; j<=n; ++j)
if(val[i][j])
{
// printf("val[%d][%d]=%d\n",i,j,val[i][j]);
int x=i,y=j;
if(!ban[x][y]) AE(x,y,INF,0);
x=i+n,y=j;
if(!ban[x][y]) AE(x,y,INF,W2*val[i][j]);
x=i,y=j+n;
if(!ban[x][y]) AE(x,y,INF,W2*val[i][j]);
x=i+n,y=j+n;
if(!ban[x][y]) AE(x,y,INF,0);
}
for(int i=1; i<=n; ++i) AE(src,i+n2,1,0), AE(i+n2,i,1,1ll*coef[i]*W), AE(i+n2,i+n,1,-1ll*coef[i]*W);
for(int i=1; i<=n; ++i) if(!dgr[i]) AE(i,des,INF,0), AE(i+n,des,INF,0);
//Get_Ans
printf("%I64d\n",MCMF());
}
int main()
{
freopen("variable.in","r",stdin);
// freopen("variable.out","w",stdout);
for(int T=read(); T--; Work());
return 0;
}
C
\(a=b\)的10分就是求异或和为0的方案数，只需要求下组合就可以了，但是没想到（orz mjt）抄了zzx的代码（orz zzx）。
#include <cstdio>
#include <cctype>
#include <bitset>
#include <algorithm>
#define gc() getchar()
#define mod 1000000007
typedef long long LL;
const int N=1e5+5;
int Ans[5],X[N],w1[N],w2[N];
inline int read()
{
int now=0,f=1;register char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;
}
inline int FP(int x,int k)
{
int t=1;
for(; k; k>>=1,x=1ll*x*x%mod)
if(k&1) t=1ll*t*x%mod;
return t;
}
namespace Subtask3
{//orz zzx
int n,A[N];
std::bitset<105>a[32];
void Gauss(int equ ,int var) {
int r , c , t ;
for(r = c = 1;r <= equ && c <= var;++ r ,++ c) {
t = r;
for(;t < equ;++ t) if(a[t][c]) break ;
if(t == equ) {
-- r ;continue ;
} else swap(a[t] , a[r]);
for(int i = r + 1;i <= equ;++ i) if (a[i][c]) a[i] ^= a[r];
}
int n = var - r , ans = 1;
for(int i = 1;i <= n;++ i) {
ans <<= 1 ;ans %= mod;
}
printf("0 0 %d %d\n",(FP(2,Subtask3::n)+mod-ans)%mod,ans);
}
void Solve(int n,int A)
{
Subtask3::n=n;
for(int i=1; i<=n; ++i)
{
int x=read()/A;
for(int j=1; j<=31; ++j) a[j][i]=x>>j&1;
}
Gauss(31,n);
}
}
int main()
{
// freopen("stone.in","r",stdin);
// freopen("stone.out","w",stdout);
int n=read(),A=read(),B=read();
if(A==B) return Subtask3::Solve(n,A),0;
bool Flag=0;
if(A>B) std::swap(A,B), Flag=1;
for(int i=1; i<=n; ++i)//写着写着不想写了
{
X[i]=read();
if(X[i]<A) continue;
if(X[i]>=A&&X[i]<B) {w1[i]=X[i]/A, w2[i]=-w1[i]; continue;}
int t1=(X[i]-A)%(A+B),t2=(X[i]-B)%(A+B);
w1[i]=1+t1/A, w2[i]=1+t2/B-t2%B/A;
}
printf("%d %d %d %d\n",Flag?0:FP(2,n),Flag?FP(2,n):0,0,0);
return 0;
}