2020牛客暑期多校训练营（第一场）

博主： Anoyer
发布时间：2020 年 07 月 12 日
2081次浏览
2 条评论
360字数
分类：小组个人训练

题目链接

A. B-Suffix Array

const bool IOS=false;        //关闭流同步
const double PI = acos(-1);
const double eps = 1e-8;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const ll INV2=500000004;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+10;
/********************CODE*********************/
#define REP(i,n) for(i=0;i<(n);++i)
#define UPTO(i,l,h) for(i=(l);i<=(h);++i)
#define DOWN(i,h,l) for(i=(h);i>=(l);--i)
template <typename T, int LEN>
struct suffixarray{
    //rank[i] 第i个后缀的排名; SA[i] 排名为i的后缀位置; Height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP
    int str[LEN*3],sa[LEN*3];
    int rank[LEN],height[LEN];
    int id[LEN];
    int best[LEN][20];
    int len;
    bool equal(int *str, int a, int b){
        return str[a]==str[b]&&str[a+1]==str[b+1]&&str[a+2]==str[b+2];
    }
    bool cmp3(int *str, int *nstr, int a, int b){
        if(str[a]!=str[b])return str[a]<str[b];
        if(str[a+1]!=str[b+1])return str[a+1]<str[b+1];
        return nstr[a+b%3]<nstr[b+b%3];
    }
    void radixsort(int *str, int *sa, int *res, int n, int m){
        int i;
        REP(i,m)id[i]=0;
        REP(i,n)++id[str[sa[i]]];
        REP(i,m)id[i+1]+=id[i];
        DOWN(i,n-1,0)res[--id[str[sa[i]]]]=sa[i];
    }
    void dc3(int *str, int *sa, int n, int m){
        #define F(x) ((x)/3+((x)%3==1?0:one))
        #define G(x) ((x)<one?(x)*3+1:((x)-one)*3+2)
        int *nstr=str+n, *nsa=sa+n, *tmpa=rank, *tmpb=height;
        int i,j,k,len=0,num=0,zero=0,one=(n+1)/3;
        REP(i,n)if(i%3)tmpa[len++]=i;
        str[n]=str[n+1]=0;
        radixsort(str+2, tmpa, tmpb, len, m);
        radixsort(str+1, tmpb, tmpa, len, m);
        radixsort(str+0, tmpa, tmpb, len, m);
        nstr[F(tmpb[0])]=num++;
        UPTO(i,1,len-1)
            nstr[F(tmpb[i])]=equal(str,tmpb[i-1],tmpb[i])?num-1:num++;
        if(num<len)dc3(nstr,nsa,len,num);
        else REP(i,len)nsa[nstr[i]]=i;
        if(n%3==1)tmpa[zero++]=n-1;
        REP(i,len)if(nsa[i]<one)tmpa[zero++]=nsa[i]*3;
        radixsort(str, tmpa, tmpb, zero, m);
        REP(i,len)tmpa[nsa[i]=G(nsa[i])]=i;
        i=j=0;
        REP(k,n)
        if(j>=len||(i<zero&&cmp3(str,tmpa,tmpb[i],nsa[j])))sa[k]=tmpb[i++];
        else sa[k]=nsa[j++];
    }
    void initSA(T *s, int n,int m){
        int i,j,k=0;
        str[len=n]=0;//末尾增加一个0，这样就省去一些特殊情况的讨论，也就是最后一个mod 3刚好等于0
        REP(i,n)str[i]=s[i];
        dc3(str,sa,n+1,m);      //可以切换成dc3
        REP(i,n)sa[i]=sa[i+1];//第0小的默认为最后一个字符0，所以答案向前移动一位，da算法不用
        REP(i,n)rank[sa[i]]=i;
        REP(i,n)//计算height数组
        {
            if(k)--k;
            if(rank[i])for(j=sa[rank[i]-1];str[i+k]==str[j+k];++k);
            else k=0;
            height[rank[i]]=k;
        }
    }
};
suffixarray<int,maxn>msa;
map<int,int>mymap;   //计算m,m表示不同字符个数，如果是字母直接用256
char s[maxn];
int a[maxn];
int id[maxn][2];
priority_queue<PII,vector<PII>,greater<PII> >q[maxn];
Anoyer(){
#ifdef LOCAL
    //fcin;
    //fcout;
#endif
    int n;
    while(~scanf("%d",&n)){
        mymap.clear();
        scanf("%s",s);
        int posa=-1,posb=-1;
        int mn=1;
        mymap[0]=mn;
        for(int i=0;i<n;++i){
            if(s[i]=='a'){
                if(posa==-1)a[i]=mymap[0];
                else {
                    if(!mymap.count(i-posa))mymap[i-posa]=++mn;
                    a[i]=i-posa+1;
 
                }
                posa=i;
            }
            else{
                if(posb==-1)a[i]=mymap[0];
                else {
                    if(!mymap.count(i-posb))mymap[i-posb]=++mn;
                    a[i]=i-posb+1;
                }
                posb=i;
            }
            mn=max(mn,a[i]);
        }
        //cout<<mn<<endl;
        int aa=n,bb=n;
        for(int i=n-1;i>=0;--i){
            if(s[i]=='a'){
                id[i][0] = aa;
                aa=i;
            }
            else if(s[i]=='b'){
                id[i][1]=bb;
                bb=i;
            }
        }
        msa.initSA(a,n,mn+10);
       // for(int i=0;i<n;++i)printf("%d ",a[i]);pf("");
       // for(int i=0;i<n;++i)printf("%d ",msa.rank[i]);pf("");
        int l=0,r=n;
        for(int i=1;i<n;++i)if(a[i]==1)r=i;
        for(int i=0;i<n-1;++i){
            int cnt=r-l-1;
            if(r==n-1){
                q[cnt].push(MP(-1,i));
            }
            else if(r==n){  //没有零
                q[cnt].push(MP(-2,i));
            }
            else q[cnt].push(MP(msa.rank[r+1],i));
            if(s[i]=='a'){
                l=r;
                a[id[i][0]]=0;
                r=id[i][0];
                if(r<l)swap(l,r);
            }
            else {
                l=r;
                a[id[i][1]]=0;
                r=id[i][1];
                if(r<l)swap(l,r);
            }
        }
        printf("%d",n);
        for(int i=0;i<n;++i){
            while(!q[i].empty()){
                printf(" %d",q[i].top().se+1);
                q[i].pop();
            }
        }
        pf("");
    }
 
}

