ABC265 复盘
[ABC265A] Apple
思路解析：判断一下一次性买 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;
}
[ABC265E] Warp
思路解析：靠着张老师点醒我们，也是成功在赛时切掉。用 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;
}