CF2067 Div.1+2
A Adjacent Digit Sums
题目大意
给你两个数字 $x, y$. 你需要判断是否存在一个整数 $n$, 使得 $S(n) = x, S(n + 1) = y$. 这里, $S(a)$ 表示十进制数 $a$ 的数位之和.
题解
显然有解当且仅当 $y = x + 1$ 或 $(x - y + 1) \equiv 0 \pmod{9} \land x > y$.
code
1int T,x,y;
2
3int main()
4{
5 read(T);
6 while(T--)
7 {
8 read(x),read(y);
9 if(y-x==1)puts("YES");
10 else if(x>y && (x-y+1)%9==0)puts("YES");
11 else puts("NO");
12 }
13 flushout();
14 return 0;
15}B Two Large Bags
题目大意
你有两大袋数字. 最初, 第一个袋子里有 $n$ 个数字: $a_1, a_2, \dots, a_n$, 而第二个袋子是空的. 您可以进行以下操作:
- 从第一个数字袋中选择任意一个数字并将其移动到第二个数字袋中.
- 从第一个袋子中选择一个第二个袋子中也有的数字, 并将其增加一 (只对第一个袋子中的数加).
这两种操作的次数不限, 顺序不限. 有可能使第一个和第二个袋子中的内容完全相同吗?
题解
根据题述操作, 当某一类数个数超过 2 个时, 我们选择保留两个数并将其它数都 +1, 显然不会使整个状态更劣, 因为我们的目的是让每种数的个数都是偶数个, 而该操作会让当前数变得合法, 且可能和后面的数配对.
所以我们从小到大枚举依次往后加即可. 最后判断是否还存在数字是奇数个.
code
1const int N = 1e3 + 10;
2int T, n, cnt[N];
3
4int main()
5{
6 read(T);
7 while (T--)
8 {
9 read(n);
10 for (int i = 1; i <= n + 1; i++)
11 cnt[i] = 0;
12 for (int i = 1, v; i <= n; ++i)
13 read(v), cnt[v]++;
14 for (int i = 1; i <= n; i++)
15 if (cnt[i] > 2)
16 cnt[i + 1] += cnt[i] - 2, cnt[i] = 2;
17 bool flag = true;
18 for (int i = 1; i <= n + 1; i++)
19 if (cnt[i] & 1)
20 flag = false;
21 puts(flag ? "YES" : "NO");
22 }
23 flushout();
24 return 0;
25}C Devyatkinо
题目大意
给你一个正整数 $n$. 在一次运算中, 你可以将十进制表示只包含数字 9 的任何正整数加到 $n$ 中, 而且可能重复多次.
要使数字 $n$ 的十进制表示中至少包含一位数字 7, 至少需要多少次运算?
例如, 如果是 $n = 80$, 只需进行一次运算即可: 在运算 $n = 179$ 之后, 将 99 加到 $n$ 中, 其中包含数字 7.
题解
不太能严格证明, 首先答案肯定不会超过 9, 因为你只 +9 也一定能在 9 步内完成. 猜测最少步数只会进行同一种操作, 即每次加的数都是同一个数. 直觉是加小的数不一定会产生进位可能会没用, 加更大的数连该数一起变也没啥用, 但不会证.
code
1const ll v[10]={3,4,5,6,7,8,9,0,1,2};
2ll T,n;
3bool check(ll nn)
4{
5 while(nn)
6 {
7 if(nn%10==7)return 1;
8 nn/=10;
9 }
10 return 0;
11}
12int main()
13{
14 read(T);
15 while(T--)
16 {
17 read(n);
18 ll nn = n,flag = 0,pw=1;
19 while(nn)
20 {
21 if(nn%10==7)flag=1;
22 nn/=10;
23 }
24 if(flag)
25 {
26 wt_str("0\n");
27 continue;
28 }
29 ll ans = v[n%10],cnt = 0;
30 for(int i=1;i<=15;i++)
31 {
32 pw*=10;
33 cnt=0;
34 nn = n;
35 while(cnt<ans)
36 {
37 nn+=pw-1;
38 cnt++;
39 if(check(nn))
40 {
41 ans=min(ans,cnt);
42 break;
43 }
44 }
45 }
46 write(ans);
47 }
48 flushout();
49 return 0;
50}D Object Identification
题目大意
交互题.
这是一个互动问题.
给你一个由 1 到 $n$ 的整数组成的数组 $x_1, \dots, x_n$. 评审团还有一个由 1 至 $n$ 的整数组成的固定但隐藏的数组 $y_1, \dots, y_n$. 数组 $y$ 中的元素是不知道的. 此外, 已知所有 $i$, $x_i \ne y_i$ 和所有成对的 $(x_i, y_i)$ 都是不同的.
陪审团秘密地想到了两个对象中的一个, 你需要确定是哪一个:
- 对象 A: 一个有向图, 有 $n$ 个顶点, 编号从 1 到 $n$, 有 $n$ 条形式为 $x_i \to y_i$ 的边.
- 对象 B: 坐标平面上的 $n$ 个点. $i$ th点的坐标为 $(x_i, y_i)$.
要猜测陪审团想到了哪个对象, 你可以进行查询. 在一个查询中, 你必须指定两个数字 $i, j$ ($1 \leq i, j \leq n, i \ne j$). 作为回应, 您将收到一个数字:
- 如果评委想到了对象 A, 您将收到图中从顶点 $i$ 到顶点 $j$ 的最短路径长度 (以边为单位), 如果没有路径, 则收到 0.
- 如果评委想到了物体 B, 则得到点 $i$ 和 $j$ 之间的曼哈顿距离, 即 $|x_i - x_j| + |y_i - y_j|$.
你有 2 个查询来确定陪审团想到了哪个对象.
题解
切入口就是 A 类返回 0, 因为当 B 类时返回值一定非负, 所以当 $x_i$ 不是全排列时, 直接询问没出现过的数到其余任何位置, 如果返回 0 就是 A, 否则是 B.
而当 $x_i$ 是排列时, 我们直接找 1 和 $n$ 两个 $x_i$ 的位置, 因为 A 类的返回值肯定小于等于 $n - 1$, 而如果是 B 类时, 问问这两个位置返回值最小就是 $n - 1$. 但也存在相等即均为 $n - 1$ 的情况. 这时候就需要问第二次, 而我们只需要简单的交换 $i, j$ 再次问问即可. 只需要检测第二次询问的值是不是等于 $n - 1$ 即可.
code
1const int N = 2e5 + 10;
2int T, n, x[N], mp[N];
3
4int main()
5{
6 cin >> T;
7 while (T--)
8 {
9 cin >> n;
10 memset(mp, 0, sizeof(int) * (n + 1));
11 for (int i = 1; i <= n; i++)
12 cin >> x[i];
13 for (int i = 1; i <= n; i++)
14 mp[x[i]]++;
15 int res1 = -1, res2 = 0, mn = 0, mx = 0,flag=0;
16 for (int i = 1; i <= n; i++)
17 {
18 if (!mp[i])
19 {
20 cout << "? " << i << ' ' << (i < n ? i + 1 : i - 1) << endl;
21 cin >> res1;
22 if(res1) cout<<"! B"<<endl;
23 else cout<<"! A"<<endl;
24 flag=1;
25 break;
26 }
27 if (!mn && mp[i])
28 mn = i;
29 if (mp[i])
30 mx = i;
31 }
32 if(flag)continue;
33 for (int i = 1; i <= n; i++)
34 if (mn == x[i])
35 {
36 mn = i;
37 break;
38 }
39 for (int i = 1; i <= n; i++)
40 if (mx == x[i])
41 {
42 mx = i;
43 break;
44 }
45 cout << "? " << mn << ' ' << mx << endl;
46 cin >> res1;
47 cout << "? " << mx << ' ' << mn << endl;
48 cin >> res2;
49 if (res1==res2&&res1>=n-1)
50 cout << "! B" << endl;
51 else
52 cout << "! A" << endl;
53 }
54 flushout();
55 return 0;
56}