在不考虑单词词性的前提下，只要求两个单词的首字母忽略大小写相同时就认为它们可能是一组ubuntu代号，请你编写程序判断给定的两个单词是否可能是一个ubuntu代号。
$T(1\leq T \leq 10^5)$
$S,T(1\leq |S|,|T|\leq 50)$
按题意判断即可
1
2
3
4
5
6
7
| void solve() {
string s, t;cin >> s >> t;
if (s[0] == t[0] || abs(s[0] - t[0]) == abs('a' - 'A')) {
cout << "Yes\n";
}
else cout << "No\n";
}
|
一个首尾相连的数组，若相邻的两个数之和为偶数选择拿走一个然后可以随意交换一对数，轮流操作，不能再操作的一方输。清楚姐姐先手。
$T(1\leq T \leq 10^4)$
$N(1\leq N\leq 26)$
$a_i(0\leq a_i \leq 10^9)$
只有1个数时直接取走，先手赢。
2个数时：奇偶/奇奇/偶偶，都是后手赢。
3个数时：奇偶奇/偶奇偶/奇奇奇/偶偶偶，都是先手赢。
…
结束时候的状态是奇偶奇偶...奇偶，如果数量是奇数个，一定存在奇奇/偶偶，操作后可能直接结束游戏或继续，如果数量是偶数个且可操作，则转移为奇数时的状态且此时下一位操作者一定可以再操作。双方的操作不会改变他面对该数字串时数字的个数的奇偶性。也就是说，只有一直面对奇数个数的一方才能赢。
故判断原始长度，看先手是否在奇数位。
1
2
3
4
5
6
7
8
9
| void solve() {
int n;cin >> n;
vector<ll>a(n);
for (int i = 0;i < n;i++) {
cin >> a[i];
}
if (n & 1)cout << "qcjj\n";
else cout << "zn\n";
}
|
D-chino’s bubble sort and maximum subarray sum(easy version)
对一个数组内的元素进行恰好$K$次相邻元素交换后，求整个数组的最大子段和。
$N,K(2\leq N\leq 10^3,0\leq K \leq 1)$
$a_i(-10^9\leq a_i \leq 10^9)$
easy版本的K只有两种取值（0和1），N的范围不大，分类处理，进行dp即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| ll maxsum(vector<ll>a) {
int n = a.size();
ll sum = a[0];
ll b = 0;
for (int i = 0;i < n;i++) {
if (b > 0)b += a[i];
else b = a[i];
if (b > sum)sum = b;
}
return sum;
}
void solve() {
int n, k;cin >> n >> k;
vector<ll>a(n);
for (int i = 0;i < n;i++)cin >> a[i];
ll ans;
if (k == 0) {
ans = maxsum(a);
}
else {
for (int i = 0;i < n - 1;i++) {
a[i] = a[i] ^ a[i + 1];
a[i + 1] = a[i] ^ a[i + 1];
a[i] = a[i] ^ a[i + 1];
if (i != 0) ans = max(ans, maxsum(a));
else ans = maxsum(a);
a[i] = a[i] ^ a[i + 1];
a[i + 1] = a[i] ^ a[i + 1];
a[i] = a[i] ^ a[i + 1];
}
}
cout << ans << endl;
}
|
给出一些cmp函数的规定，判断他们之间是否存在逻辑矛盾。
cmp的排序规则是这样的：
$cmp(x,y)=1$表示规定$x>y$，即$x$的顺序严格先于$y$
$T(1\leq T\leq 2\times 10^4)$
$N(1\leq N\leq 2)$
$x,y,z(x,y\in {1,2,3},z\in{0,1})$，表示第$i$个约束关系为$cmp(a_x,a_y)=z$。
只有3个数、两个约束关系时，不能构成$a_x<a_y$且$a_y<a_z$且$a_x>a_z$，只需判断最多存在2中约束关系时的逻辑是否合法。
对于两个数$x$、$y$，不合法的约束关系只有：$cmp(x,y)=1$且$cmp(y,x)=1$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void solve() {
int n;cin >> n;
vector<vector<int>>rules(4, vector<int>(4, -1));
bool f = true;
for (int i = 0;i < n;i++) {
int x, y, z;cin >> x >> y >> z;
if (!f)continue;
if (x == y && z == 1)f = false;
if (z == 1 && rules[y][x] == 1) {
f = false;
}
if (rules[x][y] == -1) {
rules[x][y] = z;
if (z == 1)
rules[y][x] = 0;
}
else if (rules[x][y] != z)
f = false;
}
if (f)cout << "Yes\n";
else cout << "No\n";
}
|
同G
$T(1\leq T\leq 2\times 10^4)$
$N(1\leq N\leq 50)$
$x,y,z(x,y\in {1,2,3},z\in{0,1})$，表示第$i$个约束关系为$cmp(a_x,a_y)=z$。
和G相比，N的范围大于2，不合法的情况增加了，但是依然只是3个数据之间判断合法性。
新增的三个关系不合法的情况有：
- $x<y,x<z,z<x$
- $x\leq y,y\leq z,z<x$
分别特判即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| void solve() {
int n;cin >> n;
vector<vector<int>>rules(4, vector<int>(4, -1));
bool f = true;
for (int i = 0;i < n;i++) {
int x, y, z;cin >> x >> y >> z;
if (!f)continue;
if (x == y && z == 1)f = false;
if (z == 1 && rules[y][x] == 1) {
f = false;
}
if (rules[x][y] == -1) {
rules[x][y] = z;
if (z == 1)
rules[y][x] = 0;
}
else if (rules[x][y] != z)
f = false;
}
if (rules[1][2] == 1 && rules[2][3] == 1 && rules[3][1] == 1)
f = false;
if (rules[1][3] == 1 && rules[3][2] == 1 && rules[2][1] == 1)
f = false;
for (int x = 1;x <= 3;x++) {
for (int y = 1;y <= 3;y++) {
if (y == x)continue;
int z = 6 - x - y;
if (rules[x][y] == 0 && rules[y][z] == 0 && rules[x][z] == 1)
f = false;
}
}
if (f)cout << "Yes\n";
else cout << "No\n";
}
|
定义一种运算$f$，可以将正整数按照字面值从左到右拼接，如：$f(123,569)=1234569$。
一个正整数数组，其中有多少对有序对$i,j(i≠j)$满足$f(a_i,a_j)$是36的倍数。
easy:
$N(1\leq N\leq 1000)$
$a_i(1\leq a_i \leq 10)$
hard：
$N(1\leq N\leq 10^5)$
$a_i(1\leq a_i \leq 10^{18})$
easy版本的数据较小，直接双层循环暴力即可。
hard版本可以考虑同余，k是y的位数。
$$
f(x,y)=x\times 10^{k}+y
$$
$$
f(x,y)% 36=0
$$
$$
(x\times 10^{k}+y)%36=0
$$
$$
(x%36\times 10^{k}%36+y%36)%36=0
$$
对数组预处理后，枚举以$y$结尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| // 暴力easy version
void solve() {
int n;cin >> n;
vector<int>a(n);
for (int i = 0;i < n;i++) {
cin >> a[i];
}
int cnt = 0;
for (int i = 0;i < n;i++) {
for (int j = i + 1;j < n;j++) {
int n1 = a[i] * 10 + a[j];
int n2 = a[j] * 10 + a[i];
if (n1 % 36 == 0)cnt++;
if (n2 % 36 == 0)cnt++;
}
}
cout << cnt << '\n';
}
// hard version
void solve() {
int n;cin >> n;
vector<ll>a(n);
map<int, int>cnt;
for (int i = 0;i < n;i++) {
cin >> a[i];
cnt[a[i] % 36]++;
}
ll k = 1;
vector<int>dk(19);
for (int i = 1;i < 19;i++) {
k *= 10;
dk[i] = k % 36;
}
auto getlen = [](ll x) {
int i = 0;
while (x) {
i++;x /= 10;
}
return i;
};
ll ans = 0;
for (int i = 0;i < n;i++) {
int x = a[i] % 36;
int z = getlen(a[i]);
for (int j = 0;j < 36;j++) {
if ((j * dk[z] + x) % 36 == 0) {
ans += cnt[j];
if (j == x)ans -= 1;
}
}
}
cout << ans << '\n';
}
|
