NOIP2012普及组解题报告



小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共m盆。通过调查顾客的喜好,小明列出了顾客最喜欢的n种花,从1到n标号。为了在门口展 出更多种花,规定第i种花不能超过ai盆,摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。试编程计算,一共有多少种不同的摆 花方案。

比较简单的DP。
/*
ID: Sfiction
OJ: RQNOJ
PROB: 703
*/
#include <cstdio>
const int MOD=1000007;
const int MAXN=101;
int f[MAXN][MAXN];
int a[MAXN];
int main()
{
int n,m;
int i,j,k;
scanf(“%d%d”,&n,&m);
for (i=1;i<=n;++i) scanf(“%d”,&a[i]);
f[0][0]=1;
for (i=1;i<=n;++i)
for (j=0;j<=m;++j)
for (k=0;k<=a[i]&&j>=k;++k) f[i][j]=(f[i][j]+f[i-1][j-k])%MOD;
printf(“%d”,f[n][m]);
return 0;
}

http://sfiction.blog.163.com/blog/static/19940401020139183551542/

第一题质因数分解, 题目已知正整数n是两个不同的质数的乘积, 试求出较大的那个质数, 没什么技术含量, 直接开个根号搜一遍就好了. 另外不开根号会TLE导致得60分.

1 #include <stdio.h>
2 #include <math.h>
3 int main()
4 {
5 int n;
6 scanf(“%d”, &n);
7 for (int i = 2, k = sqrt(n) + 1; i < k; ++i)
8 if (n % i == 0)
9 {
10 printf(“%d\n”, n / i);
11 break;
12 }
13 return 0;
14 }
第二题寻宝

[题目]传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏宝楼,藏宝楼的门口竖着一个木板,上面写有几个大字:寻宝说明书。说明书的内容如下:藏宝楼共有N+1层,最上面一层是顶层,顶层有一个房间里面藏着宝藏。除了顶层外,藏宝楼另有N层,每层M个房间,这M个房间围成一圈并按逆时针方向依次编号为0,…,M-1。其中一些房间有通往上一层的楼梯,每层楼的楼梯设计可能不同。每个房间里有一个指示牌,指示牌上有一个数字x,表示从这个房间开始按逆时针方向选择第x个有楼梯的房间(假定该房间的编号为k),从该房间上楼,上楼后到达上一层的k号房间。比如当前房间的指示牌上写着2,则按逆时针方向开始尝试,找到第2个有楼梯的房间,从该房间上楼。如果当前房间本身就有楼梯通向上层,该房间作为第一个有楼梯的房间。寻宝说明书的最后用红色大号字体写着:“寻宝须知:帮助你找到每层上楼房间的指示牌上的数字(即每层第一个进入的房间内指示牌上的数字)总和为打开宝箱的密钥”。请帮助小明算出这个打开宝箱的密钥。

这个题是个简单的模拟, 但是出乎意料的恶心, 当年做这个题的时候爆零, 钛蒻了, 总感觉这个比第三题难.

1 #include <stdio.h>
2 int x[10003][103], fjx[103];
3 bool k[10003][103];
4 int main()
5 {
6 int n, m, s, t, key = 0, turn;
7 scanf(“%d %d”, &n, &m);
8 for (int i = 0, j; i < n; ++i)
9 for (j = 0; j < m; ++j)
10 scanf(“%d %d”, &k[i][j], &x[i][j]);
11 scanf(“%d”, &s);
12 key = 0;
13 for (int i = 0, j = s, h = 0, fj = 0; i < n; ++i)
14 {
15 key = (key + x[i][s]) % 20123;
16 while (h < m)
17 {
18 if (k[i][j] == 1)
19 fjx[fj++] = j;
20 ++h;
21 ++j;
22 if (j == m)
23 j = 0;
24 }
25 t = (x[i][s] – 1) % fj;
26 s = fjx[t];
27 }
28 printf(“%d\n”, key);
29 return 0;
30 }
第三题摆花


[题目]小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共m盆。通过调查顾客的喜好,小明列出了顾客最喜欢的n种花,从1到n标号。为了在门口展出更多种花,规定第i种花不能超过ai盆,摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。试编程计算,一共有多少种不同的摆花方案。

