做题记录 2

F. Shift and Revers

题意

给定 \(a_i\) ,操作有让 \(a_n\) 移到第一位和翻转整个序列，问最小操作数使得 \(a_i\) 从小到大排序。

做法

（不）容易发现可以正反都做一次取 min。

P6617 查找 Search

一道有点折磨的分讨题 理不清思路容易WA

给定 \(n\) 个垃圾桶，你需要维护一个数据结构，支持以下操作：

• 1 pos val 表示将 第 \(pos\) 个垃圾桶里的垃圾的编号换成 \(val\)；
• 2 l r 询问在 \([l\oplus cnt, r\oplus cnt]\) 内是否存在垃圾编号和为 \(w\) 的 两个 垃圾桶。

没有修改显然可以设 \(nxt_i\) 表示 \(i\) 后最近的 \(w-a_i\) 位置，区间求 \(nxt_i\) 的最大值判断是否 \(\le r\)

有修改的话会寄，因为每次修改是 O(N) 的。

不过 我们可以考虑发现只用极小的有用点对 \((i,nxt_i)\) ，其中不能包含其他点对，这样每个点只对应 \(O(1)\) 个点，可以进行修改。

修改需要分类一下，找到所有有影响的点。

最后代码比较优美：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define adde(a,b) v[a].push_back(b)
#define addev(a,b,c) v[a].push_back({b,c});
#define rd read
#define all(a) a.begin(),a.end()
#define mem(a,b) memset(a,b,sizeof a);
#define pb push_back
#define vct vector
#define rev(T) reverse(T.begin(),T.end())int read()
{int f=1,k=0;char c = getchar();while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();return k*f;
}const int N = 5e5+5;int n,m,w,a[N];int ne[N];int mn[N<<2];
void pup(int k)
{mn[k] = min(mn[k<<1],mn[k<<1|1]);
}
void mdf(int k,int l,int r,int x,int v)
{if (x > r || x < l) return;if (l == r){mn[k] = v;return;}int mid = l + r >> 1;mdf(k<<1,l,mid,x,v);mdf(k<<1|1,mid+1,r,x,v);pup(k);
}int query(int k,int l,int r,int x,int y)
{if (x > r || y < l) return INF;if (x <= l && r <= y) return mn[k];int mid = l + r >> 1;return min(query(k<<1,l,mid,x,y),query(k<<1|1,mid+1,r,x,y));
}
set<int> s[N];
int findpre(int x)
{if (x == 0) return 0;int v = w-a[x];if ((int)s[v].size() == 0) return 0;auto it = s[v].lower_bound(x);if (it == s[v].begin()) return 0;it--;if ((*it)<x)return (*it);return 0;
}
int findnxt(int x)
{if (x== 0) return 0;int v = w-a[x];auto it = s[v].upper_bound(x);if (it != s[v].end() && (*it)>x) return (*it);return 0;
}bool pd(int a,int b)
{if (!a || !b) return 0;if (findnxt(a) == b && findpre(b) == a) return 1;return 0;
}void change(int x)
{int nt = findnxt(x);if (pd(x,nt))mdf(1,1,n,x,nt);else mdf(1,1,n,x,INF);
}void solvemain()
{cin >> n >> m >> w ;rep(i,1,n) a[i] =rd(),s[a[i]].insert(i);mem(ne,INF);for (int i= 1;i <= n;i++ ){ne[i] = findnxt(i);if (findpre(ne[i]) == i);else ne[i] = INF;mdf(1,1,n,i,ne[i]);}int cnt = 0;rep(i,1,m){int op =rd(),x =rd(),y =rd();if (op == 1){if (a[x] == y) continue;int prewx = findpre(x);int prex = 0;if (s[a[x]].lower_bound(x) != s[a[x]].begin())prex = *(prev(s[a[x]].lower_bound(x)));s[a[x]].erase(x);a[x] = y;s[a[x]].insert(x);int nowprex = 0,nowprewx = findpre(x);if (s[a[x]].lower_bound(x) != s[a[x]].begin())nowprex = *(prev(s[a[x]].lower_bound(x)));change(x),change(prex);change(nowprex);change(nowprewx);change(prewx);}	else{x^=cnt;y^=cnt;if (query(1,1,n,x,y) <= y) puts("Yes"),cnt++;else puts("No");}}}signed main()
{int t;t = 1;while(t--){solvemain();}return 0;
}