B. Infinite Tree

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int pmaxn = 1e5 + 2;
const int maxn = 5e5 + 10;
const int MOD = 1e9+7;
const ll inf = 0x3f3f3f3f3f3f3f3f;
vector<int> pri[maxn];
int mxpri[maxn],idpri[maxn];//最大质数，质数编号
ll w[maxn];
int lowbit(int x) { return x & (-x); }
ll sum[maxn], mul[maxn],LobN;
void add(int x, int v) {
    x = LobN - x + 1;
    while (x <= LobN) {
        sum[x] += 1;
        mul[x] = 1ll * mul[x] * v %MOD;
        x += lowbit(x);
    }
}
int Sum(int x) {
    int res = 0;
    x = LobN - x + 1;
    while (x)res += sum[x],x-=lowbit(x);
    return res;
}
int Mul(int x) {
    int res = 1;
    x = LobN - x + 1;
    while (x)res = 1ll * res * mul[x] % MOD , x -= lowbit(x);
    return res;
}
struct node {
    int id, has, dep;
};
node st[maxn];
int top = 0;
vector<pair<int, int> > e[maxn];
void build(int n) {
    int idx = n;
    st[top = 1] = { 1,1,0 };
    for (int i = 2; i <= n; i++) {
        node lc = { ++idx,Mul(idpri[mxpri[i]]),Sum(idpri[mxpri[i]]) };
        int x = i;
        for (auto v : pri[i]) while (x%v == 0)add(idpri[v], v), x /= v;
        node now = { i,Mul(1),Sum(1) };
        if (lc.has == st[top].has) {
            --idx;
            st[++top] = now;
        }
        else {
            while (top > 1 && st[top - 1].dep >= lc.dep) {
                e[st[top - 1].id].push_back({ st[top].id,st[top].dep - st[top - 1].dep }), --top;
            }
            if (st[top].has != lc.has)
                e[lc.id].push_back({ st[top].id,st[top].dep - lc.dep }),st[top] = lc;
            st[++top] = now;
        }
    }
    while (top > 1)
        e[st[top - 1].id].push_back({ st[top].id,st[top].dep - st[top - 1].dep }), --top;
}
ll sz[maxn];
ll d[maxn];
void dfs(int x, int f) {
    sz[x] = w[x];
    d[x] = 0;
    for (auto it : e[x]) {
        int v = it.first, w = it.second;
        if (v != f) {
            dfs(v, x);
            d[x] += 1ll*w * sz[v] + d[v];
            sz[x] += sz[v];
        }
    }
}
ll ans = inf;
void solve(int x, int f) {
    ans = min(ans, d[x]);
    for (auto it : e[x]) {
        int v = it.first, w = it.second;
        if (v != f) {
        
            ll sd = d[x];
            ll sv = d[v];
            ll sx = sz[x];
            ll ssv = sz[v];

            d[x] -= d[v] + 1ll * w*sz[v];
            sz[x]-= sz[v];
            d[v] += d[x] + 1ll * w *sz[x];
            sz[v] += sz[x];

            solve(v, x);
            d[x] = sd;
            d[v] = sv;
            sz[x] = sx;
            sz[v] = ssv;
        }
    }
    e[x].clear();
    sz[x] = 0;
    w[x] = 0;
}
int main() {
    int idx = 0;
    for (int i = 2; i <= pmaxn; ++i) {
        if (pri[i].size() == 0) {
            idpri[i] = ++idx;
            for (int j = i; j <= pmaxn; j += i) {
                {
                        pri[j].push_back(i);
                        mxpri[j] = i;
                }
            }
        }
    }
    int n; 
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++)scanf("%d", &w[i]);
        LobN = n;
        for (int i = 1; i <= LobN; i++)sum[i] = 0, mul[i] = 1;
        build(n);
        ans = inf;
        dfs(1, 0);
        solve(1, 0);
        printf("%lld\n", ans);
    }
    return 0;
}

C. Domino(待补)

D. Quadratic Form

题解：https://www.cnblogs.com/DeaphetS/p/13291266.html

ll f[maxn][maxn<<1],r;
ll b[maxn];
inline void Gauss(int n,int m){
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++)
            if(f[j][i]){
                if(j!=i) for(int k=1;k<=m;k++) swap(f[i][k],f[j][k]);
                break;
            }
        if(!f[i][i]){puts("No Solution");exit(0);}
        r=qpow(f[i][i],mod-2,mod);
        for(int j=i;j<=m;j++) f[i][j]=1LL*f[i][j]*r%mod;
        for(int j=1;j<=n;j++)
            if(j!=i){
                r=f[j][i];
                for(int k=i;k<=m;k++)
                    f[j][k]=(f[j][k]-1LL*r*f[i][k]%mod+mod)%mod;
            }
    }
