【题目记录】——2021“MINIEYE杯”中国大学生算法设计超级联赛（3）

以你之姓@ 2022-09-01 14:46 99阅读 0赞

### 2021“MINIEYE杯”中国大学生算法设计超级联赛（3） ###

*  1001 Bookshop 树链剖分，DFS序
 *  1002 Destinations 树链剖分，树状数组
 *  1003 Forgiving Matching
 *  1004 Game on Plane 数学，高精度
 *  1007 Photoshop Layers 思维
 *  1009 Rise in Price DP
 *  1011 Segment Tree with Pruning 模拟，思维

题目集地址【 [2021“MINIEYE杯”中国大学生算法设计超级联赛（3）][2021_MINIEYE_3]】

题目集地址【[2021“MINIEYE杯”中国大学生算法设计超级联赛（3）][2021_MINIEYE_3 1]】  
这次题目集我们只做出两个简单题1007和1011

# 1001 Bookshop 树链剖分，DFS序 #

题目地址[1001 Bookshop][]  
题意：给一棵树，每个节点有一本书，有一个价格，给出两个节点x,y，找到x和y之间的最短路径，一开始有z元，从x走到y，如果当前结点的书的价格小于等于z，就买下来，否则就不买，问最后剩下多少钱。  
思路：对树进行轻重链剖分并求出 DFS 序，在 DFS 的过程中先 DFS 一个点的重儿子，再DFS它的轻儿子们，那么每条重链在 DFS 序上是连续的。对于每个询问 (x; y; z)，令 t 为 x 和 y 的LCA，那么从 x 出发走到 t 的过程在 DFS 序里对应从右往左的 O(log n) 个区间，从 t 出发走到y的过程也对应 DFS 序里从左往右的 O(log n) 个区间。考虑离线询问，把所有询问分成两个步骤来统一处理：

*  对于每个询问，处理从 x 往上走到 LCA 的过程，即从右往左拆成 O(log n) 个区间。
 *  对于每个询问，处理从 LCA 往下走到 y 的过程，即从左往右拆成 O(log n) 个区间。  
    暂时没找到题解，自己也没空写。。

# 1002 Destinations 树链剖分，树状数组 #

题目地址[1002 Destinations][]  
题意：有n个小镇在某城，标记为1~n，由n-1条道路连接形成一棵树，有m个游客准备从一个小镇开始他的旅程。然而都没有决定自己的终点。一般情况下，一个旅客会有3个计划，第i个旅客将在第 e i j e\_\{ij\} eij镇结束旅程花费 c i j c\_\{ij\} cij美元。当一个游客作出决定后，他沿最短路径到达目的地并拜访路上的小镇。注意目的地可以和出发点一样，出发点和目的地都会参观。两个计划可能有相同的目的地但不同的花费。  
你的任务是帮助游客选择计划，保证每个城市最多一个游客拜访，总花费要最小，或者判断没有这样的解决方案。  
思路：现在问题转化为：给定若干条树链，选择总收益最大的一些链使得两两没有公共点。这是经典问题，一个简单的解法是考虑其对偶问题：在树上选择尽量少的点，每个点可以重复选多次，满足每条树链上选择的点数至少为其收益值。那么对偶问题可以贪心解决：从深到浅 DFS这棵树，在考虑 x 点时，处理所有 LCA 为 x 的链 (u; v; w)，统计 u 到 v 路径上选择的点数cnt，若不足 w，则在 LCA（即 x 点）处补充 w − cnt 个点。因此需要一个数据结构支持单点修改、查询链和，令 fx 表示 x 到根路径上的点权和，那么单点修改对 f 的影响是子树加，可以通过树状数组维护差分实现，时间复杂度 O((n + m) log n)

这个问题没弄很明白，先整个题解下来。  
AC代码：

