2019牛客暑期多校训练营（第四场）

淡淡的烟草味﹌ 2023-06-04 11:58 91阅读 0赞

## Contest Info ##

--------------------

[Contest Link][]

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center;">Solved</th> 
   <th style="text-align:center;">A</th> 
   <th style="text-align:center;">B</th> 
   <th style="text-align:center;">C</th> 
   <th style="text-align:center;">D</th> 
   <th style="text-align:center;">E</th> 
   <th style="text-align:center;">F</th> 
   <th style="text-align:center;">G</th> 
   <th style="text-align:center;">H</th> 
   <th style="text-align:center;">I</th> 
   <th style="text-align:center;">J</th> 
   <th style="text-align:center;">K</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="text-align:center;">2/12</td> 
   <td style="text-align:center;">O</td> 
   <td style="text-align:center;">-</td> 
   <td style="text-align:center;"><span>$\varnothing$</span></td> 
   <td style="text-align:center;"><span>$\varnothing$</span></td> 
   <td style="text-align:center;">-</td> 
   <td style="text-align:center;">-</td> 
   <td style="text-align:center;">-</td> 
   <td style="text-align:center;">-</td> 
   <td style="text-align:center;"><span>$\varnothing$</span></td> 
   <td style="text-align:center;">O</td> 
   <td style="text-align:center;"><span>$\varnothing$</span></td> 
  </tr> 
 </tbody> 
</table>

*  O 赛中通过
 *  \$\\varnothing\$赛后通过
 *  !尝试了但失败了
 *  \-没有尝试

## Soulation ##

--------------------

### A：meeting ###

题意：  
给一棵树，给出\$k\$个节点表示一个人，求一个节点使所有人聚集在一起的时间最短。  
思路：  
和校赛的一道题目很像，校赛是给出若干只青蛙，然后求有多少个节点\$k\$步内能到达全部的青蛙。  
对于这道题，可以跑这些人的直径\$d\$，答案就是\$\\lceil \\frac d2 \\rceil\$。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=100010;
     
    int _,n,m,d,col[maxn],dis[maxn],s,t;
    vector<int> G[maxn];
     
    void dfs(int u,int p) {
        dis[u]=dis[p]+1;
        for(int i=0;i<G[u].size();i++) {
            int v=G[u][i];
            if(v!=p) {
                //printf("%d--->%d\n",u,v);
                dfs(v,u);
            }
        }
    }
     
    int dfss(int u,int t,int p,int cnt) {
        if(u==t) return cnt;
        for(int i=0;i<G[u].size();i++) {
            int v=G[u][i];
            if(v!=p) dfss(v,t,u,cnt+1);
        }
    }
     
    int main() {
            scanf("%d%d",&n,&d);
            for(int i=1;i<n;i++) {
                int u,v;
                scanf("%d%d",&u,&v);
                G[u].push_back(v);
                G[v].push_back(u);
            }
            int x;
            for(int i=1;i<=d;i++) {
                scanf("%d",&x);
                col[x]=1;
            }
            dis[0]=1;
            dfs(x,0);
            int maxx;
            maxx=-1,s=-1;
            for(int i=1;i<=n;i++) {
                if(dis[i]>maxx&&col[i]) {
                    maxx=dis[i];
                    s=i;
                }
            }
           // puts("");
            dis[0]=-1;
            dfs(s,0);
            maxx=-1,t=-1;
            for(int i=1;i<=n;i++) {
                if(dis[i]>maxx&&col[i]) {
                    maxx=dis[i];
                    t=i;
                }
            }
            if(dis[t]&1) dis[t]+=1;
            printf("%d\n",dis[t]/2);
    }

### C：sequence ###

题意：  
给出\$a\_\{1\\ldots n\}\$和\$b\_\{1\\ldots n\}\$，求\$max\_\{1\{\\leq\}l\{\\leq\}r\{\\leq\}n\}\\\{min\\left(a\_\{l\{\\ldots\}r\}\\right)\{\\times\}sum\\left(b\_\{l\\ldots r\}\\right) \\\}\$  
思路：  
对于区间\$l\\ldots r\$，\$min\$可能是同一个值，我们可以用单调栈维护出每个点左右第一个比他小的。\$L\[i\]、R\[i\]\$表示最小是\$a\_i\$的区间，所以可以根据\$min\$的正负来确定后面\$sum\$取最大还是取最小。用线段树维护前缀和的区间最值。  
如果\$min > 0\$，\$ans=a\[i\] \\ast \\left(query(i,R\[i\])\_\{max\}\\ - \\ query(L\[i\]-1,i-1)\_\{min\}\\right)\$，即\$a\[i\]\$乘以右边的最大值减左边的最小值。  
若\$min \\leq 0\$ ，相反即可。

