tceic.com

# 完全解读NOIP2008提高组试题(全国信息学奥林匹克联赛)

NOIP2008 提高组解题报告
angwuy

1 word

writeln(max-min); end else begin writeln('No Answer'); writeln(0); end; close(input); close(Output); end.

2 matches

begin for j:=0 to 1000-i do if a[i]+a[j]+a[i+j]=n then inc(ans); end; writeln(ans); close(input); close(output); end.

3 message
DP 题,两条路线必定一上一下,而且,当到达某一列后,前面对后面的不会有影响,符合 动态规划的无后效性,方程如下: 用 dp[I,j,k]表示当到达 I 列时,上路线在 j 行到,下路线在 k 行到的最大值. 另外加一个预处理,sum[I,j1,j2]表示在第 I 列 j1 到 j2 行的数加起来的和. 边界条件: dp[2,1,k]:=sum[1,1,k]; 递推方程: dp[I,j,k]:=max(dp[I-1,j2,k2]+sum[I-1,j,j2]+sum[I-1,k,k2]) {j<=j2<k<=k2} 答案: max(dp[m,j,n]+sum[m,j,n]) 参考程序: const maxn=10; var a:array[1..maxn,1..maxn]of longint; dp,sum:array[1..maxn,1..maxn,1..maxn]of longint; n,m,i,j,k,i1,i2,j1,j2,k1,k2:longint; function max(a,b:longint):longint; begin if a>b then max:=a else max:=b; end; begin assign(input,'message.in'); reset(input); assign(output,'message.out'); rewrite(output); readln(m,n); for i:=1 to m do begin for j:=1 to n do read(a[i,j]); readln; end; for i:=1 to m do

begin for i1:=1 to n do begin sum[i,i1,i1]:=a[i,i1]; for i2:=i1+1 to n do sum[i,i1,i2]:=sum[i,i1,i2-1]+a[i,i2]; end; end; fillchar(dp,sizeof(dp),255); for i:=2 to n do dp[2,1,i]:=sum[1,1,i]; for i:=2 to m-1 do for j:=1 to n-1 do for k:=j+1 to n do if dp[i,j,k]>-1 then begin for j2:=j to k-1 do for k2:=k to n do dp[i+1,j2,k2]:=max(dp[i+1,j2,k2],dp[i,j,k]+sum[i,j,j2]+sum[i,k,k2]); end; k:=0; for i:=1 to n-1 do k:=max(k,dp[m,i,n]+sum[m,i,n]); writeln(k); close(input); close(output); end. 4.twostack

#include <iostream>

using namespace std;

const int nn = 1002, mm = nn * 2, inf = 1000000000; int n, tot, now; int a[nn], b[nn], head[nn], color[nn]; int adj[mm], next[mm]; int stack[3][nn]; bool result;

bool dfs(int i) //dfs 染色,检查图是否是二分图的经典算法 { int temp = head[i]; while (temp) //邻接表,检查每一条边 { if (! color[adj[temp]]) //如果与当前结点的结点还未染色 { color[adj[temp]] = 3 - color[i]; //进行染色 dfs(adj[temp]); //dfs } if (color[adj[temp]] == color[i]) return false; //如果两个相邻结点染色相同,说明此图不是二分图,返回无解 temp = next[temp]; } return true; }

int main() { freopen("twostack.in", "r", stdin); freopen("twostack.out", "w", stdout);

//输入 scanf("%d", n); for (int i = 1; i <= n; ++ i) scanf("%d", a[i]);

//预处理 b 数组

b[n + 1] = inf; for (int i = n; i >= 1; -- i) b[i] = min(b[i + 1], a[i]); //"min" in stl

//枚举数对(i,j)并加边 tot = 0; for (int i = 1; i <= n; ++ i) for (int j = i + 1; j <= n; ++ j) if (b[j + 1] < a[i] & a[i] < a[j]) { addedge(i, j); addedge(j, i); }

//dfs 染色 memset(color, 0, sizeof(color)); result = true; for (int i = 1; i <= n; ++ i) //每次找当前未染色的编号最小的结点,并染颜色 1 if (! color[i]) //当前位置尚未被染色 { color[i] = 1; if (! dfs(i)) //染色时出现矛盾,此时图不是一个二分图,即无法分配到两个栈中 { result = false; //记录无解 break; } }

if (! result) //无解 printf("0"); else //有解 { //模拟求解 now = 1; for (int i = 1; i <= n; ++ i) { //将当前数字压入对应的栈 if (color[i] == 1) printf("a "); else printf("c "); stack[color[i]][0] ++; stack[color[i]][stack[color[i]][0]] = a[i]; //this will work even if stack[1][0] = 0

//循环检查,如果可以的话就从栈顶弹出元素

while (stack[1][stack[1][0]] == now || stack[2][stack[2][0]] == now) { if (stack[1][stack[1][0]] == now) { printf("b "); stack[1][0] --; } else if (stack[2][stack[2][0]] == now) { printf("d "); stack[2][0] --; } now ++; } } } }