#include<cstdio>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int N=200010,M=100010*3,VAL=1000000;
    int Case,n,m,i,j,x,y,z,g[N],v[N<<1],nxt[N<<1],ed;
    int f[N],d[N],size[N],son[N],top[N],st[N],en[N],dfn;
    int G[N],X[M],Y[M],W[M],NXT[M],ED;
    ll base,ans,bit[N];
    inline void add(int x,int y){ v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
    inline void ADD(int o,int x,int y,int z){ X[++ED]=x;Y[ED]=y;W[ED]=z;NXT[ED]=G[o];G[o]=ED;}
    void dfs(int x,int y){ 
      f[x]=y;
      d[x]=d[y]+1;
      size[x]=1;
      for(int i=g[x];i;i=nxt[i])if(v[i]!=y){ 
        dfs(v[i],x);
        size[x]+=size[v[i]];
        if(size[v[i]]>size[son[x]])son[x]=v[i];
      }
    }
    void dfs2(int x,int y){ 
      top[x]=y;
      st[x]=++dfn;
      if(son[x])dfs2(son[x],y);
      for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]&&v[i]!=son[x])dfs2(v[i],v[i]);
      en[x]=dfn;
    }
    inline int lca(int x,int y){ 
      while(top[x]!=top[y]){ 
        if(d[top[x]]<d[top[y]])swap(x,y);
        x=f[top[x]];
      }
      return d[x]<d[y]?x:y;
    }
    inline ll ask(int x){ 
      ll ret=0;
      x=st[x];
      for(;x;x-=x&-x)ret+=bit[x];
      return ret;
    }
    inline void modify(int x,ll p){ for(;x<=n;x+=x&-x)bit[x]+=p;}
    void go(int x){ 
      for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x])go(v[i]);
      ll now=0;
      for(int i=G[x];i;i=NXT[i]){ 
        ll C=base+VAL-W[i],tmp=ask(X[i])+ask(Y[i])+now;
        if(C>tmp)now+=C-tmp;
      }
      ans+=now;
      modify(st[x],now);
      modify(en[x]+1,-now);
    }
    int main(){ 
      scanf("%d",&Case);
      while(Case--){ 
        scanf("%d%d",&n,&m);
        for(ed=ED=dfn=ans=i=0;i<=n;i++)g[i]=f[i]=d[i]=size[i]=son[i]=top[i]=G[i]=bit[i]=0;
        for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
        dfs(1,0);
        dfs2(1,1);
        for(i=1;i<=m;i++){ 
          scanf("%d",&x);
          for(j=0;j<3;j++)scanf("%d%d",&y,&z),ADD(lca(x,y),x,y,z);
        }
        base=1LL*m*VAL;
        go(1);
        if(ans/base==m){ 
          ans%=base;
          ans=base-ans;
        }else ans=-1;
        printf("%lld\n",ans);
      }
    }

# 1003 Forgiving Matching #

题目地址[1003 Forgiving Matching][]  
题意：两个字符串匹配，如果长度相同且相同位置的字符相同，则认为两字符串是匹配的。现在两字符串中的字符有k次不匹配的机会，也就是说两个长度相同的字符串相同位置有小于等于k个字符不同也认为两字符串匹配，同时字符创中会有通配符。给两个字符串S和T，求S的子串中与T字符串匹配的个数k=0~|T|的情况下，S的两个子串起始位置不同，就认为是不同的子串。  
思路：对于 S 的每个长度为 m 的子串，统计其与 T 匹配的位置数 fi，即可得到该子串被认为匹配的最小的 k 值。两个字符匹配当且仅当它们字符相等，或者至少有一个是通配符。假设没有通配符的存在，枚举 0 到 9 每个字符 c，那么如果 Si = Tj = c，则 fi−j 应该加上 1，可以翻转T 串后通过 FFT 求出 f。现在考虑通配符的影响， S 一个子串与 T 通过通配符匹配的位置数 = S 对应子串中通配符的数量 +T 中通配符的数量 − 对应位置都是通配符的位置数量。 S 对应子串中通配符的数量可以使用前缀和求得，对应位置都是通配符的位置数量同样可以通过 FFT 求得。  
时间复杂度 O(11n log n)  
需要用到快速傅里叶变换的加速，对于我现在来说有点困难先不详细说，先把代码贴上。