//#define DEBUG
    #include<bits/stdc++.h>
    using namespace std;
    #define lson (rt<<1)
    #define rson (rt<<1|1)
    const int N=3000010;
    const int inf=0X3f3f3f3f;
    const long long INF = 0x3f3f3f3f3f3f3f3f;
    const double eps = 1e-6;
    const double pi = acos(-1.0);
    const int mod = 1000000007;
    typedef long long ll;
    
    ll sum[N];
    int a[N],b[N];
    int L[N],R[N],st[N];
    ll Max[N<<2],Min[N<<2];
    
    void build(int l,int r,int rt) {
        if(l==r) {
            Max[rt]=Min[rt]=sum[l];
            return ;
        }
        int mid=l+r>>1;
        build(l,mid,lson);
        build(mid+1,r,rson);
        Max[rt]=max(Max[lson],Max[rson]);
        Min[rt]=min(Min[lson],Min[rson]);
    }
    
    pair<ll,ll> query(int L,int R,int l,int r,int rt) {
        if(L<=l&&R>=r) {
            return make_pair(Max[rt],Min[rt]);
        }
        pair<ll,ll> res(-INF,INF);
        int mid=l+r>>1;
        if(L<=mid) res=query(L,R,l,mid,lson);
        if(R>mid) {
            auto it=query(L,R,mid+1,r,rson);
            res.first=max(it.first,res.first);
            res.second=min(it.second,res.second);
        }
        return res;
    }
    
    int main() {
        #ifdef DEBUG
        freopen("in.txt","r",stdin);
        #endif
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) {
            scanf("%lld",&b[i]);
            sum[i]=sum[i-1]+b[i];
        }
        build(0,n,1);
        int top=0;
        for(int i=1;i<=n;i++) {
            while(top&&a[i]<=a[st[top-1]]) top--;
            if(!top) L[i]=1;
            else L[i]=st[top-1]+1;
            st[top++]=i;
        }
        top=0;
        for(int i=n;i>=1;i--) {
            while(top&&a[i]<=a[st[top-1]]) top--;
            if(!top) R[i]=n;
            else R[i]=st[top-1]-1;
            st[top++]=i;
        }
        ll ans=-INF;
        for(int i=1;i<=n;i++) {
            ll tmp=0;
            if(a[i]>0) {
                tmp=query(i,R[i],0,n,1).first-query(L[i]-1,i-1,0,n,1).second;
            } else if(a[i]<0) tmp=query(i,R[i],0,n,1).second-query(L[i]-1,i-1,0,n,1).first;
            ans=max(ans,a[i]*1LL*tmp);
        }
        printf("%lld\n",ans);
    }

### D：tirples I ###

题意：  
给出一个数\$a\$，让你输出最少的数\$x\_1,x\_2,\\ldots,x\_n\$，使\$x\_1 | x\_2 |\{\\ldots\}|x\_n = a\$，其中\$3|x\_i\$。  
思路：  
很明显，若\$3|a\$，则输出\$a\$即可。否则考虑\$a\$的二进制位有几个，若\$a\$的二进制位小于等于\$2\$无解。  
然后讨论  
若\$a\\ mod\\ 3 =1\$

*  如果\$a\$中的二进制位至少有两个\$mod\\ 3= 1\$，设它们为\$p、q\$，我们可以取\$\\\{a-p,a-q\\\}\$即可。  
    \$sample\$：\$a=13\$，可以取\$13-1=12、13-4=9\$，减去\$p\$,减去\$q\$，后者里面包含\$p\$，补回来了。
 *  如果\$a\$中既有\$mod\\ 3=1\$又有\$mod\\ 3=2\$，设\$mod\\ 3=1\$为\$p\$，\$mod\\ 3=2\$为\$q\$，我们可以取\$\\\{a-p,p+q\\\}\$  
    \$sample\$：\$a=13\$，可以取\$13-1=12、8+1=9\$，减去\$p\$，加上\$p+q\$，补回来了。
 *  如果\$a\$中没有\$mod\\ 3=1\$，设他们为\$p、q、r\$，我们可以取\$\\\{a-p-q,p+q+r\\\}\$  
    \$sample\$：\$difficulty \\ldots\$，同理。