据说是个多重背包…但是我直接写的DP…

#include <stdio.h>
int a[102], f[102];
int main()
{
int n, m, sum = 0;
scanf(“%d%d”, &n, &m);
for(int i = 1; i <= n; ++i)
scanf(“%d”, &a[i]);
f[0] = 1;
for (int i = 1, j, k; i <= n; sum = 0, ++i)
{
for (j = m, sum = 0; j > a[i]; f[j] = sum, sum = 0, –j)
for (k = j – a[i]; k <= j; sum %= 1000007, ++k)
sum += f[k];
for (j = a[i], sum = 0; j > -1; f[j] = sum, sum = 0, –j)
for (k = 0; k <= j; sum %= 1000007, ++k)
sum += f[k];
}
printf(“%d\n”, f[m]);
return 0;
}
第四题文化之旅

[题目]有一位使者要游历各国,他每到一个国家,都能学到一种文化,但他不愿意学习任何一种文化超过一次(即如果他学习了某种文化,则他就不能到达其他有这种文化的国家)。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同,有些文化会排斥外来文化(即如果他学习了某种文化,则他不能到达排斥这种文化的其他国家)。现给定各个国家间的地理关系,各个国家的文化,每种文化对其他文化的看法,以及这位使者游历的起点和终点(在起点和终点也会学习当地的文化),国家间的道路距离,试求从起点到终点最少需走多少路。

吵了很长时间的一道题, 很多人说Floyd可以直接秒杀, DFS不行. 但是有人构造出了卡死Floyd的数据, 所以保险DFS比较好. 另外要从终点开始搜, 从原点会得60(TLE). 另外CCF的数据太弱了, 不考虑文化差异能得90…

总之, 这道题的数据比较弱, floyd可以过. 但是真正完全AC的是深度优先搜索.

1 #include <stdio.h>
2 #include <stdlib.h>
3 int n, k, m, s, t, distance[101][101], culture[101], fight[101][101], search[101], p = 0;
4 bool found = false;
5 int min(int a, int b)
6 {
7 return (a > b ? b : a);
8 }
9 void DFS(int target)
10 {
11 bool CanInqueue = true;
12 int queue[101] = {0}, tail = 0;
13 search[++p] = target;
14 if (target == t)
15 {
16 found = true;
17 return;
18 }
19 for (int i = 1, j; i <= n; ++i)
20 {
21 for (j = 1; j <= p; ++j)
22 {
23 if (search[j] == i || culture[search[j]] == culture[i] || fight[culture[i]][culture[search[j]]] == 1)
24 {
25 CanInqueue = false;
26 break;
27 }
28 }
29 if (distance[target][i] == 1001)
30 CanInqueue = false;
31 if (CanInqueue)
32 queue[++tail] = i;
33 else
34 CanInqueue = true;
35 }
36 for (int i = 1; i <= tail; ++i)
37 distance[s][queue[i]] = min(distance[s][queue[i]], distance[s][target] + distance[target][queue[i]]);
38 for (int i = 1; i <= tail; ++i)
39 DFS(queue[i]);
40 return;
41 }
42 int main()
43 {
44 for (int i = 1, j; i < 101; ++i)
45 for (j = 1; j < 101; ++j)
46 distance[i][j] = 1001;
47 scanf(“%d %d %d %d %d”, &n, &k, &m, &s, &t);
48 for (int i = 1; i <= n; ++i)
49 scanf(“%d”, &culture[i]);
50 for (int i = 1, j; i <= k; ++i)
51 for (j = 1; j <= k; ++j)
52 scanf(“%d”, &fight[i][j]);
53 for (int i = 0, y, z, c; i < m; ++i, distance[z][y] > c ? distance[y][z] = distance[z][y] = c : c = 2147483646)
54 scanf(“%d %d %d”, &y, &z, &c);
55 DFS(s);
56 if (found)
57 printf(“%d\n”, distance[s][t]);
58 else
59 printf(“-1\n”);
60 return 0;
61 }

http://www.fx114.net/qa-255-84283.aspx