~~今天是特别崩溃的一天~~

又到了一天一篇的博客时刻

今天上午进行了一场模拟赛，题和代码并不是很难，主要是对于题目信息的理解和算法的变形。

那么，今天就针对我会的几道题，简要的写一下题解。

T1:#abc218bL. qwerty

本题为首题，难度较低，使用一个

int

(整形)数据映射出对应的字符即可。

CPP

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn (int)(1*(1e5)+10)
using namespace std;
int a[30];
int main()
{
	for(int i = 1;i <= 26; i++)
		cin >> a[i];
	for(int i = 1;i <= 26; i++)
		cout << (char)(a[i]+96);
	return 0;
}

T2:Cheese

本题是比较典型的贪心基础题，只需要将奶酪美味程度按照从大到小的顺序，将重量

w

取完即可。

CPP

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn (int)(3*(1e5)+10)
using namespace std;
ll n, w, ans;
priority_queue<pair<ll, ll> > pq;
int main() {
	cin >> n >> w;
	for(int i = 1; i <= n; i++) {
		ll a, b;
		cin >> a >> b;
		pq.push({a, b});
	}
//	cout << '\n';
	while(w > 0 && !pq.empty()) {
		auto x = pq.top().first, y = pq.top().second;
		
		pq.pop();
		ans += x*y;
		w -= y;
//		cout << w << ' ' << ans << '\n';
		if(w == 0)
			break;
		if(w < 0) {
			ans -= abs(w * x);
			break;
		}
	}
	cout << ans;
	return 0;
}

T3:烧水

本题主要是统计同一个时段内同时接水看出水效率能否达到要求的题目，由此可知，这是一个区间修改、单点查询的题目，~~所以我们可以用线段树：D~~所以我们可以使用一个差分数组来解决。需要注意的是，题目要求：

0≤S_i,T_i≤2×10^5

（最小值为0）。

CPP

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn (int)(2*(1e5)+10)
using namespace std;
ll n, w;
ll a[maxn], f[maxn];
int main() {
	cin >> n >> w;
	for(int i = 1; i <= n; i++) {
		int s, t, p;
		cin >> s >> t >> p;
		f[s] += p;
		f[t] -= p;
	}
	
	for(int i = 1; i < maxn; i++) {
		 
		f[i]+=f[i-1];
		
	}
	for(int i=0;i<maxn;i++){
		if(f[i] > w) {
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
	return 0;
}

T4:网格

本题是道陷阱题，本蒟蒻和几个朋友在一开始都把它当成了常规的广搜求方案数的问题，但是本题中数值范围

2≤H,W≤1000

，使用广搜的话最坏情况最多遍历到

13×13

~~别问我怎么知道~~。不妨再来细致观察一下，从左上角的

(1,1)

到结束的

(H,W)

，其过程中各个点的方案数可以求，于是我们得到了

f[i][j]=f[i][j-1]+f[i-1][j].

状态转移方程！我们按照动态规划的思路，两层循环，AC答案！

CPP

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn (int)(1*(1e9)+7)
using namespace std;
ll h, w, ans;
ll dp[1005][1005];
char f[1005][1005];
int main()
{
	cin >> h >> w;
	for(int i = 1;i <= h; i++) {
		for(int j = 1;j <= w; j++) {
			cin >> f[i][j];
//			if(f[i][j] == '.') {
//				dp[i][j] = 1;
//			}
		}
	}
	dp[0][1] = 1;
	for(int i = 1;i <= h; i++) {
		for(int j = 1;j <= w; j++) {
			if(f[i][j] == '#') {
				continue;
			}
			dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % maxn;
	//		cout << dp[i][j] << '\t';
		}
//		cout << '\n';
	}
	cout << dp[h][w];
	return 0;
}

下面插播一条紧急消息：

欢乐赛题目题解

文章操作