A
最坏的情况就是所有开着的开关尽可能配对
最好的情况就是所有开着的开关尽可能不配对
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
const int N=1e6+10;
const int mod=998244353;
const int INF = 0x3f3f3f3f;
const ll INFll = 0x3f3f3f3f3f3f3f3f;
#define endl "\n"
//vector<vector<int>>adj(N);
void solve()
{
int n; cin >> n;
int sum = 0;
for(int i = 1; i <= 2 * n; i ++) {
int x; cin >> x;
sum += x;
}
cout << sum%2 << " ";
if(sum > n) sum -= 2 * (sum - n);
cout << sum << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cout << setprecision(11) << fixed;
int t;t=1;
cin>>t;
for(int i=1;i<=t;i++){
//printf("Case %d: ",i);
solve();
}
}
B
分析
首先要保证 \(k\) 这个数作为 \(k\) 所在区间的中位数，那么就直接让这个区间以 \(k\) 为中心，
当 \(k\) 在第一轮被选出来后，要使得第二轮的中位数也为 \(k\) ，那么左边区间数量应该等于右边区间数量
直接使这个左右区间数量为1
现在就只有三个区间，"左","中", "右".
只剩一个要求了，所有区间的长度为奇数，第一轮构造可以保证 |中| 是奇数.
又因为题目保证 \(n\) 为奇数，我们枚举 |中|, 直接计算左右两个区间的长度，找到三个区间长度都为奇数的情况.
实际上 奇 = 偶 + 奇 + 偶 或者 奇 = 奇 + 奇 + 奇,
这两种情况会交替出现，加上边界判断，可以让这个枚举的复杂度降到 \(o(1)\)
n = 1 时不可能有3个区间，要特判
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
const int N=1e6+10;
const int mod=998244353;
const int INF = 0x3f3f3f3f;
const ll INFll = 0x3f3f3f3f3f3f3f3f;
#define endl "\n"
//vector<vector<int>>adj(N);
void solve()
{
int n, k;
cin >> n >> k;
int len = 0;
if(n == 1) {
cout << 1 << endl;
cout << 1 << endl;
return;
}
while(1) {
if(k - len < 1 || k + len > n) break;
int l = k - 1 - len ;
int r = n - k - len;
// cout << l << " " << r << endl;
if(l%2 && r%2) {
cout << 3 << endl;
cout << 1 << " " << l + 1 << " " << n - r + 1 << endl;
return;
}
len ++;
}
cout << "-1" << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cout << setprecision(11) << fixed;
int t;t=1;
cin>>t;
for(int i=1;i<=t;i++){
//printf("Case %d: ",i);
solve();
}
}
C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
const int N=1e6+10;
const int mod=998244353;
const int INF = 0x3f3f3f3f;
const ll INFll = 0x3f3f3f3f3f3f3f3f;
#define endl "\n"
//vector<vector<int>>adj(N);
void solve()
{
int n; cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i ++) cin >> a[i];
sort(a.begin(), a.end());
int ans = 0;
int r = 0;
for(int l = 0; l < n - 1; l ++) {
while(r < n && a[l] + a[l + 1] > a[r]) r ++;
// cout << a[l] + a[l + 1] << " " << a[r] << endl;
ans = max(r - l, ans);
// cerr << l + 1 << " " << r + 1 << endl;
}
cout << n - ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cout << setprecision(11) << fixed;
int t;t=1;
cin>>t;
for(int i=1;i<=t;i++){
//printf("Case %d: ",i);
solve();
}
}
D
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
const int N=1e6+10;
const int mod=998244353;
const int INF = 0x3f3f3f3f;
const ll INFll = 0x3f3f3f3f3f3f3f3f;
//vector<vector<int>>adj(N);
int ask(int a, int b) {
int ans;
cout << "? " << a << " " << b << endl;
cin >> ans;
return ans;
}
void solve()
{
int n;
cin >> n;
vector<int>p(n, 0);
vector<int>fa,fa2;
p[1] = 0;
int i;
for(i = 2; i < n; i ++) {
if(ask(1, i) == 0) {
p[i] = 1;
fa.push_back(i);
i ++;
break;
}
p[i] = 0;
fa.push_back(i);
}
int j = 0;
for(; i < n ; i ++) {
while(j < (int)fa.size() && ask(fa[j], i) == 1) {
j ++;
}
if(j >= (int)fa.size()) {
swap(fa, fa2);
fa2.clear();
i --;
j = 0;
} else {
p[i] = fa[j];
fa2.push_back(i);
j ++;
}
}
cout << "! ";
for(int i = 1; i < n; i ++) cout << p[i] << " "; cout << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cout << setprecision(11) << fixed;
int t;t=1;
cin>>t;
for(int i=1;i<=t;i++){
//printf("Case %d: ",i);
solve();
}
}