清北学堂比赛 Q1 解题报告
昨天晚上做了清北学堂的比赛“首届信息学在线测评大赛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染色的，之间有边的顶点都是相邻的，而相邻的格子必然是颜色不同的，所以这是一个二分图。
接下来就容易了，首先求出最大匹配，如果存在完美匹配（每个顶点都有匹配），再求最佳匹配(最小权值完备匹配)即可。
下面是四个题的程序
第一题:低价购买
/*
* 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;
}
第二题:连续串之和
/*
* 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;
}
第三题:决斗
/*
* 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;
}
第四题:最小费用多米诺
/*
* 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;
}
低价购买
<table>
<tbody>
<tr>
<td class="Text0" height="28" bgcolor="#84c1ff">描述</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">“ 低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一 支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内 一支股票每天的出售价(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。
</span></td>
</tr>
<tr>
<td class="Text0" height="24" bgcolor="#84c1ff">输入格式</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">第1行: N，股票发行天数。
第2行: N个数，是每天的股票价格。
</span></td>
</tr>
<tr>
<td class="Text0" bgcolor="#84c1ff">输出格式</td>
</tr>
<tr class="TextN">
<td class="Text0"><span class="Text4">输出仅一行包含两个数:最大购买次数和拥有最大购买次数的方案数(<=2^31)当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这2种方案被认为是相同的。</span></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">样例输入</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea" readonly="readonly">12 68 69 54 64 68 64 70 67 78 62 98 87 </textarea></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">样例输出</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea2" readonly="readonly">4 2</textarea></td>
</tr>
</tbody></table>
连续串之和
<table>
<tbody>
<tr>
<td class="Text0" height="28" bgcolor="#84c1ff">描述</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">我们定义连续串为一串整数，它的第一个元素为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
</span></td>
</tr>
<tr>
<td class="Text0" height="24" bgcolor="#84c1ff">输入格式</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">输入的第一行有一个整数n，表示连续串中元素的个数。第二行为一个整数S，表示连续串中所有元素之和。</span></td>
</tr>
<tr>
<td class="Text0" bgcolor="#84c1ff">输出格式</td>
</tr>
<tr class="TextN">
<td class="Text0"><span class="Text4">如果能够找到满足条件的连续串，你应当输出n个整数（每行一个），表示连续串中的各个元素（第k个元素输出在第k行）。否则，文件应该只包含一个单词NIE。</span></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">样例输入</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea" readonly="readonly">8 4 </textarea></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">样例输出</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea2" readonly="readonly">0 1 2 1 0 -1 0 1</textarea></td>
</tr>
</tbody></table>
决斗
<table>
<tbody>
<tr>
<td class="Text0" height="28" bgcolor="#84c1ff">描述</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">Michel最近迷上了买彩票。现在，某赌场就一轮决斗的结果开设了赌局。这个赌局同样被Michel盯上了，他决定购买这个彩票。
当然，身为有教养有文化的人，Michel买彩票并不是胡乱买的。他在买之前进行了详尽的市场调查，并拿到了任意两个选手对决后的胜败情况。可以假定正式比赛的时候决斗后果也是一样的。
同时决斗的规则是这样的：
首先，选手们围成一个圈。每一回合随机抽出一个选手的号码，让他和他右边的选手决斗。开始时，1号右边的是2号，2号右边的试三号，依此类推。特别的，n号右边的是1号。战败的选手则退出战场。例如2号战败，则1号右边的就变成了3号。
现在，他找到了你，希望你能告诉他哪些选手可能赢。
数据范围：
对于30％的数据，n=5
对于100％的数据，1<=n<=500
[感谢:陈启峰出题,清北学堂提供]
</span></td>
</tr>
<tr>
<td class="Text0" height="24" bgcolor="#84c1ff">输入格式</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">输入数据的第一行为一个整数n，表示有n个选手。
接下来n行，每行n个整数，第I+1行第J列表示第I个选手与第J个选手对决后的胜败情况，0表示选手I失败，1表示选手I获胜。</span></td>
</tr>
<tr>
<td class="Text0" bgcolor="#84c1ff">输出格式</td>
</tr>
<tr class="TextN">
<td class="Text0"><span class="Text4">输出数据的第一行为一个整数k，表示有多少选手可能赢。
接下来k行，每行一个整数，从小到大输出这些选手的编号。</span></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">样例输入</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea" readonly="readonly">2 0 0 1 0</textarea></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">样例输出</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea2" readonly="readonly">1 2</textarea></td>
</tr>
</tbody></table>
最小费用多米诺
<table>
<tbody>
<tr>
<td class="Text0" height="28" bgcolor="#84c1ff">描述</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">在 N*M 的棋盘上互不覆盖地放置 1*2 和 2*1 的多米诺方块，有一些格子上有障碍，这些格子不能放置多米诺方块。在每个没有障碍的格子上有两个费用值，分别表示这个格子上横放和竖放多米诺方块所需的费 用。试问存不存在一种放置多米诺的方案，能放满所有无障碍的格子。若存在，求出完成放置的最小费用；若不存在，求出最多能放置多少个多米诺。
数据规模
保证第一行的答案不超过 2^30。
对于 30% 的数据，N, M <= 5。
对于 80% 的数据，N, M 中至少有一个不超过8。
对于 100% 的数据，N, M <= 40。
备注
本题设有部分分，对于每种情况，如果你的程序只输出了第一行且答案正确，可以得到该测试点 70% 的分数。但是如果你的程序输出了放置方案而方案不正确，该测试点得0分。
[感谢题目作者wish]
</span></td>
</tr>
<tr>
<td class="Text0" height="24" bgcolor="#84c1ff">输入格式</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">第一行两个正整数 N 和 M，表示棋盘共 N 行 M 列。
后为两个 N*M 的矩阵，分别表示棋盘每个格子横放和竖放多米诺的费用。费用为正整数，若费用为0，则格子是障碍格（保证障碍格两个费用均为0）。
</span></td>
</tr>
<tr>
<td class="Text0" bgcolor="#84c1ff">输出格式</td>
</tr>
<tr class="TextN">
<td class="Text0"><span class="Text4">若存在至少一种放置方案，则第一行输出最小费用，后跟一个 N*M 的矩阵，表示最小费用方案。
若不存在满足要求的放置方案，则第一行输出最多能够放置多少个多米诺，后跟一个 N*M 的矩阵，输出一种放置方案。
方案可能有很多种，只需输出任意一种即可。
输出的方案中，0表示这个格子不放置多米诺，1表示这个格子的多米诺横放，2 表示这个格子的多米诺竖放。
</span></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">样例输入</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea" readonly="readonly">3 4 3 5 3 2 3 0 0 3 9 8 2 3 2 8 4 4 8 0 0 2 1 4 3 8 </textarea></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">样例输出</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea2" readonly="readonly">42 1 1 1 1 2 0 0 2 2 1 1 2 </textarea></td>
</tr>
</tbody></table>
上次修改时间 2017-05-26