AC题目列表
- C. Brave Seekers of Unicorns
- D. Bank Security Unification
- G. Biological Software Utilities
- I. Binary Supersonic Utahraptors
- J. Burnished Security Updates
- M. Brilliant Sequence of Umbrellas
- N. Best Solution Unknown
C. Brave Seekers of Unicorns
题目给出了一个$unicorn$序列的定义，暂且叫它完美序列，完美序列满足如下条件：- 非空递增且序列元素的值域为 \([1,n]\)
- 没有三个连续的元素异或和 \(=0\)
给定 一个整数n，对完美序列计数（需要求出完美序列个数），答案需要对 \(998244353\) 取模
Solution
设 $dp_i$ 表示以$i$ 结尾的数组的方案数即 \[dp[i]= \sum\limits_{j=1}^{i-1} (dp[j]-dp[i \bigoplus j]) (i⨁j<j) \]求出等于 \(i\oplus j\) 的数去掉同时维护前缀和，对于二进制下的 \(i\) ,如果第 \(x\) 位为 \(1\)，那么$ [2x,2{x+1}-1]$之间的数都是(除了最高位的\(1\)除外)，解释来说，因为要考虑$i⊕j⊕k=0 \(的情况，根据异或的性质\)i,j,k$三个数的每一个二进制数位上最多只有两个\(1\)，那就枚举\(i\)的除最高位的二进制位为\(1\) 的数位 \(x\)，固定 \(j\) 的第\(x\)位是也是\(1\),此时\(k\) 的第 $x $位为必然为\(0\)，那么第\(x\) 位往后都可以随便乱取,不会有影响,也就是\(k\)的范围是\([2^x,2^{x+1}-1]\)
Code
ll dp[N],f[N],n;
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i) {
f[i] = dp[i - 1] + 1;
int num = i, bit = 0;
while (num) {
if ((num & 1) && num != 1) {//此时i的位上是1
f[i] = (f[i] - dp[min(ksm(2, bit + 1) - 1, (ll) i)] + dp[min(ksm(2, bit) - 1, (ll) i)] + mod) % mod;
}
num >>= 1;
bit++;
}
dp[i] = (dp[i - 1] + f[i]) % mod;
}
cout << dp[n] << endl;
}
D. Bank Security Unification
题意：有 $n$个路由器，第 $i$ 个路由器的的频度是 $f_i$, 你选择任意个路由器打开，假设打开$k$了个路由器 $i_1 , i_2 , … , i_ k$, ，则此时的网络安全系数的值是 $∑ _{i=1}^{k-1}a_i\oplus a_{i+1}$ ,输出网络安全系数的最大值是多少，反之就是说从一个长度为 $n$ 序列 $a$ 中取出一个子序列，使得相邻两个元素的按位与值的和最大。求出这个最大的和Solution
首先我们希望按位与和最大，就是在希望我们选取的相邻两个元素的二进制位尽可能相同，显然$dp[i][j]$表示当前在$i$位置 ，打开$j$ 个路由器的最大按位与值（安全系数），但是此时暴力转移的$dp$是$O(n^2)$ 的，而且$n=1e6$显然也开不了二维的$dp$数组，那么可以选择优化，让$dp_i$表示当前最后一位为 $i$ 的子序列答案最大是多少，如果考虑当前的一位，显然是与之二进制相同的位是贡献最大的，所以记录 $lst[i][0/1] $表示二进制第 $i$ 位上一个是$ 0/1$ 最近的位置在哪里，每次只从对应的$lst$ 转移而来,然后每次取更新$lst$的值Code
ll n;
ll f[N],dp[N],bit[66][2];
void solve() {
cin >> n;
ll mx_bit = 0;
for (int i = 1; i <= n; ++i) {
cin >> f[i];
mx_bit = max(mx_bit, f[i]);
}
mx_bit = ceil(log2(mx_bit)) + 1;
// dbg(mx_bit);
for (int i = 1; i <= n; ++i) {//贪心取最近的相同的二进制位
if (i > 1) {
for (int j = 0; j<=mx_bit; ++j) {
int tmp = ((f[i] & (1ll << j)) > 0);
int pos = bit[j][tmp];//最近的每位二进制&相同的位置
dp[i] = max(dp[i], dp[pos] + (f[pos] & f[i]));
}
}
// dbg(dp[i]);
for (int j = 0; j <= mx_bit; ++j) {//更新
bit[j][((f[i] & (1ll << j)) > 0)] = i;
}
}
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans = max(ans, dp[i]);
}
cout << ans << endl;
}
G. Biological Software Utilities
给出一种好树的定义，删除掉一些边后能变成两两匹配的树是好树。现在给出节点的个数，求好树有多少种Solution
考虑到树的形状没有定，且也不知道删除哪一些点，但是发现最后的情况一定是两两匹配的，那么倒过来想就是把很多两两匹配完的点，通过连一些边变成一些树。首先把 $2n$ 个点分成 $n$ 个两两相同的组合的总共情况是 \[\frac{(2n)!}{n!*2^n} = \frac{\begin{pmatrix} 2n\\n\end{pmatrix} * n!}{2^n} \]然后每个组合其实可以看成是一个点，然后有一个重要的结论，\(n\) 个点的生成树个数为 \(n^{n-2}\) 个。然后由于每个最后连的边，具体到这道题里都是四条，所以最后还要乘上 \(4^{n - 2}\)
所以最后的公式就是
\[\frac{\begin{pmatrix} 2n\\n\end{pmatrix}*n!}{2^n}*4^{n-1}*n^{n-2} \]Code
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << '\n';
using namespace std;
typedef long long ll;
#define int ll
const int inf = 0x3f3f3f3f;
const ll mod = 998244353;
const int N = 1e6 + 10;
int fac[N], inv[N];
ll ksm(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
ll c(ll k, ll n) {
return fac[n] % mod * inv[k] % mod * inv[n - k] % mod;
}
void solve() {
int n;
cin >> n;
if (n & 1) {
cout << 0 << '\n';
return;
}
if (n == 2) {
cout << 1 << '\n';
return;
}
int k = n / 2;
ll ans = c(k, n) * fac[k] % mod;
for (int i = 1; i <= k; ++i) {
ans = ans * ksm(2, mod - 2) % mod;
}
for (int i = 1; i <= k - 1; ++i) {
ans = ans * 4 % mod;
}
cout << ans * ksm(k, k - 2) % mod << '\n';
}
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
int t = 1;
// cin >> t;
fac[0] = inv[0] = 1;
for (int i = 1; i <= 1e6; ++i) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = ksm(fac[i], mod - 2) % mod;
}
while(t--) {
solve();
}
return 0;
}
I. Binary Supersonic Utahraptors
题意：略Solution
答案恒定不变，签到题Code
int n,m,k;
void solve() {
int cnt_y=0,cnt_r=0;
cin>>n>>m>>k;
for(int i=1,x;i<=n;++i){
cin>>x;
cnt_y+=(x==0);
}
for(int i=1,x;i<=m;++i){
cin>>x;
cnt_r+=(x>0);
}
cout<<abs(cnt_y-cnt_r)<<endl; }="" <p="">J. Burnished Security Updates
题意：略Solution
考虑二分图染色（签到题）Code
const int maxn = 3e5 + 100, mod = 1e9 + 7;
int n, m, cnt, sz, col[maxn], ok = 1;
vector e[maxn];
void dfs(int u, int fa, int co) {
col[u] = co;
if (co == 1) cnt++;
sz++;
for (int v: e[u]) {
if (v == fa) continue;
if (col[v] == col[u]) {
ok = 0;
return;
}
if (!col[v]) dfs(v, u, -co);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (!col[i]) {
cnt = sz = 0;
dfs(i, 0, 1);
if (!ok) {
cout << -1;
return 0;
}
ans += min(sz - cnt, cnt);
}
}
cout << ans;
}
M. Brilliant Sequence of Umbrellas
构造一个长度至少为 $\left \lceil \frac{2}{3}\sqrt{n} \right \rceil $ 的递增数组，使得两两做 $gcd$ 也是递增的。Solution
由于 $gcd$ 的数组也是递增的，那么要让数组尽可能的长，就要让 $gcd$ 增长的尽可能慢。通过打表前面几个数
\[1 \ 2 \ 6 \ 15 \ 35 \ 56 \ 72 \ 99 \\ gcd数组:2 \ 3 \ 5 \ 7 \ 8 \ 9 \ 11 \]可以发现 \(gcd\) 数组要添加的数，应当是与最后一个和倒数第二个都互质的数，然后原数组就是 \(gcd\) 数组相乘回去
Code
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
vector a{1, 2, 6}, g{1, 2, 3};
void solve() {
ll n;
cin >> n;
ll k = ceil(2 * sqrt(n) * 1.0 / 3);
int cnt = 0;
for (int i = 0; i < a.size(); ++i) {
if (a[i] <= n) cnt++;
if (cnt >= k) break;
}
if (cnt >= k) {
cout << k << '\n';
for (int i = 0; i < k; ++i) {
cout << a[i] << " \n"[i == k - 1];
}
} else {
cout << "-1\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
for (int i = 4; i <= 1e6; ++i) {
if (__gcd(g.back(), i) == 1 $&&$ __gcd(g[g.size() - 2], i) == 1) {
if (g.back() * i <= 1e12) a.push_back(g.back() * i), g.push_back(i);
else break;
}
}
while (t--) {
solve();
}
return 0;
}
N. Best Solution Unknown
有 \(n\) 个人打比赛，每个人有个实力值，实力值大的会打败实力值小的，相等的都有机会赢。
打赢一个人可以增加$1$的实力值，每个人只能和相邻的人打。
每次随机取比赛，求会有哪些人可能赢
Solution
队友：线段树+分治Code
#define x first
#define ls (id << 1)
#define rs (id << 1 | 1)
#define mid (l + r >> 1)
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
const int maxn = 1e6 + 100, maxm = 3e5 + 100, inf = 0x3f3f3f3f, mod = 1e9 + 7;
int n, a[maxn];
vector ans;
struct SegTree {
int maxx[maxn * 4];
void build(int id, int l, int r) {
if (l == r) {
maxx[id] = l;
} else {
build(ls, l, mid);
build(rs, mid + 1, r);
if (a[maxx[ls]] > a[maxx[rs]])
maxx[id] = maxx[ls];
else
maxx[id] = maxx[rs];
}
}
int query(int id, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r) return maxx[id];
if (qr <= mid)
return query(ls, l, mid, ql, qr);
else if (ql > mid)
return query(rs, mid + 1, r, ql, qr);
else {
int res1 = query(ls, l, mid, ql, mid);
int res2 = query(rs, mid + 1, r, mid + 1, qr);
if (a[res1] > a[res2]) return res1;
else return res2;
}
}
}tr;
void solve(int l, int r, int maxx) {
int pos = tr.query(1, 1, n, l, r);
if (a[pos] + r - l < maxx) return;
ans.push_back(pos);
if (l <= pos - 1) solve(l, pos - 1, max(a[pos], maxx + pos - 1 - r));
if (pos + 1 <= r) solve(pos + 1, r, max(a[pos], maxx + l - pos - 1));
}
signed main() {
ios;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
tr.build(1, 1, n);
solve(1, n, 0);
cout << ans.size() << endl;
sort(ans.begin(), ans.end());
for (int i: ans) cout << i << " ";
}