//    for(int i=1;i<=n;i++){
//        for(int j=n+1;j<=m;j++) printf("%d ",f[i][j]);
//        puts("");
//    }
    return;
}
Anoyer(){
#ifdef LOCAL
    fcin;
    //fcout;
#endif
    int n,m;
    while(scanf("%d",&n)!=EOF){
        met(f,0);
        m=2*n;
        Fup(i,n){
            Fup(j,n)sf(f[i][j]),f[i][j]=(f[i][j]+mod)%mod;
            f[i][n+i]=1;
        }
        Fup(i,n)sf(b[i]),b[i]=(b[i]+mod)%mod;
        Gauss(n,m);
        ll ans=0;   //ans=B^t * A^-1 *B  利用拉格朗日乘数法
        Fup(i,n){
            for(int j=n+1;j<=m;j++)ans=(ans+f[i][j]*b[i]%mod*b[j-n]%mod)%mod;
        }
        pf(ans);
    }
}

E. Counting Spanning Trees(待补)

F. Infinite String Comparision

char a[maxn],b[maxn];
Anoyer(){
#ifdef LOCAL
    fcin;
    //fcout;
#endif
        while(~scanf("%s%s",a,b)){
            int lena = strlen(a);
            int lenb = strlen(b);
            bool sw = 0;
            if(lena < lenb){
                sw = 1;
                swap(a,b);
                swap(lena,lenb);
            }
            for(int i = lena ;i<lena*2;++i)a[i] = a[i%lena];
            lena*=2;
            bool ok = 0;
            for(int i=0;i<lena;i++){
 
                if(a[i]!=b[i % lenb]){
 
                    if(a[i] > b[i%lenb])
                      {
                        if(!sw)
                         printf(">\n");
                        else
                            printf("<\n");
                          ok=1;
                         break;
                        }
                    else if(a[i] <b[i % lenb])
                    {
                        if(!sw)
                        printf("<\n");
                        else
                            printf(">\n");
                        ok = 1;
                        break;
                    }
                }
            }
            if(!ok)printf("=\n");
        }
}

G. BaXianGuoHai, GeXianShenTong(待补)

H. Minimum-cost Flow

#include<bits/stdc++.h>

using namespace std;

#define SZ(x) (x).size()
const int M = 3e5 + 10;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e4;
int N;
struct Edge
{
    int v, cap, cost, rev;//终点，容量（指残量网络中的），费用，反向边编号
    //Edge(int t, int c, int cc, int r) :v(t), cap(c), cost(cc), rev(r){}
};
vector<Edge>G[maxn];//图的邻接表
void init(int _n) {
    N = _n;
    for (int i = 0; i <= N; i++)G[i].clear();
}
void add(int u, int v, int cap, int cost)
{
    G[u].push_back({ v, cap, cost, (int)G[v].size() });
    G[v].push_back({ u, 0, -cost, (int)G[u].size() - 1 });
}
int prevv[maxn];//最短路中的父结点
int preve[maxn];//最短路中的父边
ll dis[maxn];

bool vis[maxn];
#define P pair<ll, ll>
bool spfa(int s, int t) {
    queue<P> q;
    //priority_queue<P, vector<P>, greater<P> >q;
    fill(dis, dis + N + 1, inf);//距离初始化为INF
    fill(vis, vis + N + 1, 0);
    fill(preve, preve + N + 1, -1);
    dis[s] = 0;
    vis[s] = true;
    q.push({ 0, s });
    while (!q.empty()) {
        int u = q.front().second;
        q.pop();
        vis[u] = false;
        for (int i = 0; i < G[u].size(); i++)
        {
            Edge&e = G[u][i];
            if (e.cap > 0 && dis[e.v] > dis[u] + e.cost)//松弛操作
            {
                dis[e.v] = dis[u] + e.cost;
                prevv[e.v] = u;//更新父结点
                preve[e.v] = i;//更新父边编号
                if (!vis[e.v]) {
                    vis[e.v] = 1;
                    q.push(P(dis[e.v], e.v));
                }
            }
        }
    }
    if (preve[t] == -1)return false;
    return true;
}
ll Cost[maxn];
int idx = 1;
//返回的是最大流，cost 存的是最小费
int mincostmaxflow(int s, int t, int &cost) {
    int flow = 0;
    cost = 0;
    while (spfa(s, t)) {
        int d = inf;
        for (int x = t; x != s; x = prevv[x])
            d = min(d, G[prevv[x]][preve[x]].cap);//从t出发沿着最短路返回s找可改进量
        cost += d * dis[t];
        Cost[idx] = dis[t];
        ++idx;
        for (int x = t; x != s; x = prevv[x]) {
            Edge&e = G[prevv[x]][preve[x]];
            e.cap -= d;//修改残量值
            G[x][e.rev].cap += d;
        }
        flow += d;
    
    }
    return flow;
}
template<typename T> inline T Gcd(T a, T b) { while (b) { T t = b; b = a % b; a = t; }return a; }
ll sum[maxn];
int main() {

    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        idx = 1;
        memset(Cost, 0, sizeof(Cost));
        init(n + 5);
        int S = n + 1;
        add(S, 1, 200, 0);
        for (int i = 1; i <= m; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, 1, w);
        }
        int cost = 0;
        mincostmaxflow(1, n, cost);
        int q; scanf("%d", &q);
        for (int i = 1; i < idx; i++)sum[i] = sum[i - 1] + Cost[i];
        while (q--) {
            ll x, y; scanf("%lld%lld", &x, &y);
            if (x == 0) { printf("NaN\n"); continue; }
            ll a = y / x;
            ll b = y % x;
            if (a + (bool)b >= idx) { printf("NaN\n"); continue; }
            ll ans = sum[a] * x + Cost[a + 1] * b;
            ll gc = Gcd(ans, 1ll * y);
            printf("%lld/%lld\n", ans / gc, y / gc);
        }
    }
    return 0;
}

I. 1 or 2

#include<bits/stdc++.h>
using namespace std;


const int N = 500 + 10;

