A - Non-Adjacent Flip
这道题有点思维题的意思
首先单数肯定不行
如果是大于4的偶数那么肯定都可以（这点也要想明白）
因为1111的话，1和3配，2和4配，怎样都能配好的
接下来讨论下剩下的情况
n=3的时候，只要中间不是1都可以
其他时候我们只要把下标存起来，稍微判断就可以
代码如下
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
const int N=1e6+10; void solve(){int n;cin >> n;string s;cin >> s;int cnt = count(s.begin(), s.end(), '1');if (cnt % 2 == 1) {cout << -1 << "\n";return;}if (cnt == 0) {cout << 0 << "\n";return;}if (cnt >= 4) {cout << cnt / 2 << "\n";return;}if (n == 3) {if (s[1] == '1') {cout << -1 << "\n";} else {cout << 1 << "\n";}return;}vector<int> pos;for (int i = 0; i < n; i++) {if (s[i] == '1') {pos.push_back(i);}}if (pos[1] - pos[0] > 1) {cout << 1 << "\n";return;}if (n == 4 && pos[0] == 1) {cout << 3 << "\n";} else {cout << 2 << "\n";}
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);int T;cin>>T;while(T--){solve();}
}B - Mex on Blackboard
给定N个元素的数组A，每次操作，你可以从数组种选出任意个元素，然后向数组中加入这些
元素的MEX
问k次之后九二一得到多少种不同的数组
枚举写上去的最大数x，计算写上这个数字至少需要几次有贡献的操作，对剩下的操作数求组合数
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
const int N=1e6+10;
int n, k;
int a[N];
int cnt[N];
const int mod = 998244353;
int qpow(int a, int b){int ans = 1;while(b){if(b & 1){ans *= a;ans %= mod;}a *= a;a %= mod;b /= 2;}return ans;
}
int fc[N];
int gc[N];
void prep(){fc[0] = gc[0] = 1;for(int i=1;i<N;i++){fc[i] = (fc[i - 1] * i) % mod;gc[i] = qpow(fc[i], mod - 2);}
}int C(int n, int k){int ans = fc[n];ans *= gc[k];ans %= mod;ans *= gc[n - k];ans %= mod;return ans;
}void solve(){cin >> n >> k;for(int i=1;i<=n;i++){cin >> a[i];cnt[a[i]]++;}vector<int> holes;for(int i=0;i<N;i++){if(!cnt[i]) holes.pb(i);}prep();int ans = 0;if(holes[0] != 0){ans += C(holes[0] + k - 1, holes[0] - 1);ans %= mod;}for(int i=0;i<k;i++){int nxt = holes[i + 1];ans += C(nxt + (k - (i + 1)) - 1, nxt - 1);ans %= mod;}cout << ans << "\n";
}
signed main(){solve();
}
C - Tree and LCS
给定一棵N个节点的树T，编号为1-N，定义排列P与T的相似度为
对于T一个不重复路径（x1,x2,x3,,,,xn）,路径相似度为（x1,x2....xn）与(Px1,Px2,Px3,,,,Pxn)的最长公共子序列长度
P与T的相似度为T中所有路径相似度的最大值
请构造一个排列P，使其与T相似度最小
构造题，两T在BFS序上的相邻节点，即可将相似度锁定为 1 。
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair<int,int>
#define et cout<<'\n'
#define xx first
#define yy second
using namespace std;
const int N = 5005;
int n, d[N], p[N], que[N], l, r;
vector<int> e[N];
signed main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n;for (int i = 1; i < n; ++i) {int u, v;cin >> u >> v;e[u].push_back(v);e[v].push_back(u);++d[u], ++d[v];}l = 1;for (int i = 1; i <= n; ++i)if (d[i] == 1) que[++r] = i;while (l <= r) {int u = que[l++];for (auto v : e[u]) {if (d[v] > 1 && --d[v] == 1) {que[++r] = v;}}}iota(p + 1, p + n + 1, 1);for (int i = 1; i < n; i += 2)swap(p[que[i]], p[que[i + 1]]);for (int i = 1; i <= n; ++i) cout << p[i] << " \n"[i == n];return 0;
}
