');}

NOIP2012 普及组

Author Avatar
Actinoi 8月 12, 2019

T1:质因数分解

题目描述

已知正整数 n 是两个不同的质数的乘积，试求出两者中较大的那个质数。

输入格式

一个正整数 n 。

输出格式

一个正整数 p ，即较大的那个质数。

输入输出样例

输入样例 #1

  1. 21

输出样例 #1

  1. 7

说明/提示

n\le 2\times 10^9

NOIP 2012 普及组 第一题

题解：

​​​ ​读入一个数字 n 之后，为了减少时间复杂度，首先将 n 开一下根，然后从 2 开始枚举 n 的质因数。唯一分解定理告诉我们，一个数只能分解为一组质数的乘积，所以，我们从从 2 到 sqrt(n) 来开始枚举 n 的质因数，如果发现 n\ mod\ i\ =\ 0 之后，便得到了一个较小的质因数 i 。为了得到较大的那一个，输出 n\ ÷\ i 就可以了。

  1. #include <cmath>
  2. #include <cstdio>
  3. using namespace std;
  4. int main() {
  5.     long long n;
  6.     scanf("%lld", &n);
  7.     int l = sqrt(n) + 1;
  8.     for (long long i = 2; i <= l; i++)
  9.         if (n % i == 0) {
  10.             printf("%lld\n", n / i);
  11.             return 0;
  12.         }
  13.     return 0;
  14. }

T2:寻宝

题目描述

传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏宝楼，藏宝楼的门口竖着一个木板，上面写有几个大字：寻宝说明书。说明书的内容如下：

藏宝楼共有 N+1 层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外，藏宝楼另 0 有 N 层，每层 M 个房间，这 M 个房间围成一圈并按逆时针方向依次编号为 0,…,M-1 。其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个指示牌，指示牌上有一个数字 x ，表示从这个房间开始按逆时针方向选择第 x 个有楼梯的房间（假定该房间的编号为k），从该房间上楼，上楼后到达上一层的 k 号房间。比如当前房间的指示牌上写着 2 ，则按逆时针方向开始尝试，找到第 2 个有楼梯的房间，从该房间上楼。如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。

寻宝说明书的最后用红色大号字体写着：“寻宝须知：帮助你找到每层上楼房间的指示牌上的数字（即每层第一个进入的房间内指示牌上的数字）总和为打开宝箱的密钥”。 请帮助小明算出这个打开宝箱的密钥。

输入格式

第一行 2 个整数 N 和 M ，之间用一个空格隔开。 N 表示除了顶层外藏宝楼共 N 层楼， M 表示除顶层外每层楼有 M 个房间。

接下来 N \times M 行，每行两个整数，之间用一个空格隔开，每行描述一个房间内的情况，其中第 (i-1) \times M+j 行表示第 i 层 j-1 号房间的情况（ i=1,2,…, N ； j=1,2,…,M ）。第一个整数表示该房间是否有楼梯通往上一层（ 0 表示没有， 1 表示有），第二个整数表示指示牌上的数字。注意，从 j 号房间的楼梯爬到上一层到达的房间一定也是 j 号房间。

最后一行，一个整数，表示小明从藏宝楼底层的几号房间进入开始寻宝（注：房间编号从 0 开始）。

输出格式

一个整数，表示打开宝箱的密钥，这个数可能会很大，请输出对 20123 取模的结果即可。

输入输出样例

输入样例 #1

  1. 2 3
  2. 1 2
  3. 0 3
  4. 1 4
  5. 0 1
  6. 1 5
  7. 1 2
  8. 1

输出样例 #1

  1. 5

说明/提示

【数据范围】

对于50%数据，有 0<N≤1000,0<x≤10000 ；

对于100%数据，有 0<N≤10000,0<M≤100,0<x≤1,000,000 。

NOIP 2012 普及组 第二题

题解：

​​​ ​本题就是一道模拟题，但是题目条件比较多，比较考察读题能力。

