异或
题目描述
给定数列 \(a\)，统计有多少个三元组 \((i,j,k)\) 满足 \(i<j<k\) 并且 \((a_i\text{ xor }a_j)< (a_k\text{ xor }a_j)\)。
\(n\le 5\cdot 10^5,0\le a_i<2^{30}\)。
解法
不难想到 \(\text{trie}\) 树，但之后就卡住了...
由于 \(k\) 是最后插入的数，不妨想一下用 \(k\) 怎么统计合法的双元组 \((i,j)\)。我们发现对于 \(i,k\) 之间，决定胜负的那一位（设其为 \(p\)）一定不同，且 \(a_j\) 的第 \(p\) 位一定和 \(a_i\) 相同。放到 \(\text{trie}\) 树上就是从最高位开始遍历 \(a_k\)，每一个 \(i\) 都在异向的子树中，且容易发现这样遍历 \(i\) 是不重的。
接下来就只用搞定 \(j\) 了。具体可以分成两种情况：
- \(j\) 和 \(i\) 在与 \(k\) 异向的子树。设子树大小为 \(siz\)，答案就是 \(siz\cdot (siz-1)/2\)。
- \(j\) 甚至和其余两个数前 \(p-1\) 位都不完全相同。我们首先可以统计出第 \(p\) 位为 \(0/1\) 的数字个数，用它减去 \(siz\) 就是合法（？）的 \(j\) 的个数。真的吗？你会发现没有考虑 \(i<j\) 的条件，事实上不合法的情况可以在插入时计算 —— 在子树中维护一个 \(sub\)，每次插入时加上在外部的点，这些点对于新插入的点就是不合法的。
\(\text{[Code+#4] }\)最短路
手玩一下就能发现，我们只需要保留一类权值为 \(2^k\cdot C\) 的边。于是边的数量变成了 \(m+n\log n\) 的级别，直接拿去跑 \(\text{Dijkstra}\) 即可。
\(\text{[WF2011] MachineWorks}\)
斜率优化每次都是推柿子简简单单，细节打挂死都调不出来！这从我斜率优化板题至今不知道错在哪里就可见一斑了。生气！待会还要回去接着调！
首先题目中有一句重要的话：\(\rm acm\) 公司在任何时候都只能最多拥有一台机器。
所以不妨设 \(dp_i\) 为购买第 \(i\) 台机器能获得的最大利润，转移方程：
将机器按时间升序排序，最后插入一个时间为 \(D+1\) 的机器即可。当然，对于 \(r_i\) 也可以采用延后计算的方法，这样 \(r_i\) 就在 \(\max\) 里面了，这是一个坑了我很久的点，具体的原因下文再谈。
转移方程有 \(i,j\) 的交叉项，而且满足 \(-d_i\) 即斜率是单减的，所以可以用李超树或者 \(\text{cdq}\) 分治来优化 \(\mathtt{dp}\)，这里就只讲 \(\text{cdq}\) 分治。
将机器按时间升序排序后，给每个机器赋予一个编号，这样可以快速判断该将这个机器分在哪一边。具体可以看看代码：
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f |= (s=='-');
while(s>='0' and s<='9')
x = (x<<1)+(x<<3)+(s^48),
s = getchar();
return f?-x:x;
}
template <class T>
inline void write(T x) {
static int writ[40],w_tp=0;
if(x<0) putchar('-'),x=-x;
do writ[++w_tp]=(x-x/10*10),x/=10; while(x);
while(putchar(writ[w_tp--]^48),w_tp);
}
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int maxn = 1e5+5;
ll dp[maxn];
int n,C,D,stk[maxn],tp;
struct Product {
int d,p,r,g,id;
bool operator < (const Product &rhs) const {
return d<rhs.d;
}
} a[maxn],a1[maxn];
struct node {
ll x,y; bool opt;
bool operator < (const node &rhs) const {
return (x^rhs.x)?x<rhs.x:y>rhs.y;
}
} p[maxn],p1[maxn];
inline double slope(int i,int j) {
if(p[i].x==p[j].x) return p[i].y<p[j].y?inf:-inf;
return 1.0*(p[j].y-p[i].y)/(p[j].x-p[i].x);
}
void dicon(int l,int r) {
if(l==r) {
dp[l] = max(dp[l],0ll+C-a[l].p);
if(dp[l]<0) {
p[l].opt=1; return;
}
else p[l].opt=0;
p[l].x = a[l].g;
p[l].y = dp[l]-1ll*a[l].g*(a[l].d+1)+a[l].r;
return;
}
int mid = l+r>>1, L=l, R=mid+1;
for(int i=l;i<=r;++i)
if(a[i].id<=mid) a1[L++]=a[i];
else a1[R++]=a[i];
for(int i=l;i<=r;++i) a[i]=a1[i];
dicon(l,mid); tp=0;
for(int i=l;i<=mid;++i) {
if(p[i].opt) continue;
while(tp>1 && slope(stk[tp-1],stk[tp])<=slope(stk[tp],i)) --tp;
stk[++tp]=i;
}
if(tp) {
int j=1,k;
for(int i=mid+1;i<=r;++i) {
while(j<tp && slope(stk[j],stk[j+1])>=-a[i].d) ++j;
k=stk[j];
dp[a[i].id] = max(dp[a[i].id],p[k].y-a[i].p+1ll*a[i].d*p[k].x);
}
}
dicon(mid+1,r); L=l,R=mid+1;
for(int i=l;i<=r;++i)
if((p[L]<p[R] || R>r) && L<=mid) p1[i]=p[L++];
else p1[i]=p[R++];
for(int i=l;i<=r;++i) p[i]=p1[i];
}
int main() {
int times=0;
while(scanf("%d %d %d",&n,&C,&D),n) {
for(int i=1;i<=n;++i)
a[i].d=read(9),a[i].p=read(9),
a[i].r=read(9),a[i].g=read(9);
sort(a+1,a+n+1);
a[++n].d=D+1,a[n].p=a[n].r=a[n].g=0;
for(int i=1;i<=n;++i)
a[i].id=i,dp[i]=-inf;
dicon(1,n);
printf("Case %d: %lld\n",++times,dp[n]);
}
return 0;
}
首先关于先前那个坑点，主要问题在 l==r 的给 \(\mathtt{dp}\) 值取 \(\max\) 的操作：如果使用写出来的转移方程，而不延迟计算 \(r_i\) 的话，你会发现 \(dp_l\) 和 \(C-p_l\) 实际上根本无法比较，\(dp_l\) 和 \(C-p_l+r_l\) 才是可比较的。但是实际上，我们还需要强制 \(C-p_l\) 非负！当然这样也是可以写的，只不过会比较冗长。
另外就是斜率优化的老问题了：当横坐标相等时应该怎样判断？就这道题而言，横坐标相同时，纵坐标越大就越优，于是我们分两种情况讨论（不妨设 \(i<j\)，就分 \(y_i<y_j,y_i\ge y_j\) 两种情况），建议先写出代码，再进行判断。
\(\text{K-Anonymous Sequence}\)
呜呜呜调了半天终于明白为什么错了！
对于这种转移点有区间限制的题目，一定要等到转移点合法时再入队，不然会很难弹队！
\(\text{[FJOI 2007] }\)轮状病毒
首先破环为链，那么就是将序列划分成多段，每一段向中心点连一条边，转移方程
此时 \(1\) 和 \(n\) 是不能连通的，我们实际上可以利用这个条件：
- 考虑 \(1,2\) 不连通：相当于将 \(1,2\) 分别看成 \(n,1\)，所以方案数 \(f_n\)。
- 考虑 \(1,2\) 连通，\(2,3\) 不连通：相当于将 \(2,3\) 分别看成 \(n,1\)，但此时强制 \(1,2\) 连通，也就是最后一组长度至少为 \(2\)，所以方案数 \(\sum_{j=2}^i j\cdot f_{i-j}\)。
后面的同理，把所有柿子加起来即可。
体育测试
题目描述
你需要构造一个长度为 \(n\) 的排列 \(p\)，使其满足两类限制：
- \(p_i\) 在 \(1\) 与 \(a_i\) 之间；
- \(p_i\) 在 \(a_i\) 与 \(n\) 之间。
给定 \(a_i\) 与限制类型，你需要计算出符合条件的排列总数。
\(n\le 5000\).
解法
首先可以考虑简单的情况：假设只有限制一。很容易想到将 \(a_i\) 从小到大排序，这样我们就可以获取一个很棒的特性：在考虑到 \(i\) 号位时，我们只需要知道在这之前必须放置的个数就可以算出 \(i\) 号位可以选择的种类。更清晰一点，将 \(i\) 号位挂在 \(a_i\) 上，当遍历到 \(a_i\) 时，我们只需要知道在 \([1,a_i]\) 之中有多少个数被选，即可推出 \(i\) 号位的选数方案数。
现在限制变成了两条，所以我们不妨像上文一样计算限制一，再用一个 \(\mathtt{dp}\) 来计算限制二！
由于需要知道在 \([1,i]\) 之中有多少个数被选，所以 \(\mathtt{dp}\) 可以设计成 \(dp_{i,j}\) 表示 \([1,i]\) 的数均被选，有 \(j\) 个限制二中的位置选了 \([1,i]\) 之间的数的方案数。
在 \(\mathtt{dp}\) 时需要注意的一个点是，由于需要在 \(a_i\) 处计算 \(i\) 号位的选数方案数，要将 \(dp_{i,j}\) 加上 \(dp_{i-1,j}\)，表示给后面的数字预先留位置。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' || s<'0')
f |= (s=='-');
while(s>='0' && s<='9')
x = (x<<1)+(x<<3)+(s^48),
s = getchar();
return f?-x:x;
}
template <class T>
inline void write(T x) {
static int writ[50],tp=0;
if(x<0) putchar('-'),x=-x;
do writ[++tp] = x-x/10*10, x/=10; while(x);
while(tp) putchar(writ[tp--]^48);
}
const int maxn = 5005;
const int mod = 1e9+7;
int fac[maxn],ifac[maxn];
int n,cnt[2][maxn],dp[2][maxn];
inline int inv(int x,int y=mod-2) {
int r=1;
while(y) {
if(y&1) r=1ll*r*x%mod;
x=1ll*x*x%mod; y>>=1;
}
return r;
}
void init() {
fac[0]=1;
for(int i=1;i<=n;++i)
fac[i] = 1ll*fac[i-1]*i%mod;
ifac[n] = inv(fac[n]);
for(int i=n-1;i>=0;--i)
ifac[i] = 1ll*ifac[i+1]*(i+1)%mod;
}
inline int A(int n,int m) {
if(n<m) return 0;
return 1ll*fac[n]*ifac[n-m]%mod;
}
inline int inc(int x,int y) {
return x+y>=mod?x+y-mod:x+y;
}
int main() {
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
n=read(9); init();
for(int i=1;i<=n;++i) {
int x=read(9);
if(x>0) ++cnt[0][x];
else ++cnt[1][-x];
}
int sum=0,be=0; dp[0][0]=1;
for(int i=1;i<=n;++i) {
sum += cnt[1][i];
for(int j=0;j<=n;++j)
dp[i&1][j]=0;
for(int j=0;j<i;++j) {
if(j+1<=sum)
dp[i&1][j+1] = 1ll*dp[(i&1)^1][j]*(sum-j)%mod;
dp[i&1][j] = inc(dp[i&1][j],dp[(i&1)^1][j]);
}
if(cnt[0][i])
for(int j=0;j<=i;++j)
dp[i&1][j] = 1ll*dp[i&1][j]*A(i-j-be,cnt[0][i])%mod;
be += cnt[0][i];
}
print(dp[n&1][sum],'\n');
return 0;
}
三值排序
首先，这道题的起始与终止状态提示我们运用 “归类” 的思想，于是我们将数列划分成三个区间分别表示 \(1,2,3\) 最后应该呆的区间。那么就可以定义 \(a_{i,j}\) 为第 \(i\) 种数却在第 \(j\) 种数的区间中的数量。
比如数字 \(1\)，我们可以从两个角度来观察：
其余同理。这样就成功将得到的信息进行抽象化。看上去没啥用？
此时你会发现，将 \(1\) 中的 \(2\) 全部与 \(2\) 中的 \(1\) 交换，此时 \(2\) 中还剩下 \(\delta\) 个 \(1\). 同理，\(1\) 中还剩下 \(\delta\) 个 \(3\)， \(3\) 中还剩下 \(\delta\) 个 \(2\)！
我们可以将其简化为 "\(3\ 1\ 2\)" 的情况，容易发现需要 \(2\delta\) 次。
没有名字
题目描述
给出 \(n\) 个正整数 \(a_i\)，你要选出 \(n\) 个正整数 \(b_i\) 和 \(n\) 个正整数 \(d_i\)，对于每个 \(i\) 满足 \(b_i |a_i\) 且 \(d_i |b_i\)，求有多少种选法满足 \(∏d_i^2 ≥∏b_i\).
\(n\le 100,a_i\le 10^9\).
解法
首先可以用等差数列计算出所有满足 \(b_i |a_i\) 且 \(d_i |b_i\) 的方案，而后有一个非常奇妙的转化：\(∏d_i^2 >∏b_i\) 的方案数等于 \(∏d_i^2 <∏b_i\) 的方案数！证明就是 \(\prod b_i^2=\prod d_i^2\cdot \prod\frac{b_i^2}{d_i^2}\)，如果存在 \(∏d_i^2 >∏b_i\)，那么就一定能取到 \(\prod\frac{b_i^2}{d_i^2} <∏b_i\).
于是只需要算出 \(∏d_i^2 =∏b_i\) 的方案数就能计算出答案。
具体的数是不好考虑的，一般遇到这种题应该先考虑质因数分解，然后将每个质因子的解进行合并，对于本题亦是如此。接着我们得出，满足条件的 \(b_i,d_i\) 有：对于任意质因子都有 \(b_i\) 的幂次是 \(d_i\) 的幂次的两倍。更进一步，也可以转化成 \(d_i\) 在 \(b_i\) 中选的幂次与未选的幂次相等。
我们不妨设 \(dp_{i,j}\) 为 \(\mathtt{dp}\) 到第 \(i\) 组 \((b_i,d_i)\)，\(d_i\) 在 \(b_i\) 中选的幂次减去未选的幂次为 \(j\) 的方案数。
我的想法是将每个质因子对应的组数（\(a_i\) 的质因子中有它）扔进 \(\rm vector\)，然后分组考虑：枚举 \(j\) 与 \(j\) 的转移，转移的系数（也即计算 \(d_i\) 在 \(b_i\) 中选的幂次减去未选的幂次为 \(k\) 的方案）应当也较好算。总复杂度 \(\mathcal O(900\cdot n\log a)\).
幻数
题目描述
给出非负整数序列 \(a_1,a_2,a_3,\dots,a_n\)，请找到最小的非负整数 \(b\) 使得
其中 \(\oplus\) 表示按位异或。若不存在这样的 \(b\)，则输出 \(-1\).
多次询问。每次修改 \(\{a\}\) 中的一个数，然后请给出当前 \(\{a\}\) 所对应的最小 \(b\) 值。修改是永久的。
\(1\le n\le 10^6,a_i\le 2^{30}\).
题面是嫖的。
解法
遇到这种题的一个套路是 "按位" + "整体"。从最高位开始考虑，显然合法的二进制位只能是 "\(0000...1111\)" 或 "\(1111...0000\)"，我们可以将其分成两个部分向下递归。带修改可以用线段树维护，是两只 \(\log\) 的。
由于 "\(\le\)" 的传递性，实际上我们只用保证相邻两个数满足条件。可以发现，\(a_i\) 与 \(a_{i+1}\) 从上到下第一位不相同的二进制位 \(j\) 可以判定 \(b\) 的第 \(j\) 位的取值，\(i\) 与 \(i+1\) 其实也相当于前一种方法的分割点。而单次修改只会影响前后两个数，所以不妨用 \(cnt_{j,0/1}\) 统计使二进制位 \(j\) 必须填 \(0/1\) 的限制个数，这样就是可撤销与增加的了。时间复杂度 \(\mathcal O(30\cdot (n+q))\).
\(\text{[HAOI 2012] }\)外星人
重要的观察是 \(x\) 几乎等于所有数字中 \(2\) 的个数。
对于每个非 \(2\) 的质数，在 \(\varphi\) 过后至少产生一个 \(2\)，所以我们可以得知，当初始含 \(2\) 时，之后的状态一定有 \(2\)（除非已经终止），那么答案就是所有数字中 \(2\) 的个数；不含 \(2\) 时，答案就是所有数字中 \(2\) 的个数加一。
\(\text{[SDOI 2012] }\)吊灯
结论题毁我青春。考试的时候疯狂树形 \(\mathtt{dp}\)，人都给我干傻了。
结论：对于 \(d\mid n\)，有 "树可被划分成大小为 \(d\) 的 \(n/d\) 个连通块" 等价于 "树中至少有 \(n/d\) 个点满足其子树大小是 \(d\) 的倍数"。
考虑 "\(\Rightarrow\)"：对于每个连通块都有一个根节点 \(u\)，显然 \(u\) 的子树中除去 \(u\) 所在连通块的节点被划分成若干个大小为 \(d\) 的连通块，所以 \(u\) 的子树大小为 \(d\) 的倍数。而这样的 \(u\) 有 \(n/d\) 个。
考虑 "\(\Leftarrow\)"：其实很类似。考虑每个子树大小是 \(d\) 的倍数的点 \(u\)，它的子树可能包含若干个子树大小是 \(d\) 的倍数的点，但它的儿子一定不全是这些点，否则与前提条件相悖。除开那些子树大小是 \(d\) 的倍数的点，其余点个数显然也是 \(d\) 的倍数而且与 \(u\) 相连通，那么显然可以取出一个包含 \(u\) 且不包含 \(u\) 子树中子树大小是 \(d\) 的倍数的点的大小为 \(d\) 的连通块。
\(\text{[ROI 2017 Day 2] }\)存储器
首先一个显性的 \(\rm observation\) 是当相邻两段变成同一个字符之后，它们就会一起变化。不妨先考虑无解的情况，这可以从末状态的角度来思考：如果相邻字符末状态不同，但初状态相同，显然就无解。更进一步的，其实相邻字符末状态不同，初状态均与末状态不同的情况也是无解的，因为这种情况可以化归到上一个情况。
到了这一步我们就有了一个惊喜的发现：特判掉上文不合法的情况，串 \(s\) 就被串 \(t\) 划分成 互不干涉 的几段，而每一段的 目的 都是相同的！
这个问题可以用栈解决。详见代码。
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' || s<'0')
f |= (s=='-');
while(s>='0' && s<='9')
x = (x<<1)+(x<<3)+(s^48),
s = getchar();
return f?-x:x;
}
template <class T>
inline void write(T x) {
static int writ[50],tp=0;
if(x<0) putchar('-'),x=-x;
do writ[++ tp] = x-x/10*10, x/=10; while(x);
while(tp) putchar(writ[tp--]^48);
}
#include <cstring>
const int maxn = 1e6+5;
char s[maxn],t[maxn];
int n,stk[maxn],tp;
int main() {
bool ban;
for(int T=read(9); T; --T) {
scanf("%s %s",s+1,t+1);
n = strlen(s+1); ban = 0;
for(int L=1,R;L<=n;L=R) {
R=L;
while(R<=n && t[L]==t[R]) ++ R;
if(R<=n && (s[R-1]!=t[R-1] || s[R]!=t[R])) ban=1;
tp=0; bool sam=0;
for(int l=L,r;l<R;l=r) {
r=l;
while(r<R && s[l]==s[r]) ++ r;
int len = r-l;
if(s[l]==t[l]) {
if(sam) stk[tp] += len;
else stk[++ tp] = len, sam=1;
} else if(sam && stk[tp]>len)
stk[tp] += len;
else stk[++ tp] = len, sam=0;
if(sam) {
while(tp>2 && stk[tp]>stk[tp-1])
stk[tp-2] += stk[tp]+stk[tp-1], tp-=2;
if(tp>1 && stk[tp]>stk[tp-1])
stk[tp-1] += stk[tp], -- tp;
}
}
if(!sam || tp>1) { ban=1; break; }
}
puts(ban?"No":"Yes");
}
return 0;
}