A. 友好数字
每个测试时间限制1秒
每个测试内存限制256兆字节
对于一个整数 \(x\)，如果另一个整数 \(y\) 满足以下条件，我们称 \(y\) 是友好的：
\(y - d(y) = x\)，其中 \(d(y)\) 是 \(y\) 的各位数字之和。
对于给定的整数 \(x\)，确定它有多少个友好数字。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 \(t\)（\(1 \leq t \leq 500\)）。接下来是测试用例的描述。
每个测试用例由一行组成，包含一个整数 \(x\)（\(1 \leq x \leq 10^9\)）。
输出
对于每个测试用例，输出一个整数——问题的答案。
思路
本题上来在草稿纸上列举，很容易想到一个错误的答案：所有\(\% 9==0\)的数
因为枚举\(0\sim 70\)作为\(y\)来打表，发现所有满足的\(x\)都为9的倍数，所以便交了一发。但是实际上这仅仅是必要条件，也就是说，所有\(x\)必然是9的倍数，但是9的倍数不一定是合法的\(x\)
正确的思路应当是尝试枚举接近\(x\)的100个数，因为\(y>x+100\)时\(y-d(y)>x\)
为了更节省时间，只需要枚举接近\(x\)的10个个位为0的数字即可，因为你会发现在\(y\)的个位由0变化到9的过程中\(y-d(y)\)的值是不变的
代码
- #includeusing namespace std;#define ll long long#define int ll #define rep(i,a,b) for(int i=(a);i=(b);i--) int d(int x) { int res = 0; while (x) { res += x % 10; x /= 10; } return res;} void solve() { int x;cin >> x; rep(k, x / 10, x / 10 + 10) { if (10 * k - d(k) == x) { cout n; vectora(n + 1); vectorp(n + 1); vectorcnt(n + 1); rep(i, 1, n)cin >> p[i]; rep(i, 1, n) { cin >> a[i]; if (i >= 2 && a[i] != a[i - 1]) { cnt[a[i]].push_back(a[i - 1]); } } vectorvis(n + 1); rep(i, 1, n) { vis[p[i]] = 1; for (auto son : cnt[p[i]]) { if (!vis[son]) { cout t; while (t--)solve();}
每道测试时间限制：2 秒
每道测试内存限制：256 兆字节
爱丽丝和鲍勃有两个整数 \(p\) 和 \(q\)，他们正在用这两个数字玩游戏。玩家轮流行动，爱丽丝先手。在轮到某位玩家时，他可以执行以下两种操作之一：
- 将 \(p\) 减少一（此操作仅在 \(p>0\) 时可行）；
- 将 \(q\) 减少一（此操作仅在 \(q>1\) 时可行）。
游戏在 \(p=0\) 且 \(q=1\) 时结束。
如果在游戏过程中的任意时刻，分数 \(\frac{p}{q}\) 的值等于分数 \(\frac{2}{3}\)，则鲍勃获胜。否则，爱丽丝获胜。
给定 \(p\) 和 \(q\) 的初始值，假设双方都采取最优策略，请确定游戏的获胜者。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 \(t\)（\(1 \le t \le 10^4\)）。接下来是每个测试用例的描述。
每个输入用例由一行组成，包含两个整数 \(p\) 和 \(q\)（\(1 \le p, q \le 10^{18}\)）。
输出
对于每个输入用例，输出：
- 如果爱丽丝获胜，输出 "Alice"；
- 如果鲍勃获胜，输出 "Bob"。
思路
首先感性理解一下游戏过程，Bob能赢的情况只有双方不得不p-1,q-1,p-1,q-1,...的时候才会出现，其他情况都由Alice控制输赢
\[\begin{align}&令 \frac{x-z}{y-z}=\frac{2}{3}\\ \\\implies &3x-2y=z\end{align}\]
显然当\(z=x\)或者\(z=y\)的时候，\(\frac{x-z}{y-z}\)要么为0要么非法，\(z>\min\{ x,y \}\)的时候分子或者分母将率先出现负数，因此\(z\geq \min\{ x,y \}\)的时候Alice赢
其次，如果算出来\(z> x >> y; int z = 3 * x - 2 * y; if (z >= min(x, y) || z < 0)cout t; while (t--)solve();}[/code]D. 关于美丽数对的另一道题
每个测试的时间限制为 2 秒
每个测试的内存限制为 256 兆字节
在数组 \(a\) 中，如果下标对 \(i\)、\(j\) 满足以下条件，我们称之为美丽的：
\(a_i \cdot a_j = j - i\)
计算数组 \(a\) 中美丽数对的数量。
输入格式
每个测试包含多个测试用例。第一行包含测试用例的数量 \(t\)（\(1 \le t \le 10^4\)）。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数 \(n\)（\(2 \le n \le 2 \cdot 10^5\)）。
每个测试用例的第二行包含 \(n\) 个整数 \(a_i\)（\(1 \le a_i \le 10^9\)）。
输入的附加约束：
所有测试用例的 \(n\) 之和不超过 \(2 \cdot 10^5\)。
输出格式
对于每个测试用例，输出一个整数——问题的答案。
思路
\[a_{i}\cdot a_{j}=j-i\leq n\]
根据这一放缩，我们发现有许多的组合是不合法的，仅有相乘后小于等于n的组合才被我们考虑在内
又因为\(n\leq 2e 5\)，因此很容易想到猜测本题复杂度与\(O(\sqrt{ n })\)相关，那么便是根号分治了
我们设\(1\leq i\leq j\leq n\)，\(u=a_{i}\ ,\ v=a_{j}\)
合法条件变为：\(u\cdot v=j-i\)
先考虑\(a_{i}\leq \sqrt{ n }\)的情况：
- 由于\(O(n\sqrt{ n })\)的复杂度是可以接受的，我们可以暂时将所有\(O(\sqrt{ n })\)复杂度的操作想成\(O(1)\)，再去思考一个\(O(n)\)的解法
- 在固定一个\(j\)的情况下，可以\(O(\sqrt{ n })\)的时间内找出所有合法的\(i\)
- 枚举\(1\leq j\leq n\)，那么对于一个\(j\)，可以在\(O(\sqrt{ n })\)的时间内枚举所有的\(u\leq \sqrt{ n }\)，\(u\cdot a_{j}=j-i\implies i=j-u\cdot a_{j}\)，再判断是否有\(a_{i}==u\)即可
- 当然，要注意下标\(i\)的合法性
再考虑\(a_{i}>\sqrt{ n }\)的情况：
- 由于\(a_{i}>\sqrt{ n }\)，那么必然要有\(a_{j}\sqrt{ n }\)的前提下，\(O(\sqrt{ n })\)枚举所有的\(v\leq \sqrt{ n }\)，\(a_{i}\cdot v=j-i\implies j=i+a_{i}\cdot v\)，再判断是否有\(a_{j}==v\)即可
- 当然，也要注意下标\(j\)的合法性
代码
- #pragma GCC optimize(3, "Ofast", "inline")#includeusing namespace std;#define ll long long#define int ll #define rep(i,a,b) for(int i=(a);i=(b);i--) void solve() { int n;cin >> n; vectora(n + 1); rep(i, 1, n) cin >> a[i]; int B = sqrt(n), ans = 0; rep(j, 1, n) { int v = a[j]; rep(u, 1, B) { if (j - u * v < 1)break; if (a[j - u * v] == u)ans++; } } rep(i, 1, n) { if (a[i] n)break; if (a[i + u * v] == v)ans++; } } cout t; while (t--)solve();}
单点时间限制2秒
内存限制256MB
这是本题的困难版本。不同版本之间的区别是，在此版本中，你最多可以询问 \(n+m\) 个问题，并且 \(n \leq 30\)。只有在你解决了此问题的所有版本后，才能进行hack。
这是一个交互式问题。
裁判想好了一个无环、无自环、无重边的有向无环图，该图有 \(n\) 个顶点和 \(m\) 条边。
你的任务是确定图中包含哪些边。为此，你可以提出以下形式的问题：在图的所有路径按字典序\(^*\)排序的列表中，第 \(k\) 条路径是什么。
图中的路径是一个顶点序列 \(u_1, u_2, \dots, u_l\)，使得对于任意 \(i < l\)，图中存在边 \((u_i, u_{i+1})\)。
你的任务是通过不超过 \(n+m\) 次询问来完成此目标。
\(^*\)序列 \(a\) 字典序小于序列 \(b\) 当且仅当以下条件之一成立：
- \(a\) 是 \(b\) 的前缀，但 \(a \ne b\)；或者
- 在 \(a\) 和 \(b\) 第一个不同的位置上，序列 \(a\) 的元素小于 \(b\) 中对应的元素。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 \(t\) \((1 \le t \le 10)\)。测试用例描述如下。
每个测试用例由一行一个整数 \(n\) \((1 \le n \le 30)\) 组成 —— 表示图中的顶点数。
裁判保证给定的图不包含环或多重边。
注意 \(m\) 对你来说是未知的！
交互
每个测试用例的交互从读取整数 \(n\) 开始。
之后你可以提出最多 \(n+m\) 个问题。
要提出问题，请以 "? k" 格式（不带引号）\((1 \le k \le 2^{30})\) 输出一个字符串。每次询问后，读取一个整数 \(q\) —— 第 \(k\) 条路径的顶点数。如果 \(q = 0\)，则这样的路径不存在；否则，读取 \(q\) 个整数 —— 组成此路径的顶点编号。
要报告你的答案，首先输出一个格式为 "! m" 的字符串，然后输出 \(m\) 行描述边，格式为 "u v"，表示存在一条从 \(u\) 指向 \(v\) 的边。你可以以任意顺序输出边。输出答案不计入询问次数。
可以证明，在给定的约束条件下，图中不同路径的数量不超过 \(2^{30}\)。
每次打印查询后，不要忘记输出换行符并刷新\(^*\)输出。否则，你将得到超出闲置限制的判定结果。
如果在任何交互步骤中，你读取到 \(-1\) 而不是有效数据，你的程序必须立即退出。这意味着你的解决方案将因无效查询或任何其他错误而收到错误答案。未能退出可能会导致任意判决，因为你的解决方案将继续从已关闭的流中读取。
思路
本题的询问次数卡得非常死，\(n\)次单点询问，\(m\)次边询问，所以我们对于每一次询问，都必须得到一个有效的答案。
我们以下面的路径作为例子：
\[\begin{align}&1 \\&2 \\&2\to 1 \\&2\to 3 \\&3 \\&4 \\&5 \\&5\to 2 \\&5\to 2\to 1 \\&5\to 2\to 3 \\&5\to 3\end{align}\]
记\(siz\)为以\(u\)作为起点的路径数，那么不难发现，从第一条路径开始向下遍历，在第二次遇见结尾为\(u\)的时候，接下来的\(siz-1\)条路的后缀必定和之前遇见\(u\)的一样
比如例子中的2号点，在出现\(5\to 2\)的时候，我们知道接下来必定有两条路径是可以跳过的，因为\(siz[2]=3\)，即\(\{ 2,2\to 1,2\to 3 \}\)
所以我们可以开一个标记数组，\(vis=1\)表示\(u\)点已经访问过一次了
每次读入路径的时候，都将结尾元素连到前一个上面，这一定是一条新边
如果发现结尾元素已经\(vis\)过了，那么就跳过接下来的\(siz[back]\)条路径继续向下遍历，这样就可以保证每次询问都必定得到一个有效信息
总共询问次数为\(n+m+1\)，因为在询问完所有的路径之后，我们无法判断什么时候询问应该停止，多问一次\(n+1\)这个点，如果返回了0那么就退出
比如，如果在上述例子的结尾多加一个\(5\to 4\)，那么也是一个合法的样例，但是如果不询问是否停止，程序将无法区分这两个样例的区别
当然，这样的策略只可以通过\(E_{1}\)，但是通过\(E_{2}\)其实只需要再稍加一点点修改即可：
注意到，无论如何，第一个访问的路径必然是\(\{ 1 \}\)，因此，我们在开始询问之前令\(vis[1]=1\)，跳过第一条询问，这样就可以节省出一个询问用于查询是否结束
代码
[code]#pragma GCC optimize(3, "Ofast", "inline")#includeusing namespace std;#define ll long long#define int ll #define rep(i,a,b) for(int i=(a);i=(b);i--)void ask(int k) { cout cnt; if (cnt == 0)break; vectornow(cnt + 1); rep(i, 1, cnt)cin >> now; if (cnt >= 2) { e[now[now.size() - 2]].push_back(now.back()); } if (vis[now.back()]) { rep(i, 1, cnt - 1) { siz[now] += siz[now.back()]; } id += siz[now.back()]; continue; } vis[now.back()] = 1; rep(i, 1, cnt) { siz[now]++; } id += siz[now.back()]; } int m = 0; rep(i, 1, n) { m += e.size(); } cout > n; string s;cin >> s; dequedq1, dq2; vectorvis(n + 1); rep(i, 1, n) { if (s[i - 1] == '(') { dq1.push_back({ s[i - 1],i }); } if (s[i - 1] == ')') { if (dq1.size() && dq1.back().first == '(') { vis = vis[dq1.back().second] = 1; dq1.pop_back(); } } if (s[i - 1] == '[') { dq2.push_back({ s[i - 1],i }); } if (s[i - 1] == ']') { if (dq2.size() && dq2.back().first == '[') { vis = vis[dq2.back().second] = 1; dq2.pop_back(); } } } vectorpd; mapmp = { {'(',0},{')',1},{'[',0},{']',1} }; int cnt[2] = { 0,0 }; rep(i, 1, n) { if (!vis) { pd.push_back(mp[s[i - 1]]); cnt[mp[s[i - 1]]]++; } } // cout |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