​​​ ​由于指示牌上的数字可能会很大，需要围着本层楼跑好几圈才能够跑到能像上一层的房间，所以，我们设置一个 Floor 数组存储每层楼中有楼梯的房间的总数。然后，将指示牌上的数字 mod 一下对应的 Floor ，就可以保证在一圈之内找到通往上一层的入口。

  1. #include <iostream>
  2. #define MOD 20123
  3. using namespace std;
  4. int room[10001][101][4];
  5. int Floor[100001];
  6. int main() {
  7.     int n, m, start;
  8.     cin >> n >> m;
  9.     for (int i = 1; i <= n; i++)
  10.         for (int j = 0; j < m; j++) {
  11.             cin >> room[i][j][1] >> room[i][j][2];
  12.             Floor[i] += room[i][j][1];
  13.         }
  14.     cin >> start;
  15.     int ans = 0; //记录答案
  16.     for (int i = 1; i <= n; i++) { //从第一层楼开始向上爬
  17.         ans = (ans + room[i][start][2]) % MOD; //记录答案
  18.         int cs = 0, q = start;
  19.         room[i][start][2] = (room[i][q][2] - 1) % Floor[i] + 1; //剪枝，保证一圈之内找到入口
  20.         while (cs < room[i][q][2]) {
  21.             cs += room[i][start][1];
  22.             if (cs == room[i][q][2])
  23.                 break;
  24.             start++;
  25.             if (start == m)
  26.                 start = 0;
  27.         }
  28.     }
  29.     cout << ans << endl;
  30.     return 0;
  31. }

T3:摆花

题目描述

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

试编程计算，一共有多少种不同的摆花方案。

输入格式

第一行包含两个正整数 n 和 m ，中间用一个空格隔开。

第二行有 n 个整数，每两个整数之间用一个空格隔开，依次表示 a_1,a_2,…,a_n 。

输出格式

一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 1000007 取模的结果。

输入输出样例

输入样例 #1

  1. 2 4
  2. 3 2

输出样例 #1

  1. 2

说明/提示

【数据范围】

对于20%数据，有 0<n≤8,0<m≤8,0≤a_i≤8 ；

对于50%数据，有 0<n≤20,0<m≤20,0≤a_i≤20 ；

对于100%数据，有 0<n≤100,0<m≤100,0≤a_i≤100 。

NOIP 2012 普及组 第三题

题解：

​​​ ​本题是一个动态规划问题，但是，本题却不需要 min 或 max 函数，而是只需要简单地从上一个状态转移到当前状态。

​​​ ​我们设置一个 DP 数组，用 DP[j] 来表示当摆上 j 盆花时有多少种不同的摆花方案。

​​​ ​然后，我们用 i 来枚举每盆花，用 j 来枚举摆的花的数量，用 j\ -\ k 来枚举上一个状态，便可以得到 DP[j]\ =\ DP[j]\ +\ DP[j\ -\ k] 的动态转移方程，最后，输出 DP[m] 就可以辣！

  1. #include <iostream>
  2. #define MOD 1000007
  3. using namespace std;
  4. int a[101], DP[101];
  5. int main() {
  6.     int n, m;
  7.     cin >> n >> m;
  8.     for (int i = 1; i <= n; i++)
  9.         cin >> a[i];
  10.     DP[0] = 1;
  11.     for (int i = 1; i <= n; i++) //从第一盆花开始枚举
  12.         for (int j = m; j >= 0; j--)
  13.             for (int k = 1; k <= min(j, a[i]); k++)
  14.                 DP[j] = (DP[j] + DP[j - k]) % MOD;
  15.     cout << DP[m] << endl;
  16.     return 0;
  17. }

T4:文化之旅

题目描述

有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。

现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。

输入格式

第一行为五个整数 N,K,M,S,T ，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为 1 到 N ），文化种数（文化编号为 1 到 K ），道路的条数，以及起点和终点的编号（保证 S 不等于 T ）；

第二行为 N 个整数，每两个整数之间用一个空格隔开，其中第 i 个数 C_i ，表示国家 i 的文化为 C_i 。

接下来的 K 行，每行 K 个整数，每两个整数之间用一个空格隔开，记第 i 行的第 j 个数为 a_{ij} ， a_{ij}= 1 表示文化 i 排斥外来文化 j （ i 等于 j 时表示排斥相同文化的外来人）， a_{ij}= 0 表示不排斥（注意 i 排斥 j 并不保证 j 一定也排斥 i ）。

