A
核心思路：其实我们需要挖掘出一个性质，那就是任何一个答案都必然是个长方形。所以我们只需要计算长方形的一个周长就好了。为什么有这样一个性质呢，因为我们发现任何一条曲边都可以被拉直，因为长度是一样的。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
void solve()
{
int n;
cin >> n;
int ans = 0;
int xl=0, xr=0, yl=0, yr=0;
while (n--)
{
int x, y;
cin >> x >> y;
if (x == 0)
{
yl = min(yl, y);
yr = max(yr, y);
}
else if (y == 0)
{
xl = min(xl, x);
xr = max(xr, x);
}
}
cout << 2 * (xr - xl + yr-yl) << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}
B
核心思路：这题也是模拟样例观察出来的重要规律，那就是不可以有凹的山峰，。但是当时没有观察细致，其实是这样一个性质：
\(对于任意的a[i](i\geq2),如果存在maxv1[i-1]和maxv2[i+1]都要大于a[i]那么就肯定不可以\).
所以我们只需要求出来maxv1和maxv2就好了.
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
vector<int> square;
int a[N],maxv1[N],maxv2[N];
void solve()
{
int n;
cin >> n;
for (int i = 1;i <= n;i++)
cin >> a[i];
for (int i = 1;i <= n;i++)
maxv1[i] = max(maxv1[i - 1], a[i]);
maxv2[n] = a[n];
for (int i = n - 1;i;i--)
{
maxv2[i] = max(maxv2[i + 1], a[i]);
}
int flag = 1;
for (int i = 2;i <= n - 1;i++)
{
if (maxv1[i - 1] > a[i] && maxv2[i + 1] > a[i])
{
flag = 0;
break;
}
}
cout << (flag ? "YES" : "NO") << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}
C
核心思路：首先分析自己构造出来的这组样例：
a[i]: 1 3 2 6 5 4
idx: 0 1 2 3 4 5
然后观察:
6 5 4
3 4 5
所以我们得出来之需要找出来第一个大于等于idx的平方数，然后相减。再利用这一个数，循环下但是不可以小于我们所要的数开根号，就可以得出来一组数。
也就是我们不可以继续跑下去了，还下去就是3 6这组数了。所以限制就是l<=i.
这个也算是模拟样例得出来的结论吧。有点子马虎，但是我这样构造是绝对可行的，所以问题不大。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
vector<int> square;
int ans[N];
void Init()
{
for (int i = 0;i * i < N;i++)
square.push_back(i * i);
}
int binary_search(int n)
{
int l = 0;
int r = square.size();
while (l < r)
{
int mid = l + r >> 1;
if (n <= square[mid])
r = mid;
else
l = mid + 1;
}
return r;
}
void solve()
{
int n;
cin >> n;
int r = binary_search(n - 1), l, now;
int flag = 1;
for (int i = n - 1; i >= 0; --i) {
l = square[r] - i;
now = i;
if (l > i) {
flag = false;
}
while (l <= i) {
ans[now--] = l++;
}
i = now + 1;
r = binary_search(i - 1);
}
if (flag)
{
for (int i = 0;i < n;i++)
cout << ans[i] << " ";
cout << endl;
}
else
{
cout << -1 << endl;
}
}
int main()
{
Init();
int T;
cin >> T;
while (T--)
{
solve();
}
}
D
核心思路：这是一道交互题 。所以得先仔细阅读题目难不到那里去的。老样子先从一般情况入手：也就是人数是4的情况。
我们假设他们刚开始的胜利的场次都是t,那么进行两次比赛之后就会变成:[t,t,t+1,t+2].
我们需要通过询问得出来最后的胜利者是谁。
刚开始询问1 3如果res=0
- 就说明是平局，接下来去询问2 4就是的
如果res=1
- 就说明3比不过1，所以接下来可以去询问1 4
如果res=2
- 就说明1比不过3，所以接下去询问2 3
所以大概就是这样一个逻辑，每次询问四个就好了.
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 3e6 + 10;
int n;
int ask(int x, int y)
{
cout << "? " << x << " " << y << endl;
int ret;
cin >> ret;
return ret;
}
void solve() {
cin >> n;
n = 1 << n;
vector<int>round;
for (int i = 1; i <= n; i++)round.push_back(i);
while (round.size() > 1) {
vector<int>win;
if (round.size() == 2) {
int res = ask(round[0], round[1]);
if (res == 1)win.push_back(round[0]);
else win.push_back(round[1]);
}
else {
for (int i = 0; i < round.size(); i += 4) {
int res = ask(round[i + 0], round[i + 2]);
if (res == 0) {
if (ask(round[i + 1], round[i + 3]) == 1)win.push_back(round[i + 1]);
else win.push_back(round[i + 3]);
}
else if (res == 1) {
if (ask(round[i + 0], round[i + 3]) == 1)win.push_back(round[i + 0]);
else win.push_back(round[i + 3]);
}
else {
if (ask(round[i + 1], round[i + 2]) == 1)win.push_back(round[i + 1]);
else win.push_back(round[i + 2]);
}
}
}
round = win;
}
cout << "! " << round[0] << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}