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

Contest Info##

Contest Link

• O 赛中通过
• \(\varnothing\)赛后通过
• !尝试了但失败了
• -没有尝试

Soulation##

A：meeting###

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

#include
using namespace std;
const int maxn=100010;
 
int _,n,m,d,col[maxn],dis[maxn],s,t;
vector G[maxn];
 
void dfs(int u,int p) {
    dis[u]=dis[p]+1;
    for(int i=0;i%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;imaxx&&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
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 query(int L,int R,int l,int r,int rt) {
    if(L<=l&&R>=r) {
        return make_pair(Max[rt],Min[rt]);
    }
    pair 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
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 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<=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)\)。见下图

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

#include 
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\)的时候就算一次。

//#define DEBUG
#include
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;
 
char s[N];
int w[N],cnt[3];
 
int main() {
    #ifdef DEBUG
    freopen("in.txt","r",stdin);
    #endif
    scanf("%s",s+1);
    int len=strlen(s+1);
    for(int i=1;i<=len;i++) {
        w[i]=(w[i-1]+s[i]-'0')%3;
    }
    ll ans=0;
    for(int i=1;i<=len;i++) {
        if(s[i]=='0') {
            ans++;
            if(s[i-1]=='0') {
                ans+=cnt[w[i]];
            }
        }
        cnt[w[i-1]]++;
    }
    printf("%lld\n",ans);
}

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

//#define DEBUG
#include
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;
 
 
char s[N];
int dp[N][3];
int main() {
    #ifdef DEBUG
    freopen("in.txt","r",stdin);
    #endif
    scanf("%s",s+1);
    int len=strlen(s+1);
    ll ans=0,res=0;
    for(int i=1;i<=len;i++) {
        int num=(s[i]-'0')%3;
        dp[i][num]++;
        for(int j=0;j<3;j++) {
            dp[i][j]+=dp[i-1][(j-num+3)%3];
        }
        if(s[i]=='0') res++;
        if(i>=2&&s[i]=='0'&&s[i-1]=='0') ans+=dp[i-1][0];
    }
    printf("%lld\n",ans+res);
}

J：free###

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

//#define DEBUG
#include
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 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);
    }
}