//复杂度N^3,带花树匹配，一般图最大匹配
struct Match {
    int n;
    vector<int> G[N];    //图
    int fa[N], mt[N], pre[N], mk[N];
    int lca_clk, lca_mk[N];
    pair<int, int> ce[N];
    void add(int x, int y) {
        G[x].push_back(y);
    }
    void init(int n_) {
        n = n_;
        for (int i = 0; i <= n; i++) {
            G[i].clear();
            ce[i].first = ce[i].second = 0;
            lca_mk[i] = 0;
        }
        lca_clk = 0;
    }
    void connect(int u, int v) {
        mt[u] = v;
        mt[v] = u;
    }
    int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
    void flip(int s, int u) {
        if (s == u) return;
        if (mk[u] == 2) {
            int v1 = ce[u].first, v2 = ce[u].second;
            flip(mt[u], v1);
            flip(s, v2);
            connect(v1, v2);
        }
        else {
            flip(s, pre[mt[u]]);
            connect(pre[mt[u]], mt[u]);
        }
    }
    int get_lca(int u, int v) {
        lca_clk++;
        for (u = find(u), v = find(v); ; u = find(pre[u]), v = find(pre[v])) {
            if (u && lca_mk[u] == lca_clk) return u;
            lca_mk[u] = lca_clk;
            if (v && lca_mk[v] == lca_clk) return v;
            lca_mk[v] = lca_clk;
        }
    }
    void access(int u, int p, const pair<int, int>& c, vector<int>& q) {
        for (u = find(u); u != p; u = find(pre[u])) {
            if (mk[u] == 2) {
                ce[u] = c;
                q.push_back(u);
            }
            fa[find(u)] = find(p);
        }
    }
    bool aug(int s) {
        fill(mk, mk + n + 1, 0);
        fill(pre, pre + n + 1, 0);
        iota(fa, fa + n + 1, 0); //从0开始，构建0 1 2 3 ...序列，初始化并查集
        vector<int> q = { s };
        mk[s] = 1;
        int t = 0;
        for (int t = 0; t < (int)q.size(); ++t) {
            int u = q[t];
            for (int &v : G[u]) {
                if (find(v) == find(u)) continue;
                if (!mk[v] && !mt[v]) {
                    flip(s, u);
                    connect(u, v);
                    return true;
                }
                else if (!mk[v]) {
                    int w = mt[v];
                    mk[v] = 2; mk[w] = 1;
                    pre[w] = v; pre[v] = u;
                    q.push_back(w);
                }
                else if (mk[find(v)] == 1) {
                    int p = get_lca(u, v);
                    access(u, p, { u, v }, q);
                    access(v, p, { v, u }, q);
                }
            }
        }
        return false;
    }
    int match() {
        fill(mt + 1, mt + n + 1, 0);
        lca_clk = 0;
        int ans = 0;
        for (int i = 1; i <= n + 1; i++)
            if (!mt[i]) ans += aug(i);
        return ans;
    }

}_Match;
int d[N];
int main() {
    int n,m;

    while (~scanf("%d%d", &n, &m)) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &d[i]);
            cnt += d[i];
        }
        cnt += m * 2;
        cnt /= 2;
        _Match.init(2 * n + 2 * m + 10);
        for (int i = 1; i <= m; i++) {
            int x, y; scanf("%d%d", &x, &y);
            if (d[x] == 2) {
                _Match.add(x, 2 * n + i);
                _Match.add(2 * n + i,x);
                _Match.add(x + n, 2 * n + i);
                _Match.add(2 * n + i, x + n);
            }
            else {
                _Match.add(x, 2 * n + i);
                _Match.add(2 * n + i,x);
            }
            if (d[y] == 2) {
                _Match.add(y, 2 * n + m+i);
                _Match.add(2 * n + m + i, y);
                _Match.add(y + n, 2 * n + m + i);
                _Match.add(2 * n + m + i, y + n);
            }
            else {
                _Match.add(y, 2 * n + m + i);
                _Match.add(2 * n + m + i, y);
            }
            _Match.add(2 * n + i, 2 * n + m + i);
            _Match.add(2 * n + m + i, 2 * n + i);
        }
        if (_Match.match() == cnt)
            printf("Yes\n");
        else 
            printf("No\n");
    }
    return 0;
}

J. Easy Integration

ll pre[maxn];
Anoyer(){
#ifdef LOCAL
    fcin;
    //fcout;
#endif
    pre[0]=1;
    for(int i=1;i<maxn;++i)pre[i]=pre[i-1]*i%mod;
    int n;
    while(scanf("%d",&n)!=EOF){
        ll ans=qpow(pre[n],2,mod)*qpow(pre[2*n+1],mod-2,mod)%mod;
        pf(ans);
    }
}

最后修改：2020 年 07 月 27 日 05 : 33 PM

2 条评论

Carered
July 15th, 2020 at 01:09 pm

您好，关于I题我想请问下面这组数据您的代码的答案为什么为yes
6
6
1 1 1 1 1 1
1 3
2 3
1 2
4 5
4 6
5 6

回复
1. liuyueyang
  July 27th, 2020 at 05:34 pm
  
  @Carered
  
  不好意思，谢谢提醒，这个代码是比赛的时候水过去的，已经改成正解了，带花树匹配。
  
  回复

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

liuyueyang
不好意思，谢谢提醒，这个代码是比赛的时候水过去的，已经改成正解...
Carered
您好，关于I题我想请问下面这组数据您的代码的答案为什么为yes...
dxt
请问G题是什么思路?
liuyueyang
E：https://paste.ubuntu.com/p/rs...
Anoyer
题目待补 J L

2020牛客暑期多校训练营（第一场）

Anoyer • 2020 年 07 月 12 日

题目链接

A. B-Suffix Array

const bool IOS=false;        //关闭流同步
const double PI = acos(-1);
const double eps = 1e-8;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const ll INV2=500000004;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+10;
/********************CODE*********************/
#define REP(i,n) for(i=0;i<(n);++i)
#define UPTO(i,l,h) for(i=(l);i<=(h);++i)
#define DOWN(i,h,l) for(i=(h);i>=(l);--i)
template <typename T, int LEN>
struct suffixarray{
    //rank[i] 第i个后缀的排名; SA[i] 排名为i的后缀位置; Height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP
    int str[LEN*3],sa[LEN*3];
    int rank[LEN],height[LEN];
    int id[LEN];
    int best[LEN][20];
    int len;
    bool equal(int *str, int a, int b){
        return str[a]==str[b]&&str[a+1]==str[b+1]&&str[a+2]==str[b+2];
    }
    bool cmp3(int *str, int *nstr, int a, int b){
        if(str[a]!=str[b])return str[a]<str[b];
        if(str[a+1]!=str[b+1])return str[a+1]<str[b+1];
        return nstr[a+b%3]<nstr[b+b%3];
    }
    void radixsort(int *str, int *sa, int *res, int n, int m){
        int i;
        REP(i,m)id[i]=0;
        REP(i,n)++id[str[sa[i]]];
        REP(i,m)id[i+1]+=id[i];
        DOWN(i,n-1,0)res[--id[str[sa[i]]]]=sa[i];
    }
    void dc3(int *str, int *sa, int n, int m){
        #define F(x) ((x)/3+((x)%3==1?0:one))
        #define G(x) ((x)<one?(x)*3+1:((x)-one)*3+2)
        int *nstr=str+n, *nsa=sa+n, *tmpa=rank, *tmpb=height;
        int i,j,k,len=0,num=0,zero=0,one=(n+1)/3;
        REP(i,n)if(i%3)tmpa[len++]=i;
        str[n]=str[n+1]=0;
        radixsort(str+2, tmpa, tmpb, len, m);
        radixsort(str+1, tmpb, tmpa, len, m);
        radixsort(str+0, tmpa, tmpb, len, m);
        nstr[F(tmpb[0])]=num++;
        UPTO(i,1,len-1)
            nstr[F(tmpb[i])]=equal(str,tmpb[i-1],tmpb[i])?num-1:num++;
        if(num<len)dc3(nstr,nsa,len,num);
        else REP(i,len)nsa[nstr[i]]=i;
        if(n%3==1)tmpa[zero++]=n-1;
        REP(i,len)if(nsa[i]<one)tmpa[zero++]=nsa[i]*3;
        radixsort(str, tmpa, tmpb, zero, m);
        REP(i,len)tmpa[nsa[i]=G(nsa[i])]=i;
        i=j=0;
        REP(k,n)
        if(j>=len||(i<zero&&cmp3(str,tmpa,tmpb[i],nsa[j])))sa[k]=tmpb[i++];
        else sa[k]=nsa[j++];
    }
    void initSA(T *s, int n,int m){
        int i,j,k=0;
        str[len=n]=0;//末尾增加一个0，这样就省去一些特殊情况的讨论，也就是最后一个mod 3刚好等于0
        REP(i,n)str[i]=s[i];
        dc3(str,sa,n+1,m);      //可以切换成dc3
        REP(i,n)sa[i]=sa[i+1];//第0小的默认为最后一个字符0，所以答案向前移动一位，da算法不用
        REP(i,n)rank[sa[i]]=i;
        REP(i,n)//计算height数组
        {
            if(k)--k;
            if(rank[i])for(j=sa[rank[i]-1];str[i+k]==str[j+k];++k);
            else k=0;
            height[rank[i]]=k;
        }
    }
};
suffixarray<int,maxn>msa;
map<int,int>mymap;   //计算m,m表示不同字符个数，如果是字母直接用256
char s[maxn];
int a[maxn];
int id[maxn][2];
priority_queue<PII,vector<PII>,greater<PII> >q[maxn];
Anoyer(){
#ifdef LOCAL
    //fcin;
    //fcout;
#endif
    int n;
    while(~scanf("%d",&n)){
        mymap.clear();
        scanf("%s",s);
        int posa=-1,posb=-1;
        int mn=1;
        mymap[0]=mn;
        for(int i=0;i<n;++i){
            if(s[i]=='a'){
                if(posa==-1)a[i]=mymap[0];
                else {
                    if(!mymap.count(i-posa))mymap[i-posa]=++mn;
                    a[i]=i-posa+1;
 
                }
                posa=i;
            }
            else{
                if(posb==-1)a[i]=mymap[0];
                else {
                    if(!mymap.count(i-posb))mymap[i-posb]=++mn;
                    a[i]=i-posb+1;
                }
                posb=i;
            }
            mn=max(mn,a[i]);
        }
        //cout<<mn<<endl;
        int aa=n,bb=n;
        for(int i=n-1;i>=0;--i){
            if(s[i]=='a'){
                id[i][0] = aa;
                aa=i;
            }
            else if(s[i]=='b'){
                id[i][1]=bb;
                bb=i;
            }
        }
        msa.initSA(a,n,mn+10);
       // for(int i=0;i<n;++i)printf("%d ",a[i]);pf("");
       // for(int i=0;i<n;++i)printf("%d ",msa.rank[i]);pf("");
        int l=0,r=n;
        for(int i=1;i<n;++i)if(a[i]==1)r=i;
        for(int i=0;i<n-1;++i){
            int cnt=r-l-1;
            if(r==n-1){
                q[cnt].push(MP(-1,i));
            }
            else if(r==n){  //没有零
                q[cnt].push(MP(-2,i));
            }
            else q[cnt].push(MP(msa.rank[r+1],i));
            if(s[i]=='a'){
                l=r;
                a[id[i][0]]=0;
                r=id[i][0];
                if(r<l)swap(l,r);
            }
            else {
                l=r;
                a[id[i][1]]=0;
                r=id[i][1];
                if(r<l)swap(l,r);
            }
        }
        printf("%d",n);
        for(int i=0;i<n;++i){
            while(!q[i].empty()){
                printf(" %d",q[i].top().se+1);
                q[i].pop();
            }
        }
        pf("");
    }
 
}