#include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int N=524305;
    const double pi=acos(-1.0);
    struct comp{ 
      double r,i;comp(double _r=0,double _i=0){ r=_r,i=_i;}
      comp operator+(const comp&x)const{ return comp(r+x.r,i+x.i);}
      comp operator-(const comp&x)const{ return comp(r-x.r,i-x.i);}
      comp operator*(const comp&x)const{ return comp(r*x.r-i*x.i,r*x.i+i*x.r);}
      comp conj(){ return comp(r,-i);}
    }w[N],ww[N],A[N],B[N];
    int pos[N],Case,n,m,k,i,j,o,s[N],f[N],ans[N];char a[N],b[N];
    inline void FFT(comp a[],int n,int o){ 
      for(int i=1;i<n;i++)if(i<pos[i])swap(a[i],a[pos[i]]);
      for(int d=0,k=__builtin_ctz(n);(1<<d)<n;d++){ 
        int m=1<<d,m2=m<<1;
        for(int i=0;i<n;i+=m2)for(int j=0;j<m;j++){ 
          comp&A=a[i+j+m],&B=a[i+j],t=(o==1?w[j<<(k-d)]:ww[j<<(k-d)])*A;
          A=B-t;B=B+t;
        }
      }
      if(o==-1)for(int i=0;i<n;i++)a[i].r/=n;
    }
    int main(){ 
      scanf("%d",&Case);
      while(Case--){ 
        scanf("%d%d%s%s",&n,&m,a,b);
        reverse(b,b+m);
        for(k=1;k<=n+m-2;k<<=1);
        j=__builtin_ctz(k)-1;
        for(i=0;i<k;i++)pos[i]=pos[i>>1]>>1|((i&1)<<j);
        for(i=0;i<k;i++)w[i]=comp(cos(pi*i/k),sin(pi*i/k));
        for(i=0;i<k;i++)ww[i]=w[i],ww[i].i*=-1;
        for(i=0;i<n;i++){ 
          s[i]=0;
          if(i)s[i]+=s[i-1];
          if(a[i]=='*')s[i]++;
        }
        int cnt=0;
        for(i=0;i<m;i++)if(b[i]=='*')cnt++;
        for(i=m-1;i<n;i++){ 
          f[i]=cnt+s[i];
          if(i>=m)f[i]-=s[i-m];
        }
        for(o=0;o<=10;o++){ 
          char target=o+'0';
          if(o==10)target='*';
          for(i=0;i<k;i++)A[i]=comp(0,0);
          for(i=0;i<n;i++)if(a[i]==target)A[i].r=1;
          for(i=0;i<m;i++)if(b[i]==target)A[i].i=1;
          FFT(A,k,1);
          for(i=0;i<k;i++){ 
            j=(k-i)&(k-1);
            B[i]=(A[i]*A[i]-(A[j]*A[j]).conj())*comp(0,-0.25);
          }
          FFT(B,k,-1);
          for(i=m-1;i<n;i++){ 
            int tmp=((int)(B[i].r+0.5));
            if(o<10)f[i]+=tmp;else f[i]-=tmp;
          }
        }
        for(i=0;i<=m;i++)ans[i]=0;
        for(i=m-1;i<n;i++)ans[m-f[i]]++;
        for(i=0;i<=m;i++){ 
          if(i)ans[i]+=ans[i-1];
          printf("%d\n",ans[i]);
        }
      }
    }

# 1004 Game on Plane 数学，高精度 #

题目地址【[1004 Game on Plane][]】  
题意：Alice和Bob玩游戏，Alice从给出的直线中选k条直线，Bob自己画一条直线，Alice要让Bob的直线与选出的直线交点最多，Bob画的直线要与选出的交点最少  
思路：就是Alice尽量先选不平行的线  
AC代码：

#include<cstdio>
    #include<algorithm>
    using namespace std;
    typedef pair<int,int>P;
    const int N=100005;
    int Case,n,i,j,k,f[N];
    P a[N];
    inline int abs(int x){ return x>0?x:-x;}
    int gcd(int a,int b){ return b?gcd(b,a%b):a;}
    int main(){ 
      scanf("%d",&Case);
      while(Case--){ 
        scanf("%d",&n);
        for(i=1;i<=n;i++){ 
          int x1,y1,x2,y2;
          scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
          int dx=x2-x1,dy=y2-y1;
          if(dx==0)dy=1;
          else if(dy==0)dx=1;
          else{ 
            if(dx<0)dx=-dx,dy=-dy;
            int d=gcd(abs(dx),abs(dy));
            dx/=d,dy/=d;
          }
          a[i]=P(dx,dy);
        }
        sort(a+1,a+n+1);
        for(i=1;i<=n;i++)f[i]=0;
        for(i=1;i<=n;i=j){ 
          for(j=i;j<=n&&a[i]==a[j];j++);
          for(k=1;k<=j-i;k++)f[k]++;
        }
        for(i=j=1;i<=n;i++){ 
          while(!f[j])j++;
          f[j]--;
          printf("%d\n",i-j);
        }
      }
    }

