D. Excellent Arrays
题目描述
对于一个长度为 (n) 的数组 (a)，定义 (F(a)) 为满足 (1leq i<jleq n) 且 (a_i+a_j=i+j) 的二元组个数。
求有多少满足下列条件的数列 (a)：
- 对于所有 (a_i)，满足 (a_i ot=i)
- (lleq a_ileq r)
- (F(a)) 是所有长度为 (n) 的合法数列中的最大权值。
(nleq 2cdot 10^5)
解法
我们考虑什么情况下 (a_i+a_j=i+j) 的对数最大化，先移项，设 (k_i=a_i-i)，那么问题是满足 (k_i=-k_j) 的数对个数，所有 (a_i ot=i) 可以翻译成 (k_i ot=0)，那么最大权值一定是一半的数拿了正的 (k)，一半的数拿了负的 (k)
值域的限制在 (a_i) 上面，我们考虑把限制转到 (k) 上面，我们先考虑什么情况每个数既能选正又能选负，如果选负 (1) 是最容易爆出 (l) 的，如果选正 (n) 是最容易爆出 (r) 的，那么有下列的不等式：
那么当所有数都能任选的时候 (k) 有 (min(l-1,r-n)) 种合法取值，再乘上 ({nchoose n/2}) 即可（(n) 为奇还要考虑 ({nchoose n/2+1})）
现在如果 (k) 增大，有数就只能选正或者选负了，而且只能选正的一定是一段前缀，只能选负的一定是一段后缀，我们可以把端点算出来，设 ([lg,rg]) 表示现在能任选的端点：
在这些任选的数中选出为负的即可，因为 (k) 增大 (n) 左右组合数方案数就是 (0) 了，所以时间复杂度 (O(n))
总结
两个点的限制，把有关量拆到等号两边。算方案时，考虑何处最先去到端点值。
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 200005;
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,m,l,r,ans,fac[M],inv[M];
void init(int n)
{
fac[0]=inv[0]=inv[1]=1;
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;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
}
int C(int n,int m)
{
if(n<0 || m<0 || n<m) return 0;
return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
void work()
{
n=read();l=read();r=read();
m=n/2;ans=0;
int t=min(1-l,r-n);
ans=t*C(n,m)%MOD;
if(n%2) ans=(ans+t*C(n,m+1))%MOD;
for(int k=t+1;;k++)
{
int lg=max(1ll,k+l),rg=min(n,r-k);
if(lg>rg+1) break;//attention
ans=(ans+C(rg-lg+1,m-(lg-1)))%MOD;
if(n%2) ans=(ans+C(rg-lg+1,m+1-(lg-1)))%MOD;
}
printf("%lld
",(ans+MOD)%MOD);
}
signed main()
{
T=read();init(2e5);
while(T--) work();
}
E. Stringforces
题目描述
给一个长度为 (n) 的字符集为 (k) 的串，把问号替换成小写字符，使得每个字符最长连续段的最小值最大。
(nleq 2cdot 10^5,kleq 17)
解法
不难想到二分答案，检查的时候题目都告诉你了要状压（(kleq 17)），那么就想状压呗。
你可能不知道状压要干什么，可以逆向思维，状压的在这道题的功能应该是把枚举阶乘的 (n!) 降为 (2^{n})，这说明这道题要枚举顺序，枚举什么顺序呢？枚举让每个字符合法的顺序，既然都有顺序了我们从左到右的让字符合法即可。
设 (g[i][j]) 表示从位置 (i) 开始要到哪里才能让字符 (j) 合法，这个可以简单预处理。
设 (dp[s]) 表示让字符集合 (s) 合法的最小右端点，转移：(dp[s|c]leftarrow g[dp[s]][c])
正向的思维过程是考虑枚举字符的顺序，然后从左到右把字符放进去。
总结
考试时候傻了，以为枚举顺序之后要贪心放进最好的位置中。其实是我对枚举的理解出了问题，枚举就是考虑所有情况取其最优，所以枚举的东西就不用贪心了，思维过程是：先枚举，以 (dp) 代替枚举。
#include <cstdio>
#include <iostream>
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,k,ls[20],p[M][20],dp[1<<20];char s[M];
int check(int d)
{
for(int i=0;i<k;i++) p[n][i]=ls[i]=n+1;
for(int i=n-1;i>=0;i--)
{
int mi=n;
if(s[i]!='?') ls[s[i]-'a']=i;
//这一段中都不能有其他字符
//考虑前缀和后缀最小值
//不行只能继承上一层
for(int j=0;j<k;j++)
{
if(i+d<=mi) p[i][j]=i+d;
else p[i][j]=p[i+1][j];
mi=min(mi,ls[j]);
}
mi=n;
for(int j=k-1;j>=0;j--)
{
if(i+d>mi) p[i][j]=p[i+1][j];
mi=min(mi,ls[j]);
}
}
dp[0]=0;
for(int s=1;s<(1<<k);s++)
{
dp[s]=n+1;
for(int i=0;i<k;i++)
if((s&(1<<i)) && dp[s^(1<<i)]<n)
dp[s]=min(dp[s],p[dp[s^(1<<i)]][i]);
}
return dp[(1<<k)-1]<=n;
}
signed main()
{
n=read();k=read();
scanf("%s",s);
int l=1,r=n,ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d
",ans);
}
F. Jumping Around
题目描述
有 (n) 个石头，第 (i) 个石头的位置是 (a_i)，青蛙可以跳到与当前石头距离 (in[d-k,d+k]) 的石头，初始时在石头 (s)，你知道 (d)，每次询问给你 (k) 和 (t)，问你是否能在此种情况下跳到石头 (t)
(n,qleq 2cdot 10^5)
解法
题目误导性极强，他给定了起点，我以为正解一定要从这个起点去扩展，结果根本不需要定起点的条件。所以思维要发散，敢于把以前想的全部推倒重来。
题目的重中之重是 (k)，你发现 (k) 越大每个点能跳到的范围越大，(u) 能到 (v) 当且仅当 (k) 正好到某个值的时候，我们把这个值看成边的权值，转化成图论模型后，问题是问 (s) 和 (t) 的连通性，所以可以考虑最小生成树，找到路径上权值最大的边即可。
关键是建出最小生成树，权值的秘密在点所以考虑 ( t Borůvka) 算法（这个我不展开）。维护一个 ( t set)，考虑到当前连通块后把所有点从 ( t set) 中拿掉，然后枚举点 ( t lower\_bound) 找权值最小的连出去的边，做完以后再插入回 ( t set) 中即可，时间复杂度 (O(nlog^2n))
总结
边权和点相关的最小生成树用 ( t Borůvka) 算法。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
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,q,s,d,a[M],mx[M],fa[M];map<int,int> mp;
struct node
{
int v,c;
};vector<node> g[M];
int Abs(int x)
{
return x>0?x:-x;
}
int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
void solve()
{
set<int> s;vector<int> v[M];
for(int i=1;i<=n;i++)
{
v[find(i)].push_back(i);
s.insert(a[i]);
}
for(int i=1;i<=n;i++)
{
if(!v[i].size()) continue;
for(int x:v[i]) s.erase(a[x]);
int mn=1e9,p=0,q=0;
for(int x:v[i])
{
for(int dx:{-d,d})
{
set<int>::iterator it=s.lower_bound(a[x]+dx);
if(it!=s.end())
{
int val=Abs(Abs(a[x]-(*it))-d);
if(val<mn) mn=val,p=x,q=mp[*it];
}
if(it!=s.begin())
{
it--;
int val=Abs(Abs(a[x]-(*it))-d);
if(val<mn) mn=val,p=x,q=mp[*it];
}
}
}
if(mn<1e9 && find(p)!=find(q))
{
fa[find(p)]=find(q);m--;
g[p].push_back(node{q,mn});
g[q].push_back(node{p,mn});
}
for(int x:v[i]) s.insert(a[x]);
}
}
void dfs(int u,int fa)
{
for(node x:g[u])
{
if(x.v==fa) continue;
mx[x.v]=max(x.c,mx[u]);
dfs(x.v,u);
}
}
signed main()
{
n=m=read();q=read();s=read();d=read();
for(int i=1;i<=n;i++)
a[i]=read(),fa[i]=i,mp[a[i]]=i;
while(m>1) solve();
dfs(s,0);
while(q--)
{
int u=read(),k=read();
if(mx[u]<=k) puts("YES");
else puts("NO");
}
}