B. Infinite Tree

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int pmaxn = 1e5 + 2;
const int maxn = 5e5 + 10;
const int MOD = 1e9+7;
const ll inf = 0x3f3f3f3f3f3f3f3f;
vector<int> pri[maxn];
int mxpri[maxn],idpri[maxn];//最大质数，质数编号
ll w[maxn];
int lowbit(int x) { return x & (-x); }
ll sum[maxn], mul[maxn],LobN;
void add(int x, int v) {
    x = LobN - x + 1;
    while (x <= LobN) {
        sum[x] += 1;
        mul[x] = 1ll * mul[x] * v %MOD;
        x += lowbit(x);
    }
}
int Sum(int x) {
    int res = 0;
    x = LobN - x + 1;
    while (x)res += sum[x],x-=lowbit(x);
    return res;
}
int Mul(int x) {
    int res = 1;
    x = LobN - x + 1;
    while (x)res = 1ll * res * mul[x] % MOD , x -= lowbit(x);
    return res;
}
struct node {
    int id, has, dep;
};
node st[maxn];
int top = 0;
vector<pair<int, int> > e[maxn];
void build(int n) {
    int idx = n;
    st[top = 1] = { 1,1,0 };
    for (int i = 2; i <= n; i++) {
        node lc = { ++idx,Mul(idpri[mxpri[i]]),Sum(idpri[mxpri[i]]) };
        int x = i;
        for (auto v : pri[i]) while (x%v == 0)add(idpri[v], v), x /= v;
        node now = { i,Mul(1),Sum(1) };
        if (lc.has == st[top].has) {
            --idx;
            st[++top] = now;
        }
        else {
            while (top > 1 && st[top - 1].dep >= lc.dep) {
                e[st[top - 1].id].push_back({ st[top].id,st[top].dep - st[top - 1].dep }), --top;
            }
            if (st[top].has != lc.has)
                e[lc.id].push_back({ st[top].id,st[top].dep - lc.dep }),st[top] = lc;
            st[++top] = now;
        }
    }
    while (top > 1)
        e[st[top - 1].id].push_back({ st[top].id,st[top].dep - st[top - 1].dep }), --top;
}
ll sz[maxn];
ll d[maxn];
void dfs(int x, int f) {
    sz[x] = w[x];
    d[x] = 0;
    for (auto it : e[x]) {
        int v = it.first, w = it.second;
        if (v != f) {
            dfs(v, x);
            d[x] += 1ll*w * sz[v] + d[v];
            sz[x] += sz[v];
        }
    }
}
ll ans = inf;
void solve(int x, int f) {
    ans = min(ans, d[x]);
    for (auto it : e[x]) {
        int v = it.first, w = it.second;
        if (v != f) {
        
            ll sd = d[x];
            ll sv = d[v];
            ll sx = sz[x];
            ll ssv = sz[v];

            d[x] -= d[v] + 1ll * w*sz[v];
            sz[x]-= sz[v];
            d[v] += d[x] + 1ll * w *sz[x];
            sz[v] += sz[x];

            solve(v, x);
            d[x] = sd;
            d[v] = sv;
            sz[x] = sx;
            sz[v] = ssv;
        }
    }
    e[x].clear();
    sz[x] = 0;
    w[x] = 0;
}
int main() {
    int idx = 0;
    for (int i = 2; i <= pmaxn; ++i) {
        if (pri[i].size() == 0) {
            idpri[i] = ++idx;
            for (int j = i; j <= pmaxn; j += i) {
                {
                        pri[j].push_back(i);
                        mxpri[j] = i;
                }
            }
        }
    }
    int n; 
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++)scanf("%d", &w[i]);
        LobN = n;
        for (int i = 1; i <= LobN; i++)sum[i] = 0, mul[i] = 1;
        build(n);
        ans = inf;
        dfs(1, 0);
        solve(1, 0);
        printf("%lld\n", ans);
    }
    return 0;
}

C. Domino(待补)

D. Quadratic Form

题解：https://www.cnblogs.com/DeaphetS/p/13291266.html

ll f[maxn][maxn<<1],r;
ll b[maxn];
inline void Gauss(int n,int m){
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++)
            if(f[j][i]){
                if(j!=i) for(int k=1;k<=m;k++) swap(f[i][k],f[j][k]);
                break;
            }
        if(!f[i][i]){puts("No Solution");exit(0);}
        r=qpow(f[i][i],mod-2,mod);
        for(int j=i;j<=m;j++) f[i][j]=1LL*f[i][j]*r%mod;
        for(int j=1;j<=n;j++)
            if(j!=i){
                r=f[j][i];
                for(int k=i;k<=m;k++)
                    f[j][k]=(f[j][k]-1LL*r*f[i][k]%mod+mod)%mod;
            }
    }
//    for(int i=1;i<=n;i++){
//        for(int j=n+1;j<=m;j++) printf("%d ",f[i][j]);
//        puts("");
//    }
    return;
}
Anoyer(){
#ifdef LOCAL
    fcin;
    //fcout;
#endif
    int n,m;
    while(scanf("%d",&n)!=EOF){
        met(f,0);
        m=2*n;
        Fup(i,n){
            Fup(j,n)sf(f[i][j]),f[i][j]=(f[i][j]+mod)%mod;
            f[i][n+i]=1;
        }
        Fup(i,n)sf(b[i]),b[i]=(b[i]+mod)%mod;
        Gauss(n,m);
        ll ans=0;   //ans=B^t * A^-1 *B  利用拉格朗日乘数法
        Fup(i,n){
            for(int j=n+1;j<=m;j++)ans=(ans+f[i][j]*b[i]%mod*b[j-n]%mod)%mod;
        }
        pf(ans);
    }
}

E. Counting Spanning Trees(待补)

F. Infinite String Comparision