若\$a\\ mod\\ 3=2\$  
相反即可。

//#define DEBUG
    #include<bits/stdc++.h>
    using namespace std;
    const int N=100010;
    const int inf=0X3f3f3f3f;
    const long long INF = 0x3f3f3f3f3f3f3f3f;
    const double eps = 1e-6;
    const double pi = acos(-1.0);
    const int mod = 1000000007;
    typedef long long ll;
     
    vector<ll> b[2];
    int main() {
        #ifdef DEBUG
        freopen("in.txt","r",stdin);
        #endif
        int _;ll a;
        for(scanf("%d",&_);_;_--) {
            memset(b,0,sizeof(b));
            scanf("%lld",&a);
            if(a%3==0) {
                printf("1 %lld\n",a);
                continue;
            }
            for(int i=0;i<=60;i++) {
                if((a>>i)&1) b[i&1].push_back(1LL<<i);
            }
            if(a%3==1) {
                if(b[0].size()>=2) {
                    printf("2 %lld %lld\n",a-b[0][0],a-b[0][1]);
                } else if(b[0].size()&&b[1].size()) {
                    printf("2 %lld %lld\n",a-b[0][0],b[0][0]+b[1][0]);
                } else printf("2 %lld %lld\n",a-b[1][0]-b[1][1],b[1][0]+b[1][1]+b[1][2]);
            } else {
                if(b[1].size()>=2) {
                    printf("2 %lld %lld\n",a-b[1][0],a-b[1][1]);
                } else if(b[0].size()&&b[1].size()) {
                    printf("2 %lld %lld\n",a-b[1][0],b[1][0]+b[0][0]);
                } else printf("2 %lld %lld\n",a-b[0][0]-b[0][1],b[0][0]+b[0][1]+b[0][2]);
            }
        }
    }

### I：string ###

题意：  
给出一个字符串\$S\$，求出\$S\$的一个字串集合，使得集合中的任何一个串反转后，不会出现在集合中。  
思路：  
我们可以构建\$S\\\#rev\\left(S\\right)\$，然后用后缀数组处理出有多少个不用的子串，减去包含\$\\\#\$的字串，发现除了回文串，其他的都是对称出现的，共\$p\$个，所以可以用回文树求出本质不同的回文串个数\$q\$。所以答案就是\$\\frac\{\\left(p+q\\right)\}2\$。  
解释：设字符串\$S\$的长度为\$len\$，包含\$\\\#\$的字串个数就是\$\{\\left(len+1\\right)\}^2\$，画图就看出来了。从第一个到\$\\\#\$，每个都有\$\\left(len+1\\right)\$个字串。后缀数组处理不同的子串就是\$\\sum\_\{i=2\}^\{2\{\\ast\}len+1\}\\left(2\{\\ast\}len+1-sa\[i\]-h\[i\]\\right)\$。见下图  
![1445840-20190806235236771-1552933492.png][]

红色表示\$h\[\]\$数组，蓝色表示首字母开始的下标，黑色字串为排序后的排列。  
总长度减去蓝色下标——表示该位置开始能形成的子串个数，绿色是减去\$h\[i\]\$的结果，即贡献。  
累加贡献就是不同字串个数了。  
取自\$csl\$巨巨的代码，不知道理解的对不对，见注释。