https://www.luogu.com.cn/problem/CF1237F

CF1237F Balanced Domino Placements

题目描述

给定一个 \(h\) 行 \(w\) 列的方格棋盘，上面已经放置了一些多米诺骨牌。每个多米诺骨牌恰好覆盖棋盘上相邻的两个格子，每个格子最多只能被一个多米诺骨牌覆盖。

我们称一个多米诺骨牌的放置方式为“完全平衡”，如果没有任何一行或一列中存在被两个不同多米诺骨牌覆盖的两个格子。换句话说，每一行和每一列要么没有被覆盖的格子，要么只有一个被覆盖的格子，要么有两个被覆盖的格子且这两个格子属于同一个多米诺骨牌。

现在给定一个已经完全平衡的多米诺骨牌放置方式，问有多少种方法可以在此基础上再放置零个或多个多米诺骨牌，且仍然保持完全平衡。请输出方案数对 \(998\,244\,353\) 取模的结果。

当前的网格中有部分行部分列被叉掉，问还能放骨牌的方案数。

直接思考，先放竖着的再放横着的，发现竖着的骨牌会叉掉两行一列

对于横着的产生影响，互不独立，不方便计算。

简化问题，考虑只有竖着的。

变成了有若干固定行不可选，一次得选两行的方案数，dp。\(f_{i,j}\) 表示前 \(i\) 行选 \(j\) 次的方案数。

当然此时这些选出来的骨牌的列是错开的而且不固定。

算方案数我们只需要在剩下没有被叉的列中选出 \(j\) 列即可

因此最终为 \(f_{n,j} \times A_{cnth}^{j}\)

同理我们也可以计算出 \(g_{m,i}\) 表示只考虑横着的。

此时似乎横竖会互相影响，我们这样想：

不具体考虑每一个骨牌的具体位置，而是考虑使他们错开，互不影响。

比如说假设有 \(i\) 个竖着的，\(j\) 个横着的。\(cnt_x \ cnt_y\) 分别是没有被叉的行和列的数量

\(f_{n,i}\) 算出了 \(n\) 行选出 \(i\) 张骨牌的方案数，

考虑这 \(i\) 张骨牌能放在哪 \(i\) 列里？

可以在 \(cnt_x - 2\times j\) 个列中选择，因为一张横着的会叉掉两列。

乘法原理乘上 \(A_{cntx-2\times j}^{i}\)

此时还有一点问题。

横着的同时会叉掉一行，因此横着的也只能在 \(cnt_y - 2\times i\) 行中选择

再乘上 \(g_{m,j} \times A_{cnt_y-2\times i}^{j}\)

得到最终答案。

Game on Tree

链接

给定一棵以1为根的树，一开始全为白点

每次随机一个白点 将其与其子树染黑

问操作次数期望

做法

根据期望线性性，可以考虑每个点的贡献

则转化为 \(\sum_{x}p_x\)

\(p_x\) 是 \(x\) 点被选进操作序列的概率

x点能否选入关键在于其到根的路径是否比 x 更早选入 由于选入概率相等

所以 \(p_x = 1/dep_x\)

期望线性性的另一题

扑克牌 52 张，问抽10张牌 A 的期望个数。(A有4张)

ans：\(\frac{10}{13}\)

OOOOOOOOOO

假设这是十张牌 目前花色未知

对于每一张牌考虑 他是A的概率就为\(\frac{1}{13}\)

根据期望线性性可得答案

G - sqrt(n²+n+X)

https://atcoder.jp/contests/abc420/tasks/abc420_g

唐题

题意

找出所有使 \(\displaystyle \sqrt{n^2+n+X}\) 为整数的整数 \(n\) 。

做法

主要想法有去拆某个东西的因子做到根号或者是枚举某个东西去求 \(n\)

\[\sqrt{n^2 + n + X} = A \]

\[n ^ 2 + n + X = A ^ 2 \]

\[n ^ 2 + n + \frac{1}{4} +X - \frac{1}{4} = A ^ 2 \]

\[X - \frac{1}{4} = A^2 - (n-\frac{1}{2})^2 \]

就变成平方差然后找因子就做完了。

或者：

\[n^2 + n + X = A ^2 \\ n +X = (A-n)(A + n) \\ n + X = B(B + 2n) \\ n + X = B^2 + 2nB \\ n = \frac{X-B^2}{2B-1} \]

