2019 CCPC网络赛

左手的ㄟ右手 2023-10-10 07:49 70阅读 0赞

**一到网络赛，大家都是东亚之光**

1001

00:23:46 solved by hl

签到 枚举一下位就行了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1001

1002

2:40:10(-1) solved by hl,ysw

对序列维护一个权值线段树，维护的东西是区间最大值，然后对于每一个查询二分查找答案，如果在起始点在答案有东西的下标大于终点，就代表答案可以更小

时间复杂度n(logn)²,事实上由于权值线段树的特性，寻找大于R的最小值可以直接在线段树上操作，简化了二分这个操作，时间复杂度nlogn

比赛的时候并没有想到，冲了读入挂趁评测机不注意过去了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)  
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))  
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)  
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)  
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long  
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second 
    typedef vector<int> VI;
    const int MAXBUF=10000;char buf[MAXBUF],*ps=buf,*pe=buf+1;
    inline bool isdigit(const char& n) {
         return (n>='0'&&n<='9');}
    inline void rnext(){
         if(++ps==pe)pe=(ps=buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);}
    template <class T> inline bool in(T &ans){
    #ifdef VSCode
    ans=0;T f=1;register char c;
    do{c=getchar();if ('-'==c)f=-1;}while(!isdigit(c)&&c!=EOF);
    if(c==EOF)return false;do{ans=(ans<<1)+(ans<<3)+c-48;
    c=getchar();}while(isdigit(c)&&c!=EOF);ans*=f;return true;
    #endif
    #ifndef VSCode 
    ans =0;T f=1;if(ps==pe)return false;do{rnext();if('-'==*ps)f=-1;} 
    while(!isdigit(*ps)&&ps!=pe);if(ps==pe)return false;do{ans=(ans<<1)+(ans<<3)+*ps-48;
    rnext();}while(isdigit(*ps)&&ps!=pe);ans*=f;return true;
    #endif
    }const int MAXOUT=10000;
    char bufout[MAXOUT], outtmp[50],*pout = bufout, *pend = bufout+MAXOUT;
    inline void write(){fwrite(bufout,sizeof(char),pout-bufout,stdout);pout = bufout;}
    inline void out_char(char c){*(pout++)=c;if(pout==pend)write();}
    inline void out_str(char *s){
         while(*s){*(pout++)=*(s++);if(pout==pend)write();}}
    template <class T>inline void out_int(T x) {
         if(!x){out_char('0');return;}
    if(x<0)x=-x,out_char('-');int len=0;while(x){outtmp[len++]=x%10+48;x/=10;}outtmp[len]=0;
    for(int i=0,j=len-1;i<j;i++,j--) swap(outtmp[i],outtmp[j]);out_str(outtmp);}
    template<typename T, typename... T2>
    inline int in(T& value, T2&... value2) { in(value); return in(value2...); }
    int read(){
         int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
         if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    int N,M,K;
    int a[maxn],id[maxn];
    struct Tree{
        int l,r,Max;
    }tree[maxn << 2];
    inline void Pushup(int t){
        tree[t].Max = max(tree[t << 1].Max,tree[t << 1 | 1].Max);
    }
    inline void Build(int t,int l,int r){
        tree[t].l = l; tree[t].r = r;
        if(l == r){
            tree[t].Max = id[l];
            return;
        }
        int m = l + r >> 1;
        Build(t << 1,l,m); Build(t << 1 | 1,m + 1,r);
        Pushup(t);
    }
    inline int query(int t,int l,int r){
        if(l <= tree[t].l && tree[t].r <= r){
            return tree[t].Max;
        }
        int m = (tree[t].l + tree[t].r) >> 1;
        if(r <= m) return query(t << 1,l,r);
        else if(l > m) return query(t << 1 | 1,l,r);
        return max(query(t << 1,l,m),query(t << 1 | 1,m + 1,r));
    }
    inline void update(int t,int p){
        if(tree[t].l == tree[t].r){
            tree[t].Max = INF;
            return;
        }
        int m = (tree[t].l + tree[t].r) >> 1;
        if(p <= m) update(t << 1,p);
        else update(t << 1 | 1,p);
        Pushup(t);
    }
    inline int solve(int k,int R){
        int l = k,r = N + 1;
        int ans = N + 1;
        while(l <= r){
            int m = l + r >> 1;
            if(query(1,k,m) > R){
                ans = m;
                r = m - 1;
            }else{
                l = m + 1;
            }
        }
        return ans;
    }
    int main(){
        int T;
        in(T);
        while(T--){
            in(N); in(M);
            for(int i = 1; i <= N ; i ++) in(a[i]),id[a[i]] = i;
            id[N + 1] = INF;
            Build(1,1,N + 1);
            int ans = 0;
            while(M--){
                int op; in(op);
                if(op == 1){
                    int t; in(t);
                    t ^= ans;
                    update(1,a[t]);
                }else{
                    int r,k; in(r); in(k);
                    r ^= ans; k ^= ans;
                //    cout << k << " " << r << endl;
                    Pri(ans = solve(k,r));
                }
            }
        }
        return 0;
    }

1002

1003

1:31:38 (-1) solved by hl

主席树的tot没有初始化 RE一发

先走一个后缀数组，发现只要在给定起始位置上的Height数组连续长度超过给定子串长度len中的一段

用ST表 + 二分可以log时间求出这一段的左右端点，然后就是一个静态区间K大，主席树即可

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)  
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))  
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)  
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)  
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long  
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second 
    typedef vector<int> VI;
    int read(){
         int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
         if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    int N,M,K;
    char str[maxn];
    int sa[maxn],rak[maxn],tex[maxn],tp[maxn],Height[maxn];
    void GetHeight() {
        int j, k = 0;
        for(int i = 1; i <= N; i++){
            if(k) k--;
            int j = sa[rak[i] - 1];
            while(str[i + k] == str[j + k]) k++;
            Height[rak[i]] = k;
        }
    }
    void Qsort(){
        for(int i = 0; i <= M ; i ++) tex[i] = 0;
        for(int i = 1; i <= N ; i ++) tex[rak[i]]++;
        for(int i = 1; i <= M ; i ++) tex[i] += tex[i - 1];
        for(int i = N; i >= 1 ; i --) sa[tex[rak[tp[i]]]--] = tp[i];
    }
    void SA(){
        for(int i = 1; i <= N ; i ++) rak[i] = str[i] - 'a' + 1,tp[i] = i;
        Qsort();
        for(int w = 1,p = 0; p < N; w <<= 1,M = p){
            p = 0;
            for(int i = 1; i <= w; i ++) tp[++p] = N - w + i;
            for(int i = 1; i <= N ; i ++) if(sa[i] > w) tp[++p] = sa[i] - w;
            Qsort();
            swap(tp,rak);
            rak[sa[1]] = p = 1;
            for(int i = 2; i <= N ; i ++){
                rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w])?p:++p;
            }
        }
    }
    int T[maxn];
    struct Tree{
        int lt,rt,sum;
        void init(){
            lt = rt = sum = 0;
        }
    }tree[maxn * 32];
    int tot;
    void newnode(int &t){
        t = ++tot;
        tree[t].init();
    }
    void Build(int &t,int l,int r){
        newnode(t);
        if(l == r) return;
        int m = l + r >> 1;
        Build(tree[t].lt,l,m); Build(tree[t].rt,m + 1,r);
    }
    void update(int &t,int pre,int l,int r,int p){
        newnode(t);
        tree[t] = tree[pre];
        tree[t].sum++;
        if(l == r) return;
        int m = l + r >> 1;
        if(p <= m) update(tree[t].lt,tree[pre].lt,l,m,p);
        else update(tree[t].rt,tree[pre].rt,m + 1,r,p);
    }
    int query(int L,int R,int l,int r,int k){
        if(k > tree[R].sum - tree[L].sum) return -1;
        if(l >= r) return l;
        int num = tree[tree[R].lt].sum - tree[tree[L].lt].sum;
        int m = l + r >> 1;
        if(num >= k) return query(tree[L].lt,tree[R].lt,l,m,k);
        else return query(tree[L].rt,tree[R].rt,m + 1,r,k - num);
    }
    const int SP = 20;
    int MIN[maxn][SP];
    int mm[maxn];
    void initRMQ(int n,int b[]){
        for(int i = 1; i <= n ; i ++){
            for(int j = 0; j < SP; j ++){
                MIN[i][j] = INF;
            }
        }
        mm[0] = -1;
        for(int i = 1; i <= n ; i ++){
            mm[i] = ((i & (i - 1)) == 0)?mm[i - 1] + 1:mm[i - 1];
            MIN[i][0] = b[i];
        }
        for(int j = 1; j <= mm[n]; j ++){
            for(int i = 1; i + (1 << j) - 1 <= n ; i ++){
                MIN[i][j] = min(MIN[i][j - 1],MIN[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int rmq(int x,int y){
        if(x > y) return -1;
        int k = mm[y - x + 1];
        return min(MIN[x][k],MIN[y - (1 << k) + 1][k]);
    }
    int main(){
        int TTT = read();
        while(TTT--){
            Sca2(N,K); tot = 0;
            scanf("%s",str + 1);
            M = 122;
            SA(); GetHeight();
            Build(T[0],1,N);
            for(int i = 1; i <= N ; i ++) update(T[i],T[i - 1],1,N,sa[i]);
            initRMQ(N,Height);
            while(K--){
                int l,r,k; Sca3(l,r,k);
                int len = r - l + 1;
                int p = rak[l];
                int L = p + 1,R = p;
                int ll = 2,rr = p;
                while(ll <= rr){
                    int mid = ll + rr >> 1;
                    if(rmq(mid,p) >= len){
                        rr = mid - 1;
                        L = mid;
                    }else{
                        ll = mid + 1;    
                    }
                }
                L--;
                ll = p + 1,rr = N;
                while(ll <= rr){
                    int mid = ll + rr >> 1;
                    if(rmq(p + 1,mid) >= len){
                        ll = mid + 1;
                        R = mid;
                    }else{
                        rr = mid - 1;
                    }
                }
                Pri(query(T[L - 1],T[R],1,N,k));
            }
        }
        return 0;
    }

1003

1004

3:37:37(-2) solved by hl

做法

1.离线所有询问

2.将一个(点，当前距离)的二元组不断扔进堆，每次取出一个二元组然后丢进所有这个点引申出去的二元组

3.直到取出前50000个，所有答案就都出来了

注意点

1.堆内只能容忍最多5w个二元组，不限制会MLE，所以要用multiset弹出最大的

2.菊花图可以轻松卡掉，如果不边排序的话

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    const int MAXBUF=10000;char buf[MAXBUF],*ps=buf,*pe=buf+1;
    inline bool isdigit(const char& n) {
         return (n>='0'&&n<='9');}
    inline void rnext(){
         if(++ps==pe)pe=(ps=buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);}
    template <class T> inline bool in(T &ans){
    #ifdef VSCode
    ans=0;T f=1;register char c;
    do{c=getchar();if ('-'==c)f=-1;}while(!isdigit(c)&&c!=EOF);
    if(c==EOF)return false;do{ans=(ans<<1)+(ans<<3)+c-48;
    c=getchar();}while(isdigit(c)&&c!=EOF);ans*=f;return true;
    #endif
    #ifndef VSCode 
    ans =0;T f=1;if(ps==pe)return false;do{rnext();if('-'==*ps)f=-1;} 
    while(!isdigit(*ps)&&ps!=pe);if(ps==pe)return false;do{ans=(ans<<1)+(ans<<3)+*ps-48;
    rnext();}while(isdigit(*ps)&&ps!=pe);ans*=f;return true;
    #endif
    }const int MAXOUT=10000;
    char bufout[MAXOUT], outtmp[50],*pout = bufout, *pend = bufout+MAXOUT;
    inline void write(){fwrite(bufout,sizeof(char),pout-bufout,stdout);pout = bufout;}
    inline void out_char(char c){*(pout++)=c;if(pout==pend)write();}
    inline void out_str(char *s){
         while(*s){*(pout++)=*(s++);if(pout==pend)write();}}
    template <class T>inline void out_int(T x) {
         if(!x){out_char('0');return;}
    if(x<0)x=-x,out_char('-');int len=0;while(x){outtmp[len++]=x%10+48;x/=10;}outtmp[len]=0;
    for(int i=0,j=len-1;i<j;i++,j--) swap(outtmp[i],outtmp[j]);out_str(outtmp);}
    template<typename T, typename... T2>
    inline int in(T& value, T2&... value2) { in(value); return in(value2...); }
    #define For(i, x, y) for(int i=x;i<=y;i++)  
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))  
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)  
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)  
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long  
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second 
    typedef vector<int> VI;
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 5e4 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    int N,M,Q;
    struct Edge{
        int to;
        LL dis;
        Edge(){}
        Edge(int to,LL dis):to(to),dis(dis){}
    };
    bool cmp(Edge a,Edge b){
        return a.dis < b.dis;
    }
    vector<Edge>MAP[maxn];
    PII query[maxn];
    struct node{
        int pos;
        LL dis;
        node(){}
        node(int pos,LL dis):pos(pos),dis(dis){}
        friend bool operator < (node a,node b){
            return a.dis < b.dis;
        }
    };
    LL ans[maxn];
    int main(){
        int T; in(T);
        while(T--){
            in(N); in(M); in(Q);
            for(int i = 0 ; i <= N; i ++) MAP[i].clear();
            for(int i = 1; i <= M ; i ++){
                int u,v; LL w;
                in(u); in(v); in(w);
                MAP[u].push_back(Edge(v,w));
            }
            for(int i = 1; i <= N ; i ++) sort(MAP[i].begin(),MAP[i].end(),cmp);
            for(int i = 1; i <= Q; i ++){
                in(query[i].fi);
                query[i].se = i;
            }
            sort(query + 1,query + 1 + Q);
            multiset<node>P;
            for(int i = 1; i <= N ; i ++){
                for(int j = 0 ; j < MAP[i].size(); j ++){
                    P.insert(node(MAP[i][j].to,MAP[i][j].dis));
                //    cout << MAP[i][j].to << " " << MAP[i][j].dis << endl;
                }
            }
            multiset<node>::iterator it;
            int sum = query[Q].fi;
            LL ed = 4e18;
            while(P.size() > sum){
                it = P.end(); it--;ed = (*it).dis;
                P.erase(it);
            }    
            int k = 0;
            int cnt = 1;
            while(sum--){
                it = P.begin();
                node u = *it;  k++;  P.erase(it);
                while(cnt <= Q && query[cnt].fi == k) ans[query[cnt].se] = u.dis,cnt++;
                for(int i = 0 ; i < MAP[u.pos].size(); i ++){
                    int v = MAP[u.pos][i].to;
                    if(MAP[u.pos][i].dis + u.dis >= ed) break;
                    P.insert(node(v,MAP[u.pos][i].dis + u.dis));
                    while(P.size() > sum){
                        it = P.end(); it--;
                        ed = (*it).dis;
                        P.erase(it); 
                    }
                }    
            }
            for(int i = 1; i <= Q; i ++){
                Prl(ans[i]);
            }
        }
        return 0;
    }

1004

1006

0:18:13 solved by hl

签到，从后往前依次输出即可

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1006

1007

0:13:46 solved by hl

签到，按照规律弄出一个大的矩阵然后输出即可

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1007

1008

1:54:25(-1) solved by zcz

因hl冲了一发贪心而产生的WA

队友写的 我不太明白怎么做

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    long long a[100005];
    long long b[100005];
    
    
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            int n,k;
            cin>>n>>k;
            long long s1=0;
            long long s2=0;
            for(int i=0;i<n;i++)
            {
                scanf("%lld",&a[i]);
                s1+=a[i]/k;
                s2+=a[i];
                b[i]=k-(a[i]%k);
            }
            sort(b,b+n);
            for(int i=0;i<n-(s1+1);i++)
            {
                s2+=b[i];
            }
            cout<<s2+k<<endl;
        }
        return 0;
    }

1008

转载于:https://www.cnblogs.com/Hugh-Locke/p/11408509.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif