最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

Codeforces Round #857 Div.1 1801 E F 题解

来源：博客园


(相关资料图)

点我看题

1801 E. Gasoline prices

先来看这样一道题：一个长为n的字符串，每个字符都是一个英文小写字母。有q个限制，每个限制形如\(x\ y\ len\)，表示从位置x与从位置y开始的长度为len的子串相同。要求出满足所有限制的字符串的数量。这题和本题1801E是很像的，只是1801E要对所有限制的每个前缀都求答案，且问题移到了树上。

来看看这个字符串题的做法。先对这个串建立st表，\(f_{i,j}\)表示左端点在i，长度为\(2^j\)的子串。我们对st表的每层(\(f_{*,j}\)为一层)维护一个并查集，如果\(f_{a,j}\)与\(f_{b,j}\)在第j层的并查集中被连接，就表示从a开始和从b开始的长度为\(2^j\)的子串必须相等。对于每条限制，令\(lev=\lfloor lg(len) \rfloor\)，在第lev层的并查集中把\(f_{x,lev}与f_{y,lev}\)连接，把\(f_{x+len-2^{lev},lev}与f_{y+len-2^{lev},lev}\)连接。处理完所有的限制后，从大到小枚举所有j，然后枚举i，令\(f_{i,j}\)在第j层并查集中的根为\(f_{k,j}\)，那么就在第j-1层中连接\(f_{i,j-1}和f_{k,j-1}\)，以及\(f_{i+2^{j-1},j-1}和f_{k+2^{j-1},j-1}\)。这样就把所有限制信息都像线段树一样pushdown到了第0层，只要检查第0层的并查集连通块个数就知道有多少个等价类了。答案是\(26^{等价类个数}\)。

然后这个字符串题如果要对q个限制的每个前缀都求答案的话也是很容易的，可以每次添加一个限制后直接不断pushdown到第0层，并在修改第0层时维护连通块个数。每一层的并查集最多被修改n次(如果发现并查集中当前要连接的两个位置已经连通，就直接退出，不继续pushdown)，如果并查集复杂度算\(logn\)的话，总复杂度\(O(nlog^2n)\)。

再回到原问题。其实可以直接把上面的st表搬到树上，\(f_{i,j}\)表示从点i向祖先方向的前\(2^j\)个点构成的链，\(g_{i,j}\)表示从点i向祖先方向的前\(2^j\)个点构成的链reverse后的结果，第j层的并查集中包含\(f_{*,j}\)和\(g_{*,j}\)中的所有元素(其中第0层只包括\(f_{*,0}\)中的元素)，可以给它们从1到2n编个号。对于一个限制，我们要求两条链上的点的值一一对应相等，仍然是在并查集中直接合并，只是这里要以两条链的LCA为分界分成3部分，其中一部分是把一个\(f_{*,*}和一个g_{*,*}\)合并，还有两部分是把两个f合并。并查集中的每一层最多被合并\(2n\)次，所以总复杂度仍然是\(O(nlog^2n)\)(有点卡常)。如果不仔细想无脑写的话很容易写得很烦，下面的代码参考了platelet的写法。

点击查看代码
#include #define rep(i,n) for(int i=0;i0){if(a&1) (ret*=res)%=MOD;a>>=1;(res*=res)%=MOD;}return ret;}LL n,q,par[200010][20],l[200010],r[200010],dep[200010];LL ans=1;vector  g[200010];void dfs(LL pos,LL d){  dep[pos]=d;  rep(i,g[pos].size()) dfs(g[pos][i],d+1);}LL getLCA(LL x,LL y){  for(int i=18;i>=0;--i) if(par[x][i]>0&&dep[par[x][i]]>=dep[y]) x=par[x][i];  for(int i=18;i>=0;--i) if(par[y][i]>0&&dep[par[y][i]]>=dep[x]) y=par[y][i];  if(x==y) return x;  for(int i=18;i>=0;--i) if(par[x][i]!=par[y][i]) x=par[x][i],y=par[y][i];  return par[x][0];}LL getAnces(LL x,LL y){rep(i,19) if(y&(1<>n;  for(int i=2;i<=n;++i) scanf("%lld",&par[i][0]),g[par[i][0]].pb(i);  rep(i,19) repn(j,n) par[j][i+1]=par[par[j][i]][i];  repn(i,n) scanf("%lld %lld",&l[i],&r[i]),(ans*=(r[i]-l[i]+1))%=MOD;  dfs(1,0);  cin>>q;  rep(qn,q)  {    LL a,b,c,d,ab,cd;    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);    if(ans==0)    {      puts("0");      continue;    }    ab=getLCA(a,b);cd=getLCA(c,d);    if(dep[a]-dep[ab]

1801 F. Another n-dimensional chocolate bar

\(k\le 1e7\)，所以可能会想到去枚举把b从小到大排序，然后去掉所有1之后得到的那个序列(最多有\(logk\)个元素)。但在这些枚举出的序列中并不是所有都可能成为最优的，如果我们可以把其中的一个数-1，使得序列所有元素的乘积仍然\(\ge k\)，那它就肯定不是最优的。这样一来就大大减少了可能序列的个数。

进一步看看能不能枚举一些更简单的东西。假设当前要求\(\prod b_i\ge k"\)，我们看看\(b_1\)可能的取值有哪些。令枚举出的\(b_1\)的值为\(v\)，\(v"=\lceil \frac {k"}v \rceil\)。则必须满足\(\lceil \frac {k"}{v"} \rceil=v\)，否则把v减1，此时的\(v和v"\)仍然满足条件，显然更优。在枚举v时，只要枚举所有满足\(v\le v"\)的v就能找到所有可能的\((v,v")\)了，因为\(v和v"\)也可以交换。我们用暴搜预处理所有可能出现的\(k"\)及其对应的可能出现的\((v,v")\)，方法为先对输入的k搜索可能的\(v和v"\)，然后再把\(v和v"\)作为可能的\(k"\)继续搜索递归下去(需要记忆化)，具体实现方法见代码。搜出来后会发现可能的\(k"\)只有7000种左右，可能的\((v,v")\)总数则不超过\(10^6\)个。令\(s_i\)表示当i作为上面的\(k"\)时，所有\((v,v")\)的集合。

所以可以令\(f_{i,j}\)表示处理到a中的第i个数，要求\(\prod_{p=i}^n b_p\ge j\)时的最优答案。对\(f_{i,j}\)进行主动转移时只要枚举\(s_j\)中的所有元素就行了。发现这个数组的第一维完全没用，可以删掉，所以空间也没问题了。

时间复杂度\(O(10^6n)\)左右。

点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define pb push_back#define mpr make_pairvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;LL n,k,a[110];bool vis[10000010];vector  possi;vector  > trans;double dp[10000010],mul[10000010];void dfs(LL x){  if(vis[x]) return;  possi.pb(x);vis[x]=true;  for(LL dv=1;;++dv)  {    LL res=(x+dv-1)/dv;    if(dv>res) break;    dfs(dv);dfs(res);    if((x+res-1)/res!=dv) continue;    if(dv>1) trans.pb(mpr(x,mpr(dv,res)));    if(dv!=res&&res>1) trans.pb(mpr(x,mpr(res,dv)));  }}int main(){  fileio();    cin>>n>>k;  dfs(k);  LL mx=1;  rep(i,n) scanf("%lld",&a[i]),mx=min(mx*a[i],(LL)1e11);  if(mx

关键词：