char a[maxn],b[maxn];
Anoyer(){
#ifdef LOCAL
    fcin;
    //fcout;
#endif
        while(~scanf("%s%s",a,b)){
            int lena = strlen(a);
            int lenb = strlen(b);
            bool sw = 0;
            if(lena < lenb){
                sw = 1;
                swap(a,b);
                swap(lena,lenb);
            }
            for(int i = lena ;i<lena*2;++i)a[i] = a[i%lena];
            lena*=2;
            bool ok = 0;
            for(int i=0;i<lena;i++){
 
                if(a[i]!=b[i % lenb]){
 
                    if(a[i] > b[i%lenb])
                      {
                        if(!sw)
                         printf(">\n");
                        else
                            printf("<\n");
                          ok=1;
                         break;
                        }
                    else if(a[i] <b[i % lenb])
                    {
                        if(!sw)
                        printf("<\n");
                        else
                            printf(">\n");
                        ok = 1;
                        break;
                    }
                }
            }
            if(!ok)printf("=\n");
        }
}

G. BaXianGuoHai, GeXianShenTong(待补)

H. Minimum-cost Flow

#include<bits/stdc++.h>

using namespace std;

#define SZ(x) (x).size()
const int M = 3e5 + 10;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e4;
int N;
struct Edge
{
    int v, cap, cost, rev;//终点，容量（指残量网络中的），费用，反向边编号
    //Edge(int t, int c, int cc, int r) :v(t), cap(c), cost(cc), rev(r){}
};
vector<Edge>G[maxn];//图的邻接表
void init(int _n) {
    N = _n;
    for (int i = 0; i <= N; i++)G[i].clear();
}
void add(int u, int v, int cap, int cost)
{
    G[u].push_back({ v, cap, cost, (int)G[v].size() });
    G[v].push_back({ u, 0, -cost, (int)G[u].size() - 1 });
}
int prevv[maxn];//最短路中的父结点
int preve[maxn];//最短路中的父边
ll dis[maxn];

bool vis[maxn];
#define P pair<ll, ll>
bool spfa(int s, int t) {
    queue<P> q;
    //priority_queue<P, vector<P>, greater<P> >q;
    fill(dis, dis + N + 1, inf);//距离初始化为INF
    fill(vis, vis + N + 1, 0);
    fill(preve, preve + N + 1, -1);
    dis[s] = 0;
    vis[s] = true;
    q.push({ 0, s });
    while (!q.empty()) {
        int u = q.front().second;
        q.pop();
        vis[u] = false;
        for (int i = 0; i < G[u].size(); i++)
        {
            Edge&e = G[u][i];
            if (e.cap > 0 && dis[e.v] > dis[u] + e.cost)//松弛操作
            {
                dis[e.v] = dis[u] + e.cost;
                prevv[e.v] = u;//更新父结点
                preve[e.v] = i;//更新父边编号
                if (!vis[e.v]) {
                    vis[e.v] = 1;
                    q.push(P(dis[e.v], e.v));
                }
            }
        }
    }
    if (preve[t] == -1)return false;
    return true;
}
ll Cost[maxn];
int idx = 1;
//返回的是最大流，cost 存的是最小费
int mincostmaxflow(int s, int t, int &cost) {
    int flow = 0;
    cost = 0;
    while (spfa(s, t)) {
        int d = inf;
        for (int x = t; x != s; x = prevv[x])
            d = min(d, G[prevv[x]][preve[x]].cap);//从t出发沿着最短路返回s找可改进量
        cost += d * dis[t];
        Cost[idx] = dis[t];
        ++idx;
        for (int x = t; x != s; x = prevv[x]) {
            Edge&e = G[prevv[x]][preve[x]];
            e.cap -= d;//修改残量值
            G[x][e.rev].cap += d;
        }
        flow += d;
    
    }
    return flow;
}
template<typename T> inline T Gcd(T a, T b) { while (b) { T t = b; b = a % b; a = t; }return a; }
ll sum[maxn];
int main() {

    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        idx = 1;
        memset(Cost, 0, sizeof(Cost));
        init(n + 5);
        int S = n + 1;
        add(S, 1, 200, 0);
        for (int i = 1; i <= m; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, 1, w);
        }
        int cost = 0;
        mincostmaxflow(1, n, cost);
        int q; scanf("%d", &q);
        for (int i = 1; i < idx; i++)sum[i] = sum[i - 1] + Cost[i];
        while (q--) {
            ll x, y; scanf("%lld%lld", &x, &y);
            if (x == 0) { printf("NaN\n"); continue; }
            ll a = y / x;
            ll b = y % x;
            if (a + (bool)b >= idx) { printf("NaN\n"); continue; }
            ll ans = sum[a] * x + Cost[a + 1] * b;
            ll gc = Gcd(ans, 1ll * y);
            printf("%lld/%lld\n", ans / gc, y / gc);
        }
    }
    return 0;
}

I. 1 or 2

#include<bits/stdc++.h>
using namespace std;


const int N = 500 + 10;