容易发现 \(B\) 的范围并不大，大约是 \(O(\sqrt n)\)，暴力求解。

F - kirinuki

https://atcoder.jp/contests/abc420/tasks/abc420_f

问题陈述

给一个 01矩阵，问有多少相连子矩阵面积 \(\le k\) 且均为 \(0\)。

做法

这种子矩形问题考虑扫描线。

用一条竖线从左到右扫，显然需要维护能向左边延伸的距离。

即为 \(a_i\)

问题转化为

\[\sum_{i=1}^{n} \sum_{j=1}^{n} min(\left \lfloor \frac{k}{r-l+1} \right \rfloor ,min(a[l,l+1,\cdots,r])) \\ \]

容易想到单调栈建出笛卡尔树。

设最小值为 \(x\)，区间为 \([l,r]\)

场上想到这一步就不会了。

实际上我们可以继续推式子。

发现式子只跟区间长度相关，于是

\[\sum_{len} min(\left \lfloor \frac{k}{len} \right \rfloor ,x) \times c_{len} \]

\(c_{len}\) 表示长为 \(len\) 的区间个数

考虑 \(c_{len}\) 的形态。

笛卡尔树经典结论

经典结论是它应该为 \(1,2,3,4,\cdots,x,x,\cdots,x,x-1,x-2,\cdots,3,2,1\)

分讨一下。

1. \(\left \lfloor \frac{k}{len} \right \rfloor \le x\)

   \[\sum_{len \ge b} \left \lfloor \frac{k}{len} \right \rfloor \times c_{len} \]

   发现式子很整除分块，不过很爆，因为是 \(O(\sqrt k)\) 的。

   但是因为 \(k\) 是固定的于是我们可以通过一些预处理做到 O(1)。

2. 反之，即为 \(c_{len} \times x\) ，也可以做到 \(O(1)\)。

具体来说，设 \(\large f_i = f_{i-1} +\lfloor \frac{k}{i} \rfloor *i,g_i = g_{i-1} +\lfloor \frac{k}{i} \rfloor\)

上述式子都能通过 \(f,g\) 加减得到。

总结：多列式子推式子简化或转化问题。

day4 C 互不相同

给定 \(a_i\)，定义一次操作为选择一段子区间加上任意整数 \(x\)，问至少几次操作使得全局互不相同。

假设做了 k 次区间加法 产生 \(2k\) 个端点

可以发现端点之间每个区间内部都是互不相同的。

那么原题可以等价为我们选择一个左端点每次贪心的选直到有相同的就新开一个区间。

此时需要操作的次数 = (区间数+1)/2

因为一次操作会产生两个端点。

此时还有一个问题是左右两端的贡献计算，一种方法是枚举左端点找出对应右端点，

另一种方法是强行将原序列拼成一个环，即将原数组复制一遍，往后倍增跳满足 r-l+1<=n

便能自然地算出左右端贡献了。

CSP-S 模拟赛 Day 1 B. 随机左移

你有一个长度为 n 的排列 p1,…,pn，一开始 pi=i。

你想做如下操作 m 次：

• 选择一个数字 x(1≤x≤n)，然后把 p1,p2,…,px 循环左移，也就是变成 p2,p3,…,px,p1。

你想知道这个做法是不是足够随机，所以给你一个排列 q1,q2,…,qn，问在 nm 种不同的操作方法中，有多少种操作的方法使得 p 恰好变成 q。输出答案对 1000000007 (1e9+7) 取模的结果。

