题目提交网站

A

答案：1478

B

**文字游戏题，答案自取，不多bibi
不算012，答案为4
算012，，答案为14
算倒序（321），答案为15
算倒序（210），答案为47

C

思路

先算出一周做题量，可以得出周数，剩下的直接暴力判断就行，水题

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll a, b, n;
	cin >> a >> b >> n;
	ll week = a * 5 + b * 2, ans = 0;
	ans += n / week * 7;
	n %= week;
	if(n > 5 * a) {
		ans += 5;
		n -= 5 * a;
		if(n > 0) n -= b, ans += 1;
		if(n > 0) n -= b, ans += 1;
	}
	else {
		ans += (n + a - 1) / a;
	}
	cout << ans << '\n';

	return 0;
}

D

思路

不难相出，答案就是当前花的左右距离最大值的二倍。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> ans(n + 1);
	for(int i = 1; i <= n; i++) {
		int l = i - 1;
		int r = n - i;
		ans[i] = max(l, r) * 2;
	}
	for(int i = 1; i <= n; i++) cout << ans[i] << '\n';
	return 0;
}

E

思路

没读懂题，后边补上。。。大家读懂的可以给我评论个题意

F

思路

我赛场上先是写了发$O(n^4)$的大暴力，后边写完所有题了再回来优化了一下，最终复杂度为$O(n^3)$。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int maxn = 5e2 + 5;
int a[maxn][maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> a[i][j];
			a[i][j] += a[i - 1][j];
		}
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = i; j <= n; j++) {
			int tmp = 0, l = 1, r = 0;
			while(r <= m && l <= m) {
				while(r + 1 <= m && tmp + a[j][r + 1] - a[i - 1][r + 1] <= k) {
					r++;
					tmp += a[j][r] - a[i - 1][r];
				}
				ans += r - l + 1;
				tmp -= a[j][l] - a[i - 1][l];
				l++;

			}
		}
	}
	cout << ans << '\n';

	return 0;
}

G

思路

看到所有题目后最先开的这个题，讲一下我思路

首先引入一个题目，用$1\ast 2$的骨牌填满$2\ast n$的方格，问方案数是多少？
设$f[i]$为长度为$i$时的方案数，不难得出$f[1]=1,f[2]=2$，那么当$i=3$的时候状态转移方程是什么样的呢？

• 我们考虑结尾是一条竖着的骨牌，并且前$i-1$长度的状态我们已经得出了，所以有$f[i]+=f[i-1]$
• 我们考虑结尾是两个横着的骨牌，并且前$i-2$长度的状态我们已经得出了，所以有$f[i]+=f[i-2]$
• 有同学会问，那结尾还可以是两个竖着的呢？我们仔细想，这个状态真的是我们需要的吗？在第一个状态里，结尾为一个竖着的骨牌，并且在$f[i-1]$这个状态里也包含了结尾有一个竖着的骨牌的状态，所以我们不需要结尾是两个竖着的骨牌状态。
• 所以得出，$f[i]=f[i-1]+f[i-2]$

那我们把这种想法带入到本题当中，并且考虑结尾的状态

经过分析可以得出状态转移方程
$f[0]=1,f[1]=1,f[2]=2,i\le 2$
$f[i]=f[i-1]+f[i-2]+2\ast f[i-3]+.....+2\ast f[0],i\ge 3$
但是复杂度是$O(n^2)$的，我们考虑优化
对于转移方程的后面部分，共同带有2倍，我们可以用一个变量代替，并且每次循环的时候加上$f[i-3]$ 的值就行了，复杂度$O(n)$

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int mod = 1e9 + 7;

int main() {
	int n;
	cin >> n;
	vector<ll> f(n + 1);
	f[0] = 1, f[1] = 1, f[2] = 2;
	ll pre = 0;
	for(int i = 3; i <= n; i++) {
		f[i] = (f[i - 1] + f[i - 2]) % mod;
		pre = (pre + f[i - 3] * 2) % mod;
		f[i] = (f[i] + pre) % mod;
	}
	cout << f[n] << '\n';
	
	return 0;
}

H

思路

• 注意，给出的爆炸半径都是小于等于10的
• 一个点处可能有多个炸弹
• 所以我们设当前点的坐标为$(x,y)$，我们只需要枚举$((x-10,x+10),(y-10,y+10))$这个范围内的点就行了，复杂度由$O(n^2)$降为$O(400\ast n)$，剩下的就是普通BFS了。