#include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 1 << 19;
    struct Suffix_Array
    {
        char s[maxn];
        int sa[maxn], t[maxn], t2[maxn], c[maxn], rank[maxn], height[maxn];
        void build_sa(int m, int n)
        {
            n++;
            int *x = t, *y = t2;
            for (int i = 0; i < m; i++) c[i] = 0;
            for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
            for (int i = 1; i < m; i++) c[i] += c[i - 1];
            for (int i = n - 1; ~i; i--) sa[--c[x[i]]] = i;
            for (int k = 1; k <= n; k <<= 1)
            {
                int p = 0;
                for (int i = n - k; i < n; i++) y[p++] = i;
                for (int i = 0; i < n; i++)
                    if (sa[i] >= k) y[p++] = sa[i] - k;
                for (int i = 0; i < m; i++) c[i] = 0;
                for (int i = 0; i < n; i++) c[x[y[i]]]++;
                for (int i = 1; i < m; i++) c[i] += c[i - 1];
                for (int i = n - 1; ~i; i--) sa[--c[x[y[i]]]] = y[i];
                swap(x, y);
                p = 1;
                x[sa[0]] = 0;
                for (int i = 1; i < n; i++)
                    x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
                if (p >= n) break;
                m = p;
            }
            n--;
            int k = 0;
            for (int i = 0; i <= n; i++) rank[sa[i]] = i;
            for (int i = 0; i < n; i++)
            {
                if (k) k--;
                int j = sa[rank[i] - 1];
                while (s[i + k] == s[j + k]) k++;
                height[rank[i]] = k;
            }
        }
    
        int dp[maxn][30];
        void initrmq(int n)
        {
            for (int i = 1; i <= n; i++)
                dp[i][0] = height[i];
            for (int j = 1; (1 << j) <= n; j++)
                for (int i = 1; i + (1 << j) - 1 <= n; i++)
                    dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
        }
        int rmq(int l, int r)
        {
            int k = 31 - __builtin_clz(r - l + 1);
            return min(dp[l][k], dp[r - (1 << k) + 1][k]);
        }
        int lcp(int a, int b)
        {
            a = rank[a], b = rank[b];
            if (a > b) swap(a, b);
            return rmq(a + 1, b);
        }
        //
        long long solve(int n, int sz)  //  ans= \sum{sz-sa[i]+1-h[i]}  见图解                              
        {                               //但是算带'$'的时候不带末尾'0'，所以这里也不带。sz-sa[i]+h[i]
            long long ans = 1LL * sz * (sz + 1) / 2; // sa[0]=sz,所以sz-sa[i]累加就是 1+2+……+sz
            for (int i = 1; i <= sz; i++) ans -= height[i];
            ans -= 1LL * n * n + 2LL * n + 1; // (len+1)^2
            return ans;
        }
    } sa;
    
    struct Palindromic_Tree
    {
        int ch[maxn][26], f[maxn], len[maxn], s[maxn];
        int cnt[maxn]; // 结点表示的本质不同的回文串的个数(调用count()后)
        int num[maxn]; // 结点表示的最长回文串的最右端点为回文串结尾的回文串个数
        int last, sz, n;
        int newnode(int x)
        {
            memset(ch[sz], 0, sizeof(ch[sz]));
            cnt[sz] = num[sz] = 0, len[sz] = x;
            return sz++;
        }
        void init()
        {
            sz = 0;
            newnode(0), newnode(-1);
            last = n = 0, s[0] = -1, f[0] = 1;
        }
        int get_fail(int u)
        {
            while (s[n - len[u] - 1] != s[n]) u = f[u];
            return u;
        }
        void add(int c)
        { // c-='a'
            s[++n] = c;
            int u = get_fail(last);
            if (!ch[u][c])
            {
                int np = newnode(len[u] + 2);
                f[np] = ch[get_fail(f[u])][c];
                num[np] = num[f[np]] + 1;
                ch[u][c] = np;
            }
            last = ch[u][c];
            cnt[last]++;
        }
        void count()
        {
            for (int i = sz - 1; ~i; i--) cnt[f[i]] += cnt[i];
        }
    } pam;
    
    int main()
    {
        scanf("%s", sa.s);
        pam.init();
        int n = strlen(sa.s);
        for (int i = 0; sa.s[i]; i++) pam.add(sa.s[i] - 'a');
        sa.s[n] = '$';
        for (int i = 0, j = n - 1; i < n; i++, j--) sa.s[n + 1 + i] = sa.s[j];
        sa.s[n * 2 + 1] = '\0';
        sa.build_sa(128, n * 2 + 1);
        long long p = sa.solve(n, n * 2 + 1);
        long long q = pam.sz-2; //节点大小即为本质不同回文子串个数
        printf("%lld\n", (p + q) / 2);
    //    for(int i=0;i<=n*2+1;i++) printf("%c**",sa.s[i]);
    //    puts("");
    //    for(int i=0;i<=n*2+1;i++) {
    //        printf("%d*****",sa.height[i]);
    //        for(int j=sa.sa[i];j<=n*2+1;j++) printf("%c**",sa.s[j]);
    //        puts("");
    //    }
    //    for(int i=0;i<=n*2+1;i++) printf("%d**",sa.sa[i]);
    //    printf("%d&&&",q);
    }