# 1007 Photoshop Layers 思维 #

题目地址【[1007 Photoshop Layers][]】  
题意：  
按照规则计算RGB，加图层，涂层有两种类型，一种直接覆盖原来图层，一种是这一层的RGB值加上之前图层的RGB值，如果超过255，就等于255，最开始背景图的RGB是(0,0,0),测试数据给出的RGB值是16进制。  
思路：  
就是简单的计算关键是处理16进制数，用printf和scanf就很方便。

AC代码：

#include <bits/stdc++.h>
    #define lmax 200005
    
    using namespace std;
    int biao[lmax];
    int color1[lmax];
    int color2[lmax];
    int color3[lmax];
    int jilu[lmax];
    
    int main()
    { 
        int t,n,q,l,r;
        scanf("%d",&t);
        while(t--)
        { 
            scanf("%d%d",&n,&q);
            int xi=0;
            for(int i=1; i<=n; i++)
            { 
                scanf("%d %x",&biao[i],&color1[i]);
                color3[i]=color1[i]%256;
                color1[i]=color1[i]/256;
                color2[i]=color1[i]%256;
                color1[i]=color1[i]/256;
                if(biao[i]==1)
                { 
                    jilu[xi]=i;
                    xi++;
                }
                else
                { 
                    color1[i]+=color1[i-1];
                    color2[i]+=color2[i-1];
                    color3[i]+=color3[i-1];
                }
            }
    
    
    
            for(int k=1; k<=q; k++)
            { 
                scanf("%d%d",&l,&r);
                int i=l;
                int bb=upper_bound(jilu,jilu+xi,r)-jilu;
                if(biao[r]==1)
                { 
                    i=r;
                }
                else
                { 
                    if(jilu[bb-1]>=l)
                        i=jilu[bb-2];
                    else
                        i=l;
                }
                if(biao[i]==1)
                    printf("%02X%02X%02X\n",min(color1[r],255),min(color2[r],255),min(color3[r],255));
                else
                    printf("%02X%02X%02X\n",min(color1[r]-color1[i-1],255),min(color2[r]-color2[i-1],255),min(color3[r]-color3[i-1],255));
            }
        }
        return 0;
    }

# 1009 Rise in Price DP #

题目地址[1009 Rise in Price][]  
题意：一个二维地图，每一个坐标有固定的钻石数量和升值价格，只能往右或往下走，问走到最右下角的格子时，总的钻石的价格最多是多少。  
思路：设 f\[i\]\[j\]\[k\] 表示从 (1, 1) 走到 (i, j)，一路上收集了 k 个钻石时，钻石的单价最高能涨到多少，  
则 ans = max(k × f\[n\]\[n\]\[k\])。  
对于固定的 (i, j) 来说，考虑两个状态 f\[i\]\[j\]\[x\]和 f\[i\]\[j\]\[y\]，其中 x < y，如果 f\[i\]\[j\]\[x\] ≤ f\[i\]\[j\]\[y\]，则  
状态 f\[i\]\[j\]\[x\] 一定不可能发展为最优解，可以剔除。对于每个 (i, j)，用列表按照 k 升序保存所有  
状态，并剔除不可能成为最优解的状态即可。  
随机数据下当 n = 100 时，单个 (i, j) 的有效状态的峰值 k 大约为几千。时间复杂度  
 O ( n 2 k ) O(n^2k) O(n2k)

