题目链接
D. Bits Reverse每次将三个连续的位反转，其实中间的位是不变的，就是把第一位和第三位互换，可以发现奇数位和偶数位互不影响，那么分别处理奇数位和偶数位即可。然后分别比较1的位数是否相同，然后再计算移动的步数（这里用了贪心，也可以直接将对应1的位置加起来相减取绝对值）
#includeG. Greatest Common Divisor#include #include using namespace std; int main() { ios::sync_with_stdio(false), cin.tie(0); long long n, m; int a[100], b[100]; int t, c = 0; cin >> t; while (t--) { cout << "Case " << ++c << ": "; vector cnta, cntb;//记录1的位置 int sum = 0; cin >> n >> m; //将每一位保存到数组中 for (int i = 0; i < 64; i++) { a[i] = n & 1; b[i] = m & 1; n >>= 1; m >>= 1; } //处理奇数位 for (int i = 0; i < 64; i++) { if (i & 1) { if (a[i]) cnta.push_back(i); if (b[i]) cntb.push_back(i); } } //判断1的位数是否相同，如果不同就输出-1 if (cnta.size() != cntb.size()) { cout << -1 << endl; continue; } else { //累加移动步数，注意要除2 for (int i = 0; i < cnta.size(); i++) sum += abs(cnta[i] - cntb[i]) / 2; cnta.clear(); cntb.clear(); } //处理偶数位 for (int i = 0; i < 64; i++) { if (!(i & 1)) { if (a[i]) cnta.push_back(i); if (b[i]) cntb.push_back(i); } } if (cnta.size() != cntb.size()) { cout << -1 << endl; continue; } else { for (int i = 0; i < cnta.size(); i++) sum += abs(cnta[i] - cntb[i]) / 2; cnta.clear(); cntb.clear(); } cout << sum << endl; } return 0; }
先将数字排个升序，并去除重复的。然后将相邻数字的差值记录成一个集合，记这个集合中所有数字的最大公约数为gc。如果gc大于1则有解。
然后进行判断
如果gc和a[0]不互质的话，直接输出0即可，否则取gc的最小因数m（大于1的）作为这个序列的公约数。
证明： 如果数字间的差都是m(gc的一个大于1的因数)，那么当第一个数字a[0]能被m整除时，后面的元素也一定可以被整除，因为a[…]可以表示成a[0]+n*m
#include #includeH. Hamming Distance#include #include #define maxn 100005 using namespace std; inline int scf(int &a) { return scanf("%d", &a); } inline int gcd(int a, int b) { while (b != 0) { int t = a; a = b; b = t % b; } return a; } int num[maxn]; int main() { //将数字进行排序，如果数字间的差值的gcd大于1，就可行 int t, c = 0; cin >> t; while (t--) { printf("Case %d: ", ++c); vector v; int n; int gc; cin >> n; for (int i = 0; i < n; i++) scf(num[i]); sort(num, num + n); v.push_back(num[0]); for (int i = 1; i < n; i++) //去除重复数字 if (num[i] != num[i - 1]) v.push_back(num[i]); if (v.size() == 1) { if (v[0] > 1) printf("0"); else printf("1"); } else { gc = v[1] - v[0]; for (int i = 2; i < v.size(); i++) gc = gcd(gc, v[i] - v[i - 1]); if (gc == 1) printf("-1"); else { if (gcd(gc, v[0]) > 1) { printf("0"); } else { for (int i = 2; i * i <= gc; i++) { if (gc % i == 0) { gc = i; break; } } printf("%d", gc - v[0] % gc); } } } printf("n"); } return 0; }
首先从后往前记录不同的字符位数，记录在h[]中，为了使最终的字符序列对于两个初始序列的汉明距离相同，已放置的字符的汉明距离要小于h[i+1]，否则无法保证汉明距离相同。
#includeJ. Stone Game#include #include #include #define maxn 10005 using namespace std; int h[maxn], t, dis; //h[i]记录i位之后有多少位不同的字符数 char a[maxn], b[maxn]; bool check(char ch, int index) { int cnt = 0; if (a[index] != ch) cnt++; if (b[index] != ch) cnt--; if (abs(cnt + dis) <= h[index + 1]) return 1; return 0; } int main() { char ans[maxn]; cin >> t; for (int k = 1; k <= t; k++) { scanf("%s %s", a, b); int len = strlen(a); h[len] = 0; for (int i = len - 1; i >= 0; i--) { h[i] = h[i + 1]; if (a[i] != b[i]) h[i]++; } for (int i = 0; i < len; i++) { for (char ch = 'a'; ch <= 'z'; ch++) { if (check(ch, i)) { ans[i] = ch; if (a[i] != ch) dis++; if (b[i] != ch) dis--; break; } } } ans[len] = ' '; printf("Case %d: %sn", k, ans); } return 0; }
因为相邻数字不能相同，因此要找升序降序的序列进行改变才不会影响，谷点可以直接置0，顶点要在最后根据两边的数字进行改变。
#include#include #define maxn 1000005 #define mem(a) memset(a, 0, sizeof(a)) #define frein freopen("in.txt", "r", stdin) using namespace std; int num[maxn], ans[maxn]; int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int t; cin >> t; //在开头和结尾插入-1，方便处理 num[0] = -1; ans[0] = -1; for (int k = 1; k <= t; k++) { int n; long long cnt = 0; vector point, uppoint; cin >> n; for (int i = 1; i <= n; i++) cin >> num[i]; num[n + 1] = -1; ans[n + 1] = -1; point.push_back(0); for (int i = 1; i <= n; i++) { //谷点 因为两边的石头数都大于谷点 所以可以直接变成0 if (num[i] < num[i - 1] && num[i] < num[i + 1]) { cnt += num[i]; num[i] = 0; ans[i] = 0; point.push_back(i); } //顶点 最后处理 else if (num[i] > num[i - 1] && num[i] > num[i + 1]) point.push_back(i); } point.push_back(n + 1); //找升序和降序的段 然后改变那一段的石头 for (int i = 1; i < point.size(); i++) { int p1 = point[i - 1], p2 = point[i]; //这一段是升序 if (num[p2] > num[p1]) { uppoint.push_back(p2); for (int j = p1 + 1; j < p2; j++) ans[j] = ans[j - 1] + 1; } else //这一段是降序 { for (int j = p2 - 1; j > p1; j--) ans[j] = ans[j + 1] + 1; } } //处理顶点 for (int i : uppoint) ans[i] = max(ans[i - 1], ans[i + 1]) + 1; for (int i = 1; i <= n; i++) cnt += num[i] - ans[i]; if (cnt & 1) cout << "Case " << k << ": Alice" << endl; else cout << "Case " << k << ": Bob" << endl; } return 0; }
