ABC265 复盘

思路解析：判断一下一次性买 3 个便宜还是 3 个分开买便宜，选更便宜的方法尽量多买剩下的单独买即可。

#include<bits/stdc++.h>
using namespace std;
int n, x, y;
int main() {
	cin >> x >> y >> n;
	if(3 * x <= y) {
		cout << n * x;	
	}
	else {
		cout << y * (n / 3) + (n - (n / 3) * 3) * x;	
	}
	return 0;
}

[ABC265B] Explore

思路解析：模拟，遇到一个有奖金的房间就给时限加上对应的 \(y\) ，同时对于每个房间都减去路程所消耗的 \(a[i - 1]\)，注意是先判断再修改时限。

错因：题意不清，没注意顺序

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll n, m, t;
ll a[N], z[N];
int main() {
	cin >> n >> m >> t;
	for(int i = 1; i < n; i++) {
		cin >> a[i];
	}
	for(int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		z[x] = y;
	}
	for(int i = 1; i < n; i++) {
		if(t <= a[i]) {
			cout << "No";
			return 0;
		}
		t -= a[i];
		t += z[i + 1];
	}
	cout << "Yes";
	return 0;
}

[ABC265C] Belt Conveyor

思路解析：模拟，我用的是 dfs ，遇到之前走过的就返回，并在返回后输出-1；如果出了地图就输出当前坐标，并exit(0)，防止多输出一个-1。

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m;
char ch[N][N];
bool vis[N][N];
map<char, int> dx, dy;
void init() {
	dx['U'] = -1;
	dx['D'] = 1;
	dy['L'] = -1;
	dy['R'] = 1;
}
void dfs(int x, int y) {
	if(vis[x][y]) return;
	vis[x][y]= true;
	int nx = x + dx[ch[x][y]], ny = y + dy[ch[x][y]];
	if(nx > 0 && nx <= n && ny > 0 && ny <= m) {
		dfs(nx, ny);
	}
	else {
		cout << x << " " << y;
		exit(0);
	}
}
int main() {
	init();
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> ch[i][j];
		}
	}
	dfs(1, 1);
	cout << "-1";
	return 0;
}

[ABC265D] Iroha and Haiku (New ABC Edition)

思路解析：二分，枚举 \(x\)，剩下的变量二分即可。

错因：\(x\) 应从 \(0\) 开始枚举

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll n, a[N], p, q, r;
ll s[N];
int main() {
	cin >> n >> p >> q >> r;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	for(int i = 0; i <= n - 3; i++) {
		int pos1 = lower_bound(s + 1, s + n + 1, p + s[i - 1]) - s;
		if(s[pos1] - s[i - 1] == p) {
			int pos2 = lower_bound(s + 1, s + n + 1, q + s[pos1]) - s;
			if(s[pos2] - s[pos1] == q) {
				int pos3 = lower_bound(s + 1, s + n + 1, r + s[pos2]) - s;
				if(s[pos3] - s[pos2] == r) {
					cout << "Yes";
					return 0;
				}
			}
		}
	}
	cout << "No";
	return 0;
}

思路解析：靠着张老师点醒我们，也是成功在赛时切掉。用 dp，首先我们对于二维矩阵不能开 \(10^9\) 的数组，于是可以发现我们经过的每一个点都是由题目里的三种操作得来的，所以我们遍历到的每一个点都可以用 \(i\) 个操作一 \(+\) \(j\) 个操作二 \(+\) \(k\) 个操作三表示出来，于是我们定义 dp[i][j][k] 代表这个点经过了 \(i\) 个操作一 \(+\) \(j\) 个操作二 \(+\) \(k\) 个操作三这么多的操作，然后由于每一个点都可以从三种状态中的任意一中推过来，所以状态计算自然就是 dp[i][j][k] = dp[i - 1][j][k] + dp[i][j - 1][k] + dp[i][j][k - 1]。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PII pair<int, int>
const int M = 1e5 + 10;
const int mod = 998244353;
ll n, m, a, b, c, d, e, f;
ll x[M], y[M];
ll dp[310][310][310];
map<PII, int> mp;
int main() {
	cin >> n >> m >> a >> b >> c >> d >> e >> f;
	for(int i = 1; i <= m; i++) {
		cin >> x[i] >> y[i];
		mp[{x[i], y[i]}] = 1;
	}
	dp[0][0][0] = 1;
	ll ans = 0;
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= n; j++) {
			for(int k = 0; k <= n; k++) {
				if(i > 0) {
					dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % mod;
				}
				if(j > 0) {
					dp[i][j][k] = (dp[i][j][k] + dp[i][j - 1][k]) % mod;
				}
				if(k > 0) {
					dp[i][j][k] = (dp[i][j][k] + dp[i][j][k - 1]) % mod;
				}
				ll xx = i * a + j * c + k * e;
				ll yy = i * b + j * d + k * f;
				if(mp.find({xx, yy}) != mp.end()) {
					dp[i][j][k] = 0;
				}
				if(i + j + k == n) {
					ans = (ans + dp[i][j][k]) % mod;
				}
			}
		}
	}
	cout << ans;
	return 0;
}