话说好久没写题（解）了。。
先贴份题解：http://wjmzbmr.com/archives/hnoi-2013-题解/（LJ神题解。。Lazycal表示看不懂。。）
以下是Lazycal's题解：
对于一个得分序列，可以发现不论如何排列，答案都是一样的。而且n的得分序列可以由n-1的推来。于是，我们可以搜索第一个队伍与其他队伍的比赛结果，由比赛结果得出n-1支队伍的得分序列，递归搜索。然后用每个队伍的得分和队伍个数作为状态，对每个状态进行压缩，利用最小表示法。由于每个队伍最多只能得27分，所以状态总数不超过28^9/(9!)*2（因为只能存在一个0）为千万级别，可以接受。
/************************************************************** Problem: 3139 User: lazycal Language: C++ Result: Accepted Time:732 ms Memory:1868 kb ****************************************************************/ #include <cstdio> #include <algorithm> #include <functional> #include <map> const int MOD=1000000000+7; int n; std::map<long long,long long>Map; struct Status { int a[11]; long long hash() { long long res=0; for (int i=0;i<=n;++i) res=res*28+a[i]; return res; } void sort() { std::sort(a+n-a[0]+1,a+1+n/*,std::greater<int>()*/); } }start,bound; long long dfs(const int step,Status now) { if (now.a[0] == 1) return Map[now.hash()]=-1; if (now.a[n-now.a[0]+1] > 3*(n-step+1)) return -1; if (step > n) { --now.a[0]; now.sort(); if (Map[now.hash()]) return Map[now.hash()]; return dfs(n-now.a[0]+2,now); } long long res=0,tmp; int idx=n-now.a[0]+1; if (now.a[idx] >= 3) { now.a[idx] -= 3; tmp=dfs(step+1,now); if (tmp!=-1) (res+=tmp)%=MOD; now.a[idx] +=3; } if (now.a[idx] >= 1 && now.a[step] >= 1) { now.a[idx] -= 1; now.a[step] -= 1; tmp=dfs(step+1,now); if (tmp!=-1) (res+=tmp)%=MOD; now.a[idx] += 1; now.a[step] += 1; } if (now.a[step] >= 3) { now.a[step] -= 3; tmp=dfs(step+1,now); if (tmp!=-1) (res+=tmp)%=MOD; now.a[step] += 3; } res=res?res:-1; if (step == idx+1) Map[now.hash()]=res; return res; } int main() { #ifndef ONLINE_JUDGE freopen("3139.in","r",stdin); freopen("3139.out","w",stdout); #endif scanf("%d",&n); if (n==1) {puts("1");return 0;} for (int i=1;i<=n;++i) scanf("%d",start.a+i); start.a[0]=n; start.sort(); bound.a[0]=1; bound.a[n]=0; Map[bound.hash()]=1; printf("%lld\n",dfs(2,start)); } 代码(………………将就着用吧,两种代码高亮的混合使用…………)
假设我们选择x*y*z(x<y<z)这样一块区域，则费用为x。也就是说，我们可以视作x次的1*y*z。又因为a*b*c<=5000，所以min{a,b,c}<=17。不妨设min{a,b,c}=a。因此答案<=a。一开始还以为只要把需要消的1*b*c消了就可以了。结果去网上查了题解才知道这样并不一定是最优的……
正解应当是用2^a枚举哪个1*b*c要取，然后转化成二维的最小棋盘覆盖。最小棋盘覆盖就是用最少的行或列把指定点覆盖。没错，这个我也不会……
膜拜了abcdabcd987的题解后才明白。其实是最小点覆盖的模型。只要把行和列拆开，作为二分图的X和Y顶点，然后对于需要覆盖的点从所属的行连向列即可。
/************************************************************** Problem: 3140 User: lazycal Language: C++ Result: Accepted Time:1192 ms Memory:1320 kb ****************************************************************/ #include <cstdio> #include <algorithm> const int N=5000+9; int ans,a,b,c,T,vis[N],match[N],num,son[N],ec,times; bool t[N]; struct Edge{int link,next;}es[N*10]; inline void addedge(const int x,const int y) { es[++ec].next=son[x]; es[ec].link=y; son[x]=ec; } struct point { int x,y,z; point(const int _x=0,const int _y=0,const int _z=0):x(_x),y(_y),z(_z) { if (a<=b && a<=c) std::swap(x,x); else if (b<=a && b<=c) std::swap(x,y); else std::swap(x,z); } }one[N]; bool find(const int u) { for (int i=son[u];i;i=es[i].next) { const int v=es[i].link; if (vis[v]==times) continue; vis[v]=times; if (!match[v]/*BUGS!!!*/ || find(match[v])) { match[v]=u; return 1; } } return 0; } void dfs(const int step,int cnt) { if (cnt>=ans) return; if (step>a) { ec=0; for (int i=1;i<=b;++i) son[i]=0; for (int i=0;i<num;++i) if (!t[one[i].x]) addedge(one[i].y,one[i].z); for (int i=1;i<=c;++i) match[i]=0; for (int i=1;i<=b;++i) { ++times; if ((cnt+=find(i))>=ans) return; } ans=cnt; return; } t[step]=1; dfs(step+1,cnt+1); t[step]=0; dfs(step+1,cnt); } int main() { #ifndef ONLINE_JUDGE freopen("3140.in","r",stdin); freopen("3140.out","w",stdout); #endif scanf("%d",&T); while (T--) { scanf("%d%d%d",&a,&b,&c); num=0; for (int i=1;i<=a;++i) for (int j=1;j<=b;++j) for (int k=1,x;k<=c;++k) { scanf("%d",&x); if (x) one[num++]=point(i,j,k); } if (a<=b && a<=c) std::swap(a,a); else if (b<=a && b<=c) std::swap(a,b); else std::swap(a,c); ans=a; dfs(1,0); printf("%d\n",ans); } }
这题非常神！的的确确是个好题！
这题我是看着http://tieba.baidu.com/p/2283515454?pid=31800289139&cid=0#318002891399楼的回复以及http://cxjyxx.me/?p=329的题解才懂的……表示自己太弱了……
注：以下a[i],b[i],n,m如题目所述。
首先我们考虑特殊情况，并将b[i]为0的项赋值为-1，令S为所有数之和：
全1。此时不难发现答案是|S|/m上取整。全-1。同上，为|S|/m上取整。一半1，一半-1。我们将较少的1or-1与另一边抵消。如 1 1 1 1 1 -1 -1 ------> 1 1 1 (1 1 -1 -1)，这样就跟上面的大概一样了。其它情况也差不多。猜测：ans=|S|/m上取整(S!=0)。
答案：
ans>=|S|/m上取整，这很显然。m<=|S|:不妨设S>0，则将所有的-1根附近的1消掉，最终便只剩1了，ans=|S|/m上取整。m>|S|:令s[i]=b[i]+b[i+1]+...+b[n] S=0: 若s[i]=0的个数>=m,则ans=0，此时取最后一个点和后m-1个s[i]=0的点即可。否则ans=1。因为若ans要为0，则所选的最后一个点必须满足s[i]=0（因为s[i]即为最后的旅途），倒二个也是，依此类推，所选的点s[i]都为0。但s[i]=0的个数<m，所以ans>=1。数据构造：观察s数组，必定是0 1……1 0……0 1……1 0。也就是像一个个小山一样。每次取一条等高线，就可符合题意。S!=0:我们首先选出|S|个数，这步同2。剩下的便是一个个与上一个问题一样的子问题了。字典序：
S=0 且 m<= s[i]=0的个数：此时只要在s[i]=0的所有i中跑单调队列即可。即维护队列里面a[i]从小到大，然后按照输入顺序入队，只要后面s[i]=0的个数还足够，就一直入队。其它情况：这个比较麻烦。假设我们上一次选了a[last],则下次的i需满足abs(s[last+1]-s[i])<=ans 且 s[i+1]/m'上取整<=ans(m'为剩下的天数) 且 n-i>=m，就相当于一个子问题。于是，可以按s[i]分类，为每个s[i]开一个队列，维护队列a[i]单调递増，只要后面的个数够，就不断入队。选的时候从s[last]-ans到s[last]+ans枚举，先把下标<last的弹出，然后选出a[i]最小的一个。详见代码。 /************************************************************** Problem: 3141 User: lazycal Language: C++ Result: Accepted Time:2696 ms Memory:41820 kb ****************************************************************/ #include <cstdio> #include <cstdlib> #include <cmath> #include <queue> #define _(x) static_cast<double>(x) #define __(x) static_cast<int>(x) const int N=500000+9; int n,m,sum[N],cnt[N],a[N],tot; struct node{int l,r,x;}t[N*2]; int newnode(const int l,const int r,const int x) { t[++tot].x=x; t[tot].l=l; t[tot].r=r; return tot; } class Queue { int be,en,len; public: void push_back(int x) { if (!len) be=en=newnode(0,0,x); else t[en].r=newnode(en,0,x),en=t[en].r; ++len; } bool empty(){return !len;} int front(){return t[be].x;} int back(){return t[en].x;} void pop_back() { en=t[en].l; --len; } void pop_front() { be=t[be].r; --len; } void push(int x) { while (!empty() && a[back()]>a[x]) pop_back(); push_back(x); } }Qu[N*2],*qu=Qu+N,Q[N*2],*q=Q+N; int Min(const int x,const int y) { if (a[x]<a[y]) return x; return y; } int main() { #ifndef ONLINE_JUDGE freopen("3141.in","r",stdin); freopen("3141.out","w",stdout); #endif scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) { scanf("%d%d",a+i,sum+i); if (!sum[i]) sum[i] = -1; } for (int i=n-1;i;--i) sum[i] += sum[i+1]; for (int i=n;i;cnt[i] += cnt[i+1], --i) if (!sum[i]) ++cnt[i]; int S = sum[1], d = S ? (abs(S) - 1)/m + 1 : cnt[1] < m; cnt[n+1]=-1; if (!d) { for (int i=1,j=2; i<m; ++i) { for (; cnt[j+1]>=m-i; ++j) if (!sum[j+1]) q[0].push(j); printf("%d ",a[q[0].front()]); q[0].pop_front(); } }else { a[n+1]=n+1; int la = 0; for (int i=2; i<=n; ++i) qu[sum[i]].push_back(i-1); for (int i=1; i<m; ++i) { int ans = n+1; for (int j=sum[la+1]-d; j<=sum[la+1]+d; ++j) { if (__(ceil(_(abs(j))/(m-i))) > d) continue; for (; !qu[j].empty() && n-qu[j].front() >= m-i; qu[j].pop_front()) /*printf("test: %d\n",qu[j].front()),*/if (qu[j].front() > la) q[j].push(qu[j].front()); for (; ! q[j].empty() && q[j].front() <= la; q[j].pop_front()); if (!q[j].empty()) ans = Min(ans,q[j].front()); } la = ans; printf("%d ",a[ans]); } } printf("%d",a[n]); }
这题也不会……实在是太弱了
令a[i]为相邻两天股票价格之差，可以发现对于一个a序列，对ans的贡献是N-a[1]-a[2]-...-a[K-1]。于是答案就是N*M^(K-1)-M*(M+1)/2*M^(K-2)*(K-1)
/************************************************************** Problem: 3142 User: lazycal Language: C++ Result: Accepted Time:0 ms Memory:804 kb ****************************************************************/ #include <cstdio> long long P; long long power(long long x,int k) { long long res=1; for (;k;x=x*x%P,k/=2) if (k&1) res=res*x%P; return res; } int main() { #ifndef ONLINE_JUDGE freopen("3142.in","r",stdin); freopen("3142.out","w",stdout); #endif //N*M^(K-1)-M*(M+1)/2*M^(K-2)*(K-1) long long N,K,M; scanf("%lld%lld%lld%lld",&N,&K,&M,&P); if (K==1) {printf("%lld\n",N%P);return 0;} long long tmp=power(M,K-2),ans=(N%P*tmp%P*M%P-M*(M+1)/2%P*tmp%P*(K-1)%P)%P; printf("%lld\n",(ans+P)%P); }
这题……不讲了……高斯消元……
/************************************************************** Problem: 3143 User: lazycal Language: C++ Result: Accepted Time:1008 ms Memory:6880 kb ****************************************************************/ #include <cstdio> #include <cmath> #include <algorithm> const int N=500+9,M=N*N; const double EPS = 1e-9; struct edge{int u,v;}es[M]; double times[M],a[N][N]; int d[N],n,m; void Guass(int equ,int val) { for (int col = 1, row = 1; col <= val; ++col, ++row) { int maxr = row; for (int i = row + 1; i <= equ; ++i) if (fabs(a[i][col]) > fabs(a[maxr][col])) maxr = i; if (maxr != row) for (int i = col; i <= val + 1; ++i) std::swap(a[maxr][i],a[row][i]); for (int i = col + 1; i <= val + 1; ++i) a[row][i] /= a[row][col]; a[row][col] = 1; for (int i = 1; i <= equ; ++i) if (i != row) { for (int j = col + 1; j <= val + 1; ++j) a[i][j] -= a[i][col]*a[row][j]; a[i][col]=0; } } } int main() { #ifndef ONLINE_JUDGE freopen("3143.in","r",stdin); freopen("3143.out","w",stdout); #endif scanf("%d%d",&n,&m); for (int i=1;i<=m;++i) { scanf("%d%d",&es[i].u,&es[i].v); ++d[es[i].u]; ++d[es[i].v]; } for (int i=1;i<=m;++i) { a[es[i].u][es[i].v]=-static_cast<double>(1)/d[es[i].v]; a[es[i].v][es[i].u]=-static_cast<double>(1)/d[es[i].u]; } for (int i=1;i<n;++i) a[i][i]=1,a[i][n]=0; a[n][n]=0; a[1][n]=1; Guass(n-1,n-1); for (int i=1;i<=m;++i) times[i]=a[es[i].u][n]/d[es[i].u]+a[es[i].v][n]/d[es[i].v]; std::sort(times+1,times+1+m); double ans=.0; for (int i=1;i<=m;++i) ans+=times[i]*(m-i+1); printf("%.3f\n",ans); }
网络流最小割。增加一层，然后每层向上层连一条边，容量为下层点权。对于第k层的点，每个点都向k-d层连一条容量为无穷大的边。源向底层每个点连容量为无穷大的边，顶层向汇连容量为无穷大的边。然后跑一遍最小割。
/************************************************************** Problem: 3144 User: lazycal Language: C++ Result: Accepted Time:964 ms Memory:9260 kb ****************************************************************/ #include <cstdio> #include <cstring> #include <algorithm> const int N=65602,INF=0x7fffffff; int src,sink,Vc,cnt[N],dis[N],ec,p,q,r,d,son[N]; struct Edge { int next,v,f; }es[N*10]; inline int node(const int x,const int y,const int z){return x*p*q+y*q+z;} inline void addedge(const int x,const int y,const int z) { es[ec].v=y; es[ec].f=z; es[ec].next=son[x]; son[x]=ec++; } inline void Addedge(const int x,const int y,const int z){addedge(x,y,z);addedge(y,x,0);} int sap(const int u,const int aug) { if (u==sink) return aug; int sum=0,mindis=Vc; for (int i=son[u];i!=-1;i=es[i].next) { const int v=es[i].v; if (es[i].f && dis[v]+1==dis[u]) { int t=sap(v,std::min(aug-sum,es[i].f)); sum+=t; es[i].f-=t; es[i^1].f+=t; if (sum==aug || dis[src]>=Vc) return sum; } if (es[i].f && mindis>dis[v]) mindis=dis[v]; } if (!sum) { if (!--cnt[dis[u]]) dis[src]=Vc; ++cnt[dis[u]=mindis+1]; } return sum; } int max_flow() { cnt[0]=Vc; int flow=0; while (dis[src]<Vc) flow+=sap(src,INF); return flow; } int main() { #ifndef ONLINE_JUDGE freopen("3144.in","r",stdin); freopen("3144.out","w",stdout); #endif scanf("%d%d%d%d",&p,&q,&r,&d); memset(son,-1,sizeof son); for (int i=0;i<r;++i) for (int j=0;j<p;++j) for (int k=0,x;k<q;++k) { scanf("%d",&x); Addedge(node(i,j,k),node(i+1,j,k),x); if (i-d>=0) { if (j-1>=0) Addedge(node(i,j,k),node(i-d,j-1,k),INF); if (j+1<p) Addedge(node(i,j,k),node(i-d,j+1,k),INF); if (k-1>=0) Addedge(node(i,j,k),node(i-d,j,k-1),INF); if (k+1<q) Addedge(node(i,j,k),node(i-d,j,k+1),INF); } } Vc=(r+1)*p*q+2,src=(r+1)*p*q,sink=(r+1)*p*q+1; for (int i=0;i<p;++i) for (int j=0;j<q;++j) Addedge(src,node(0,i,j),INF),Addedge(node(r,i,j),sink,INF); printf("%d\n",max_flow()); }
转载于:https://www.cnblogs.com/lazycal/p/3221342.html