//复杂度N^3,带花树匹配，一般图最大匹配
struct Match {
    int n;
    vector<int> G[N];    //图
    int fa[N], mt[N], pre[N], mk[N];
    int lca_clk, lca_mk[N];
    pair<int, int> ce[N];
    void add(int x, int y) {
        G[x].push_back(y);
    }
    void init(int n_) {
        n = n_;
        for (int i = 0; i <= n; i++) {
            G[i].clear();
            ce[i].first = ce[i].second = 0;
            lca_mk[i] = 0;
        }
        lca_clk = 0;
    }
    void connect(int u, int v) {
        mt[u] = v;
        mt[v] = u;
    }
    int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
    void flip(int s, int u) {
        if (s == u) return;
        if (mk[u] == 2) {
            int v1 = ce[u].first, v2 = ce[u].second;
            flip(mt[u], v1);
            flip(s, v2);
            connect(v1, v2);
        }
        else {
            flip(s, pre[mt[u]]);
            connect(pre[mt[u]], mt[u]);
        }
    }
    int get_lca(int u, int v) {
        lca_clk++;
        for (u = find(u), v = find(v); ; u = find(pre[u]), v = find(pre[v])) {
            if (u && lca_mk[u] == lca_clk) return u;
            lca_mk[u] = lca_clk;
            if (v && lca_mk[v] == lca_clk) return v;
            lca_mk[v] = lca_clk;
        }
    }
    void access(int u, int p, const pair<int, int>& c, vector<int>& q) {
        for (u = find(u); u != p; u = find(pre[u])) {
            if (mk[u] == 2) {
                ce[u] = c;
                q.push_back(u);
            }
            fa[find(u)] = find(p);
        }
    }
    bool aug(int s) {
        fill(mk, mk + n + 1, 0);
        fill(pre, pre + n + 1, 0);
        iota(fa, fa + n + 1, 0); //从0开始，构建0 1 2 3 ...序列，初始化并查集
        vector<int> q = { s };
        mk[s] = 1;
        int t = 0;
        for (int t = 0; t < (int)q.size(); ++t) {
            int u = q[t];
            for (int &v : G[u]) {
                if (find(v) == find(u)) continue;
                if (!mk[v] && !mt[v]) {
                    flip(s, u);
                    connect(u, v);
                    return true;
                }
                else if (!mk[v]) {
                    int w = mt[v];
                    mk[v] = 2; mk[w] = 1;
                    pre[w] = v; pre[v] = u;
                    q.push_back(w);
                }
                else if (mk[find(v)] == 1) {
                    int p = get_lca(u, v);
                    access(u, p, { u, v }, q);
                    access(v, p, { v, u }, q);
                }
            }
        }
        return false;
    }
    int match() {
        fill(mt + 1, mt + n + 1, 0);
        lca_clk = 0;
        int ans = 0;
        for (int i = 1; i <= n + 1; i++)
            if (!mt[i]) ans += aug(i);
        return ans;
    }

}_Match;
int d[N];
int main() {
    int n,m;

    while (~scanf("%d%d", &n, &m)) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &d[i]);
            cnt += d[i];
        }
        cnt += m * 2;
        cnt /= 2;
        _Match.init(2 * n + 2 * m + 10);
        for (int i = 1; i <= m; i++) {
            int x, y; scanf("%d%d", &x, &y);
            if (d[x] == 2) {
                _Match.add(x, 2 * n + i);
                _Match.add(2 * n + i,x);
                _Match.add(x + n, 2 * n + i);
                _Match.add(2 * n + i, x + n);
            }
            else {
                _Match.add(x, 2 * n + i);
                _Match.add(2 * n + i,x);
            }
            if (d[y] == 2) {
                _Match.add(y, 2 * n + m+i);
                _Match.add(2 * n + m + i, y);
                _Match.add(y + n, 2 * n + m + i);
                _Match.add(2 * n + m + i, y + n);
            }
            else {
                _Match.add(y, 2 * n + m + i);
                _Match.add(2 * n + m + i, y);
            }
            _Match.add(2 * n + i, 2 * n + m + i);
            _Match.add(2 * n + m + i, 2 * n + i);
        }
        if (_Match.match() == cnt)
            printf("Yes\n");
        else 
            printf("No\n");
    }
    return 0;
}

J. Easy Integration

ll pre[maxn];
Anoyer(){
#ifdef LOCAL
    fcin;
    //fcout;
#endif
    pre[0]=1;
    for(int i=1;i<maxn;++i)pre[i]=pre[i-1]*i%mod;
    int n;
    while(scanf("%d",&n)!=EOF){
        ll ans=qpow(pre[n],2,mod)*qpow(pre[2*n+1],mod-2,mod)%mod;
        pf(ans);
    }
}

2020牛客暑期多校训练营（第一场）

题目链接

A. B-Suffix Array

B. Infinite Tree

C. Domino(待补)

D. Quadratic Form

E. Counting Spanning Trees(待补)

F. Infinite String Comparision

G. BaXianGuoHai, GeXianShenTong(待补)

H. Minimum-cost Flow

I. 1 or 2

J. Easy Integration

2 条评论

发表评论取消回复

2019 ICPC 徐州复现赛

2020牛客暑期多校训练营（第一场）

ACDreams小组个人训练（八）-- CF#603

ACDreams小组个人训练（九）-- CF#590

Benelux Algorithm Programming Contest 2019

2020 Multi-University Training Contest 3

ICPC Central Europe Regional Contest 2019

ICPC Southeastern Europe Contest 2019

2020 Multi-University Training Contest 4

ICPC North Central NA Contest 2017

2020牛客暑期多校训练营（第一场）

题目链接

A. B-Suffix Array

B. Infinite Tree

C. Domino(待补)

D. Quadratic Form

E. Counting Spanning Trees(待补)

F. Infinite String Comparision

G. BaXianGuoHai, GeXianShenTong(待补)

H. Minimum-cost Flow

I. 1 or 2

J. Easy Integration

A. B-Suffix Array

B. Infinite Tree

C. Domino(待补)

D. Quadratic Form

E. Counting Spanning Trees(待补)

F. Infinite String Comparision

G. BaXianGuoHai, GeXianShenTong(待补)

H. Minimum-cost Flow

I. 1 or 2

J. Easy Integration

2 条评论

发表评论 取消回复

2020牛客暑期多校训练营（第一场）

A. B-Suffix Array

B. Infinite Tree

C. Domino(待补)

D. Quadratic Form

E. Counting Spanning Trees(待补)

F. Infinite String Comparision

G. BaXianGuoHai, GeXianShenTong(待补)

H. Minimum-cost Flow

I. 1 or 2

J. Easy Integration

发表评论取消回复