记些明日の欠片。
1
题目背景
给定一个初始整数数组，需要依次执行 \(Q\) 次操作，最后统计数组中值在指定范围 \([L, R]\) 内的元素个数。操作类型
- 加法操作：对于数组中所有满足 \(a_j \ge x_i\) 的元素，执行 \(a_j \gets a_j + x_i\)。
- 截断除法操作：对于数组中所有满足 \(a_j \le s_i\) 的元素，执行 \(a_j \gets \mathrm{trunc}\left(\dfrac{a_j - s_i}{t_i}\right)\)，其中 \(\mathrm{trunc}(y)\) 表示对实数 \(y\) 向零截断（即去掉小数部分，使其向零取整）。
注意
在执行所有操作的过程中，保证数组中每个元素的绝对值始终不超过 \(2^{63}\)。数据范围
- \(1 \le n, Q \le 2 \times 10^5\)
- \(-2^{63} < L \le R < 2^{63}\)
- 初始数组元素满足 \(|a_i| \le 10^9\)
- 操作参数：
- \(q_i \in \{1, 2\}\)
- \(0 \le x_i < 2^{63}\)
- \(1 \le s_i, t_i \le 10^9\)
一个很重要的观察是所有操作不会改变原数组中两个数的相对大小顺序。
最初想到的是反过来只对 \(L,R\) 操作，就能确认在原数组的范围。
但是这里反过来是不方便的，我们考虑确定两个进行操作前的数 \(l,r\)，使得进行完成操作后的 \(L\le l\) 且最小，\(r\le R\) 且最大，这样就能确人在原数组中的范围。
于是二分答案即可。
但是实现有些细节，我最初实现的是直接在值域上二分，但是这样就不保证操作过程中溢出，就会产生一堆边界条件。
说到溢出检查，这里给一个非常 native 的溢出检查方案：
bool ofl(ll a,ll b){__int128 g1=a,g2=b;__int128 res=g1*g2;if(res>LLONG_MAX)return 1;else return 0;
}
看起来好有道理啊。
一个更好的实现思路是给原序列排序后在原序列上二分。这种就保证了不会溢出出现什么奇怪的 corner case。
注意二分边界的定义导致的可能的开闭区间要求。
code
Show me the code
#define psb push_back
#define mkp make_pair
#define ls p<<1
#define rs (p<<1)+1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#define rd read()
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
ll read(){ll x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
const int N=2e5+5;
int a[N];
int n,q,L,R;
struct query{int q,x,s,t;
}q1[N];
bool ofl(int a,int b){__int128 g1=a,g2=b;__int128 res=g1*g2;if(res>LLONG_MAX)return 1;else return 0;
}
int check(int a1){for(int i=1;i<=q;i++){if(q1[i].q==1&&a1>=q1[i].x){a1=(a1+q1[i].s);if(ofl(a1,q1[i].t))return LLONG_MAX;a1=a1*q1[i].t;}if(q1[i].q==2&&a1<=q1[i].x){__int128 g1=a1,g2=q1[i].s,g3=q1[i].t;a1=(g1-g2)/g3;}}return a1;
}
signed main(){freopen("arithmetic.in","r",stdin);freopen("arithmetic.out","w",stdout);cin>>n>>q>>L>>R;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n);for(int i=1;i<=q;i++){cin>>q1[i].q>>q1[i].x>>q1[i].s>>q1[i].t;}a[n+1]=LLONG_MAX;int l1=1,r1=n+1;while(l1<r1){int mid=l1+r1>>1;if(check(a[mid])>=L)r1=mid;else l1=mid+1;}int l2=1,r2=n+1;while(l2<r2){int mid=l2+r2>>1;if(check(a[mid])<=R)l2=mid+1;else r2=mid;}cout<<r2-r1;return 0;
}
2
题目背景
戴夫需要从一组植物中选择最大数量的植物来抵御僵尸。每个植物有两个属性：攻击力 \(s\) 和类型 \(t\)（\(t=1\) 表示特殊植物，\(t=0\) 表示普通植物）。选择条件
对于每个被选中的植物 \(i\)，必须满足以下条件之一：
- 它是特殊植物（即 \(t_i = 1\)），
- 或者存在一个被选中的植物 \(j\)（可以是 \(i\) 自己），使得 \(s_i\) 能整除 \(s_j + 1\)（即 \(s_i \mid (s_j + 1)\)）。
数据范围
- 数据组数 \(T \leq 10^4\)
- 所有组的总植物数 \(\Sigma n \leq 10^6\)
- 植物攻击力 \(1 \leq s_i \leq 3 \times 10^6\)
- 植物类型 \(t_i \in \{0, 1\}\)
首先可以把选择关系扔到有向图上，之后在图上缩点拓扑排序即可。
关于建图，我们使用筛法预处理出 \(1\sim 3\times 10^6\) 的每个数的因数集合，这个东西的时间复杂度是 \(n\log n\) 的。
之后根据这个建图就可以了。
想的时候忘了还能筛因数唐了好久，我在干什么啊。
还没有 code。
3
问题描述
给定 \(T\) 组测试数据，每组数据包含三个正整数 \(k, b, y\)。求非负整数 \(x\) 使得 \((k \times x + b) \oplus y\) 最小，并输出这个最小的共振度。数据范围
- 测试组数 \(T \leq 10^5\)
- 参数 \(k, b, y\) 满足 \(1 \leq k, b, y \leq 10^{18}\)
神秘一句话。
猜了个结论结果寄了。
又是和异或有关的东西想想从高位贪心。
我们考虑从高位向低位填入二进制位。当然不能乱填，考虑我们还没填的 \(k\) 位，假设下面都填 \(0\) 得到的数是 \(s\)，那么我们下面能填出来的数必然是一个连续的区间 \([s,s+2^k-1]\)。
接下来，我们可以判断是否存在一个数 \(x\)，使得 \(kx+b\) 落在区间 \([s,s+2^k-1]\)，就是简单的解个不等式。
于是如果放 \(1\) 不行再放 \(0\)，每次放一位判断一次，这样贪心就对了。
很精密的技巧。
还没有代码。
4 编辑距离
我怎么连这个都忘了。
LC72 编辑距离
由于我们的目标只要让两个字符串相同就好了，因此删除操作其实是没用的，我们完全可以无脑的往后面加一个和对方字符串最后一个字符相同的字符来让两个字符串相同。
于是设 \(f_{i,j}\) 表示让 \(s\) 前 \(i\) 个和 \(t\) 前 \(j\) 个字符相同所需最小操作数，转移就是：
\(f_{i,j} \leftarrow f_{i,j-1}+1\)
\(f_{i,j} \leftarrow f_{i-1,j}+1\)
若 \(s_i \ne t_j\)，有 \(f_{i,j} \leftarrow f_{i-1,j-1}+1\)
若 \(s_i = t_j\)，有 \(f_{i,j} \leftarrow f_{i-1,j-1}\)
三种里面取个最小值。
初始值是：
对于所有 \(i\in [0,|s|]\)，\(f_{i,0} \leftarrow i\)
对于所有 \(j\in [0,|t|]\)，\(f_{0,j} \leftarrow j\)
答案是 \(f_{|s|,|t|}\)
贺了一个实现：
code by Ikaruga LeetCode
Show me the code
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));for (int i = 0; i < dp.size(); i++) {dp[i][0] = i;}for (int j = 0; j < dp[0].size(); j++) {dp[0][j] = j;}for (int i = 1; i < dp.size(); i++) {for (int j = 1; j < dp[i].size(); j++) {dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;if (word1[i - 1] == word2[j - 1]) {dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);}}}return dp.back().back();}
};
5
题目背景
诗人需要将初稿字符串 \(S\) 修改为新稿字符串 \(T\)，两个字符串均由大小写字母组成。她只能通过键盘操作进行修改，初始时光标位于字符串开头且大写锁定关闭。求解最小敲击次数。操作类型
- 移动光标向左或向右一格：1 次敲击
- 在光标前输入字符（与当前大写锁定状态一致）：1 次敲击
- 按住 Shift 输入字符（与当前大写锁定状态相反）：2 次敲击
- 切换大写锁定状态：1 次敲击
- 删除光标前的字符：1 次敲击
数据范围
- \(1 \leq |S|, |T| \leq 7 \times 10^3\)
编辑距离高级版。
首先注意到光标移动这种东西是不需要我们关心的，我们其实就是简单的从后往前扫一遍，光标移动的距离就是 \(S\) 的长度。
然后是大小写，这个东西放进状态里就行了。
于是设 \(f_{i,j,0}\) 表示把 \(S\) 的前 \(i\) 位和 T 的前 \(j\) 位相等，且大写键状态位关闭时的最小敲击数，\(f_{i,j,1}\) 表示大写键开启时的。
转移时考虑改变状态，按着 shift，对应的常数都是 \(2\)。类似转移即可。
还没有代码。
6
题目背景
定义一个字符串为“dancer”当且仅当它可以重新排列成回文串（即最多有一个字符出现奇数次）。问题描述
给定一个字符串 \(s\)，求有多少种将 \(s\) 划分为若干连续子串的方案，使得每个子串都是 dancer。答案对 \(998244353\) 取模。数据范围
- 数据组数 \(T\)，总字符串长度 \(\sum n \leq 3 \times 10^5\)
- 字符串 \(s\) 的长度 \(n \leq 10^5\)
- 字符集为 20 个小写字母（从 a 到 t）
容易有 \(O(n^2)\) 的转移，也就是 \(dp_{i}\) 表示前 \(i\) 个字符分的状态数，当然是不够好的。
考虑我们实际上在转移什么，dancer 字符串也就是其中最多只能出现一种字符出现次数为奇数次，我们转移时候切出来的区间 \([j,i]\) 和 区间 \([1,j-1]\) 都应该满足这样的出现次数关系。
因为字符只有 \(20\) 位，我们把每个字符出现的奇偶性压到一个 int 里面去。
这样的状态是有前缀性质的，也就是若 \([1,i]\) 的状态是 \(m_1\)，\([1,j-1]\) 的状态是 \(m_2\)，那么 \([j,i]\) 的状态是 \(m1 \oplus m2\)。
我们根据状态做一次前缀和，具体的，设 \(p_m\) 表示在当前更新的 \(i\) 之前，\([1,i-1]\) 的前缀中状态是 \(m\) 的 \(dp_i\) 之和。
我们记录从 \(1\) 到 \(i\) 的总前缀状态，因为每次只会产生一个状态，这样更新 \(p_m\) 的时间复杂度是 \(O(1)\) 的。
接下来，我们枚举所有的合法状态 \(m'\) 来代表一个可能的后缀 \([j,i]\) 的状态，这样的状态仅会有 \(21\) 种，\(m\oplus m'\) 得到的就是我们能转移过来的前缀应满足的状态。
于是在这个状态也合法的前提下让 \(dp_i \leftarrow dp_{i}+p_{m\oplus m'}\) 即可实现快速转移。
转移完成后要更新 \(p_m\)，也就是 \(p_m \leftarrow p_m+dp_i\)
非常清新的一个状压思路！
还没有代码。