Codeforces Round 1008 (Div. 2)¶
又是一次掉分，最近打CF总是好难受啊。还是实力太弱太弱导致的。感觉非常的难受啊。不过也合理，我又付出了什么呢？真正自己思考的题能有几个呢？😭😭😭
真的还是很失落的，好久没上分了，甚至一直卡在青名，好久没有体会到上分的快乐了。唉唉。
比赛链接: https://codeforces.com/contest/2078
上不了分就要加训，我一定要上分。
A¶
正常的 A 题，直接观察发现正好平均值等于 X 的都是 YES ，然后就猜一发直接交，后面再想想吧。
void ChatGptDeepSeek()
{
int n,x;
cin>>n>>x;
vector<int>a(n+1);
for(int i=1;i<=n;i++)
cin>>a[i];
int sum=0;
for(int i=1;i<=n;i++)
sum+=a[i];
//如果选了一个因子 那么？
//3？
if(sum==n*x) cout<<"YES\n";
else cout<<"NO\n";
}
B¶
肯定不可能所有人都能到 \(n\) ，因为 \(a_i\ne i\) ，但是我们完全可以做到只有一个不等于 \(n\) 。
分下奇偶讨论一下.
\(k\) 为奇数，则我们需要第一次就能直接到 \(n\) ，所以就全等于 \(n\) 。
\(k\) 为偶数，则第一次不要到 \(n\) ，那就到 \(n-1\) 呗，然后 \(n-1\) 到 \(n\) 。
void ChatGptDeepSeek()
{
int n,k;
cin>>n>>k;
//k为奇数？
//全为 n ，除了最后一个
//k为偶数？
//第一次全部去n-1 ，然后n-1去n
//2 2?
//2 1
if(k&1){
for(int i=1;i<=n-1;i++){
cout<<n<<' ';
}
cout<<n-1<<'\n';
}else{
for(int i=1;i<n-1;i++)
cout<<n-1<<' ';
cout<<n<<" "<<n-1<<'\n';
}
}
C¶
其实挺 easy 的 ，但是为什么一直没看出来呢。。。
太慢了，这把打得不好的很大一部分原因就是 C 写得太慢了。虽然之后还是不一定能 AC D题。
由于每个数字都不同，所以我们通过组合，肯定可以使得那个表达式是大于0或者小于0。
那么我们如果把 \(b\) 里最大的值当作 \(a_1\) ，那么肯定可以使得 \(a_2\) 后面减的是一个正数，这样 \(a_2\) 就是我们构造出的新数字，它比原数组中每一个数字都大。
构造一个比最小值小的数字也是可以做到的，但是可能会不是一个正整数。
这个思路好像还真不是很好想。
void ChatGptDeepSeek()
{
//+b0 -b1
int n;
cin >> n;
vector<int> b(n * 2 + 1);
for (int i = 1; i <= n * 2; i++) {
cin >> b[i];
}
sort(b.begin() + 1, b.end());
// set<int> st1, st2;
// ll s1 = 0, s2 = 0;
// for (int i = 1; i <= n; i++)
// st1.insert(b[i]), s1 += b[i];
// for (int i = n + 1; i <= n * 2; i++)
// st2.insert(b[i]), s2 += b[i];
//如果说大的n 个 减去小的 n个
//正好等于了某一个值
//- + - + -
//选一个很大的数字，然后减了之后正好等于an?可行吗
//4
//1 2 3 4
//6-1+2-3
ll s=b[2*n];
//s-x=a[2n]
for(int i=1;i<2*n;i++){
if(i&1) s+=b[i];
else s-=b[i];
}
cout<<b[2*n]<<" "<<s<<' ';
for(int i=1;i<2*n;i++)
cout<<b[i]<<" \n"[i+1==2*n];
}
其实能写出来 C 也是有点不容易了。。。
D¶
不得不说这D确实不难的，但是确实是一直没想到。。。
我单想到了哪个乘的离得近就给哪个，但是我没想到如果大小相同，可以先把多出来的留着，之后再决定怎么分配。。
好牛啊。
using ll = long long;
void ChatGptDeepSeek()
{
int n;
cin >> n;
ll x = 0, L = 1, R = 1;
while (n--) {
char o1, o2;
int x1, x2;
cin >> o1 >> x1 >> o2 >> x2;
if (o1 == 'x' && o2 == 'x') {
if (x1 > x2) {
L += x;
x = L * (x1 - 1) + R * (x2 - 1);
} else if (x1 < x2) {
R += x;
x = L * (x1 - 1) + R * (x2 - 1);
} else {
x = x * x1 + L * (x1 - 1) + R * (x2 - 1);
}
} else if (o1 == 'x') {
L += x;
x = L * (x1 - 1) + x2;
} else if (o2 == 'x') {
R += x;
x = R * (x2 - 1) + x1;
} else {
x += x1 + x2;
}
}
cout << L + R + x << '\n';
}
E¶
本来是一点思路都没的，看了评论区有人说用 01010101 和 10101010 问，也有说拿 0 和 101010101 ，我当时没太理解第一种。
我本来自己想的是，先问一次 0 ，这样就知道 \(x+y\) 的值了。第二次我想的是问一个全 \(1\) 的数字来着。这样我可以知道 \(x\) 和 \(y\) 每一位上的 \(1\) 的数量。
但是事实上并不行，因为有的地方那一位0个1，答案会是 \(2\) 倍的这一位的值，也可能是 \(1\) 位的高一位的值。。。并不能确定具体是那一位给的贡献。
所以我们问 0 和 1010101010 就能确定奇数或者偶数位上的 1 的数量，然后用 \(x+y\) 减去这个值，就得到了 \(x\) 和 \(y\) 的偶数位的和，就可以知道偶数位的每一位上的 \(1\) 的数量。于是就知道了每一位的情况。
其实 10101010 和 01010101 这两个一起问，也是差不多同理的。
令奇数位上全为 \(1\) 的 \(101010101 = n\) ，那么 \((x|n)+(y|n)-2n\) 实际上就等于 \(x+y\) 在奇数位上的和，就可以求出它们奇数位的异或的值。然后再另一个数字可以求出偶数位的异或的值，就达到了和另一种问法的相同的效果。
还是比较不容易想到的。。但感觉难度不太高的，起码只知道问什么数字就很容易写了。
constexpr int val = 715827882;
int ask(int n)
{
cout << n << endl;
int res;
cin >> res;
return res;
}
void ChatGptDeepSeek()
{
// 问01010101非常有道理啊
// 因为这一位的1，一定会比后面所有的和要大
// 不对，，，但是怎么和10101010结合起来呢？
// 直接问 0 和 0101010101吧
//
int sum = ask(0);
int res = ask(val);
vector<int> b(30);
int x = res - sum, y = 0;
for (int i = 29; i >= 0; i -= 2) {
if (x >= (1 << (i + 1))) {
// b[i] = 2;
x -= 1 << (i + 1);
} else if (x >= (1 << i)) {
b[i] = 1;
x -= 1 << i;
y += 1 << i;
} else {
y += 1 << (i + 1);
b[i] = 2;
}
}
assert(x == 0);
x = sum - y;
for (int i = 28; i >= 0; i -= 2) {
if (x >= (1 << (i + 1))) {
x -= 1 << (i + 1);
b[i] = 2;
} else if (x >= (1 << i)) {
x -= 1 << i;
b[i] = 1;
}
}
cout << "!" << endl;
int m;
cin >> m;
for (int i = 29; i >= 0; i--) {
// cerr << b[i] << " \n";
if (m >> i & 1) {
sum += (2 - b[i]) * (1 << i);
}
}
cout << sum << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// int sum=0;
// for(int i=29;i>=0;i--){
// if(i&1) sum|=1<<i;
// }
// cerr<<sum<<'\n';
int T = 1;
cin >> T;
while (T--)
ChatGptDeepSeek();
return 0;
}
这里只写了第一种，另一种同理的。