NOIP真题
某中学在安排期末考试时发现，有 7 个学生要参加 7 门课程的考试，下表列出了哪些学生参加哪些考试（用√表示要参加相应的考试）。 最少要安排_____个不同的考试时间段才能避免冲突？
#include <iostream>
using namespace std;
int main() {
int a[6] = {1, 2, 3, 4, 5, 6};
int pi = 0;
int pj = 5;
int t , i;
while (pi < pj) {
t = a[pi];
a[pi] = a[pj];
a[pj] = t;
pi++;
pj--;
}
for (i = 0; i < 6; i++)
cout << a[i] << ",";
cout << endl;
return 0;
}输出 ：____
#include <iostream>
using namespace std;
int main() {
char a[100][100], b[100][100];
string c[100];
string tmp;
int n, i = 0, j = 0, k = 0, total_len[100], length[100][3];
cin >> n;
getline(cin, tmp);
for (i = 0; i < n; i++) {
getline(cin, c[i]);
total_len[i] = c[i].size();
}
for (i = 0; i < n; i++) {
j = 0;
while (c[i][j] != ':') {
a[i][k] = c[i][j];
k = k + 1;
j++;
}
length[i][1] = k - 1;
a[i][k] = 0;
k = 0;
for (j = j + 1; j < total_len[i]; j++) {
b[i][k] = c[i][j];
k = k + 1;
}
length[i][2] = k - 1;
b[i][k] = 0;
k = 0;
}
for (i = 0; i < n; i++) {
if (length[i][1] >= length[i][2])
cout << "NO,";
else {
k = 0;
for (j = 0; j < length[i][2]; j++) {
if (a[i][k] == b[i][j])
k = k + 1;
if (k > length[i][1])
break;
}
if (j == length[i][2])
cout << "NO,";
else
cout << "YES,";
}
}
cout << endl;
return 0;
}输入 :
3
AB:ACDEbFBkBD
AR:ACDBrT
SARS:Severe Atypical Respiratory Syndrome
输出 : ____
（注：输入各行前后均无空格）
#include<iostream>
using namespace std;
int lps(string seq, int i, int j) {
int len1, len2;
if (i == j)
return 1;
if (i > j)
return 0;
if (seq[i] == seq[j])
return lps(seq, i + 1, j - 1) + 2;
len1 = lps(seq, i, j - 1);
len2 = lps(seq, i + 1, j);
if (len1 > len2)
return len1;
return len2;
}
int main() {
string seq = "acmerandacm";
int n = seq.size();
cout << lps(seq, 0, n - 1) << endl;
return 0;
}输出 ：____
#include <iostream>
#include <cstring>
using namespace std;
int map[100][100];
int sum[100], weight[100];
int visit[100];
int n;
void dfs(int node) {
visit[node] = 1;
sum[node] = 1;
int v, maxw = 0;
for (v = 1; v <= n; v++) {
if (!map[node][v] || visit[v])
continue;
dfs(v);
sum[node] += sum[v];
if (sum[v] > maxw)
maxw = sum[v];
}
if (n - sum[node] > maxw)
maxw = n - sum[node];
weight[node] = maxw;
}
int main() {
memset(map, 0, sizeof(map));
memset(sum, 0, sizeof(sum));
memset(weight, 0, sizeof(weight));
memset(visit, 0, sizeof(visit));
cin >> n;
int i, x, y;
for (i = 1; i < n; i++) {
cin >> x >> y;
map[x][y] = 1;
map[y][x] = 1;
}
dfs(1);
int ans = n, ansN = 0;
for (i = 1; i <= n; i++)
if (weight[i] < ans) {
ans = weight[i];
ansN = i;
}
cout << ansN << " " << ans << endl;
return 0;
}输入 :
11
1 2
1 3
2 4
2 5
2 6
3 7
7 8
7 11
6 9
9 10
输出 : ____
（交朋友）根据社会学研究表明，人们都喜欢找和自己身高相近的人做朋友。 现在有 n 名身高两两不相同的同学依次走入教室，调查人员想预测每个人在走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样时，这名同学会更想和高的那个人做朋友。比如一名身高为 1.80 米的同学进入教室时，有一名身高为 1.79 米的同学和一名身高为 1.81 米的同学在教室里，那么这名身高为1.80 米的同学会更想和身高为 1.81 米的同学做朋友。对于第一个走入教室的同学我们不做预测。
由于我们知道所有人的身高和走进教室的次序，所以我们可以采用离线的做法来解决这样的问题，我们用排序加链表的方式帮助每一个人找到在他之前进入教室的并且和他身高最相近的人。
#include <iostream>
using namespace std;
#define MAXN 200000
#define infinity 2147483647
int answer[MAXN], height[MAXN], previous[MAXN], next[MAXN]; int rank[MAXN];
int n;
void sort(int l, int r) {
int x = height[rank[(l + r) / 2]], i = l, j = r, temp;
while (i <= j)
{
while (height[rank[i]] < x) i++;
while (height[rank[j]] > x) j--;
if ( ___(1)___ ) {
temp = rank[i]; rank[i] = rank[j]; rank[j] = temp;
i++; j--;
}
}
if (i < r) sort(i, r);
if (l < j) sort(l, j);
}
int main()
{
cin >> n;
int i, higher, shorter;
for (i = 1; i <= n; i++) {
cin >> height[i];
rank[i] = i;
}
sort(1, n);
for (i = 1; i <= n; i++) {
previous[rank[i]] = rank[i - 1];
___(2)___ ;
}
for (i = n; i >= 2; i--){
higher = shorter = infinity;
if (previous[i] !=0)
shorter = height[i] - height[previous[i]];
if (next[i] != 0)
___(3)___ ;
if ( ___(4)___ )
answer[i] = previous[i];
else
answer[i] = next[i];
next[previous[i]] = next[i];
___(5)___ ;
}
for (i = 2; i <= n; i++)
cout << i << ":" << answer[i];
return 0;
}(交通中断）有一个小国家，国家内有 n 座城市和 m 条双向的道路，每条道路连接着两座不同的城市。其中 1 号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道，如果只有第i(i>1) 个城市因地震而导致交通中断时，首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第 i 个城市而导致从首都出发无法到达某个城市，也认为到达该城市的最短路径长度改变。
对于每一个城市 i，假定只有第 i 个城市与外界交通中断，输出有多少个城市会因此导致到首都的最短路径长度改变。
我们采用邻接表的方式存储图的信息，其中 head[x] 表示顶点 x 的第一条 边的编号，next[i] 表示第 i 条边的下一条边的编号, point[i] 表示第 i 条边的终点，weight[i] 表示第 i 条边的长度。
#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 6000
#define MAXM 100000
#define infinity 2147483647
int head[MAXN], next[MAXM], point[MAXM], weight[MAXM];
int queue[MAXN], dist[MAXN], visit[MAXN];
int n, m, x, y, z, total = 0, answer;
void link(int x,int y,int z) {
total++;
next[total] = head[x]; head[x] = total; point[total] = y; weight[total] = z; total++;
next[total] = head[y]; head[y] = total; point[total] = x; weight[total] = z;
}
int main() {
int i, j, s, t; cin >> n >> m;
for (i = 1; i <= m; i++) {
cin >> x >> y >> z;
link(x, y, z);
}
for (i = 1; i <= n; i++) dist[i] = infinity;
___(1)___ ;
queue[1] = 1;
visit[1] = 1;
s = 1;
t = 1;
// 使用 SPFA 求出第一个点到其余各点的最短路长度
while (s <= t) {
x = queue[s % MAXN];
j = head[x];
while (j != 0) {
if ( ___(2)___ ) {
dist[point[j]] = dist[x] + weight[j];
if (visit[point[j]] == 0) {
t++;
queue[t % MAXN] = point[j];
visit[point[j]] = 1;
}
}
j = next[j];
}
___(3)___ ;
s++;
}
for (i = 2; i <= n; i++) {
queue[1] = 1;
memset(visit, 0, sizeof(visit));
visit[1] = 1;
s = 1;
t = 1;
while (s <= t) { // 判断最短路长度是否不变
x = queue[s];
j = head[x];
while (j != 0) {
if (point[j] != i && ___(4)___ &&visit[point[j]] == 0) {
___(5)___ ;
t++;
queue[t] = point[j];
}
j = next[j];
}
s++;
}
answer = 0;
for (j = 1; j <= n; j++)
answer += 1 - visit[j];
cout << i << ":" << answer - 1 << endl;
}
return 0;
}一个人站在坐标（0，0）处，面朝 x 轴正方向。第一轮，他向前走 1 单位距离，然后右转；第二轮，他向前走 2 单位距离，然后右转；第三轮，他向前走 3 单位距离，然后右转……他一直这么走下去。请问第 2017 轮后，他的坐标是：（___ , ___）。
如下图所示，共有 13 个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由 1 变 0，或由 0 变 1）。现在要使得所有的格子中的数字都变为 0，至少需要_____次操作。
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int t[256];
char s[10];
int i;
scanf("%s", s);
for(i = 0; i < 256; i++) t[i] = 0;
for(i = 0; i < strlen(s); i++) t[s[i]]++;
for(i = 0; i < strlen(s); i++)
if(t[s[i]] == 1) {
cout << s[i] << endl;
return 0;
}
cout << "no" << endl;
return 0;
}输入：
xyzxyw
输出：（ ）
#include <stdio.h>
int g(int m, int n, int x) {
int ans=0;
int i;
if(n == 1)
return 1;
for(i = x; i <= m / n; i++)
ans += g(m - i, n - 1, i);
return ans;
}
int main()
{
int t, m, n;
scanf("%d%d", &m, &n);
printf("%d
", g(m, n, 0));
return 0;
}输入：
7 3
输出：（ ）
#include <iostream>
#include <string>
using namespace std;
int main()
{
string ch;
int a[200];
int b[200];
int n, i, t, res;
cin >> ch;
n = ch.length();
for(i = 0; i < 200; i++) b[i] = 0;
for(i = 1; i <= n ; i++) {
a[i] = ch[i-1] - '0';
b[i] = b[i-1] + a[i];
}
res = b[n];
t = 0;
for(i = n; i > 0; i--) {
if(a[i] == 0) t++;
if(b[i-1] + t < res) res = b[i-1] + t;
}
cout << res << endl;
return 0;
}输入：
1001101011001101101011110001
输出：（ ）
#include <iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int x = 1;
int y = 1;
int dx = 1;
int dy = 1;
int cnt = 0;
while(cnt != 2) {
cnt = 0;
x = x + dx;
y = y + dy;
if(x == 1 || x == n) {
++cnt;
dx = -dx;
}
if(y == 1 || y == m) {
++cnt;
dy = -dy;
}
}
cout << x << " " << y << endl;
return 0 ;
}1）输入：
4 3
输出：（ ）
2）输入：
2017 1014
输出：（ ）
（快速幂）请完善下面的程序，该程序使用分治法求 xp mod m 的值。
输入：三个不超过 10000 的正整数 x, p, m。
输出：xp mod m 的值。
提示：若 p 为偶数，xp = (x2)p/2；若 p 为奇数，xp = x (x2)(p-1)/2。
#include <iostream>
using namespace std;
int x, p, m, i, result;
int main()
{
cin >> x >> p >> m;
result = ①;
while(②)
{
if(p % 2 == 1)
result = ③;
p /= 2;
x = ④;
}
cout << ⑤ << endl;
return 0 ;
}（切割绳子）有 n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段，求绳段的最大长度是多少。
输入：第一行是一个不超过 100 的正整数 n，第二行是 n 个不超过 10^6的正整数，表示每条绳子的长度，第三行是一个不超过 10^8 的正整数 m。
输出 ：绳段的最大长度，若无法切割，输出 Failed。
#include <iostream>
using namespace std;
int n, m, i, lbound, ubound, mid, count;
int len[100]; //绳子长度
int main()
{
cin >> n;
count = 0;
for (i = 0; i < n; i++) {
cin >> len[i];
①;
}
cin >> m;
if (②) {
cout << "Failed" << endl;
return 0;
}
lbound = 1 ;
ubound = 1000000 ;
while (③) {
mid = ④;
count =0 ;
for (i = 0; i < n; i++ )
⑤;
if (count < m)
ubound = mid - 1 ;
else
lbound = mid ;
}
cout << lbound << endl;
return 0;
}甲乙丙丁四人在考虑周末要不要外出郊游。已知①如果周末下雨，并且乙不去，则甲一定不去；②如果乙去，则丁一定去；③如果丙去，则丁一定不去；④如果丁不去，而且甲不去，则丙一定不去。如果周末丙去了，则甲____（去了/没去），乙____（去了/没去），丁 ___ （去了/没去），周末____（下雨/没下雨）。
从 1 到 2018 这 2018 个数中，共有___个包含数字 8 的数。包含数字 8 的数是指有某一位是“8”的数，例如“2018”与“188”。
#include <cstdio>
char st[100];
int main() {
scanf("%s", st);
for (int i = 0; st[i]; ++i) {
if ('A' <= st[i] && st[i] <= 'Z')
st[i] += 1;
}
printf("%s
", st);
return 0;
}输入：
QuanGuoLianSai
输出：（ ）
#include <cstdio>
int main() {
int x;
scanf("%d", &x);
int res = 0;
for (int i = 0; i < x; ++i) {
if (i * i % x == 1) {
++res;
}
}
printf("%d", res);
return 0;
}输入：
15
输出：（ ）
#include <iostream>
using namespace std;
int n, m;
int findans(int n, int m) {
if (n == 0) return m;
if (m == 0) return n % 3;
return findans(n - 1, m) - findans(n, m - 1) + findans(n - 1, m - 1);
}
int main(){
cin >> n >> m;
cout << findans(n, m) << endl;
return 0;
}输入：
5 6
输出：（ ）