代码

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>

using namespace std;

bool cek(pii a, pii b, int r) {
	double dis = 0;
	double x1 = a.first, y1 = a.second;
	double x2 = b.first, y2 = b.second;
	dis = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
	return dis <= r;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	map<pii, int> m1, m2, cnt;
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		int x, y, r;
		cin >> x >> y >> r;
		cnt[pii(x, y)]++;
		m1[pii(x, y)] = max(m1[pii(x, y)], r);
	}
	for(int i = 1; i <= m; i++) {
		int x, y, r;
		cin >> x >> y >> r;
		m2[pii(x, y)] = max(m2[pii(x, y)], r);
	}
	map<pii, int> vis;
	queue<pair<pii, int>> q;
	for(auto it : m2) {
		q.push(it);
		vis[it.first] = 1;
	}
	int ans = 0;
	while(q.size()) {
		pair<pii, int> now = q.front();
		q.pop();
		int x = now.first.first, y = now.first.second, r = now.second;
		for(int i = -10; i <= 10; i++) {
			for(int j = -10; j <= 10; j++) {
				if(i == 0 && j == 0) continue;
				int nx = x + i;
				int ny = y + j;
				if(vis.count(pii(nx, ny)) == 0 && m1.count(pii(nx, ny)) != 0) {
					if(cek(now.first, pii(nx, ny), r)) {
						q.push(pair<pii, int>(pii(nx, ny), m1[pii(nx, ny)]));
						vis[pii(nx, ny)] = 1;
						ans += cnt[pii(nx, ny)];
					}
				}
			}
		}
	}
	cout << ans << '\n';

	return 0;
}

I

思路

• 全分：记忆化搜索/DP
• 骗部分分：二进制枚举/ 暴力DFS
  $dp[i][j][k]$代表当前到第$i$位，遇到了$j$次店，还剩$k$斗酒。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int maxn = 205;
const int mod = 1e9 + 7;

ll dp[maxn][maxn][maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	dp[0][0][2] = 1;
	for(int i = 1; i <= n + m; i++) {
		for(int j = 0; j <= n; j++) {
			for(int k = 1; k <= n + m; k++) {
				if(k % 2 == 0) dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][k >> 1]) % mod;
				dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k + 1]) % mod;
			}
		}
	}
	int ans = 0;
	cout << dp[n + m - 1][n][1] << '\n';

    return 0;
}

J

思路

• 并查集+优先队列
• 如果$a[i]=a[i-1]$，那么合并，并且维护当前集合的祖先是当前集合编号最小的编号
• 每次取最大的，砍掉，直到结束

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll gao(ll x) {
	return sqrt(x / 2 + 1);
}

struct DSU {
	int n;
	vector<int> fa, rank;
	DSU(int n_ = 0) : n(n_), fa(n_ + 1), rank(n_ + 1) {
		iota(fa.begin(), fa.end(), 0);
	}

	int find(int x) {
		return x == fa[x] ? x : fa[x] = find(fa[x]);
	}

	void merge(int x, int y) {
		x = find(x), y = find(y);
		if(x == y) return ;
		if(y > x) swap(x, y);
		fa[x] = y;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<ll> a(n + 2, -0x3f3f3f3f);
	priority_queue<pair<ll, int>> q;
	DSU dsu(n + 2);
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		q.push(pair<ll, int>(a[i], i));
	}
	for(int i = 2; i <= n; i++) {
		if(a[i] == a[i - 1]) {
			dsu.merge(i, i - 1);
		}
	}
	ll ans = 0;
	while(q.size()) {
		pair<ll, int> now = q.top();
		q.pop();
		ll x = now.first, id = now.second;
		bool ok = 0;
		if(a[id] == 1) continue;
		if(dsu.find(id) != id) continue;
		if(a[dsu.find(id)] == a[dsu.find(id - 1)]) {
			dsu.merge(id, id - 1); 
			continue;
		}
		a[id] = gao(a[id]);
		ans++;
		if(a[dsu.find(id)] == a[dsu.find(id - 1)]) {
			dsu.merge(id, id - 1); 
			continue;
		}
		q.push(pair<ll, int>(a[id], id));
	}
	cout << ans << '\n';
	return 0;
}