正文索引 [隐藏]

传送门→

A猴子摘桃

小学奥数，掰手指都能数出来是22.

B平方和

也没啥好说的，填空题暴力就完事了。

#include <cmath>
#include <iostream>

using namespace std;

bool check(int x)
{
    while(x > 0)
    {
		int t = x % 10;
		if(t == 2 || t == 0) return true;
		x /= 10;
	}
        return false;
}

int main()
{
	long res = 0;
	for(int i = 1; i <= 2020; i++)
		if(check(i)) res += i * i;
	cout << res;
	return 0;
}

C数学家

依然是暴力。最朴实的方法就是三重循环，我也是这么去枚的，跑了几分钟吧。
还有一种更快的枚举是去枚举x与y来验证(87-x^2-y^2)开三次根的值是否符合要求，估计也不会快到哪去，也就没写。

#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;

bool c[10001];

long long poww(long long a, long long b)
{
    long long ans = 1, base = a;
    while(b != 0)
	{
		if(b & 1 != 0)
			ans *= base;
		base *= base;
		b >>= 1;
	}
    return ans;
}

int main()
{
	for (long long i = -5000; i <= 5000; i++)
		for (long long j = -5000; j <= 5000; j++)
			for(long long k = -5000; k <= 5000; k++)
				if(poww(i, 3) + poww(j, 3) + poww(k, 3) == 87 && i < j < k)
					cout << i << " " << j << " " << k << endl;
	return 0;
}

这个快速幂根本没有意义→_→

D迷宫

很板子的一道BFS 题。初始化把第一行的非1点加入队列，然后开始广搜，搜到29行的非1点就是出口。
因为BFS的层序遍历特性，如果当前的step已经比最小步数大了，那么接下来走出的任何一条路径步数都一定比最小步数多，所以此时可以直接return。

值得一提的是，在“计算最短路径条数”这类问题中，因为存在走同一个节点的情况，所以不能简单的用一个布尔数组vis去作判断。
普遍的解决方案是将vis改为一个初始值为-1的int数组。每走过一个点就将当前累积的步数更新到vis[x][y]中。如果当前累积的步数小于等于vis[x][y]，那说明可能得到更短或者等于当前最短步数的答案，所以该点合法可走。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

typedef long long ll;

int cnt = 0;
int min_step = 2000;
int n = 30, m = 50;

char mp[100][100];
int vis[100][100];

int dx[]={1,0,-1,0};
int dy[]={0,-1,0,1};

//节点结构体 
struct node 
{
    int x, y;
    int step;
};

queue<node> q;

//判断当前是否还在地图内 
inline bool is_in(int x, int y) 
{
    return x >= 0 && x < n && y >= 0 && y < m;
}

void bfs() 
{
	//设置临时节点，用来初始化队列 
    node t;
    t.x = 0;
    t.step = 0;
    //初始化队列 
    for (int i = 0; i < m; i++) 
    {
        if (mp[0][i] == '0') 
        {
            t.y = i;
            vis[0][i] = 0;
            q.push(t);
        }
    }

    while (!q.empty()) 
	{
        node nd = q.front();q.pop();
        //弹出一个点作为当前点，开始走 
        for (int i = 0; i < 4; i++) 
		{
            int nextx = nd.x + dx[i];
			int nexty = nd.y + dy[i];
            
            if (is_in(nextx, nexty) && (vis[nextx][nexty] == -1 || vis[nextx][nexty] >= nd.step + 1) && mp[nextx][nexty] == '0') 
			{
                t.x = nextx;
                t.y = nexty;
                t.step = nd.step + 1;
                q.push(t);
                vis[t.x][t.y] = t.step;//更新vis 
                
                if (nextx == n-1)//到达边界 
				{
					//步数已经超了，返回 
                    if (nd.step+1 > min_step) return;
                    //更新最短路，累加器累加 
                    min_step = nd.step + 1;
                    cnt++;
                }
            }
        }
    }
}

int main()
{
    memset(vis, -1, sizeof(vis));
    for (int i = 0; i < n; i++) cin >> mp[i];
    bfs();
    cout << cnt;
    return 0;
}

E数的逆元

这题说的很花，还定义了所谓的数域，其实就是在1~1e9+7的范围内找到那个使(i*20191031) % 1e9+7 = 1的i。填空题当然还是暴力啦。

#include <cstdio>
#include <iostream>

#define rep(a, b, c) for (long long a = b; a <= c; a++)

using namespace std;

const long long MOD = 1e9+7;

int main()
{
	rep(i, 0, MOD-1)
	{
		if((i * 20191031) % MOD == 1) cout << i << endl;
	}
	return 0;
}

也没有多慢，我也就跑了1.5秒。

F火星救援

好眼熟的题目，应该是哪一年NOIP的成年老题。没想到几年后还能见到当初刷过的老题，真是缘分到了。
这其实是一个类似贪心的策略。不难得出最有效地方法就是：车同时出发，跑了s/n里路后第一辆车报废掉自己然后把油均分给剩下的n-1辆车，如此往复。最后就转换成了求

[latexpage]
s * (1 + \frac{1}{2} + \frac{1}{3} + … + \frac{1}{n})

对于多组数据，预处理一下就好。

#include <cstdio>
#include <cstring>
#include <iostream>

#define lget(x) scanf("%lld", &x)
#define rep(a, b, c) for(int a = b; a <= c; a++)

using namespace std;

const int LIM = 1000010;

double f[LIM];
long long t, n, s;

int main()
{
	rep(i, 1, 1000000)
		f[i] = f[i-1] + (1.0/i);
	lget(t);
	while(t--)
	{
		lget(n);
		lget(s);
		printf("%lf\n", s * f[n]);
	}
	return 0;
}

G决斗

这题挺水的，都不知道为什么会在这个位置。根据题意直接写就行了，感觉没有什么坑啊。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

#define get(x) scanf("%d", &x)
#define lget(x) scanf("%lld", &x)
#define set(a,b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (int a = b; a <= c; a++)

using namespace std;

const int INF = 0X7F7F7F7F;
const int LIM = 200010;

int f[LIM];
int n, k, p;
long long tot;

int main()
{
	cin >> n;
	rep(i, 1, n)
	{
		get(f[i]);
		tot = (tot + f[i]) % n;
	}
	tot += 1;
	cin >> k;
	cout << tot << endl;
	f[int(tot)] < k ? printf("Win") : printf("Escape");
	return 0;
}