好久以前的了。
我的题是 10
10
两棵根为 1 的树，一次可以删一个点、把所有儿子连到它的父亲，问最少操作次数使两棵树一样，\(n\le40\)
03
对序列 \(a\)，定义一次变换为先让 \(\displaystyle s_k=\left(\sum_{i=k-\text{lowbit}(k)+1}^ka_i\right)\bmod 998\ 244\ 353\)，然后 \(a_i\gets s_i\)，问给出 \(k\) 次变换后的数组 \(b_i\)，让你输出一个可行的原数组 \(a_i\)，\(n\le2\cdot10^5,1\le k\le10^9,0\le b_i<998244353\).
04
给 \(n,m\)，求 \((a,b)\) 个数，其中 \(a\in[1..n],b\in[1..m]\)，且 \(b\cdot\gcd(a,b)\) 是 \(a+b\) 的倍数，\(n,m\le2\cdot10^6\).
05
二分图匹配，但是左边每个人连向的都是一段区间，\(\forall k\in[1..n_1]\)，输出从右边点选任意长度为 \(k\) 的区间和左边所有人做匹配，匹配数能达到 \(k\) 的区间的个数，\(n_1,n_2\le2\cdot10^5\).
06
三维空间的墙角平铺有 \(n\times m\) 的立方体，每个立方体有一个颜色，目标是通过添加立方体来使每个颜色的立方体集合形成一个连通块，\(n,m,k\le50\)，最多允许添加 \(4\cdot10^5\) 个立方体.
07
\(n(\le1000)\) 个数的回文数组 \(a(1\le a_i\le10^9)\)，现给出它 \(\frac{n(n+1)}2-1\) 个子区间和，问还原数组 \(a\).
Solution
10
记两棵树为 \(S,T\)
操作性质：祖先关系不变
启示：若 \(S\) 中 \(i\) 是 \(j\) 的祖先 而在 \(T\) 中 \(i\) 不是 \(j\) 的祖先，那 \(i,j\) 必不能同时存在
建一个图，边 \((i,j)\) 表示 \(i,j\) 的祖先关系在两棵树中相同，我们需要找到其中的最大完全子图（最大团）
这就有很多方法了，std是这样：
\(f(state)\) 表示从 \(state\) 里面选点，选出团的最大大小
记忆化搜索，设 \(v\) 为 \(state\) 里的第一个点：
- 选 \(v\)：把 \(state\) AND一下 \(v\) 的所有邻居（不含 \(v\)），再返回 \(f(state)+1\)
- 不选 \(v\)：把 \(state\) 里 \(v\) 这一位变成 \(0\)，再返回 \(f(state)\)
边界：\(f(0)=0\)；答案：\(f(2^n-1)\).
他证明了这个复杂度是 \(O(n\cdot2^{0.5n})\)，方法是分类讨论，但是我感觉不怎么对，反正 \(O(\)能过\()\).
03
Sol1：给的式子是个 \(\log\) 阶前缀和状物，所以最后每个位置必定是一个对 \(k\) 的 \(O(\log)\) 阶多项式，故暴力跑前 \(\log\) 次，然后对每个位置都插一遍就做完了，\(O(n\log n)\).
Sol2：由树状数组结构得 \(a_i\) 对 \(a_i\) 及它的祖先产生贡献，那设有两点 \(u,v\)，且 \(u\) 在 \(v\) 的上面 \(d\) 层，做了 \(k\) 次，考虑 \(v\) 对 \(u\) 贡献了多少次，发现相当于对 \(\{1,0,0,0,\ldots\}\) 做 \(k\) 次前缀和，答案为 \(C_{d+k-1}^{k-1}\).于是我们从叶子往上依次减贡献，\(O(n\log n)\).
Code
#include <bits/stdc++.h>
using namespace std;
const int p = 998244353;
int Qpow(int x, int y = p - 2) {
int res = 1;
for (; y; y >>= 1, x = 1ll * x * x % p) if (y & 1) res = 1ll * res * x % p;
return res;
}
int C(int n, int m) {
int P = 1, Q = 1;
for (int i = n; i >= n - m + 1; --i) P = 1ll * P * i % p;
for (int i = 1; i <= m; ++i) Q = 1ll * Q * i % p;
return (int)(1ll * P * Qpow(Q) % p);
}
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n + 1), fa(n + 1), du(n + 1, 0);
for (int i = 1; i <= n; ++i) cin >> a[i], fa[i] = i + (i & -i), (fa[i] > n) ? (fa[i] = 0) : (++du[fa[i]]);
queue<int> q;
for (int i = 1; i <= n; ++i) if (!du[i]) q.push(i);
while (!q.empty()) {
int u = q.front(), d = 1, v = u;
q.pop();
if (!--du[fa[u]]) q.push(fa[u]);
while (fa[u]) (a[fa[u]] -= 1ll * C(d + k - 1, d) * a[v] % p - p) %= p, u = fa[u], ++d;
}
for (int i = 1; i <= n; ++i) cout << a[i] << " \n"[i == n];
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int tt;
cin >> tt;
while (tt--) solve();
return 0;
}
04
- \(a=pg,b=qg,\gcd(p,q)=1,g=\gcd(a,b)\)
- \(b\cdot\gcd(a,b)=k(a+b)\)，即 \(kg(p+q)=qg^2\)，即 \(k(p+q)=gq\)
- \(\gcd(p+q,q)=1\)，故设 \(g=(p+q)r\)
- 条件转化为 \(a=p(p+q)r,b=q(p+q)r,\gcd(p,q)=1\)，发现 \(p\le\sqrt n,q\le\sqrt m\)
- 枚举 \(p,q\)，\((a,b)\) 的个数与 \(r\) 无关，\(O(\sqrt{nm})=O(n)\)，因为 \(n,m\) 同阶.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
ll ans = 0;
int n, m;
cin >> n >> m;
for (int p = 1; p * p <= n; ++p)
for (int q = 1; q * q <= m; ++q) {
int a = p * (p + q), b = q * (p + q);
if (gcd(p, q) == 1 && a <= n && b <= m)
ans += min(n / a, m / b);
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int tt;
cin >> tt;
while (tt--) solve();
return 0;
}
05
前置知识：Hall 定理
判断右边点单个区间 \([l,r]\)，考虑 Hall 定理，设 \(N(S)\) 为右边点 \(S\) 对应的左边点集大小，\(S\) 合法当且仅当 \(|N(S)|\ge|S|\)，那么 \([l,r]\) 合法当且仅当 \(\forall S\subseteq[l,r],S\) 合法.
猜测只用判断成一段区间的 \(S\)，但是会被以下数据叉掉：
3
1 3
2 2
2 2
对于 \([1,3]\)，只有 \(\{1,3\}\) 不合法.
于是考虑处理初始的左边点的线段，发现对于 \([a,b],[a,c](b\le c)\)，把他们换成 \([a,b],[a+1,c]\) 不影响结果（\(a=b=c\) 时相当于删掉这条线段），因为对于 \(a\) 点，为了最优，他一定会选 \([a,b]\) 而非 \([a,c]\).
处理后每个人的左端点互不相同，此时找性质，发现：
- 可以只判成一段区间的 \(S\)，因为若一个不合法的 \(S\) 不是一段连续的区间，考虑将其补全成一段区间，此时他还是不合法，因为每补全一个数，\(|N(S)|\) 至多增加 \(1\)，此时有只包含这个数的区间.
- 看单调性，发现若 \([l,r]\) 不合法，\([l,r+1],[l-1,r]\) 也不合法，因为 \([l,r]\) 合法当且仅当 \(\forall S\subseteq[l,r],S\) 合法.
于是可以双指针求，对每个 \(l\) 最大的 \(r\) 使 \([l,r]\) 合法，最后差分统计即可.
Code
// by:Joey_c / sto hunction orz
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define reo(i,j,k) for(int i=j;i>=k;i--)
#define debug fprintf(stderr,"Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fi first
#define se second
#define pb emplace_back
#define mp make_pair
typedef long long ll;
constexpr int N=2e5+10;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n,m=0,nn;cin>>n,nn=n;vector<pair<int,int>>a(n+1);vector<int>buc[N];rep(i,1,n)cin>>a[i].fi>>a[i].se,m=max(m,a[i].se),buc[a[i].fi].pb(a[i].se);
n=0;priority_queue<int,vector<int>,greater<int>>q;
rep(i,1,m){
for(int j:buc[i])q.push(j);while(!q.empty()&&q.top()<i)q.pop();if(!q.empty())a[++n]=mp(i,q.top()),q.pop();
}
vector<int>b(m+2,0),c(m+2,0),ans(max(m,nn)+2,0);rep(i,1,n)b[a[i].fi]=1,++c[a[i].se];
for(int s=0,l=m,r=m;l;--l){
s+=c[l];while(r>=l&&s<r-l+1)s-=b[r--];if(r<=m)++ans[r-l+1];
}reo(i,max(m,nn),1)ans[i]+=ans[i+1];rep(i,1,nn)cout<<ans[i]<<"\n";
return 0;
}
06
思路：每次我们只关心最上层的方块，先让每列之间都隔出一列空列，然后一层一层的使每个颜色连通.
题解，自己粗略算了一发，377500，足以通过.
07
记区间和数组为 \(s_i\)，考虑如果知道所有区间和怎么做：
- 做法一：考虑出现奇数次的 \(s_i\)，一定是跨过中点且两边长度相等的，那我们把它们排序，设序列中点为 \(i,j(i\le j)\)，我们得到 \([i,j],[i-1,j+1],[i-2,j+2],\ldots,[1,n]\) 的和，差分后可以还原数组 \(a\).
- 做法二：考虑 \(s_i\) 的最大值和次大值，一定是 \([1,n],[1,n-1]\)，那我们可以得到 \(a_1,a_n\)，进而得到 \([2,n-1]\) 的和；将 \([1,n],[1,n-1],[2,n-1]\) 从集合里删去后，最大值一定是 \([1,n-2]\)，那我们可以推出 \(a_2,a_{n-1}\)，进而得到 \([1,n-2],[2,n-2],[3,n-2]\) 的和。注意到所有可能大于 \([1,n-3]\) 的区间和我们都知道，那把它们全都删掉后最大值即为 \([1,n-3]\)，依次推下去可以还原数组 \(a\).
现在考虑有一个元素缺失怎么做： - \(s_i\) 最大值出现 2 次：即缺失的是 \([1,n]\)，我们采用做法一，可以得到 \(a_2,a_3,\ldots,a_{n-1}\)，由于此时最大值为 \([1,n-1]\)，也容易得到 \(a_1,a_n\).
- \(s_i\) 最大值出现 1 次：直接采用做法二，只要 \([1,n]\) 不缺失就不影响做法二.
时间：\(O(n^2\log n)\).