Personal solution.
A. Yet another permutation problem
背景
来自 Codeforces Round 876 (Div. 2) D题。
*2100 dp.
题意
给定一个 \(n\) 的排列 \(a\)，对于整数 \(k\)，按照下面的操作进行排序：
在排列中任意添加 \(k\) 个 \(0\)；
在一次操作中，可选择一个和 \(0\) 相邻的元素，并将其移动到任何位置。
对于 \(k \in [1, n]\)，输出第二种操作最少需要几次，才能让排列升序。
思路
\(dp\)。
首先，既然需要最少操作，不妨找到最长递增子序列，因而我们会发现，我们只需用该序列的元素将排列分段，每一段放上一个 \(0\)，即可让需要的 \(0\) 个数最少。如果个数不够，那怎么去掉呢？如何优先选择呢？
上面的思路很显然，但存在一种情况：有多个最长递增子序列。因而，这种 "暴力" 的方法不可行。
既然上面的子序列问题已经需要使用 \(dp\) 了，我们不妨想想如何用 \(dp\) 直接解决。
上面，我们提到了分段的概念，那么我们可以将其应用到单个元素的状态区分上。
对于一个元素，他有下面三种状态：
和它相邻的元素比他小，那么它可以作为前面那个元素所在递增段的一部分；
和他前面不相邻的元素比他小，那么它可以成为新的一个递增段；
前面没有一个元素比他小，那么 它注定会被移动
因而，我们定义 \(dp[i][j]\) 为前 \(i\) 个位置分了 \(j\) 段，可得出下面的状态转移方程：
如果 \(a[i - 1] < a[i]\)，那么 \(dp[i][j] = dp[i - 1][j]\)；
对于 \(p \in [0, i - 1]\)，如果 \(a[k] < a[i]\)，那么 \(dp[i][j] = \min(dp[i][j], dp[k][j - 1] + i - k - 1)\)，其中 \(i - k - 1\) 为 \(i, k\) 之间元素的数量。
时间复杂度：\(O(n ^ 3)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 2);
for(int i=1;i<=n;i++) cin >> a[i];
a[n + 1] = inf;
vector<vector<int>> dp(n + 2, vector<int>(n + 1, inf));
for(int i=0;i<=n;i++) dp[0][i] = 0;
for(int i=1;i<=n+1;i++){ //遍历到哪个元素
for(int j=0;j<=n;j++){ //分多少块
if(a[i - 1] < a[i]) dp[i][j] = dp[i - 1][j]; //相邻满足递增，不分块
if(j > 0){
for(int k=0;k<i;k++){
if(a[k] < a[i]) dp[i][j] = min(dp[i][j], dp[k][j - 1] + i - k - 1); //不相邻，分块
}
}
}
}
for(int i=1;i<=n;i++) cout << dp[n + 1][i] << ' ';
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}意义是防穿，但是没防住
B. Yet another A-B problem
题意
给定一串数字，以及一个差值，输出所有数对中，差值的绝对值为所给差值的数量。
思路
签到题。
记录每个数字对应的数量，然后扫一遍即可。
本题削弱了数据范围，不然需要离散化或者哈希。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, c;
cin >> n >> c;
vector<int> a(n + 1);
vector<int> cnt(n + 1);
for(int i=1;i<=n;i++) {
cin >> a[i];
cnt[a[i]] ++;
}
int ans = 0;
for(int i=1;i<=n;i++){
if(a[i] - c >= 1) ans += cnt[a[i] - c];
if(a[i] + c <= n) ans += cnt[a[i] + c];
}
cout << ans / 2 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}没想到有那么多人写暴力，完全是意料之外
C. Cls, Orz is giving me a hard time
题意
对于集合 \(A = \{3^0, 3^1, \ldots, 3^{n - 1}\}\)，定义 \(B\) 为 \(A\) 的所有非空子集，\(B\) 的值为集合内所有元素的和。
输出第 \(k\) 小的 \(B\) 的值。
思路
简单思维题，进制转换。
类比于 \(2\) 进制，我们不难发现，我们只是把二进制表示法的底数换为了 \(3\)。
比如一个二进制数 \(1001101\)，用 \(3\) 为底数，就可以表示为 \(1 \cdot 3^6 + 0 \cdot 3 ^ 5 + 0 \cdot 3 ^ 4 + 1 \cdot 3^3+ 1 \cdot 3^2+ 0 \cdot 3 ^ 1 + 1 \cdot 3^0\)。
显然，类比二进制，如果高位上一个为 \(1\)，一个为 \(0\)，那么前者也一定是大于后者的。
那么，我们直接将 \(k\) 转为二进制，然后将底数 \(2\) 替换为 \(3\)，再转回 \(10\) 进制即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
int ans = 0, base = 1;
while(n > 0){
ans += (n % 2) * base;
n /= 2, base *= 3;
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}对二进制的理解
D. Dozens of duel
题意
给定 \(10\) 次博弈，定义博弈如下：
两个玩家给出一个数，将最大的数字记为 \(x\)，并规定给出最大数的玩家为先手。保证两个人给出的数字不一样；
两个人轮流从 \(x\) 中删去一个质数或者 \(1\)，需要满足删去之后 \(x \geq 0\)；
先将 \(x\) 减为 \(0\) 的玩家获胜。
思路
博弈。
首先，如果某个人遇到了 \(4\)，那么它肯定会输。因为此时他只能选择 \(1, 2, 3\)，而无论选什么对方都能赢。
其次，如果某个人遇到了 \(4\) 的倍数，那么：
如果他拿掉了偶数 \(2\)，对方就可以拿掉偶数 \(2\)；
如果他拿掉了一个 \(1\)，或者其他奇质数，对方就可以对应拿掉 \(1\) 或者 \(3\)。
这样的话，无论如何，对方都能让这个人处于 \(4\) 的倍数中，从而最后到达 \(4\) 这个必败态。
从而，我们只要看一开始的数字是什么即可，如果是 \(4\) 的倍数，那么后手赢，否则先手赢。
时间复杂度：\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int _t = 10;
while(_t --){
int n1, n2;
cin >> n1 >> n2;
int ans = n1 > n2 ? 0 : 1,
n = max(n1, n2);
if(n % 4 == 0) ans ++;
cout << ans % 2 + 1 << '\n';
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}博弈可以乱猜！（
E. Puteng Puteng Bird
题意
给定一串操作序列，每个操作包含一个位运算 \(\mathtt{And, Or, Xor}\) 以及一个数字 \(x\)，你需要将当前数字与 \(x\) 进行指定的位运算。
现在，给定初始值的最大值 \(M\)，确定任意一个开始值，使操作结束得到的数字最大，并输出这个最大的数字。
思路
位运算，贪心，思维。
首先，位运算是一位一位运算的。
而我们可以发现，在本题中，每一位之间的操作是 相互不影响 的。
那么，我们只需贪心地从高位开始枚举，尽可能让最后的结果中，高位为 \(1\)，且满足初始值在范围内即可。
时间复杂度：\(O(n \log T_{\max})\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m;
cin >> n >> m;
vector<pii> a(n + 1);
for(int i=1;i<=n;i++){
string now;
cin >> now >> a[i].sc;
if(now == "OR") a[i].fs = 1;
else if(now == "AND") a[i].fs = 2;
else a[i].fs = 3;
}
auto cal = [&](int x){
for(auto [tp, v] : a){
if(tp == 1) x |= v;
else if(tp == 2) x &= v;
else x ^= v;
}
return x;
};
int ans = 0;
for(int i=31;i>=0;i--){
if(ans + (1ll << i) > m) continue;
if((cal(ans) & (1ll << i)) < (cal(ans + (1ll << i)) & (1ll << i))) ans += 1ll << i;
}
cout << cal(ans) << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}关键在于看不看得出来每一位独立
F. Project of pulling water
背景
来自 Universal Cup Season 1 Stage 22 K题。
题意
对于一个 \(0, 1\) 矩阵，定义一次操作为选定一个值为 \(0\)，且相邻 \(4\) 个格子中，至少有两个格子是 \(1\) 的格子，并将其修改为 \(1\)。
执行若干次操作，直到无法操作时，如果所有格子都是 \(1\)，那么符合条件。
输出符合条件的一种构造，满足矩阵内 \(1\) 的个数最少。
思路
构造，思维。
首先，如果一行都是 \(1\)，那么只要隔一行之后，在另一行任意位置插入一个 \(1\)，就可以让这两行都变为 \(1\)，可以画图理解。
那么，现在的问题就是找出让一行全变为 \(1\) 的最小代价的构造。
我们可以发现，我们只要找出最大的一个正方形，然后将其一条对角线全都填上 \(1\)，就可以让整个正方形全都变为 \(1\)。
那么，如下是一个可行的构造方式：
1 0 0
0 1 0
0 0 1
0 0 0
1 0 0
0 0 0
1 0 0
1 0 0其中，前三行是我们所说的正方形，之后我们隔一行放入一个 \(1\)，注意最后一行一定要有 \(1\)，不然最后一行会空出来。
时间复杂度：\(O(n m)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m;
cin >> n >> m;
int a = n, b = m;
if (a < b) swap(a, b);
cout << (b + (a - b + 1) / 2) << '\n';
vector<vector<int>> ans(n + 1, vector<int>(m + 1));
for (int i = 1; i <= min(n, m); i++) ans[i][i] = 1;
if (n > m){
for(int i=min(n, m)+2;i<=n;i+=2) ans[i][1] = 1;
ans[n][1] = 1;
}else if(n < m){
for(int j=min(n, m)+2;j<=m;j+=2) ans[1][j] = 1;
ans[1][m] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << ans[i][j] << ' ';
}
cout << '\n';
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}MC的特性！
G. Word Search
题意
给定一个字符矩阵，定义当且仅当两个字符的 \(\max(x\) 轴距离的绝对值 \(, y\) 轴距离的绝对值 \() \leq 1\) 时两个字符相邻。
给定 \(q\) 个询问，每次询问给出一个字符串 \(s\)，判断字符矩阵中是否存在连续的一串字符，满足下标不重复，且等于 \(s\)。
思路
回溯搜索。
数据范围很小，所以我们可以直接爆搜。
我们枚举所有合法的点作为起点，然后进行深度优先搜索 \(\mathtt{dfs}\)，最后判断是否合法即可。
注意，本题需要进行回溯搜索。
时间复杂度：\(O(nm\cdot8 \cdot 7^{len-1})\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m, q;
cin >> n >> m >> q;
vector<string> s(n);
for(int i=0;i<n;i++) {
cin >> s[i];
transform(s[i].begin(), s[i].end(), s[i].begin(), ::tolower);
}
bool ok = false;
vector<vector<bool>> st(n + 1, vector<bool>(m + 1));
vector<pair<int, int>> dxy = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
auto dfs = [&](auto dfs, int x, int y, int now, string &p) -> void{
if(now == p.size()){
ok = true;
return;
}
if(ok) return;
for(auto [dx, dy] : dxy){
int tx = x + dx, ty = y + dy;
if(tx >= 0 && ty >= 0 && tx < n && ty < m && !st[tx][ty] && p[now] == s[tx][ty]){
st[tx][ty] = true;
dfs(dfs, tx, ty, now + 1, p);
st[tx][ty] = false;
}
}
};
while(q --){
string p;
cin >> p;
transform(p.begin(), p.end(), p.begin(), ::tolower);
ok = false;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(s[i][j] == p[0]){
st[i][j] = true;
dfs(dfs, i, j, 1, p);
st[i][j] = false;
if(ok) break;
}
}
if(ok) break;
}
cout << (ok ? "YES\n" : "NO\n");
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}非常裸的搜索题
H. Baba's Radar
背景
来自 POJ - Radar Installation.
题意
给定若干个在 \(x\) 轴上方的点，在 \(x\) 轴上放置尽可能少的圆，其中圆的半径 \(r\) 给定，使得所有点都被覆盖。
思路
贪心，\(dp\)，区间覆盖。
首先，我们可以发现，对于一个点，能覆盖到该点的雷达的范围是以该点为圆心，\(2r\) 为半径的圆。
而我们只能在 \(x\) 轴放置雷达，从而如果我们在 \(x\) 轴和该圆的交点所构成的弦上放置雷达，就能让这个点能被覆盖到。
从而，问题转化为，给定若干个线段，去除尽可能多的线段，使最后所有原先给定的线段都与删除后的线段有交集。
我们从左往右考虑：
如果我们需要删除尽可能多的线段，我们一定希望当前选择的线段，它能拓展到的右边界尽可能大。
那么我们不妨直接贪心地将所有线段按照右端点升序排序，然后从左往右取出线段。
此时，如果 当前线段的左端点 小于等于 前面选择的所有线段的右端点最大值，我们就无需选上这个线段，因为这个线段一定和最后的总线段有交集。而相反的，如果 当前线段的左端点 大于 前面选择的所有线段的右端点最大值，那么我们就需要选上这个线段，同时我们更新右端点的最大值即可。
至于如何转化为线段，勾股定理一下即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
int _r;
int _t = 1;
while(true){
cin >> n >> _r;
if (n == 0 && _r == 0) return;
vector<pair<double, double> > a(n);
bool ok = true;
for(int i=0;i<n;i++) {
int x, y;
cin >> x >> y;
if(y > _r) ok = false;
double dx = sqrt((double) _r * _r - y * y);
a[i] = {x + dx, x - dx};
}
if(!ok) {
cout << "Case " << _t << ": " << -1 << '\n';
_t ++;
continue;
}
sort(all(a));
double nr = -inf;
int cnt = 0;
for(int i=0;i<n;i++){
double l = a[i].sc, r = a[i].fs;
if (l > nr){
nr = r;
cnt ++;
}
}
cout << "Case " << _t << ": " << cnt << '\n';
_t ++;
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}就是POJ的题提交太头大了（
I. Oh, no! Where is baby O?
背景
来自 Codeforces Round 864 (Div. 2) C题。
*1600 构造+贪心+交互.
题意
给定一个矩阵，定义当且仅当两个格子的 \(\max(x\) 轴距离的绝对值 \(, y\) 轴距离的绝对值 \() \leq 1\) 时两个格子相邻。
对于一个未知位置 \(P\)，定义询问为输出一个位置的横纵坐标，并将会得到一个回复，为从未知位置走到指定位置需要的最短路径，其中每次只能移动到题意第一行所说的相邻格子上。
在最多三次询问内，确定未知位置的横纵坐标。
思路
构造，贪心，交互。
首先，如果我们知道了最短路径的长度，那么我们就可以确定这个未知位置位于以询问点为中心的一个正方形的边上。
那么，我们不妨先询问点 \((1, 1)\)。
如果我们得到的长度大于 \(\min(n, m)\)，那么可以画图发现，未知位置位于一条直线上，此时我们直接以这条直线的端点为询问，就可以通过简单的计算得到未知位置。
否则，我们将上一次询问的回复设为 \(t\)，可以发现未知位置一定在 \((x, t + 1), x \leq t + 1\) 或 \((t + 1, y), y \leq t + 1\)，上，也就是一个 "L" 型。
我们不妨询问点 \((t + 1, t + 1)\)，并记回复为 \(p\)，显然现在，两个 "L" 相交，刚好有两个交点。
显然，我们只需再以任意一个交点为询问，只要回复是 \(0\)，那么就是我们选择的点，否则就是另一个点了。
时间复杂度：\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m;
cin >> n >> m;
auto ask = [&](int x, int y) -> int{
cout << "? " << x << ' ' << y << '\n';
cout.flush();
int i;
cin >> i;
return i;
};
int t = ask(1, 1);
if(t >= min(n, m)){
if(n > m){
int p = ask(t + 1, 1);
cout << "! " << t + 1 << ' ' << p + 1 << '\n';
cout.flush();
}else{
int p = ask(1, t + 1);
cout << "! " << p + 1 << ' ' << t + 1 << '\n';
cout.flush();
}
}else{
int p = ask(t + 1, t + 1),
q = ask(t + 1 - p, t + 1);
if(q == 0) cout << "! " << t + 1 - p << ' ' << t + 1 << '\n';
else cout << "! " << t + 1 << ' ' << t + 1 - p << '\n';
cout.flush();
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}很有趣的交互题
J. I am a Master of Scout
题意
给定一个 \(n \times m\) 的矩阵，以及 \(q\) 个询问。
定义一次询问为给定一个坐标 \((x, y)\)，并以该坐标为原点，建立坐标系，输出第二象限和第四象限的所有元素的和（不包括坐标轴和原点）。
思路
二维前缀和。
我们直接预处理好整个矩阵的二维前缀和，然后对于每一个询问，代入公式，计算左上角那一块的和，以及右下角那一块的和即可。
时间复杂度：\(O(n ^ 2 + q)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, t;
cin >> n >> t;
vector<vector<int>> pre(n + 1, vector<int>(n + 1));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin >> pre[i][j];
pre[i][j] += pre[i - 1][j];
pre[i][j] += pre[i][j - 1];
pre[i][j] -= pre[i - 1][j - 1];
}
}
while(t --){
int x, y;
cin >> x >> y;
cout << pre[x - 1][y - 1] + (pre[n][n] - pre[n][y] - pre[x][n] + pre[x][y]) << '\n';
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}很裸很裸的二维前缀和
K. 小菜的卡牌
背景
赛时临时加的签到题之一。
题意
给定三个数，输出最大的两个数之和。
思路
签到。
如题，你可以排个序。
时间复杂度：\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
vector<int> a(3);
for(int i=0;i<3;i++) cin >> a[i];
sort(all(a));
cout << a[1] + a[2] << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}堪比 Hello World
L. 小菜的神奇口袋
背景
赛时临时加的签到题之一。
题意
给定一个袋子，初始状态下包含 \(A\) 个青色小球，\(0\) 个红色小球。
定义一次操作为将青色小球 \(+B\)，红色小球 \(+C\)。
输出最小的操作数，使青色小球的个数不超过红色小邱的个数的 \(D\) 倍。或者输出无解 \(-1\)。
思路
签到。
设操作数为 \(x\)，可得 \(A + Bx \leq CDx\)。
移项可得 \((CD - B)x \geq A\)。
从而，\(CD - B < 0\) 时，有 $x $ 负数，无解。
\(CD - B = 0\) 时，有 \(A \leq 0\)，无解。
否则，答案为 \(\lceil \frac{a}{CD - B} \rceil\)。
时间复杂度：\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int a, b, c, d;
cin >> a >> b >> c >> d;
if(c * d - b > 0){
int ans = (a + c * d - b - 1) / (c * d - b);
cout << ans << '\n';
}else cout << -1 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}列个式子分讨一下即可