链接：Codeforces Round 983 (Div. 2)
A：Circuit
大意：
n个灯，每个灯连两个开关，每个开关只连一个灯，每个灯对应的两个开关如果异或为1就亮
现给定开关状态，求灯亮的最大和最小数量
思路：
求最小数量的话，将开关为1的尽量组一起，我们发现，如果开关为1的数量为奇数，最小亮一个灯，偶数不亮灯
求最大数量，将开关为1的如果<= n，直接输出开关为一的数量就行，开关为1的大于n，输出2n-开关为1即可，因为这就相当于先给每个灯安排一个为1的开关，然后剩下的为1的开关慢慢踩灯，那最后亮的就是n - (cnt - n)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int, int>>
#define ff first
#define ss second
// ++ ~! */+- <<>> <> == &^| &&|| =
void solve()
{
int n;cin >> n;
int cnt = 0;
for (int i = 1; i <= n * 2; i++)
{
int x;cin >> x;
cnt += x;
}
int mx, mn;
if (cnt <= n)
{
mx = cnt;
mn = cnt & 1;
}
else
{
mx = 2 * n - cnt;
mn = cnt & 1;
}
cout << mn << ' ' << mx << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
/* /\_/\
* (= ._.)
* / > \>
*/B：Medians
大意：
给一组长度为奇数的排列1~n，分成奇数个子数组，求子数组的中位数构成的数组的中位数能否是k，能的话输出方案
思路：
这道题n是奇数，并且限制子数组为奇数，这就说明，每个中位数都是排列中的数
首先考虑中位数为k不存在的情况，当k不存在时，k只可能是1或者n（n=1的时候除外），因为中位数只可能是中间的数
k如果合理，那么我们可以分成左边m个子数组，右边m个子数组，中间以k为中位数，为了方便输出，可以取中间只包含k，然后对m进行奇偶讨论，奇数直接左右都是一整块，偶数再拆分成两个奇数（偶数也可以让中间的子数组变成三个数，最后也输出三个子数组），构成五个子数组
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int, int>>
#define ff first
#define ss second
// ++ ~! */+- <<>> <> == &^| &&|| =
void solve()
{
int n, k;cin >> n >> k;
if (n == 1)
{
cout << 1 << endl;
cout << 1 << endl;
}
else if (k == 1 || k == n)
{
cout << -1 << endl;
}
else if (n == 3 && k == 2)
{
cout << 3 << endl;
cout << "1 2 3" << endl;
}
else
{
if ((k & 1 )== 0)
{
cout << 3 << endl;
cout << 1 << ' ' << k << ' ' << k + 1 <<endl;
}
else if(k & 1)
{
cout << 5 << endl;
cout << 1 << ' ' << 2 << ' ' << k << ' ' << k + 1 << ' ' << k + 2 << endl;
}
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
/* /\_/\
* (= ._.)
* / > \>
*/C：Trinity
大意：
给一组数，问最少可以通过赋值（a[i] = a[j]）几次使得，对于任意三个数，都能组成三角形
思路：
这道题的话，可以排个序，然后求最大的合法区间长度，然后用n减去即可
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int, int>>
#define ff first
#define ss second
// ++ ~! */+- <<>> <> == &^| &&|| =
void solve()
{
int n;cin >> n;
vi a(n);
for (int i = 0; i < n; i++)cin >> a[i];
sort(a.begin(), a.end());
vi dp(n);
int num = 0;
for (int i = 0, j = 2; i < n - 2; i++)
{
while (j < n && a[i] + a[i + 1] > a[j])j++;
num = max(num, j - i);
if (j == n)break;
}
cout << n - num << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
/* /\_/\
* (= ._.)
* / > \>
*/D：Genokraken
大意：
交互题，有一颗树，节点为0~n-1，砍下树根之后，剩下的就变成一条条链子了，并且一个节点父亲的编号是小于该节点编号的
1、去掉树根，同一路径上就没有兄弟了
2、p[i] < i
3、x < y,p[x] < p[y]
请还原这棵树
思路：
1、p[i] < i,我们可以按编号从小到大一个一个问，从树根开始不断还原这棵树：因为p[i] < i, 那么1节点的父节点就是0了；2节点呢？0或者1；3？0或1或2。。。
2、x < y,p[x] < p[y]
这棵树特征是这样的，每个节点要不就跟上一个编号的节点，父亲在相同层，父亲的编号小于上一个编号的父亲的编号（树根除外），要不就是上一个编号节点的儿子
那我们就先还原链子的头，找到树根的儿子，询问1和之后的编号，直到出现1的儿子，然后后面就依次找了，对于某个节点，一层一层地询问了相当于，直到找到父亲，然后继续往下问，将每个节点父亲全部问完，然后就输出答案
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int, int>>
#define ff first
#define ss second
// ++ ~! */+- <<>> <> == &^| &&|| =
int query(int a, int b) // 0父子，1不同链
{
cout << "? " << a << ' ' << b << endl;
cout.flush();
int x;
cin >> x;
return x;
}
void answer(const vi& v)
{
cout << "! ";
for (int i = 1; i < v.size(); i++)
{
cout << v[i] << ' ';
}
cout << endl;
cout.flush();
}
void solve()
{
int n;cin >> n;
vi p(n);
int i = 2, j = 2;
while (query(1, j))//先找直接跟根节点相连的
p[j ++] = 0;
p[j ++] = 1;
while (j < n) // j一个一个找父亲
{
while (query(i, j))i ++;
p[j ++] = i++;
}
answer(p);
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
/* /\_/\
* (= ._.)
* / > \>
*/