#include<cstdio>
    #include<algorithm>
    #include<vector>
    using namespace std;
    typedef long long ll;
    typedef pair<int,int>P;
    typedef vector<P>V;
    const int N=105;
    int Case,n,m,i,j,k,a[N][N],b[N][N];ll ans;V f[N][N];P pool[1000005];
    inline void ext(const P&t){ 
      while(m&&pool[m].second<=t.second)m--;
      if(!m||pool[m].first<t.first)pool[++m]=t;
    }
    inline void merge(const V&A,const V&B,V&C){  //剔除掉A和B中不可能发展为最优解的情况
      int ca=A.size(),cb=B.size(),i=0,j=0;
      m=0;
      while(i<ca&&j<cb)ext(A[i].first<B[j].first?A[i++]:B[j++]);
      while(i<ca)ext(A[i++]);
      while(j<cb)ext(B[j++]);
      C.resize(m);
      for(i=0;i<m;i++)C[i]=pool[i+1];
    }
    int main(){ 
      scanf("%d",&Case);
      while(Case--){ 
        scanf("%d",&n);
        for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&a[i][j]);
        for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&b[i][j]);
        f[1][1].resize(1);
        f[1][1][0]=P(a[1][1],b[1][1]);
        for(i=1;i<=n;i++)for(j=1;j<=n;j++){ 
          if(i==1&&j==1)continue;
          if(i==1)f[i][j]=f[i][j-1];
          else if(j==1)f[i][j]=f[i-1][j];
          else merge(f[i-1][j],f[i][j-1],f[i][j]);
          for(k=0;k<f[i][j].size();k++){ 
            f[i][j][k].first+=a[i][j];
            f[i][j][k].second+=b[i][j];
          }
        }
        ans=0;
        for(i=0;i<f[n][n].size();i++)ans=max(ans,1LL*f[n][n][i].first*f[n][n][i].second);
        printf("%lld\n",ans);
      }
    }

# 1011 Segment Tree with Pruning 模拟，思维 #

题目地址【[1011 Segment Tree with Pruning][]】  
题意：  
按照题目给定规则建线段树，问建成的树有多少节点。给定区间长度n和限制值k，在建树的过程中进行判断，如果节点区间长度大于k则为此节点向下建子树，否则不建子树。  
思路：  
先找到节点代表的区间长度都大于等于k的最后一层，这样这一层上面的节点都是建好的，根据公式计算上面所有节点数。然后判断这一层中有多少长度大于k的节点，乘2加上前面的值即可。  
AC代码：

#include <bits/stdc++.h>
    using namespace std;
    unsigned long long qpow(long long a, int n){ 
    	unsigned long long ans = 1;
    	while(n){ 
    		if(n&1)
    		{ 
    			ans *= a;
    		}
    		a *= a;
    		n >>= 1;
    	}
    	return ans;
    }
    int main()
    { 
        cin.sync_with_stdio(0);
        cin.tie(0);
    
        int t;
        cin >> t;
        unsigned long long res;
        while(t--)
        { 
            res = 0;
            unsigned long long k, n;
            cin >> k >> n;
            if(n == 1)
            { 
                cout << 2 * k - 1 << endl;
                continue;
            }
            unsigned long long c;
            c = k / n;
            int lay = log2(c);
            res += (qpow(2,lay + 1)-1);
            if((c = k / qpow(2, lay)) > n)
            { 
                res += qpow(2, lay) * 2;
            }
            else if((c = k / qpow(2, lay)) == n)
            { 
                res += 2 * (k % qpow(2, lay));
            }
            cout << res << endl;
        }
        return 0;
    }

[2021_MINIEYE_3]: https://acm.hdu.edu.cn/search.php?field=problem&key=2021%A1%B0MINIEYE%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A83%A3%A9&source=1&searchmode=source
[2021_MINIEYE_3 1]: https://acm.hdu.edu.cn/contests/contest_show.php?cid=986
[1001 Bookshop]: https://acm.hdu.edu.cn/showproblem.php?pid=6973
[1002 Destinations]: https://acm.hdu.edu.cn/showproblem.php?pid=6974
[1003 Forgiving Matching]: https://acm.hdu.edu.cn/showproblem.php?pid=6975
[1004 Game on Plane]: https://acm.hdu.edu.cn/showproblem.php?pid=6976
[1007 Photoshop Layers]: https://acm.hdu.edu.cn/showproblem.php?pid=6979
[1009 Rise in Price]: https://acm.hdu.edu.cn/showproblem.php?pid=6981
[1011 Segment Tree with Pruning]: https://acm.hdu.edu.cn/showproblem.php?pid=6983