接下来的 M 行，每行三个整数 u,v,d ，每两个整数之间用一个空格隔开，表示国家 u 与国家 v 有一条距离为 d 的可双向通行的道路（保证 u 不等于 v ，两个国家之间可能有多条道路）。

输出格式

一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出 -1 ）。

输入输出样例

输入样例 #1

  1. 2 2 1 1 2 
  2. 1 2 
  3. 0 1 
  4. 1 0 
  5. 1 2 10

输出样例 #1

  1. -1

输入样例 #2

  1. 2 2 1 1 2 
  2. 1 2 
  3. 0 1 
  4. 0 0 
  5. 1 2 10

输出样例 #2

  1. 10

说明/提示

输入输出样例说明 1

由于到国家 2 必须要经过国家 1 ，而国家 2 的文明却排斥国家 1 的文明，所以不可能到达国家 2 。

输入输出样例说明 2

路线为 1 -> 2

【数据范围】

对于 100%的数据，有 2≤N≤100

1≤K≤100

1≤M≤N^2

1≤k_i≤K

1≤u, v≤N

1≤d≤1000,S≠T,1≤S,T≤N

NOIP 2012 普及组 第四题

题解：

​​​ ​Emmm......由于本题被证明没有靠谱的多项式复杂度的做法，所以没有正解。那么。。。就怎么玄学怎么来呗！

​​​ ​我采用了 Floyd() 求最短路的方法。我们用 road[i][j] 表示 i 国家到 j 国家的最短路，并将所有的 road 赋值为正无穷。读入每条路径，将双向通行的道路转为单向通行的道路：判断这条路所联通的两个国家 u 、 v 的文化是否互相排斥。如果 u 不排斥 v 的话则添加 u\ ->\ v 的道路， v 不排斥 u 的话则添加 v\ ->\ u 的道路。至此，初始化完毕。

​​​ ​ Floyd () 函数里面就是三重 for() 循环。用变量 i,\ j,\ k 枚举从 i\ ->\ j 途径 k 的路径。如果 i\ ->\ k\ ,\ k\ ->\ j 之间有路的话，那么， road[i][j]\ =\ min(road[i][j],\ (road[i][k]\ +\ road[k][j])) 。最后，判断一下 road[s][t] 是否小于正无穷，小于的话输出 road[s][t] ，否则输出 -1 。

  1. #include <cstring>
  2. #include <iostream>
  3. using namespace std;
  4. int c[101];
  5. int exclude[101][101];
  6. int n, k, m, s, t;
  7. int road[101][101];
  8. int pass[101][101];
  9. void Floyd () {
  10.     for (int i = 1; i <= n; i++)
  11.         for (int j = 1; j <= n; j++)
  12.             if (i != j)
  13.                 for (int k = 1; k <= n; k++)
  14.                     if (i != k && j != k)
  15.                         road[i][j] = min(road[i][j], (road[i][k] + road[k][j]));
  16. }
  17. int main() {
  18.     memset(road, 0x3f3f3f, sizeof(road));
  19.     cin >> n >> k >> m >> s >> t;
  20.     for (int i = 1; i <= n; i++)
  21.         cin >> c[i];
  22.     if(c[s] == c[t]){
  23.         cout << -1;
  24.         return 0;
  25.     }
  26.     for (int i = 1; i <= k; i++)
  27.         for (int j = 1; j <= k; j++)
  28.             cin >> exclude[i][j];
  29.     for (int i = 1; i <= m; i++) {
  30.         int u, v, d;
  31.         cin >> u >> v >> d;
  32.         if (c[u] != c[v] && exclude[c[v]][c[u]] == 0) //两个国家文化不同且不互相排斥
  33.             road[u][v] = min(road[u][v], d); // road 表示从 u 到 v 的最小路，所以要先判断 v 文化是否排斥 u 文化，
  34.         if (c[u] != c[v] && exclude[c[u]][c[v]] == 0)
  35.             road[v][u] = min(road[v][u], d);
  36.     }
  37.     Floyd();
  38.     if (road[s][t] < 0x3f3f3f)
  39.         cout << road[s][t] << endl;
  40.     else
  41.         cout << -1 << endl;
  42.     return 0;
  43. }