[9018]1930 国家
题目大意：给定A、B序列，A序列中的数若满足a xor b%2=1则连边，B序列中数若满足a xor b%2=0或a or b二进制下有奇数个1则连边，再给出A和B的连边关系，求最大团。（数据组1：A<=80，B<=100；数据组2：A<=5，B<=1500）
思路：这题是本校以前某次测试的题，当时看了看感觉不可做就跳过了……观察发现，最大团中A序列的点不会超过2个（因为a和b必须一奇一偶才能连边，奇或偶超过1个必然不是团），于是可以先枚举取A中的哪些点，然后取出相连的B中的点，按奇偶分成二分图，考虑最小割，若二分图两边一对点或起来有偶数个1则不能一起选入答案，连INF，然后跑一遍模板就能A了。复杂度O（能过）。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read() { int x=0;char c; while((c=getchar())<'0'||c>'9'); for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+c-'0'; return x; } #define MA 80 #define MB 1500 #define MV 1500 #define ME 562500 #define S MV+1 #define T MV+2 #define INF 0x3fffffff struct edge{int nx,t,w;}e[ME*2+5]; int h[MV+5],en,d[MV+5],q[MV+5],qn,c[MV+5]; int g[MA+5][MB+5],va[MA+5],vb[MB+5],ql[MB+5],qln,qr[MB+5],qrn,s[1<<16]; inline void ins(int x,int y,int w) { e[++en]=(edge){h[x],y,w};h[x]=en; e[++en]=(edge){h[y],x,0};h[y]=en; } int bfs() { int i,j; memset(d,0,sizeof(d)); for(d[q[i=qn=0]=S]=1;i<=qn;c[q[i]]=h[q[i]],++i)for(j=h[q[i]];j;j=e[j].nx) if(e[j].w&&!d[e[j].t])d[q[++qn]=e[j].t]=d[q[i]]+1; return d[T]; } int dfs(int x,int r) { if(x==T)return r; int u=0,k; for(int&i=c[x];i;i=e[i].nx)if(e[i].w&&d[e[i].t]==d[x]+1) { k=dfs(e[i].t,r-u<e[i].w?r-u:e[i].w); u+=k;e[i].w-=k;e[i^1].w+=k; if(u==r)return r; } return d[x]=0,u; } inline int cal(int x){return s[x>>16]+s[x&((1<<16)-1)];} int dinic() { int i,j,r=0; memset(h,0,sizeof(h));en=1; for(i=1;i<=qln;++i)ins(S,i,1); for(i=1;i<=qrn;++i)ins(i+qln,T,1); for(i=1;i<=qln;++i)for(j=1;j<=qrn;++j) if(cal(ql[i]|qr[j])%2==0)ins(i,j+qln,INF); while(bfs())r+=dfs(S,INF); return r; } int main() { int t=read(),a,b,m,i,j,k,ans; for(i=0;i<16;++i)for(j=1<<i;j<1<<i+1;++j)s[j]=s[j-(1<<i)]+1; while(t--) { a=read();b=read();m=read(); for(i=1;i<=a;++i)va[i]=read(); for(i=1;i<=b;++i)vb[i]=read(); memset(g,0,sizeof(g)); while(m--)i=read(),g[i][read()]=1; for(qln=qrn=0,i=1;i<=b;++i)(vb[i]&1?ql[++qln]:qr[++qrn])=vb[i]; ans=b-dinic(); for(i=1;i<=a;++i) { for(qln=qrn=0,j=1;j<=b;++j)if(g[i][j]) (vb[j]&1?ql[++qln]:qr[++qrn])=vb[j]; ans=max(ans,qln+qrn+1-dinic()); } for(i=1;i<=a;++i)for(j=i+1;j<=a;++j)if(va[i]%2!=va[j]%2) { for(qln=qrn=0,k=1;k<=b;++k)if(g[i][k]&&g[j][k]) (vb[k]&1?ql[++qln]:qr[++qrn])=vb[k]; ans=max(ans,qln+qrn+2-dinic()); } printf("%d ",ans); } }
[9018]1667 吴桐学长和网管
题目大意：从1~M中选出N个不同的数，求其倒数和等于X/Y的方案数。（N,M<=50，X,Y<=100，保证方案数不超过10^5）
思路：好像这题正解直接搜索剪枝就过了？我看到这题就想折半搜索，先枚举前M/2，然后Hash存起来，再枚举后M/2算答案，精度有点玄学我手写了个分数类型（不知道会不会爆LL），一开始用的std::map，1秒多才过，我就把题目时限从1s改成2s了哈哈哈，后来手写了个期望O(1)的map，总算卡到1s内。复杂度期望O(2^(M/2))
#include<cstdio> #define MOD 523333 #define ME 1000000 int gcd(int x,int y){return y?gcd(y,x%y):x;} struct fs { long long x,y; friend bool operator<(fs a,fs b){return a.x*b.y<b.x*a.y;} fs operator+(fs b) { int xx=x*b.y+b.x*y,yy=y*b.y,g=gcd(xx,yy); return (fs){xx/g,yy/g}; } }f; struct edge{int nx,t;fs s;}e[ME+5]; int n,ans,en; inline void ins(int*h,int x,fs s){e[++en]=(edge){h[x],0,s};h[x]=en;} struct map { int h[MOD]; int&operator[](fs a) { int x=((a.x*23333+a.y)%MOD+MOD)%MOD,i; for(i=h[x];i;i=e[i].nx)if(e[i].s.x==a.x&&e[i].s.y==a.y)return e[i].t; ins(h,x,a);if(en>ME)puts("X");return e[en].t; } }mp[26]; void dfs1(int x,int h,int k,fs s) { if(k>n||f<s)return; if(x>h){++mp[k][s];return;} dfs1(x+1,h,k,s);dfs1(x+1,h,k+1,s+(fs){1,x}); } void dfs2(int x,int h,int k,fs s) { if(k>n||f<s)return; if(x>h){ans+=mp[n-k][f+(fs){-s.x,s.y}];return;} dfs2(x+1,h,k,s);dfs2(x+1,h,k+1,s+(fs){1,x}); } int main() { int m,x,y; scanf("%d%d%d%d",&n,&m,&f.x,&f.y); dfs1(1,m>>1,0,(fs){0,1});dfs2((m>>1)+1,m,0,(fs){0,1}); printf("%d",ans); }