做法

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define int ll
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define adde(a,b) v[a].push_back(b)
#define addev(a,b,c) v[a].push_back({b,c});
#define rd read
#define all(a) a.begin(),a.end()
#define mem(a,b) memset(a,b,sizeof a);
#define pb push_back
#define vct vector
#define rev(T) reverse(T.begin(),T.end())
#define endl "\n"const int N = 5e6+5,mod = 1e9 + 7;int n,m,a[N];int ksm(int a,int b)
{int res = 1;while (b){if (b & 1) res = 1ll * res * a % mod;b >>= 1;a = 1ll * a * a % mod;}return res;
}
void solvemain()
{cin >> n >> m;rep(i,1,n) cin >> a[i];int maxn = max(n,m);vct<int> jc(maxn + 2),ijc(maxn + 2);for (int i = 0;i <= maxn;i++)jc[i] = i?jc[i-1]*i%mod:1;ijc[maxn] = ksm(jc[maxn],mod-2);for (int i = maxn-1;i >= 0;i--)ijc[i] = ijc[i + 1] * (i + 1) % mod;auto C = [&](int a,int b){if (a < b) return 0ll;return jc[a] * ijc[b] % mod * ijc[a-b] % mod;};int j = n;int b = n;for (int i = n;i >= 1;i--){while (j >= 1 && a[j] != i) j--;if (a[j] == i) b = i-1;}// cout << b << endl;auto pw = [&](int x){if (x & 1) return -1;return 1;};ll ans = 0;vector<int> f(n + 2);f[0] = 0;for (int i = 1;i <= n;i++) f[i] = ksm(i,m)*ijc[i]%mod;rep(i,1,n) (f[i] += f[i-1]) %= mod;for (int i = 0;i <= n;i++){int l = max(i,b) - i;int r = n - i;// cout << l << ' '<< r << endl;if (l > r) continue;if (r < 0) continue;int res;if (l == 0) res = f[r];else res = (f[r] - f[l-1] + mod) % mod;// cout << res << endl;(ans += pw(i) * ijc[i] % mod * res % mod) %=mod;ans = (ans % mod + mod) % mod;// cout << ans << endl;// cout << ans << endl;}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t;t = 1;while(t--){solvemain();}return 0;
}

CSP-S 模拟赛 A. 序列

给点序列 \(a_1,a_2,\cdots ,a_n\)，问有多少非负整数序列 \(x_1,x_2,\cdots,x_n\) 满足：

• \(\forall i,0 \le x_i \le a_i\)。
• 满足 \(x_1 | x_2 | \cdots | x_n = x_1 + x_2 + \cdots + x_n\)。

\(n \le 16,a_i < 2^{60}\)

状压+数位 DP 好题。

条件二可以转化为 \(x\) 两两并为 \(0\)。按位考虑，即每一位至多一个 \(1\)。

考虑从高位开始给每一位填数，那么需要判断是否超过 \(a_i\) ，可以想到用数位 \(DP\)。

对于每一个数字记录当前是否达到最大限制，即数位 DP 中的 \(limit\)。

用一个 \(16\) 位二进制记录即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define int ll
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define adde(a,b) v[a].push_back(b)
#define addev(a,b,c) v[a].push_back({b,c});
#define rd read
int read()
{int f=1,k=0;char c = getchar();while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();return k*f;
}const int N = 25,M = 66,mod = 998244353;int n,a[N];int num[N][M];int f[M][(1<<16)+10];void solve()
{cin >> n;rep(i,1,n) a[i] = rd();for (int i = 1;i <= n;i++){for (int j = 1;j <= 60;j++){num[i][j] = (a[i]>>(j-1))&1;}}for (int j = 0;j < (1<<n);j++) f[0][j] = 1;for (int i = 1;i <= 60;i++){for (int j = 0;j < (1<<n);j++){int cur = 0;for (int k = 1;k <= n;k++){if ((j>>(k-1)&1) && num[k][i]==0) cur += (1<<(k-1));}(f[i][j] += f[i-1][cur])%=mod;for (int k = 1;k <= n;k++) {int sj = (j>>(k-1))&1;int limit = 1;if (sj == 1) limit = num[k][i];if (limit == 0) continue;int ncur = cur;if (sj) ncur += (1<<k-1);(f[i][j] += f[i-1][ncur])%=mod;}		}}cout << f[60][(1<<n)-1] << endl;
}signed main()
{int t;t = 1;while(t--){solve();}return 0;
}

CF2133E I Yearned For The Mines

https://www.luogu.com.cn/problem/CF2133E

有趣的题。

题意

一棵树，每次可以删除一个点及相邻的边，或者check一个点有没有人，然后人会移动。

构造出一组操作序列使得人一定会被抓到。长度不超过 \(\frac{5}{4}n\)

做法

发现一条链都可以从头扫过去。

发现 \(\frac{5}{4}\) 这个数字，考虑用 \(\frac{1}{4}\) 次操作把原树变成可以 n 次查询出来的形状。

大概是若干条链。

也就是说我们要一次操作至少使得四个点进入所在联通块是一条链。

做法即为从底往上做，若有 \(siz_x \ge 4\) 就删除 \(x\)。

列举发现一定可行。

