NOIP2015普及组复赛 解题分析

1.金币

算法分析

直接模拟。

#include 
#include 
#include 
using namespace std;
int main()
{
	int i=1,sum=0,ans=0,n;
	scanf("%d",&n);
	while(1)
	{
		sum+=i;  // sum是天数  
		if(sum>n) break;
		ans+=i*i;
		++i;
	}
	ans+=(n-sum+i)*i;
	printf("%dn",ans);
	return 0;
}

算法拓展

1.打表法。可以预处理出每一天获得的金币数量，最后从前到后加起来就能得到答案。最多10000天，复杂度很小。

#include 
#include 
#include 
using namespace std;
int f[10010];
int main()
{
	int sum = 0; // 天数 
	int k;
	cin>>k;
	for (int i = 1; i <= 10000; ++i)
	{
		if (sum > 10000) break;
		for (int j = sum + 1; j <= sum + i; ++j)
			f[j] = i;
		sum += i; 
	} 
	int ans = 0;
	for (int i = 1; i <= k; ++i) ans += f[i];
	cout< 
2.数学分析法。平方和公式：
    
     
      
       
        n
       
       
        (
       
       
        n
       
       
        +
       
       
        1
       
       
        )
       
       
        (
       
       
        2
       
       
        n
       
       
        +
       
       
        1
       
       
        )
       
       
        /
       
       
        6
       
      
      
       n(n+1)(2n+1)/6
      
     
    n(n+1)(2n+1)/6。可以通过循环计算出前
    
     
      
       
        k
       
      
      
       k
      
     
    k天包含了几个完整平方，利用公式快速计算。
 
#include 
#include 
#include 
using namespace std;
int main()
{
	int k;
	cin>>k;
	int n = 0, sum = 0; // sum：天数 
	while (1)
	{
		++n;
		if (sum + n > k) break;
		sum += n; 
	} 
	--n;
	int ans = n * (n + 1) * (2 * n + 1) / 6;
	ans += (k - sum) * (n + 1);
	cout< 
2.扫雷游戏
 
算法分析
 
对于
    
     
      
       
        n
       
      
      
       n
      
     
    n行
    
     
      
       
        m
       
      
      
       m
      
     
    m列的字符数组的读入需要注意的是，建议用
    
     
      
       
        c
       
       
        i
       
       
        n
       
      
      
       cin
      
     
    cin读入，不要用
    
     
      
       
        s
       
       
        c
       
       
        a
       
       
        n
       
       
        f
       
      
      
       scanf
      
     
    scanf。因为
    
     
      
       
        s
       
       
        c
       
       
        a
       
       
        n
       
       
        f
       
      
      
       scanf
      
     
    scanf加
    
     
      
       
        %
       
       
        c
       
      
      
       %c
      
     
    %c会把空格和回车当字符读入，造成错误。
 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
char c[110][110];
int main()
{
	int n, m; 
	cin>>n>>m;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			cin>>c[i][j];
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			if (c[i][j] == '*') cout<<"*";
			else
			{
				int num = 0;
				if (c[i-1][j] == '*') ++num;
				if (c[i][j+1] == '*') ++num;
				if (c[i+1][j] == '*') ++num;
				if (c[i][j-1] == '*') ++num;
				if (c[i-1][j-1] == '*') ++num;
				if (c[i-1][j+1] == '*') ++num;
				if (c[i+1][j+1] == '*') ++num;
				if (c[i+1][j-1] == '*') ++num;
				cout< 
3.求和
 
算法分析