给你一个字符串,判断是否可以在重排列这个字符串后,使得字符串不存在 长度大于等于 2 的回文子串。
很容易发现,一旦字符串长度超过 2,无论怎样都会存在回文子串,000,001,010,011,100,101,110,111。都存在回文子串。然后只需要特判一下 11, 00 即可
int main (){ IOS int t; cin >> t; while (t --){ int n; cin >> n; string s; cin >> s; if (n >= 3){ cout << "NO" << endl; } else{ if (s == "11" || s == "00") cout << "NO" << endl; else cout << "YES" << endl; } } return 0; }
给你一个 0 到 n - 1 的排列,要求你构造出 最大相邻亦或值最小的排列顺序。
由题给样例的输出结果 2, 4,8,大胆猜测答案一定是 2 的幂次。
要使相邻数的亦或值最小,势必要尽可能消去二进制表达中最高位的 1。
我们拿 8 举例:
000 001 010 011 100 101 110 111
要使相邻的异或值最小,最高位是 1 的所有数应该放在一起相互抵消,但是一定有一个数的最高位是是抵消不掉的。要使这个值尽可能小,我们应该使亦或的结果只保留最高位的1。最简单的方法就是让 0 和 状如100000 的数 (此处 1 是最高位其他位均为 0),相邻摆放,小于100000的数放 0 一侧,大于的放另一侧。这样构造的结果可以保证答案不超过100000.
以 16 为例:
即 1 2 3 4 5 6 7 0 8 9 10 11 12 13 14 15,最大相邻亦或值为 8。
int main (){ IOS int t; cin >> t; while (t --){ int n; cin >> n; int m = 1; for (int i = 1 ; i <= n + 3; i *= 2){ if (i * 2 > n - 1){ m = i; break; } } for(int i = 1 ; i < m ; i ++) cout << i << ' '; cout << 0 << ' '; for (int i = m ; i < n ; i ++) cout << i << ' '; cout << endl; } return 0; }
进行尽可能少的操作使得 a = b,操作如下:
非常蒙蔽的题,和标题一样觉得很神奇。结论是,只进行操作 1 或者 操作 2,直到进行一次操作 3就可以使得 a = b。
基于本人水平无法给出证明,但是题目有个很可疑的条件,b 的总和 不超过 1e6。其实看到这个条件就应该往暴力方向想了。赛中写了半年的模拟,一直 WA2。本场比赛依旧是小寄。
int main (){ IOS int t; cin >> t; while (t --){ int a, b, ans1 = 0, ans2 = 0; cin >> a >> b; int ta = a, tb = b; while ((ta | tb) != tb){ ta ++; ans1 ++; } ta = a, tb = b; int tempb = b * 2 + 100; while (((ta | tb) != tb) && tb < tempb){ tb ++; ans2 ++; } cout << min (min (ans1 + 1, ans2 + 1), b - a) << endl; } return 0; }
打得比上一次好,但是 C 做得依旧是一脸懵逼。最近的 C 感觉都有点阴间了。B过得慢了,但又好像没有太慢。可能是atcoder打多了。