做完了。

值得注意的是从底往上做不要用什么按 dep 排序之类的汤比做法，而是 dfs递归往下做。

CF2133D Chicken Jockey

https://www.luogu.com.cn/problem/CF2133D

神秘贪心，dp。

给定 \(a_i\)，杀死一个小怪 \(i\)，其后面一个受到 i 的摔伤，杀一次减 \(1\)，问最少杀几次。

做法

一个小怪只会受到一次伤害且只可能是 \(i-1\) 或 \(1\)。

因为不可能出现在新的堆叠中再去受到更大的摔伤，这样是不优的。

线性dp即可。

f[1] = 0;
for (int i = 2;i <= n;i++)
{f[i] = (f[i-2] + min(a[i],i-1));f[i] = max(f[i],f[i-1] + 1);
}
cout << s-f[n] <<  endl;

CF1545B

https://codeforces.com/problemset/problem/1545/B

有趣的排列组合题。

CF1545B AquaMoon and Chess

题目描述

你有一个长为 \(n\) 的棋盘,这个棋盘上有一些棋子,你可以进行如下操作:

如果第 \(i + 2\) 个位置是空的,且第 \(i + 1\) 个位置非空,则可以将第 \(i\) 个位置的棋子挪到第 \(i + 2\) 个位置 (\(i + 2 \leq n\)).

如果第 \(i - 2\) 个位置是空的,且第 \(i - 1\) 个位置非空,则可以将第 \(i\) 个位置的棋子挪到第 \(i - 2\) 个位置 (\(i - 2 \geq 1\)).

给出一个棋盘，求可达状态数。

做法

trick 是不要去管每个东西具体在什么位置，而是相对的关系。

可以发现 \(11\) 可以随意行动，我们可以看成把 \(11\) 捆绑起来，一起移动。

当只有 \(11\) 时，设数量为 \(a\)，\(0\) 的数量为\(c\)，根据排列组合的捆绑法易得答案为 \(C_{a+c,a}\)。

当有单个 \(1\) 时，我们可以看成经过 \(1\) 就交换位置

而 \(111\) 的情况会被算重，可以钦定 \(11\) 一定在前面，则若确定了一种放置 \(11\) 的方法，\(1\) 的位置也相继确定。

则答案即为 \(C_{a+c,a}\)。

CF1415D XOR-gun

https://www.luogu.com.cn/problem/CF1415D

有意思的题目。

题目描述

Arkady 拥有一个非递减数组 \(a_1, a_2, \ldots, a_n\)。

每一步，你可以选择数组中两个相邻的元素，记为 \(x\) 和 \(y\)，将它们从数组中移除，并在它们的位置插入整数 \(x \oplus y\)

你希望数组不再是非递减的。请问最少需要多少步？如果无论如何操作数组都始终保持非递减，请输出 \(-1\)。

做法

先考虑一些特殊情况，如果每个数二进制数位长度不同，那么为 \(-1\)。因为无论如何操作都是非递减的。

而当出现连续 \(3\) 个数的数位长度都相同时，我们可以操作后两个数来达成目的，此时答案为 \(1\)。

考虑鸽巢原理，最多只有 \(30\) 个数位，当 \(n > 60\) 时，必有连续三个数数位长度相同，答案为 \(1\)。

当 \(n \le 60\) 时，发现每次异或的数都是一段区间，\(O(n^3)\) 暴力枚举即可。

2103 F. Maximize Nor

https://codeforces.com/contest/2103/problem/F

有趣的题目。

对于每一个 \(i\) 求包含 \(i\) 的区间的最大权值，权值为区间 \(nor\)。(or 取反)。

按位考虑。

发现遇到一个 \(1\) 就变成 \(0\)。

于是对于一个区间我们只需要关注最后一个 \(1\)，在根据左端点位置和前面 \(0\) 的奇偶性来判断 0/1。

于是区间权值可以 \(O(log V)\) 。

又因为只需要关注最后一个 \(1\)，所以假设固定了 \(r\)，左端点每移动两位，权值就会重复，而在第一个 \(1\) 的位置会发生一些变化。

于是有：对于固定的 \(r\)，不同权值只有 \(O(k)\) 种。

于是我们暴力找出这些区间，做一个区间 chkmx，最后每一个 \(i\) 查一下即可。

值得注意的是并不需要线段树，只需要 扫描线维护 multiset即可。