题目链接 - Codeforces Round 931 (Div. 2)

A. Too Min Too Max

题意

给出一个数组， 现在要你选择四个下标$i,j,k,l$ , 问$|a_i - a_j|+|a_j - a_k|+|a_k - a_l|+|a_l - a_i|$ 最大是多少。（$i , j,k,l$ 必须互不相同）

思路

题目要求的其实就是选出四个数组成一个环，使得相邻两个数的差的和最大。

于是我们先探究 ： 如果选出了某四个数，如何调整他们在环中的顺序能使得总和最大。 不难想到， 将较大的两个数放在第一和第三位， 较小的两个数放在第二和第四位时， 得到的结果最大。 此时为($a_i - a_j) +( a_k - a_j )+ (a_k - a_l)+(a_i - a_l)$ ，即$2*(a_i + a_k - a_j -a_l)$

第二步我们考虑如何选择这四个数能使得结果最大。 很明显我们需要尽可能让 较大的两个数$a_i,a_k$ 更大，较小的两个数$a_j.a_l$更小。

于是对于整个数组，选出最大的两个数，以及最小的两个数，就可以得到最优结果。

对数组a进行排序， 就得到了最终结果为 $2*(an + a{n-1} - a_1 - a_2)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
	int n;
	cin>>n;
	vector<int> a;
	rep(i,1,n){int num;cin>>num;a.push_back(num);}
	sort(a.begin(),a.end());
	cout<<2*(a[n-1]+a[n-2]-a[0]-a[1])<<'\n';
}
signed main(){
	int T = 1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

B. Yet Another Coin Problem

题意

现在有一些面值为$1,3,6,10,15$ 的硬币 ， 问如何选择各个硬币的数量，使得总面值恰好为n，并且硬币的总数量最少。

$(1 \le n \le 10^9)$

思路

我们观察这些硬币的面值，可以发现$3,6,15$ 都是3的倍数。而另一个大面值硬币又可以表示为$10 = 3*3+1$ 。于是我们有如下策略：

  1. 尽可能多地选择3 ，此时可能剩下$[0,2]$的面值。即$md = 0,1,2$ , 如果md 为0，那么我们就可以将这些面值为3的硬币尽可能多地兑换为面值为15和6的硬币。

  2. 如果有剩余， 若手中面值3的硬币的数量大于等于3 ，就可以将这三个3和一个1 换成一个10。

  3. 如果有剩余并且手中的面值3的硬币数量小于3，那么就只能用面值为1的硬币来填补这个空缺了。

代码

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
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
	int n;
	cin>>n;
	int md = n%3; //md是除以3后的余数
	int t = n/3;// t是除以3后的结果
	int ans = 0;
	if(md == 2){//如果余两个,那么就尝试将一个余数和3个3结合。
		if(t>=3) {ans++;t-=3;}//成功结合
		else ans++;//不能结合
		md = 1;
	}
	if(md == 1){//同理
		if(t >= 3) {ans++;t-=3;}
		else ans++;
		md = 0;
	}
	//这时候md一定为0
    ans += t / 5; // 能换成多少个15
    t %= 5;
    ans += t / 2;// 剩下的还能换成多少个6
    t %= 2;
    ans+=t; // 都换不成了，就用3吧
    //输出答案
	cout<<ans<<'\n';
}
signed main(){
	int T = 1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

C. Find a Mine

题意

和上一场的C一样，又是交互题。 给出一个n *m的网格，其中有两个位置有地雷，但你不知道他们在哪， 你最多可以询问四次。

每次提供一个坐标， 裁判会告诉你两个地雷距离这个坐标的曼哈顿距离 中的最小值是多少。 现在需要你在最多四次询问之后，给出任意一颗地雷的具体坐标。

曼哈顿距离 ： 两个坐标$(x1 ,y1) , (x2,y2)$ 的曼哈顿距离为$|x1-x2|+|y1-y2|$ 。对于如下5*5的网格， 点$(3,3)$与所有点的曼哈顿距离如下

picture1

思路

我们发现确定一个点以及一个曼哈顿距离后 ，我们可以得到可能的范围是一个菱形。 如果我们将询问点设置在表格的一角，那么表格中可能的格子就组成了一个对角线。 于是我们询问地图的三个角，就得到了三条对角线，他们三者相交一定最多次出现两个交点。（也可能是一个）。之后我们再询问其中一个交点，如果给出的答案是0，就代表他是地雷，如果不是0，就代表另一个是地雷。

picture2

我们可能遇到两个对角线相交没有准确格子的情况（如上图中的红对角线和蓝对角线，二者没有共同的格子）

代码

这里有些地方需要讲解一下：

在代码中，先询问了左上，右下，右上三个角。得到了三个曼哈顿距离 $a, b,c$。

怎么求两个交点呢？ 先看左上和右上两个对角线形成的交点。假设为$(x_1,y_1)$ ，那么就有

$x_1 - 1 + y_1 - 1 = a$

$m - y_1 + x_1 - 1 = c$ 解方程可以得到 $x_1 = \frac{a+c-m+3}{2} , y_1 = \frac{a-c+1+m}{2}$ , 但我们发现可能会出现x和y不是整数的时候（也就是$a+c-m$为偶数的时候），这时候就不可取。（代码中表示为将x和y都设置为-1）

按照同样的方法

$m - y_2 + x_2 - 1 = c$

$n-x_2 + m - y_2 = b$

可以找到另一个交点$x_2 = \frac{2*m+n-b-c-1}{2} , y_2 = \frac{n+c-b+1}{2}$。

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
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int n,m;
bool inrange(int x,int y){
	if(x<=n && x >= 1 && 1<=y && y<=m) return true;
	else return false;
}
void solve(){
	cin>>n>>m;
	cout<<"? 1 1"<<endl;
	int a; cin>>a;
	cout<<"? "<<n<<" "<<m<<endl;
	int b;cin>>b;
	cout<<"? 1 "<<m<<endl;
	int c;cin>>c;
	int x1,y1,x2,y2;
	int t = a+c - (m-1);
	if(t%2){x1 = y1 = -1;}
	else {y1 = t/2+1;x1 = (a-t/2)+1;}
	t = b+c - (n-1);
	if(t%2){x2 = y2 = -1;}
	else{y2 = m-t/2;x2=(c-t/2)+1;}
	if(!inrange(x1,y1)) {cout<<"! "<<x2<<" "<<y2<<endl;}
	else if(!inrange(x2,y2)) {cout<<"! "<<x1<<" "<<y1<<endl;}
	else{
		cout<<"? "<<x1<<" "<<y1<<endl;
		int d;cin>>d;
		if(d == 0) cout<<"! "<<x1<<" "<<y1<<endl;
		else cout<<"! "<<x2<<" "<<y2<<endl;
	}
}
signed main(){
	int T = 1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

D1. XOR Break — Solo Version

题意

给出操作方法为：若操作前的数值为$y$，那么选择一个x ，使得$x<y , x \oplus y<y$ , 之后令$y = x$或$y = y \oplus x$ 。

给出n和m$(m<n)$ 问能否让n进行一定次数的操作后， 变为m。

$\oplus$ 为异或符号， $x \oplus y $表示$x$和$y$的异或 。

思路

首先应该注意到的是： 我们不论选择$y = x$还是$y = y \oplus x$ ，都是等价的,因为若令$y = y \oplus x $ 那么不妨将我们设置的原先的$x_1$更改为$y\oplus x_2$ 这样选择$y = y \oplus x_2 = y \oplus (y \oplus x_1) = x1$ 是等价的。 因此我们对于某个y，他可以一步变化的数为集合${x| x<n\& x\oplus y < y }$

接下来我们可以发现如下两个规律：

  1. 如果$y$是11111（全1），那么y可以变为任意小于$y$的数。
  2. 如果$y$= 10000（只有一个1），那么y再也不能变化了 。

接下来我们找对于n所形成的可达的集合。其中的最大值：

先找到n的前两个为1的位置。（如果n只有一个1那么根据规律2可知无解），假设为a和b，如

当$n = 1010001_{(2)}$ 时，$a = 1，b = 3$ 。（从左往右标注从1开始的下标）

那么为了使得$m$和$n \oplus m$都比$n$小，二者必须有一个变成0。

并且此时得知一个引论： 在a和b中间的这部分数位，m中的该部分必须全为0 。(反例：n = 101000，m = 01000,这里在m的第2位为1于是n一定不能到达m) ，否则便无解。

于是新的n（我们将他命名为$nn$）则是$nn = 0010001$ 或者 $nn = 1000001$。我们发现对于b右边的数位（也就是第二个1之后的数位），无论他如何改变，都可以满足nn^n 和nn均小于n（因为最靠前的两个1位$a,b$已经保证了这个性质），那么我们不妨让之后的数位都变为1（因为这样子可以尽可能地满足规律1，使得$nn$到$m$更有可能）

于是我们得到如下结论，在令一个原本为1的位置变为0后，如果n中已经出现过至少两个1，那么之后的数位都可以变为1 。

那么应该把哪一位的1变为0呢？

检查n和m的二进制数，然后从大端找，找第一个n和m数位不同的地方，这时候一定是n的数位是1，m的数位是0
比如

1
2
n = 111000
m = 101000

发现左边第二位是1，于是将这一位置为0 , 这样就保证了对于前两位的1，有 m 和n^m都小于n。在此之后，将之后的位置（第3位到第6位）都变为1，便得到了nn = 101111 。我们构造的这个$nn$保证了在前半部分和m完全相同，无需理会，后半部分又全是1，可以随意变换。也就是说，只要nn大于m，那么一定可以从$nn$变成$m$。

因此我们得知了变化顺序$n \to nn \to m$ ，由于$nn$可能等于$m$，因此也可能是$n \to m$ 。

代码

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
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n,m;
    cin>>n>>m;
    int nn = n;
    int flag = 0;
    for(int i = 62;i>=0;i--){
        if(flag == 0 && ((n>>i)&1)!=((m>>i)&1)){
            flag = 1;
            nn -= (1<<i);
        }
        else if(flag == 1 && (n>>i)&1==0){
            flag = 2;
        }else if(flag == 2){
            nn |= (1<<i);
        }
    }
    if(nn<m){cout<<-1<<endl;return;}
    if(nn == m){
        cout<<2<<endl;
        cout<<n<<" "<<m<<endl;
    }else{
        cout<<3<<endl;
        cout<<n<<" "<<nn<<" "<<m<<endl;
    }
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}