A

签到题，小学奥数（拓展阅读：牛吃草问题）

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int s1 = 15 * 20;
	int s2 = 20 * 10;
	
	cout << (s1 - s2) / (20 - 10) << endl;	
	
	return 0;
}

B

签到题，回忆 printf 保留宽度输出。

长脑子复习：最小数字宽度

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int a[5];
	for (int i = 0; i < 5; i ++ ) cin >> a[i];
	
	for (int i = 0; i < 5; i ++ )
	{
		a[i] /= 3;
		
		if (i - 1 < 0) a[4] += a[i];
		else a[i - 1] += a[i];
		if (i + 1 > 4) a[0] += a[i];
		else a[i + 1] += a[i];
	}
	
	for (int i = 0; i < 5; i ++ )
		printf("%5d", a[i]);
	
	return 0;
}

C

做法：依次遍历每一个数字求和，超过 m 就新开一段，最终输出总段数即可。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, m, s = 0, cnt = 1;
	cin >> n >> m;
	
    while (n -- )
	{
        int a;
        cin >> a; 
        if (s + a <= m)	s += a;
        else
		{
            cnt ++;
            s = a;
        }
    }
    cout << cnt << endl;
    
	return 0;
}

D

练习 string ，未学高中生物DNA知识根据题意自学即可。

#include <bits/stdc++.h>
using namespace std;

int main() 
{
    string a;
    cin >> a;

    for (int i = 0; i < a.size(); i ++ ) 
	{
        if (a[i] == 'A')
            cout << 'T';
        else if (a[i] == 'T')
            cout << 'A';
        else if (a[i] == 'G') 
            cout << 'C';
        else cout << 'G';
    }

    return 0;
}

E

NOIP2008普及组

做法：跳过字符 - 用 printf 直接读入数字

#include<bits/stdc++.h>
using namespace std;

int main()
{
	char a[20], t1, t2;
	int s = 0;
	scanf("%c-%c%c%c-%c%c%c%c%c-%c", 
	&a[1], &a[2], &a[3], &a[4], &a[5], &a[6], &a[7], &a[8], &a[9], &t1);
	
	for(int i = 1; i <= 9; i ++ )
		s += (a[i] - '0') * i;
	
	t2 = s % 11 + '0';
	if(t2 == 10 + '0') t2 = 'X';
	if(t1 == t2)
	{
		cout << "Right" << endl;
		return 0;
	}
		
	printf("%c-%c%c%c-%c%c%c%c%c-%c", 
	a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9], t2);
	return 0;
 }

F

模拟题，每个能量元素补充的体力范围为 [1, N] ，为保证战斗期更持久（战斗力增长大），每次作顶格补充，超过 M 的部分再减去即可，枚举每一个能量元素，当用完的时候即战斗力最大。

#include<bits/stdc++.h>
using namespace std;

int main() 
{
	int M, N, X, S = 0; // 体力值M，战斗力N，能量元素X 
	cin >> M >> N >> X;
	while(X)
	{
		X -- ;
		S += N;
		if(S >= M) 
		{
			S = M;
			while(S) 
			{
				if(S % N == 0)// 雇佣兵每连续战斗n天，战斗力就会上升1点
					N ++ ;
				S -- ;// 战斗期结束体力值将为0
			}
		}
	}
	
	cout << N << endl;
	
	return 0;
}

G

智慧数 = 两个正整数的平方差，设 a 为智慧数，则 a = b - c ，则 b < a，不用考虑 n 个智慧数的存储，直接枚举判断输出即可。

#include <bits/stdc++.h>
using namespace std;

bool check(int x)
{
	for (int i = 2; i <= x; i ++ )
		for (int j = 1; j <= i - 1; j ++ )
			if (i * i - j * j == x) return true;
	
	return false;
}

int main()
{
	int n, cnt = 0;
	cin >> n;
	
	for (int i = 1; ; i ++ )
	{
		if (check(i)) cnt ++ ;
		if (cnt == n)
		{
			cout << i << endl;
			return 0;
		}
	}
	
	return 0;
 }

H

NOIP2004普及组

算法：贪心、全排列，O(nm)

做法1：这道题目可以直接用 next_permutation 函数来做。

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;

int n, m;
int a[N];

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
	
	while (m -- ) next_permutation(a, a + n);
	
	for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);	
	
	return 0;
}

做法2：这里我们考虑一下 next_permutation 函数的原理，然后手动实现一遍。

对于给定的某个排列，我们想求出比它大的最小的排列。 可以从后往前遍历这个排列，找到第一个可以让排列的字典序变大的位置。

只有当序列单调下降时，它才不存在更大的排列，因此我们要找的位置就是第一次出现 ak−1<ak的位置。

那么此时将 ak−1变成比它大的最小数，然后将剩余部分从小到大排序，得到的排列就是比原排列大的最小排列了。

这里有个小优化：

由于 ak−1后面的部分已经从大到小排好序，因此只需将其翻转，就可以得到从小到大排序的结果了，不需要使用 sort函数，时间效率可以降到线性。

时间复杂度 一共求 m次next_permutation，每次需要 o(n)的时间，因此总时间复杂度是 O(nm)。

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;

int n, m;
int a[N];

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    while (m -- )
    {
        int k = n - 2;
        while (a[k] > a[k + 1]) k -- ;
        int t = k + 1;
        while (t + 1 < n && a[t + 1] > a[k]) t ++ ;
        swap(a[t], a[k]);
        reverse(a + k + 1, a + n);
    }

    for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);

    return 0;
}

做法3：康拓展开

I

NOIP2006普及组

算法：排序、去重，O(nlogn)

考察了两个函数的使用：

sort：可以将序列排序。

unique：可以将序列中所有相邻的重复元素删除（只保留一个）。此处的删除，并不是真的删除，而是指重复元素的位置被不重复的元素覆盖了。最后会返回不重复序列的后一个位置。

时间复杂度：

sort需要 O(nlogn)的时间，unique需要 O(n)的时间，因此总时间复杂度是 O(nlogn)。

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int n;
int a[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    sort(a, a + n);
    int k = unique(a, a + n) - a;
    printf("%d\n", k);
    for (int i = 0; i < k; i ++ ) printf("%d ", a[i]);
    return 0;
}

J

算法：去重函数 unique

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;

int n, s;
int a[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) 
	{
		scanf("%d", &a[i]);
		s += a[i];
	}
    sort(a, a + n, greater<int>());
    cout << s << endl << a[0] << endl << a[n - 1] << endl;
    
    int k = unique(a, a + n) - a;
    for (int i = 0; i < k; i ++ ) printf("%d ", a[i]);
    return 0;
}