B 题非常有意思,C 题的难度感觉不应该放在C题,D 题构造头皮都抠破了
A - Palindromic Indices
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
string s;
cin >> n >> s;
int r = (n + 1) / 2, ans = 1;
while (s[r] == s[n / 2] && r < n) {
ans += 2;
r++;
}
cout << ans - (n % 2 == 0) << '\n';
}
return 0;
}
B - AND Sorting
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int ans = (int)(1ll << 32) - 1;
for (int i = 0; i < n; i++) {
if (a[i] != i) {
ans &= (a[i] & i);
}
}
cout << ans << '\n';
}
return 0;
}
C - LIS or Reverse LIS?
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
map<int, int> mp1, mp2;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (!mp1.count(x) && !mp2.count(x)) {
mp1[x]++;
} else {
mp2[x]++;
mp1.erase(x);
}
}
cout << (int) (mp1.size() + 1) / 2 + (int) mp2.size() << '\n';
}
return 0;
}
D - Circular Spanning Tree
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
string s;
cin >> n >> s;
int root = -1;
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
root = (i + 1) % n;
break;
}
}
if (root == -1) {
cout << "NO\n";
continue;
}
vector<bool> adj(n, true);
for (int i = root + 1; i < n; i++) {
if (s[i] == '0') {
adj[(i + 1) % n] = false;
}
}
for (int i = 0; i < root - 1; i++) {
if (s[i] == '0') {
adj[i + 1] = false;
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (i == root) {
continue;
}
ans += (int) adj[i];
}
if (s[root] - '0' != (ans & 1)) {
cout << "NO\n";
continue;
}
cout << "YES\n";
for (int i = 0; i < n; i++) {
if (i == root) {
continue;
}
if (adj[i]) {
cout << i + 1 << ' ' << root + 1 << '\n';
} else {
cout << (i - 1 + n) % n + 1 << ' ' << i + 1 << '\n';
}
}
}
return 0;
}
请问B中ans=(1ll << 32) - 1是什么意思?这个不是很理解
就是0x7fffff,二进制里除了高位全是1,或者用unsigned int也可以
谢谢,明白了