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 ++; } } } }

### NOIP2008提高组复赛试题及题解.doc

NOIP2008提高组复赛试题及题解 - 全国信息学奥林匹克联赛(NOIP200

### NOIP2008 提高组 复赛试题.pdf

NOIP2008 提高组 复赛试题_学科竞赛_高中教育_教育专区。官方经典版面,无水印与多余文字。 全国信息学奥林匹克联赛(NOIP2008)复赛 提高组 全国信息学奥林匹克联赛(...

### NOIP2008复赛提高组试题.doc

NOIP2008复赛提高组试题 - 全国信息学奥林匹克联赛(NOIP2008)复赛 提高组 一、题目概览 中文题目名称 英文题目名称 可执行文件名 输入文件名 输出文件名 每个测试...

### NOIP2008提高组复赛试题.doc

NOIP2008提高组复赛试题 - 全国信息学奥林匹克联赛(NOIP2008)复

### NOIP2008提高组复赛模拟试题.doc

NOIP 2008 复赛模拟试题 (提高组) 全国青少年信息学奥林匹克 联赛复赛

### NOIP2008提高组初赛试题_C++含答案 改动.doc

NOIP2008提高组初赛试题_C++含答案 改动_学科竞赛_高中教育_教育专区。第十四届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组● ● 二、不定项选择题(共 10 ...

### NOIP2008初赛提高组试题.doc

NOIP2008初赛提高组试题 - 第十四届全国青少年信息学奥林匹克联赛初赛试题 一、单项选择题(共 10 题,每题 1.5 分,共计 15 分。每题有且仅 有一个正确答案)...

### NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题....doc

NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案_学科竞赛_高中教育_教育专区。信息学奥林匹克联赛提高组初赛试题及答案。 ...

### NOIP2008年提高组初赛试题(十四届)(非常详细).doc

NOIP2008 初赛(提高组)试题&解析 第十四届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 Pascal 语言 二小时完成 )●● 全部试题答案均要求写在答卷纸上,写在...

### NOIP2008第十四届全国青少年信息学奥林匹克联赛初赛试....doc

NOIP2008第十四届全国青少年信息学奥林匹克联赛初赛试题(含答案)_学科竞赛_高中教育_教育专区。2008 第十四届全国青少年信息学奥林匹克联赛初赛试题( 提高组 C 语言 ...

### NOIP2008全国青少年信息学奥林匹克联赛获奖名单(提高组....doc

NOIP2008全国青少年信息学奥林匹克联赛获奖名单(提高组_专业资料。NOIP2008 全国...完全解读NOIP2008提高组... 8页 1下载券 2008NOIP(全国青少年信息... 9...

### NOIP2008提高组初赛试题_C++含答案.doc

NOIP2008提高组初赛试题_C++含答案 - 第十四届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 C++ 语言 二小时完成 )●● 全部试题答案均要求写在答卷纸上,写...

### noip2008普及组复赛试题(附题解).doc

noip2008普及组复赛试题(附题解)_IT/计算机_专业资料。NOIP2008的复赛试题(普及组)+题解 全国信息学奥林匹克联赛(NOIP2008)复赛 普及组 全国信息学奥林匹克联赛...

### CCF 全国信息学奥林匹克联赛(NOIP2012)复赛 提高组Day1....doc

CCF 全国信息学奥林匹克联赛(NOIP2012)复赛 提高组Day1试题_学科竞赛_小学教育...第12届全国青少年信息学... 6页 1下载券 完全解读NOIP2008提高组... 8...