### K：number ###

题意：  
给出一个字符串，问有多少个不同的子串能整除\$300\$。子串不同即起始位置不同。  
思路：  
一道去年暑假队友做到过的原题。虽然是赛后我才回忆起来的。前缀和或\$DP\$  
能整除\$300\$，即数位和是\$3\$的倍数且末尾至少两个\$0\$（0除外）  
所以可以求前缀和\$mod 3\$，若要和为\$3\$的倍数，\$sum\[r\]-sum\[l\]=0\$ ，所以我们可以同时记录前面有多少个\$0,1,2\$。当连续两个\$0\$的时候就算一次。

\$dp\[i\]\[j\]\$表示以第i个字符结尾的子串中数位和\$mod 3=j\$的个数。\$0\$另外统计。每次遇到两个连续的\$0\$，算一次答案。

### J：free ###

题意：  
给出一个无向连通图，每条边有相应的花费，然后可以选择最多\$k\$条边免费，求\$s-t\$的最小花费。  
思路：  
飞行路线原题，\$dp\[i\]\[j\]\$表示到达\$i\$点用了\$j\$次特权的花费。可能不足\$k\$条边，所以选最小值。\$spfa\$搞一搞。

//#define DEBUG
    #include<bits/stdc++.h>
    using namespace std;
    const long long inf=92233720368547758;
    const int maxn=2010;
    const int maxm=2010;
    typedef long long ll;
    
    int n,m,k,st,ed;
    int head[maxn];
    ll dis[maxn][1010];
    bool vis[maxn][1010];
    
    struct Edge{
        int to,next;
        ll w;
    }edge[100010];
    
    int tol;
    void addedge(int u,int v,ll w) {
        edge[tol].to=v;
        edge[tol].w=w;
        edge[tol].next=head[u];
        head[u]=tol++;
    }
    
    void init() {
        tol=0;
        for(int i=0;i<=n;i++) {
            head[i]=-1;
            for(int j=0;j<=1010;j++) {
                dis[i][j]=inf;
                vis[i][j]=false;
            }
        }
    }
    
    struct node{
        int u,step;
    };
    
    void spfa() {
        dis[st][0]=0;
        queue<node> q;
        vis[st][0]=true;
        q.push({st,0});
        while(!q.empty()) {
            node f=q.front();
            q.pop();
            vis[f.u][f.step]=false;
            for(int i=head[f.u];i!=-1;i=edge[i].next) {
                int v=edge[i].to;
                if(dis[v][f.step]>dis[f.u][f.step]+edge[i].w) {
                    dis[v][f.step]=dis[f.u][f.step]+edge[i].w;
                    if(!vis[v][f.step]) {
                        vis[v][f.step]=true;
                        q.push({v,f.step});
                    }
                }
                if(f.step+1<=k) {
                    if(dis[v][f.step+1]>dis[f.u][f.step]) {
                        dis[v][f.step+1]=dis[f.u][f.step];
                        if(!vis[v][f.step+1]) {
                            vis[v][f.step+1]=true;
                            q.push({v,f.step+1});
                        }
                    }
                }
            }
        }
    }
    
    int main() {
        #ifdef DEBUG
        freopen("in.txt","r",stdin);
        #endif // DEBUG
        while(~scanf("%d%d%d%d%d",&n,&m,&st,&ed,&k)) {
            init();
            for(int i=1;i<=m;i++) {
                int u,v;
                ll w;
                scanf("%d%d%lld",&u,&v,&w);
                addedge(u,v,w);
                addedge(v,u,w);
            }
            spfa();
            ll ans=inf;
            for(int i=0;i<=k;i++) ans=min(ans,dis[ed][i]);
            printf("%lld\n",ans);
        }
    }

转载于:https://www.cnblogs.com/ACMerszl/p/11312349.html

[Contest Link]: https://ac.nowcoder.com/acm/contest/884#question
[1445840-20190806235236771-1552933492.png]: /images/20230601/49592fb7276e4c1893f75b224e492a62.png