思维构造】Game with Chips—CF1327C"/>
【思维构造】Game with Chips—CF1327C
Game with Chips—CF1327C
思路
方法很暴力。
先整体向上移动 n − 1 n-1 n−1 格,再整体向左移动 m − 1 m-1 m−1 格。然后呈 S 型从左上(初始位置)移动,直到遍历完所有的 n ∗ m n*m n∗m 个格子。
易知这种方法满足题目要求“each chip visits the position that Petya selected for it at least once”。
这种方法需要的操作次数 n − 1 + m − 1 + n ∗ m − 1 < = n ∗ m + 1 n-1 + m-1 + n*m-1 <= n*m+1 n−1+m−1+n∗m−1<=n∗m+1 (暴力遍历 n n n、 m m m 的所有数值大小得出),即所有输入情况都可以使用这种方法,不用考虑操作次数超出要求。
C o d e Code Code
#include <bits/stdc++.h>
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 2e5 + 10;int n, m, k;void solve(int Case) {cin >> n >> m >> k;for (int i = 1; i <= 2 * k; i ++) {int x, y; cin >> x >> y;}cout << n-1 + m-1 + n*m-1 << "\n";for (int i = 1; i <= n - 1; i ++) cout << "U";for (int i = 1; i <= m - 1; i ++) cout << "L";for (int i = 1; i <= n; i ++) {for (int j = 1; j <= m - 1; j ++) {cout << "LR"[i % 2 != 0];}if (i != n) cout << "D";}cout << "\n";
}signed main() {cin.tie(0)->ios::sync_with_stdio(false);int T = 1;
// cin >> T; cin.get();int Case = 0;while (++ Case <= T) solve(Case);return 0;
}
更多推荐
【思维构造】Game with Chips—CF1327C
发布评论