ABC347(A-E)
A - Divisible¶
题目大意
给你 \(N\) 个整数 \(A = (A_1, A_2, \cdots, A_N)\) 和一个整数 \(K\) ，如果 \(A_i\) 是 \(K\) 的倍数，输出 \(\frac{A_i}{K}\)。
参考代码
#include <iostream>
using namespace std;
int main()
{
int n, k, x;
cin >> n >> k;
while(n--)
{
cin >> x;
if(x % k == 0)
cout << x / k << ' ';
}
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
while (n-- > 0) {
int x = in.nextInt();
if (x % k == 0)
System.out.printf("%d ", x / k);
}
in.close();
}
}
B - Substring¶
题目大意
给你一个字符串 \(S\)，求出 \(S\) 有多少个不同的子串。
参考代码
#include <iostream>
#include <unordered_set>
using namespace std;
int main()
{
string s;
cin >> s;
int n = s.size();
unordered_set<string> vis;
for(int i = 0; i < n; i++)
{
string now;
for(int j = i; j < n; j++)
{
now += s[j];
vis.insert(now);
}
}
cout << vis.size() << endl;
return 0;
}
import java.util.HashSet;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
char[] s = in.next().toCharArray();
int n = s.length;
HashSet<String> vis = new HashSet<>();
for (int i = 0; i < n; i++) {
String now = "";
for (int j = i; j < n; j++) {
now += s[j];
vis.add(now);
}
}
System.out.println(vis.size());
in.close();
}
}
C - Ideal Holidays¶
题目大意
假设一个星期有 \(A+B\) 天，其中前 \(A(A \le 10^9)\) 天是假期，接下来的 \(B(B \le 10^9)\) 天是工作日。有 \(N(N \le 2 \times 10^5)\) 个计划，其中第 \(i\) 个计划是在 \(D_i\) 天后。你忘记了今天是一星期中哪一天。问：是否存在一种可能，使得这 \(N\) 个计划都能在假日完成？
解题思路
每一天我们实际只关心是一个星期的第几天，所以我们计算所有的 \(D_i \bmod (A+B)\) ，然后将得到的结果取最小值和最大值，令 \(l = \min\limits_{i = 1} ^ N\{D_i \bmod (A+B)\}\)，\(r = \max\limits_{i = 1} ^ N\{D_i \bmod (A+B)\}\)，则如果 \(r-l+1 \le A\) 即可。因为我们可以将 \(l\) 对应的那一天视为第一天假期，则 \(r\) 对应的部分一定不会超过 \(A\)。
这是我一开始的做法，后来发现 WA 了一个点，考虑下面这个样例：
4 4 5
1 2 8 9
这个样例应该输出 Yes，原因是可以将 1 对应第三天假期，这样，在新的星期中，8 和 9 对应的就是假期的第一天和第二天。
所以我们可以发现，第一天假期不一定是 \(l\) 对应的那一天，在上面这个例子中，将 \(8\) 视为假期的第一天，此时序列相当于 8 9 10 11，此时判断的就是 11 和 8 的长度。
因此处理出所有的 \(D_i \bmod (A+B)\) ，然后排序，接着枚举哪一天应该成为假期的第一天，假设枚举到 \(i\)，这上一天就是 \(i-1\), 判断两者的长度，只要有一个满足即可。
参考代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int n, a, b, c;
cin >> n >> a >> b;
c = a + b;
vector<int> d(n);
for(int i = 0; i < n; i++)
{
scanf("%d", &d[i]);
d[i] %= c;
}
sort(d.begin(), d.end());
d.erase(unique(d.begin(), d.end()), d.end());
n = d.size();
if(d[n-1] - d[0] < a)
{
puts("Yes");
return 0;
}
for(int i = 0; i < n - 1; i++)
{
if(d[i] + c - d[i+1] < a)
{
puts("Yes");
return 0;
}
}
puts("No");
return 0;
}
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int a = in.nextInt();
int b = in.nextInt();
int c = a + b;
int[] d = new int[n];
for (int i = 0; i < n; i++) {
d[i] = in.nextInt();
d[i] %= c;
}
Arrays.sort(d);
if (d[n - 1] - d[0] < a) {
System.out.println("Yes");
return;
}
for (int i = 0; i < n - 1; i++) {
if (d[i] + c - d[i + 1] < a) {
System.out.println("Yes");
return;
}
}
System.out.println("No");
in.close();
}
}
D - Popcount and XOR¶
题目大意
给你三个数字 \(a(a \le 60)\)，\(b(b \le 60)\) 和 \(C(C \le 2^{60})\)，问：是否存在数对 \((X, Y)\) 满足下列所有条件。
- \(0 \le X < 2^{60}\)
- \(0 \le Y < 2^{60}\)
- \(X\) 的二进制中有 \(a\) 个 \(1\)
- \(Y\) 的二进制中有 \(b\) 个 \(1\)
- \(X \oplus Y = C\)
解题思路
先将 \(C\) 对应的二进制数组处理出来，然后定义 \(dp[i][x][y]\) 表示是否存在满足 \(C\) 的前 \(i\) 位的前提下，\(X\) 用了 \(x\) 个 \(1\)，\(Y\) 用了 \(y\) 个 \(1\) 的方案。则初始时 \(dp[0][0][0] = 1\)，转移的时候根据 \(C\) 的数位分类，如果 \(C_i=1\) 则 \(X_iY_i = 10\) 或者 \(X_iY_i = 01\)，如果 \(C_i = 0\) 则 \(X_iY_i = 00\) 或者 \(X_iY_i = 11\)。
需要注意的是不一定要恰好用完所有的 \(1\)，因为 \(C\) 是有可能存在前导 \(0\) 的，而前导 \(0\) 可以由两个 \(1\) 异或得到。
参考代码
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int maxn = 64;
LL a, b, C;
int n, num[maxn];
bool dp[maxn][maxn][maxn];
int main()
{
cin >> a >> b >> C;
while(C)
{
num[++n] = C & 1;
C >>= 1;
}
dp[0][0][0] = 1;
for(int i = 1; i <= n; i++)
if(num[i])
{
for(int x = 0; x <= a; x++)
for(int y = 0; y <= b; y++)
dp[i][x][y] = (x && dp[i-1][x-1][y]) || (y && dp[i-1][x][y-1]);
}
else
{
for(int x = 0; x <= a; x++)
for(int y = 0; y <= b; y++)
dp[i][x][y] = dp[i-1][x][y] || (x && y && dp[i-1][x-1][y-1]);
}
int x, y, cnt = -1;
for(int i = 0; i <= a; i++)
for(int j = 0; j <= b; j++)
if(dp[n][i][j] && a-i == b-j && a-i+n <= 60)
{
cnt = a-i;
x = i;
y = j;
break;
}
if(cnt == -1)
{
puts("-1");
return 0;
}
LL X = 0, Y = 0;
for(int i = n; i; i--)
if(num[i])
{
if(x && dp[i-1][x-1][y])
{
X |= 1ll << (i-1);
x--;
}
else
{
Y |= 1ll << (i-1);
y--;
}
}
else
{
if(x && y && dp[i-1][x-1][y-1])
{
X |= 1ll << (i-1);
Y |= 1ll << (i-1);
x--;
y--;
}
}
for(int i = 0; i < cnt; i++)
{
X |= 1ll << (n + i);
Y |= 1ll << (n + i);
}
cout << X << ' ' << Y;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
long C = in.nextLong();
boolean[] num = new boolean[64];
int n = 0;
while (C > 0) {
num[++n] = (C & 1) > 0 ? true : false;
C >>= 1;
}
boolean[][][] dp = new boolean[n + 1][(int) a + 1][(int) b + 1];
dp[0][0][0] = true;
for (int i = 1; i <= n; i++)
if (num[i]) {
for (int x = 0; x <= a; x++)
for (int y = 0; y <= b; y++)
dp[i][x][y] = (x > 0 && dp[i - 1][x - 1][y]) || (y > 0 && dp[i - 1][x][y - 1]);
} else {
for (int x = 0; x <= a; x++)
for (int y = 0; y <= b; y++)
dp[i][x][y] = dp[i - 1][x][y] || (x > 0 && y > 0 && dp[i - 1][x - 1][y - 1]);
}
int x = 0, y = 0, cnt = -1;
for (int i = 0; i <= a; i++)
for (int j = 0; j <= b; j++)
if (dp[n][i][j] && a - i == b - j && a - i + n <= 60) {
cnt = a - i;
x = i;
y = j;
break;
}
if (cnt == -1) {
System.out.println(-1);
return;
}
long X = 0, Y = 0;
for (int i = n; i > 0; i--)
if (num[i]) {
if (x > 0 && dp[i - 1][x - 1][y]) {
X |= 1l << (i - 1);
x--;
} else {
Y |= 1l << (i - 1);
y--;
}
} else {
if (x > 0 && y > 0 && dp[i - 1][x - 1][y - 1]) {
X |= 1l << (i - 1);
Y |= 1l << (i - 1);
x--;
y--;
}
}
for (int i = 0; i < cnt; i++) {
X |= 1l << (n + i);
Y |= 1l << (n + i);
}
System.out.printf("%d %d", X, Y);
in.close();
}
}
E - Set Add Query¶
题目大意
你需要维护一个长度为 \(N(N \le 2 \times 10^5)\) 的序列 \(A = (A_1, A_2, \cdots, A_N)\) 和一个集合 \(S\) 。 初始的时候，\(A\) 中的所有数字都是 \(0\)，集合 \(S\) 也为空。有 \(Q(Q \le 2 \times 10^5)\) 个操作，每个操作给你一个数字 \(x_i(1 \le x_i \le N)\)，然后执行：
-
- 如果 \(x_i\) 在 \(S\) 中，则将其从 \(S\) 中删去。
- 如果 \(x_i\) 不在 \(S\) 中，则将其加入到 \(S\) 中。
- 遍历 \(S\) 中所有的数字 \(x\)，然后给 \(A_x\) 加上集合 \(S\) 的大小 \(|S|\)。
问：在 \(Q\) 次操作后，序列 \(A\) 的内容是？
解题思路
考虑追踪每个数字在集合中存活的时间，当数字 \(x\) 加入集合，一直到这个数字被删去，中间 \(|S|\) 都会对 \(A_x\) 产生影响，而这个区间是连续的。显然要维护一个 \(|S|\) 变化的前缀和，然后记录一下数字上一次加入的时间，用 last[x] 表示 x 上一次加入集合的时间，如果 last[x] == 0 表示 x 不在集合中。当元素被删去时，查找出对应的前缀和，一次性加上去就好。这样每次操作的时间复杂度就是 \(O(1)\) 的。
\(Q\) 次操作后，还需要对集合中剩下的所有元素再加一遍。
参考代码
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int maxn = 2E5 + 10;
int last[maxn];
LL s[maxn], a[maxn];
LL getsum(int l, int r)
{return s[r] - s[l-1];}
int main()
{
int n, q, x, now = 0;
cin >> n >> q;
for(int i = 1; i <= q; i++)
{
scanf("%d", &x);
if(last[x])
{
a[x] += getsum(last[x], i-1);
last[x] = 0;
now--;
}
else
{
last[x] = i;
now++;
}
s[i] = s[i-1] + now;
}
for(int i = 1; i <= n; i++)
if(last[i])
a[i] += getsum(last[i], q);
for(int i = 1; i <= n; i++)
printf("%lld ", a[i]);
return 0;
}
import java.util.Scanner;
public class Main {
private static long[] s;
private static long getsum(int l, int r) {
return s[r] - s[l - 1];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int q = in.nextInt();
int[] last = new int[n + 1];
long[] a = new long[n + 1];
s = new long[q + 1];
int now = 0;
for (int i = 1; i <= q; i++) {
int x = in.nextInt();
if (last[x] > 0) {
a[x] += getsum(last[x], i - 1);
last[x] = 0;
now--;
} else {
last[x] = i;
now++;
}
s[i] = s[i - 1] + now;
}
for (int i = 1; i <= n; i++)
if (last[i] > 0)
a[i] += getsum(last[i], q);
for (int i = 1; i <= n; i++)
System.out.printf("%d ", a[i]);
in.close();
}
}
创建日期: 2024-04-02