D. Love-Hate
题目描述
有 (n) 个长度为 (m) 的二进制串，为 (1) 的串至多有 (p) 个。
试从中选出 (lceilfrac{n}{2} ceil) 个串，使得他们并集为 (1) 个位个数最大。
(nleq 2cdot 10^5,mleq 60,pleq 15)
解法1
暴力出奇迹！我们搜索可能的答案，计算有多少个串能选进去。
每次加入可能成为答案的数位（至少出现 (lceilfrac{n}{2} ceil) 次），然后用 ( t bitset) 维护能选的串的数量。
解法2
一个更加稳定的做法，我们考虑充分利用选串个数为 (lceilfrac{n}{2} ceil) 这个条件，考虑对于一个串他有 (frac{1}{2}) 的概率不出现在答案里面，而如果一个串出现在答案里面我们一定能用它算出答案，答案一定是他的子集。
那么我们随机 (20) 个下标，就有 ((frac{1}{2})^{20}) 的概率得到正确答案。
确定下标之后就好做了，我们看有多少个人的子集是 (s)，可以子集枚举 (O(3^p+pcdot n)) 算出。
你发现这是个 ( t FWT) 正变换的过程，所以也可以 (O(pcdot 2^p+pcdot n)) 算出。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
const int M = 200005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,p,mx,ans[65],a[M][65],bit[1<<15],cnt[1<<15];
int random(int x)
{
return (rand()*rand()+rand())%x;
}
void work(int x)
{
vector<int> v;
for(int i=1;i<=m;i++)
if(a[x][i]) v.push_back(i);
memset(cnt,0,sizeof cnt);
for(int i=1;i<=n;i++)
{
int msk=0;
for(int j=0;j<v.size();j++)
if(a[i][v[j]]) msk|=(1<<j);
cnt[msk]++;
}
for(int i=0;i<(1<<p);i++)
for(int j=i;;j=(j-1)&i)
{
if(i!=j) cnt[j]+=cnt[i];
if(j==0) break;
}
for(int i=0;i<(1<<p);i++)
if(cnt[i]>=(n+1)/2 && bit[i]>mx)
{
mx=bit[i];
memset(ans,0,sizeof ans);
for(int j=0;j<p;j++)
if(i&(1<<j)) ans[v[j]]=1;
}
}
signed main()
{
n=read();m=read();p=read();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
scanf("%1d",&a[i][j]);
}
for(int i=1;i<(1<<p);i++)
bit[i]=bit[i>>1]+(i&1);
for(int i=1;i<=20;i++)
{
int x=random(n)+1;
work(x);
}
for(int i=1;i<=m;i++)
printf("%d",ans[i]);
}
E.Crypto Lights
题目描述
有 (n) 栈灯，每次随机选择一盏未点亮的灯点亮，如果存在连续 (k) 栈灯亮了两个及以上就跳出，求点亮灯个数的期望。
(2leq kleq nleq 10^5)
解法
好久没做过这么纯粹的期望题了，但是不会
拆贡献是算期望最重要的方法，具体的，对于本题我们计算点亮 (i) 栈灯，并且当前状态合法的概率，对所有 (i) 的概率求和 (+1) 就是期望。
可以先算方案数，我们选择 (i) 个灯亮，因为不能把不合法的方案算进去，所以我们计算方式是先强制每两个 (1) 中有 (k-1) 个 (0)，然后剩下的 (0) 任意插入 (1) 的间隙中，这相当于 (n-(i-1)(k-1)) 个位置中选择 (i) 个 (1)，即 ({n-(i-1)(k-1)choose i})
因为有顺序问题所以还要略微修正一下，因为这 (i) 个灯可以任意顺序点亮所以要乘上 (i!)，因为我们的考虑不是完全的，所以每一种方案实际上代表着 ((n-i)!) 种最终方案。即使有些方案会中途夭折，我们还是可以把最终总方案当成 (n!)，只不过有些方案的贡献计算变化罢了，所以要乘上 ((n-i)!) 再除以 (n!)：
#include <cstdio>
const int M = 100005;
const int MOD = 1e9+7;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,k,ans,fac[M],inv[M];
void init(int n)
{
fac[0]=inv[0]=inv[1]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
for(int i=2;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[i]%MOD;
}
int C(int n,int m)
{
if(n<m) return 0;
return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
signed main()
{
T=read();init(1e5);
while(T--)
{
n=read();k=read();ans=0;
for(int i=1;i<=n;i++)
ans=(ans+C(n-(i-1)*(k-1),i)*fac[i]%MOD*fac[n-i])%MOD;
ans=(ans*inv[n]+1)%MOD;
printf("%lld
",ans);
}
}
F. Favorite Game
题目描述
在二维平面内，有 (n) 个传送塔和 (m) 个地标，初始时阿七可以降落在任意地点，每秒可以选择不动，或者向四周移动一步。如果阿七到过某个传送塔，就会将其激活，以后可以瞬间移动到这个传送塔的位置。
每个地标有指定地点和指定时间 (t_i)，如果阿七正好在 (t_i) 时间到达这个地标就可以完成一个刺杀任务，最大化任务完成数。
(nleq 14,mleq 100,1leq x,yleq 10^6,1leq t_ile10^9)
解法
首先把所有地标按指定时间升序排序，这样就确定了 (dp) 的转移顺序。
可以定义出最朴素的状态，设 (dp(s,i,j)) 表示阿七到达的传送塔集合状压为 (s)，任务完成总数为 (i)，现在的地点是 (j)（可能是地标也可能是传送塔）的最小消耗时间，但是状态数就有了 (O(2^nm^2)) 直接起飞，我们不妨来搞一些 ( t observations)：
- 重要的量有四个：到达的传送塔集合，任务完成总数，现在所处地点，当前时间，看上去三维 (dp) 是必须的。
- 如果阿七在传送塔，因为可以瞬移，所以我们不用关心阿七在哪个传送塔，那么就只剩了三个量。
- 如果阿七在地标，因为刺杀任务的时间指定是 (t_i)，所以我们不用关心时间，那么也只剩了三个量。
- 所有的情况可以分为阿七在传送塔和阿七在地标。
综合以上观察，我们得到了优化的思路：通过类似分类讨论的方法来减少状态量，给 (dp) 降维。
上面是我自己的思考，现在就能顺理成章地得到题解的做法：设 (f[s][i]) 表示到达的传送塔集合为 (s)，任务完成总数为 (i)，现在处于传送塔的最小时间；设 (g[s][i]) 表示到达传送塔集合为 (s)，现在处于地标 (i) 的最大任务完成总数，来写转移：
- 设 (w[s][i]) 表示到达传送塔集合为 (s)，从某个传送塔到地点 (i) 的最小时间，这个可以预处理方便转移。
- 从某个传送塔出发到一个新的传送塔：(f[soplus j][i]leftarrow f[s][i]+w[s][j])
- 从某个传送塔出发到一个新的地标：(g[s][j]leftarrow i+1)，当满足 (f[s][i]+w[s][j]leq t[j]) 时转移
- 从地标出发到一个新的传送塔：(f[soplus j][g[s][i]]leftarrow t[i]+min(w[s][j],dis[i][j]))
- 从地标到下一个地标：(g[s][j]leftarrow g[s][i]+1)，当满足 (min(w[s][j],dis(i,j))+t[i]leq t[j]) 时转移
时间复杂度 (O(2^nm^2))，有一些小细节可以参考代码注释。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 120;
const int N = 1<<14;
const int inf = 0x3f3f3f3f;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,ans,f[N][M],g[N][M],w[N][M];
//f[s][i]:stand for having reached tower s,visited i landmarks,now in a tower
//g[s][i]:stand for having reached tower s,now in a landmark
struct node
{
int x,y,t;
bool operator < (const node &r) const
{
return t<r.t;
}
}a[M];
int Abs(int x) {return x>0?x:-x;}
int get(node a,node b)
{
return Abs(a.x-b.x)+Abs(a.y-b.y);
}
signed main()
{
n=read();m=read();
for(int i=0;i<n;i++)
a[i].x=read(),a[i].y=read();
for(int i=n;i<n+m;i++)
a[i].x=read(),a[i].y=read(),a[i].t=read();
sort(a+n,a+n+m);
for(int s=0;s<(1<<n);s++)
{
for(int i=0;i<n+m;i++)
{
f[s][i]=w[s][i]=inf;g[s][i]=-inf;
for(int j=0;j<n;j++)
if(s&(1<<j))
w[s][i]=min(w[s][i],get(a[i],a[j]));
}
}
for(int i=0;i<n;i++) f[1<<i][0]=0;
for(int i=0;i<m;i++) g[0][i]=1;
for(int s=0;s<(1<<n);s++)
{
//transitions with f
for(int i=0;i<=m;i++)
if(f[s][i]<inf)
{
for(int j=0;j<n;j++)
if(!(s&(1<<j)))
f[s|(1<<j)][i]=
min(f[s|(1<<j)][i],f[s][i]+w[s][j]);
for(int j=0;j<m;j++)//j will not be a landmark that is visited
if(f[s][i]+w[s][j+n]<=a[j+n].t)
g[s][j]=max(g[s][j],i+1);
}
//transitions with g
for(int i=0;i<m;i++)
if(g[s][i]>=0)
{
for(int j=0;j<n;j++)
if(!(s&(1<<j)))
f[s|(1<<j)][g[s][i]]=min(f[s|(1<<j)][g[s][i]]
,a[i+n].t+min(get(a[i+n],a[j]),w[s][j]));
for(int j=i+1;j<m;j++)//to guarantee j is not visited
if(min(get(a[i+n],a[j+n]),w[s][j+n])+a[i+n].t<=a[j+n].t)
g[s][j]=max(g[s][j],g[s][i]+1);
ans=max(ans,g[s][i]);
}
}
printf("%d
",ans);
}
G. Try Booking
题目描述
大保( t J)发廊近期的生意火爆，对于 (n) 天的营业期，大保收到了 (m) 个订单，表示在 ([l_i,r_i]) 让阿七剪头发。大保会按收到订单的顺序处理，如果当前订单和以前订单没有冲突，就接这个订单。
大保想知道如果忽略 (r_i-l_i+1<x) 的订单最后阿七的营业天数是多少，对于所有 (xin[1,n]) 都要求出答案。
(nleq 5cdot 10^4,mleq 10^5)
解法
我真的没观察出什么性质，当前订单的选取对后面的影响实在是太大了。
有一个重要的 ( t observation)：如果我们每次都能直接找到下一个接的订单，那么总共接订单的数量是 (sum_{i=1}^nfrac{n}{i}=O(nlog n))
也就是说只要我们能快速找到下一个订单是谁复杂度就对了，由于是一个二维偏序问题，那么直接上一个树套树即可，知道订单之后就把当前区间分成两半递归下去，相当于一个分治查的过程。
时间复杂度 (O(nlog^3n))，原谅我没有写代码。
H. Hopping Around the Array
题目描述
小飞在长度为 (n) 的数组上面玩游戏，位置 (i) 有一个跳跃距离 (a_i)，小飞可以选择通过一步跳跃降落到 ((i,i+a_i]) 的任意一个地点。但是它觉得直接跳太累了，所以阿七可以帮助它移走任意 (k) 个位置，剩下的位置会重新编号，但是 (a) 不会改变。
一共有 (q) 次游戏，每次从 (l) 处出发，(r) 处结束，能移走 (k) 个位置，但是不能移走起点和终点。作为世界上最强的飞鸡，小飞想知道最小跳跃次数。
(1leq n,qleq 20000,1leq lleq rleq n,0leq kleq min(30,r-l))
解法
首先考虑一个简化的问题，如果没有移走位置的操作怎么最小化飞行次数。
你肯定会说 (dp)，这固然很好，但是这种方法无法扩展到本题的情况。不妨贪心一点考虑，肯定不能无脑跳最远的地方，但是我们可以让我们的跳跃范围最远，也就是我们找到 (a_i+i) 最大的位置直接跳它，这种贪心在最后一步的跳远除外都是使用的，而且它的可扩展性显然优于 (dp)
然后考虑有了移走操作怎么办，移走操作的本质是增加跳跃范围，也就是说只有你想跳到 (a[i]+i+x) 的时候你才会移走 (x) 个格子，否则无需移走格子也能跳到你想要的地方。
如果询问只有一组现在是可以解决的，但是本题是多组询问。回忆我省选的惨痛经历，这种既有步数移动又是多组询问的问题是和倍增很搭的，因为 (k) 很小而且需要分配移动操作所以可以把他加入状态中，那么不难定义出倍增数组 (f[i][j][k]) 表示从位置 (i) 开始跳 (2^j) 步，移走 (k) 个格子能到达的最远范围。
考虑转移，首先要枚举前一半用掉的删除次数是 (x)，那么用 (st) 表找到 ([i,f[i][j-1][x]]) 这个范围中最大 (a_p+p) 的 (p)，然后就可以从 (p) 完成后半段的跳跃，最远的范围就是 (f[p][j-1][k-x])，这样就完成了 (f[i][j][k]) 的转移。我们初始化 (f[i][0][x]=i+a[i]+x) 即可。
现在考虑怎么用这个倍增数组回答询问，大体的思路是用 ( t lca) 后半段的那种方法，我们多跳 (2^x) 看会不会跳到 (r)，如果没有跳到 (r) 了那么就把 (2^j) 计入 (ans)，最后把 (ans+1) 输出即可。
由于我们要分配移动次数所以我们定义 (g[i]) 表示从 (l) 开始跳若干步，用掉的移动次数是 (i) 的最远范围，转移就枚举新跳的 (2^x) 步中用掉了移动次数 (j)，找到 ([l,g[i]]) 中最大 (p+a_p) 的 (p)，用 (f[p][x][j]) 转移到辅助数组 (tmp[i+j]) 中即可。
注意要限制不能跳出 (n)，要不然下标会有问题，时间复杂度 (O((n+q)cdot k^2cdot log n))
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 20005;
const int N = 31;
#define make make_pair
#define pii pair<int,int>
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,q,a[M],lg[M],f[M][20][N],g[N],tmp[N];pii dp[M][20];
//f[i][j][k]:stand for the max (l+al) can reach from i through 2^j jumps and k delete
int ask(int l,int r)//ask the l of max (l+al)
{
int k=lg[r-l+1];
return max(dp[l][k],dp[r-(1<<k)+1][k]).second;
}
void init()
{
for(int j=1;(1<<j)<=n;j++)//st
for(int i=1;i+(1<<j)-1<=n;i++)
dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
for(int i=1;i<=n;i++)
for(int j=0;j<N;j++)
f[i][0][j]=min(n,i+a[i]+j);//this "min" is necessary
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i<=n;i++)//please don't limit the range of i
for(int k=0;k<N;k++)
for(int x=0;x<=k;x++)
{
int t=ask(i,f[i][j-1][x]);//find the position
f[i][j][k]=max(f[i][j][k],f[t][j-1][k-x]);
}
}
signed main()
{
n=read();q=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
dp[i][0]=make(min(n,a[i]+i),i);
if(i>1) lg[i]=lg[i>>1]+1;
}
init();
while(q--)
{
int l=read(),r=read(),k=read(),ans=0;
if(l==r) {puts("0");continue;}
if(l+a[l]+k>=r) {puts("1");continue;}
for(int i=0;i<=k;i++) g[i]=l;
for(int x=15;x>=0;x--)
{
if((1<<x)>n) continue;
for(int i=0;i<=k;i++) tmp[i]=g[i];
for(int i=0;i<=k;i++)
{
int t=ask(l,g[i]);
for(int j=0;i+j<=k;j++)
tmp[i+j]=max(tmp[i+j],f[t][x][j]);
}
int fl=0;
for(int i=0;i<=k;i++)
if(tmp[i]>=r) fl=1;
if(fl) continue;
for(int i=0;i<=k;i++) g[i]=tmp[i];
ans+=(1<<x);
}
printf("%d
",ans+1);
}
}