五 02
昨天晚上做了清北学堂的比赛“首届信息学在线测评大赛Q1”，名字很响亮。今天写了一份题解，发出来。
第一题:低价购买
要求求出方案数的最长单调序列(LIS)问题。我把序列先倒转了过来，然后求最长上升序列。由于需要去除重复序列，可以增加一个域Next[i]，定义Next[i]=min{ k | k>i 且 A[k]=A[i] }，表示大于i且离i最近的Next[i]，使得第Next[i]个数与第i个数相同。如果不存在这样的数则Next[i]=无穷大。这样的话如果出现Next[i]不为0且Next[j]<i可直接跳过。
状态设定
F[i]为以第i个元素为结尾的最长上升序列的长度
G[i]为以第i个元素为结尾的最长上升序列的方案数
状态转移方程
F[i] = Max{ F[j] + 1 | A[j] < A[i] 且 Next[j] > i }
G[i] = Sum{ G[j] | F[j] + 1 = F[i] }
边界条件
G[0]=1
为了方便，增加一个极大的元素到序列结尾。这样目标状态为
最长长度 F[N+1]-1
方案数 G[N+1]
第二题:连续串之和
相邻元素绝对值之差必须为1，所以显然构造出的和最大的序列一定为0,1,2,3,…,N-1，和为(N-1)*N/2，最小和同理为-(N-1)*N/2。于是如果给定的S不在最大值与最小值的区间内，一定无解。
我们先生成一个和最大的序列，0,1,2,3,…,N-1，然后再考虑调整使得满足条件。假设当前的和与S的差为D，可以发现，无论怎样变换序列，D的奇偶性的不改变的。因为无论改变那个元素，都只能从比前一个元素多1变成少1，或者从比前一个元素少1变成多1，调整多个也是一样的，变化量为偶数。所以说，如果初始的D为奇数，则一定不可能有解。
余下来的情况一定为有解的情况了。把序列顺序做差，初始化每项差值都为1，则对应了0,1,2,3,…,N-1。可以发现，修改一个差值从1到-1会引起后面所有项的值减少2，总的减少量就是后面项的个数*2。这时就可以设计出算法了，从第一个差值开始尝试从1变成-1，更新当前和，直到等于S为止。最后再根据差值序列还原出原序列。时间复杂度为O(N)。
第三题:决斗
观察发现，如果第i个人想与第j个人决斗(i<j)，i,j必须相邻，也就是i,j之间的人必须全部被打败。换句话说，如果i,j相邻，一定存在一个k(i<k<j)，使得i,k相邻，k与j相邻，而且i可以打败k或者j可以打败k。这样就把问题缩小了，可以以此进行动态规划。考虑到是一个环，我们可以把N个人复制一遍，接在后面。
设定状态
F[i,j] 表示第i个人是否可以与第j个人相邻 (1<=i<j<=N*2)，第i个人在环上另一面的映射为i+N
状态转移方程
F[i,j]= Or { F[i,k]=F[k,j]=true | i可以打败k或j可以打败k }
边界条件
由于i和i+1两个一定是相邻的，所以有
F[i,i+1]=true
判断第i个人可以胜出的条件就是F[i,i+N]=true，此时i两边的人全部败了，i获胜。
时间复杂度O(N^3)。
第四题:最小费用多米诺
把棋盘上每个非障碍格子看作一个顶点，相邻两个非障碍格子对应的顶点连接一条边，权值为在这两个格子上放上多米诺方块的费用。判断是否能放满只需求出该图的最大匹配，并判断是否每个顶点都有匹配。如何求最大匹配？带花树？不，这是一个二分图！
为什么是二分图？因为棋盘是可以2染色的，之间有边的顶点都是相邻的，而相邻的格子必然是颜色不同的，所以这是一个二分图。
接下来就容易了，首先求出最大匹配，如果存在完美匹配（每个顶点都有匹配），再求最佳匹配(最小权值完备匹配)即可。
下面是四个题的程序
第一题:低价购买
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | /* * Problem: RQN Q1 低价购买 * Author: Guo Jiabao * Time: 2009.5.2 21:48 * State: Solved * Memo: 动态规划 LIS */ #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> const int MAXN=50001,INF=0x7FFFFFFF; using namespace std; int F[MAXN],G[MAXN],A[MAXN],Next[MAXN]; int N,Ans=-INF,Ans2; void init() { int i,j; freopen("low.in","r",stdin); freopen("low.out","w",stdout); scanf("%d",&N); for (i=N;i>=1;i--) scanf("%d",&A[i]); Next[0]=INF; for (i=1;i<=N;i++) { Next[i]=INF; for (j=i+1;j<=N;j++) if (A[j]==A[i]) { Next[i]=j; break; } } A[++N]=INF; } void dynamic() { int i,j; memset(G,0,sizeof(G)); G[0]=1; for (i=1;i<=N;i++) { F[i]=0; for (j=0;j<=i-1;j++) { if (Next[j]>i && A[j] < A[i]) { if (F[j] > F[i]) { F[i] = F[j]; G[i] = G[j]; } else if (F[j] == F[i]) G[i] += G[j]; } } F[i]++; } Ans=F[N]-1; Ans2=G[N]; } int main() { init(); dynamic(); printf("%d %d",Ans,Ans2); return 0; } |
第二题:连续串之和
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | /* * Problem: RQN Q1 连续串之和 * Author: Guo Jiabao * Time: 2009.5.1 20:01 * State: Done * Memo: 构造 */ #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> const int MAXN=10001; using namespace std; int A[MAXN],N,S; void init() { freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); scanf("%d%d",&N,&S); } void construct() { int i,Lim,Dif,k,d; Lim=N*(N-1)/2; Dif=Lim-S; if (S>Lim || S<-Lim || Dif%2==1) { printf("NIE"); return; } for (i=2;i<=N;i++) A[i]=1; for (i=2;i<=N && Dif;i++) { k=(N-i+1)*2; if (Dif >= k) { A[i] = -1; Dif -= k; } } k=0;d=0; for (i=1;i<N;i++) { k += A[i]; d+=k; printf("%dn",k); } k += A[i]; d+=k; printf("%d",k); } int main() { init(); construct(); return 0; } |
第三题:决斗
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | /* * Problem: RQN Q1 决斗 * Author: Guo Jiabao * Time: 2009.5.1 20:24 * State: Done * Memo: 动态规划 */ #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> using namespace std; const int MAXN=1001; bool F[MAXN][MAXN]; bool Beat[MAXN][MAXN]; int N,N2,Wcnt; int Win[MAXN]; void init() { int i,j,c; freopen("mus.in","r",stdin); freopen("mus.out","w",stdout); scanf("%d",&N); N2=N*2; for (i=1;i<=N;i++) { for (j=1;j<=N;j++) { scanf("%d",&c); Beat[i][j]=Beat[i][j+N]=Beat[i+N][j]=Beat[i+N][j+N]= c==1; } } } void dynamic() { int i,j,k,l; for (i=1;i<N2;i++) { F[i][i+1]=true; } for (l=3;l<=N+1;l++) { for (i=1;i<=N2;i++) { if ((j=i+l-1)>N2) break; for (k=i+1;k<=j-1;k++) { if (F[i][k] && F[k][j] && (Beat[i][k] || Beat[j][k])) { F[i][j]=true; break; } } } } for (i=1;i<=N;i++) { if (F[i][i+N]) { Wcnt++; Win[ Wcnt ]=i; } } printf("%dn",Wcnt); for (i=1;i<Wcnt;i++) { printf("%dn",Win[i]); } printf("%d",Win[i]); } int main() { init(); dynamic(); return 0; } |
第四题:最小费用多米诺
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 | /* * Problem: RQN Q1 最小费用多米诺 * Author: Guo Jiabao * Time: 2009.5.2 19:40 * State: Solved * Memo: 棋盘2染色 二分图匹配 匈牙利 费用流 */ #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> const int MAXN=41,MAXV=MAXN*MAXN,MAXE=MAXV*8,INF=0x7FFFFFFF; const int dx[4]={0,1,-1,0},dy[4]={1,0,0,-1}; using namespace std; struct Queue { int Q[MAXV],head,tail,size; bool inq[MAXV]; Queue(){head=size=0,tail=-1;memset(inq,0,sizeof(inq));} void ins(int p) { size++; if (++tail>=MAXV) tail=0; Q[tail]=p; inq[p]=true; } int pop() { int r=Q[head]; size--; if (++head>=MAXV) head=0; inq[r]=false; return r; } }Q; struct edge { edge *next,*op; int t,c,v; }ES[MAXE],*V[MAXV],*fe[MAXV]; struct point { int vx,vy,id,put; }P[MAXN][MAXN]; int N,M,S,T,MatchCnt,MaxCostFlow,EC,Number; int color[MAXV],Match[MAXV],sp[MAXV],fp[MAXV],PX[MAXV],PY[MAXV]; bool vis[MAXV]; void init() { int i,j; freopen("domino.in","r",stdin); freopen("domino.out","w",stdout); scanf("%d%d",&N,&M); for (i=1;i<=N;i++) for (j=1;j<=M;j++) { scanf("%d",&P[i][j].vx); if (P[i][j].vx) Number++; } for (i=1;i<=N;i++) for (j=1;j<=M;j++) scanf("%d",&P[i][j].vy); } inline bool inrange(int x,int y) { return x>=1 && x<=N && y>=1 && y<=M; } void dye(int x,int y,int c) { P[x][y].id=++T; PX[T]=x; PY[T]=y; color[T]=c; for (int k=0;k<4;k++) { int px=x+dx[k],py=y+dy[k]; if (inrange(px,py) && P[px][py].vx && !P[px][py].id) { dye(px,py,3-c); } } } inline void addedge(int a,int b,int c,int v) { ES[++EC].next=V[a]; V[a]=ES+EC; V[a]->t=b; V[a]->c=c; V[a]->v=v; ES[++EC].next=V[b]; V[b]=ES+EC; V[b]->t=a; V[b]->c=0; V[b]->v=-v; V[a]->op=V[b]; V[b]->op=V[a]; } void makegraph() { int i,j,k,px,py,a,b,v; for (i=1;i<=N;i++) for (j=1;j<=M;j++) if (P[i][j].vx && !P[i][j].id) dye(i,j,1); for (i=1;i<=N;i++) for (j=1;j<=M;j++) for (k=0;k<2;k++) { px=i+dx[k],py=j+dy[k]; if (inrange(px,py)) { a=P[i][j].id; b=P[px][py].id; if (a==0 || b==0) continue; if (color[b]==1) { v=a; a=b; b=v; } if (k==0) v = P[i][j].vx + P[px][py].vx; else v = P[i][j].vy + P[px][py].vy; addedge(a,b,1,v); } } S=0;T++; for (i=1;i<T;i++) { if (color[i]==1) addedge(S,i,1,0); else addedge(i,T,1,0); } } bool path(int i) { for (edge *e=V[i];e;e=e->next) { int j=e->t; if (!vis[j] && e->c>0) { vis[j]=true; if (Match[j]==0 || path(Match[j])) { Match[j]=i; return true; } } } return false; } bool hungary() { for (int i=1;i<T;i++) { if (color[i]==1 && !Match[i]) { memset(vis,0,sizeof(vis)); if (path(i)) MatchCnt++; } } return MatchCnt*2==Number; } bool spfa() { int i,j; for (i=S;i<=T;i++) sp[i]=INF; sp[S]=0; Q.ins(S); while (Q.size) { i=Q.pop(); for (edge *e=V[i];e;e=e->next) { j=e->t; if (e->c && sp[i] + e->v < sp[j]) { sp[j] = sp[i] + e->v; fp[j] = i; fe[j] = e; if (!Q.inq[j]) Q.ins(j); } } } return sp[T]!=INF; } void CostFlow() { int i,delta; while (spfa()) { delta=INF; for (i=T;fp[i];i=fp[i]) if (fe[i]->c < delta) delta = fe[i]->c; for (i=T;fe[i];i=fp[i]) { fe[i]->c -= delta; fe[i]->op->c +=delta; } MaxCostFlow += delta * sp[T]; } for (i=1;i<T;i++) { if (color[i]==1) { for (edge *e=V[i];e;e=e->next) { if (e->c==0) { Match[e->t] = i; break; } } } } } void print(int Ans) { int i,j; printf("%dn",Ans); for (i=1;i<T;i++) { if (color[i]==2) { j=Match[i]; if (PX[i]==PX[j]) P[ PX[i] ][ PY[i] ].put = P[ PX[j] ][ PY[j] ].put = 1; else P[ PX[i] ][ PY[i] ].put = P[ PX[j] ][ PY[j] ].put = 2; } } for (i=1;i<=N;i++) { for (j=1;j<M;j++) printf("%d ",P[i][j].put); printf("%d",P[i][j].put); if (i!=N) printf("n"); } } void solve() { makegraph(); if (hungary()) { CostFlow(); print(MaxCostFlow); } else print(MatchCnt); } int main() { init(); solve(); return 0; } |
低价购买
描述 “ 低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一 支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内 一支股票每天的出售价(2^16范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一个程序计算 最大购买次数。 这里是某支股票的价格清单：
日期 1 2 3 4 5 6 7 8 9 10 11 12
价格 68 69 54 64 68 64 70 67 78 62 98 87最优秀的投资者可以购买最多4次股票，可行方案中的一种是：
日期 2 5 6 10
价格 69 68 64 62数据规模
对于100%的数据，1 <= N <= 5000。输入格式 第1行: N，股票发行天数。
第2行: N个数，是每天的股票价格。
输出格式 输出仅一行包含两个数:最大购买次数和拥有最大购买次数的方案数(<=2^31)当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这2种方案被认为是相同的。 样例输入 样例输出
连续串之和
描述 我们定义连续串为一串整数，它的第一个元素为0，并且任两个相邻元素之差的绝对值为1。更精确的说，如果[a1, a2, …, an]为一个连续串，那么有：
对于任意的1<k<n，|ak – ak+1|=1
a1=0
任务：
写一个程序：
读入连续串的长度和连续串中所有元素的和；
找出一个给定长度的连续串，使其所有元素的和与给定的和相等，或者指出这样的连续串不存在。数据规模
对于100%的数据，1 <= n <= 10000，|S| <= 50000000。
输出任意一个可行解即可，本题的Special Judge已经由RenQing编写完毕.
最新更新[RQ刚刚出完数据...所以来透露一下]:
对于30%的数据 n<=12 s<=30
对于60%的数据 n<=1000 s<=1500
对于100%的数据 n<=10000 s<=50000000输入格式 输入的第一行有一个整数n，表示连续串中元素的个数。第二行为一个整数S，表示连续串中所有元素之和。 输出格式 如果能够找到满足条件的连续串，你应当输出n个整数（每行一个），表示连续串中的各个元素（第k个元素输出在第k行）。否则，文件应该只包含一个单词NIE。 样例输入 样例输出
决斗
描述 Michel最近迷上了买彩票。现在，某赌场就一轮决斗的结果开设了赌局。这个赌局同样被Michel盯上了，他决定购买这个彩票。
当然，身为有教养有文化的人，Michel买彩票并不是胡乱买的。他在买之前进行了详尽的市场调查，并拿到了任意两个选手对决后的胜败情况。可以假定正式比赛的时候决斗后果也是一样的。
同时决斗的规则是这样的：
首先，选手们围成一个圈。每一回合随机抽出一个选手的号码，让他和他右边的选手决斗。开始时，1号右边的是2号，2号右边的试三号，依此类推。特别的，n号右边的是1号。战败的选手则退出战场。例如2号战败，则1号右边的就变成了3号。
现在，他找到了你，希望你能告诉他哪些选手可能赢。数据范围：
对于30％的数据，n=5
对于100％的数据，1<=n<=500[感谢:陈启峰出题,清北学堂提供]
输入格式 输入数据的第一行为一个整数n，表示有n个选手。
接下来n行，每行n个整数，第I+1行第J列表示第I个选手与第J个选手对决后的胜败情况，0表示选手I失败，1表示选手I获胜。输出格式 输出数据的第一行为一个整数k，表示有多少选手可能赢。
接下来k行，每行一个整数，从小到大输出这些选手的编号。样例输入 样例输出
最小费用多米诺
描述 在 N*M 的棋盘上互不覆盖地放置 1*2 和 2*1 的多米诺方块，有一些格子上有障碍，这些格子不能放置多米诺方块。在每个没有障碍的格子上有两个费用值，分别表示这个格子上横放和竖放多米诺方块所需的费 用。试问存不存在一种放置多米诺的方案，能放满所有无障碍的格子。若存在，求出完成放置的最小费用；若不存在，求出最多能放置多少个多米诺。 数据规模
保证第一行的答案不超过 2^30。
对于 30% 的数据，N, M <= 5。
对于 80% 的数据，N, M 中至少有一个不超过8。
对于 100% 的数据，N, M <= 40。备注
本题设有部分分，对于每种情况，如果你的程序只输出了第一行且答案正确，可以得到该测试点 70% 的分数。但是如果你的程序输出了放置方案而方案不正确，该测试点得0分。
[感谢题目作者wish]输入格式 第一行两个正整数 N 和 M，表示棋盘共 N 行 M 列。
后为两个 N*M 的矩阵，分别表示棋盘每个格子横放和竖放多米诺的费用。费用为正整数，若费用为0，则格子是障碍格（保证障碍格两个费用均为0）。
输出格式 若存在至少一种放置方案，则第一行输出最小费用，后跟一个 N*M 的矩阵，表示最小费用方案。
若不存在满足要求的放置方案，则第一行输出最多能够放置多少个多米诺，后跟一个 N*M 的矩阵，输出一种放置方案。
方案可能有很多种，只需输出任意一种即可。
输出的方案中，0表示这个格子不放置多米诺，1表示这个格子的多米诺横放，2 表示这个格子的多米诺竖放。
样例输入 样例输出
赞
[回复]
牛啊
顺便问一下，您的view code是博客系统自带的吗？
[回复]
插件 wp-codebox
[回复]