T1 莓良心
又是这毛病，场上怎么也想不到正解，然后看了题解恍然大悟。还是太菜。🐷
大概就是，贪心地，找到所有区间最小的 \(L\) 和最大的 \(R\)，那么所有的点都可以被放置到 \(L\) 和 \(R\) 这两个点上。
那就好办了，将所有的 \(l\) 和 \(r\) 排序后讨论，分两种情况讨论：
- 如果 \(L\le R\)，那么所有的点都可以被放到这段区间里，那么答案就全为 \(0\)。直接 break。
- 如果 \(R < L\)，那么它们之间的点的数量为 \(n-i - i\)，这些点的贡献为 \((n-2i)(L-R)\)，再加上这个区间自己的那一对点即可。所以贡献是 \((L-R)(n-2i+1)\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 3e5 + 5;
int n, L[N], R[N], ans;
int main(){freopen("case.in", "r", stdin); freopen("case.out", "w", stdout);ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n; for(int i=1; i<=n; ++i) cin>>L[i]>>R[i];sort(L+1, L+1+n, [](const int x, const int y){ return x > y; });sort(R+1, R+1+n, [](const int x, const int y){ return x < y; });for(int i=1; i<=n; ++i){if(L[i] <= R[i]) break;ans += (L[i] - R[i]) * (n - (i<<1) + 1);} return cout<<ans, 0;
}
T2 尽梨了
很巧妙的大思维题。可我没有思维。
题目很屎，翻译过来就是让你构造两个零一串，分别满足 \(a_i\) 或者 \(b_j\) 等于 \(c_{i,j}\)。
假设第 \(i\) 行为 \(00110\)，如果序列 \(b=00101\) 那么无解，如果序列 \(b=00100\) 那么 \(a_i=1\)，如果序列为 \(b=11111\) 那么 \(a=0\)。综上，只要 \(b\) 中有足够的 \(1\)，那么这些 \(1\) 都必须要踩在序列的 \(1\) 。设这一行的 \(1\) 的数量为 \(tot\), \(b\) 中 \(1\) 的数量为 \(cnt\)。那么有：
- \(cnt<tot\)：\(a_i=1\)
- \(cnt>tot\): \(a_i=0\)
- \(cnt=tot\)：\(a_i=?\)
考虑枚举 \(b\) 中 \(1\) 的数量，然后遍历每一行。如果有 \(cnt=tot\)，那么这些行的 \(a_i\) 是不确定的，可以发现的是，如果这些行不是完全一样的话，那么无解。所以答案 \(*2^{行数}\)。我们记 \(le\) 为小于等于 \(cnt\) 的行的并，\(qe\) 为大于等于 \(cnt\) 的行的并。那么 \(le\) 中的 \(1\) 是 必须被放的，\(qe\) 中的 \(1\) 是 可以被放置的。考虑到 \(b\) 一共有 \(i\) 个 \(1\)，那么还剩下 \(i-cnt_{le}\) 个 \(1\) 可以瞎放，而瞎放的位置还剩下 \(cnt_{qe}-cnt_{le}\) 个，贡献即为 答案 \(*\dbinom{cnt_{qe}-cnt_{le}}{i-cnt_{le}}\)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int N = 5e3 + 5, M = 998244353;
int n, fac[N], inv[N];
inline int qpow(int a, int k){int ans = 1; while(k){if(k & 1) ans = (ll)ans * a % M;a = (ll)a * a % M; k >>= 1;} return ans;
}
inline void init(){fac[0] = 1; for(int i=1; i<=n; ++i) fac[i] = (ll)fac[i-1] * i % M;inv[n] = qpow(fac[n], M-2); for(int i=n-1; i>=0; --i) inv[i] = (ll)inv[i+1] * (i+1) % M;
}
inline int C(int a, int b){if(a < 0 || b < 0 || a < b) return 0;return (ll)fac[a] * inv[b] % M * inv[a-b] % M;
}
bitset<N> mp[N], le[N], qe[N];
vector<int> tot[N];
int ans;
int main(){freopen("de.in", "r", stdin); freopen("de.out", "w", stdout);ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n; init(); for(int i=1; i<=n; ++i){cin>>mp[i]; mp[i] <<= 1;tot[mp[i].count()].push_back(i);}for(int i=1; i<=n; ++i){le[i] = le[i-1];for(int j : tot[i]) le[i] |= mp[j];}for(int i=1; i<=n; ++i) qe[n+1][i] = 1;for(int i=n; i>=1; --i){qe[i] = qe[i+1];for(int j : tot[i]) qe[i] &= mp[j];}for(int i=0; i<=n; ++i){if((le[i] & qe[i]) == le[i]){int cnt1 = le[i].count(), cnt2 = qe[i].count();ans = ((ll)ans + (ll)qpow(2, tot[i].size()) * C(cnt2-cnt1, i-cnt1) % M) % M;}} return cout<<ans, 0;
}
T3 团不过
实力不行，还去拼尽全力求解容斥……
据说容斥可做，但已经不是我力所能及的范围了。而且 DP 可以高效地将大容斥划分成小情况考虑，大大减轻思维难度。
令 \(g[i]\) 表示有 \(i\) 堆石子时的总方案数，\(f[i]\) 表示这 \(i\) 堆石子异或和不为零且互不相同的方案数。那么答案即为 \(g[n] - f[n]\)。
考虑递推转移。\(g[i]\) 即为全排列，所以 \(g[i]=g[i-1]*(tot-1)\)。\(tot=2^n\)。\(f[i]\) 既要保证异或和为零，又要保证相等，所以 \(f[i]=g[i-1]-f[i-1]-(tot-i+1)*(i+1)*f[i-2]\)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int N = 1e7 + 5, M = 1e9 + 7;
int n, tot, f[N], g[N];
inline int qpow(int a, int k){int ans = 1; while(k){if(k & 1) ans = (ll)ans * a % M;a = (ll)a * a % M; k >>= 1;} return ans;
}
int main(){freopen("yui.in", "r", stdin); freopen("yui.out", "w", stdout);scanf("%d", &n); tot = qpow(2, n); g[1] = tot - 1, f[1] = 0; g[0] = f[0] = 1;for(int i=2; i<=n; ++i){g[i] = ((ll)g[i-1] * (tot - i) % M + M) % M;f[i] = (((ll)g[i-1] - (ll)f[i-1] - (ll)(tot-i+1) * (i-1) % M * f[i-2] % M) % M + M) % M;} printf("%d", ((g[n] - f[n]) % M + M) % M);
}
T4 七负我
最大团即为最优答案。证明很好证，使用基本不等式即可。
#include<bits/stdc++.h>
using namespace std;
int n, x, m, mnt;
bitset<45> G[45], R[45], P[45], X[45];
inline void Bron_Kerbosch(int d){if(P[d].none() && X[d].none()) return void(mnt = max(mnt, (int)R[d].count()));int bg = P[d]._Find_first();for(int i=P[d]._Find_first(); i<=n; i=P[d]._Find_next(i)){if(G[bg][i]) continue;R[d+1] = R[d], P[d+1] = P[d], X[d+1] = X[d];R[d+1][i] = 1, P[d+1] &= G[i], X[d+1] &= G[i];Bron_Kerbosch(d+1);P[d][i] = 0, X[d][i] = 1;}
}
int main(){freopen("nanami.in", "r", stdin); freopen("nanami.out", "w", stdout);ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n>>m>>x;for(int i=1, u, v; i<=m; ++i)cin>>u>>v, G[u][v] = G[v][u] = 1;for(int i=1; i<=n; ++i) P[0][i] = 1;Bron_Kerbosch(0);double ans = (1.0 - 1.0 / mnt) / 2 * x * x;cout<<fixed<<setprecision(6)<<ans;
}
