一、A - Ian Visits Mary

• 思路:
  思维题,仔细观察发现.要想他们中间没有数字,那我们就第一步先走到(1,b - 1),然后再从(1,b - 1)走到(a,b)

• 代码:

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
const int N = 1e6 + 10,M = 1000007,INF = 1e18 + 1,mod = 1000000007;void solve()
{int a,b; cin >> a >> b;if(__gcd(a,b) == 1){cout << "1" << endl;cout << a << ' ' << b <<endl;}else{cout << "2" << endl;cout << 1 << ' ' << b - 1 << endl;cout << a << ' ' << b << endl;                                }}signed main()
{ios::sync_with_stdio(false);  cin.tie(0); cout.tie(0);int T; T = 1;cin >> T;while(T--) solve();
}

二、B - Grid Reconstruction

• 思路:

  1: 你把图画出来会发现,加减是绝对的,也就是某个位置如果是 + ,不管从哪条路径到这个点来都是 + ,如果是 - ,不管哪条路径过来的都是 -

  2: 这时候就贪心来想,把[n + 1 ,2 * n]之内的数字赋值给 + ,[1,n]之内的数字赋值给 -

  3: 就是对于 + 就是第一行进行降序,也就是n * 2,n* 2 - 2,n * 2 - 4,对第二行进行升序,n + 1,n + 3,n + 5,这种,对于 – ,就上下两行交错的赋值,也就是第一列为1,第二列2,第三列为3,…

• 代码:

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
const int N = 1e6 + 10,M = 1000007,INF = 1e18 + 1,mod = 1000000007;
int a[N][2];
void solve()
{int n; cin >> n;int p = n * 2;int q = n + 1;for(int i = 1;i <= n;i ++ ){if(i & 1){a[i][1] = i;a[i][0] = p;p -= 2;}else{a[i][0] = i;a[i][1] = q;q += 2;}}for(int i = 1;i <= n;i ++ ) cout << a[i][0] << ' ';	cout << endl;for(int i = 1;i <= n;i ++ )	cout << a[i][1] << ' '; cout << endl;}signed main()
{ios::sync_with_stdio(false);  cin.tie(0); cout.tie(0);int T; T = 1;cin >> T;while(T--) solve();
}

三、C - Ian and Array Sorting

• 思路:
  1: 先遍历一遍对于a[i - 1] > a[i]的这种,就改变a[i]和a[i + 1],也就是操作a[i + 1] += a[i - 1] - a[i] ,a[i] = a[i - 1];

  2: 遍历完一遍以后,这个数组要么就变成非递减的,要么除了最后一个其他都是非递减的,

  3: 我们再从后往前遍历对于a[i] > a[i + 1],就改变a[i]和a[i - 1],也就是再操作一遍,最后再遍历一下看看是否有非递减的数字,有就是 NO

• 代码:

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
const int N = 1e6 + 10,M = 1000007,INF = 1e18 + 1,mod = 1000000007;
int a[N];
void solve()
{int n; cin >> n;for(int i = 1;i <= n;i ++ ) cin >> a[i];for(int i = 2;i <= n;i ++ ){if(a[i] < a[i - 1]){int t = a[i - 1] - a[i];if(i + 1 <= n){a[i] = a[i - 1];a[i + 1] = t + a[i + 1];}}}if(a[n] >= a[n - 1] || (n - 1) % 2 == 0) {cout << "YES" << endl;return;}for(int i = n - 1;i >= 1;i -- ){if(a[i] > a[i + 1] && i - 1 >= 1){int t = a[i] - a[i + 1];a[i] = a[i + 1];a[i - 1] -= t; }}for(int i = 2;i <= n;i ++ ){if(a[i] < a[i - 1]){cout << "NO" << endl;	return;}}cout << "YES" << endl;}signed main()
{ios::sync_with_stdio(false);  cin.tie(0); cout.tie(0);int T; T = 1;cin >> T;while(T--) solve();
}

四、D - Sum Graph

• 思路:
  这个也是看别人的代码,我们首先可以进行操作1两次,就是add(n),add(n + 1),这样你的连接的每个点最终会变成一条链,然后你再随便找一个点 ,进行n次查找操作,找出距离该点最长的那个点,那么这个点就一定是这条链的其中一个端点,然后再从该端点出发,进行n次查找就可以知道这个排列(因为题目说排列两个所以,2 *n次操作就可以了)
• 代码:

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
const int N = 1e6 + 10,M = 1000007,INF = 1e18 + 1,mod = 1000000007;
int a1[N],a2[N],b[N],c[N];
int p[N];void add(int x)
{cout << "+ " << x << endl;	int k; cin >> k;
} 
int ask(int x,int y)
{cout << "? " << x << ' ' << y << endl;int k; cin >> k;return k;
}void print(int n)
{cout << "! ";for(int i = 1;i <= 2 * n;i ++ ) cout << p[i] << ' ';cout << endl; int w; cin >> w;
}void solve()
{int n; cin >> n;add(n);add(n + 1);int k = 1,t = 0;int cnt = 0;for(int i = 1;i <= n / 2;i ++){b[++cnt] = n - i + 1;b[++cnt] = i; // 把这条链放到数组中}if(n & 1) b[++cnt] = n / 2 + 1;// 如果是奇数,特判一下for(int i = 1;i <= n;i ++ ){c[b[i]] = b[n - i + 1]; // c数组这个没啥用,a1[i - 1] = b[i]; // 距离左端点距离为i - 1的点的值a2[i - 1] = b[n - i + 1]; //距离右端点距离为i - 1的点的值}int id = -1,mx = -1;for(int i = 2;i <= n;i ++ ) // 找出端点在id位置{int dis = ask(1,i);if(dis > mx){mx = dis;id = i;}}p[id] = n; // 这个位置要么是np[n + id] = c[n]; // n + i就是另一个端点for(int i = 1;i <= n;i ++ ){if(i == id) continue;int dis = ask(id,i); // id = 2int val = a1[dis];p[i] = val;p[i + n] = a2[dis];}print(n);
}signed main()
{ios::sync_with_stdio(false);  cin.tie(0); cout.tie(0);int T; T = 1;cin >> T;while(T--) solve();
}