2019 ICPC 南京网络赛

短命女 2023-10-10 07:49 80阅读 0赞

A. 00:40:35 solved by hl

很显然需要一种方法O(1)定位x,y上的数字，利用矩阵的规律可以找到

然后就是一个子矩阵和问题，小范围可以直接二维前缀和，大范围就是一个二位偏序问题，

将一个询问拆成4个询问，树状数组解决即可

![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 = 1e6 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    int N,M,Q;
    LL pre[maxn];
    void init(){
        pre[0] = 0;
        for(int sum = N,i = 1; sum > 0; i ++,sum -= 2){
            pre[i] = pre[i - 1] + sum + sum + sum + sum - 4;
        }
    }
    inline int min(int a,int b,int c,int d){
        return min(min(min(a,b),c),d);
    }
    inline LL id(int x,int y){
        int q = min(x,y,N - x + 1,N - y + 1);
        LL ans = pre[q - 1] + 1;
        int sx = N - q + 1,sy = N - q + 1;
        if(sx == x) return ans + sy - y;
        ans += sy - q; sy = q;
        if(sy == y) return ans + sx - x;
        ans += sx - q; sx = q;
        if(sx == x) return ans + y - sy;
        ans += (N - q + 1) - sy; sy = N - q + 1;
        return ans + x - sx;
    }
    inline LL val(int x,int y){
        LL sum = id(x,y);
        LL ans = 0;
        while(sum){
            ans += sum % 10;
            sum /= 10;
        }
        return ans;
    }
    struct Good{
        int x,y;
        LL ans;
    }g[maxn];
    struct Query{
        int x,y,id,flag;
        Query(int x = 0,int y = 0,int id = 0,int flag = 0):x(x),y(y),id(id),flag(flag){}
    }query[maxn];
    LL fans[maxn];
    bool cmp(Good a,Good b){
        return a.x < b.x;
    }
    LL tree[maxn];
    void add(int u,int v){
        for(;u <= N; u += u & -u) tree[u] += v;
    }
    LL getsum(int u){
        LL ans = 0;
        for(;u > 0; u -= u & -u) ans += tree[u];
        return ans;
    }
    bool cmp2(Query a,Query b){
        return a.x < b.x;
    }
    int main(){
        int T = read();
        while(T--){
            Mem(tree,0);
            Sca3(N,M,Q);init();
            for(int i = 1; i <= Q; i ++) fans[i] = 0;
            for(int i = 1; i <= M; i ++){
                g[i].x = read(),g[i].y = read();
                g[i].ans = val(g[i].x,g[i].y);
            }
            int cnt = 0;
            for(int i = 1; i <= Q; i ++){
                int x1 = read(),y1 = read(),x2 = read(),y2 = read();
                query[++cnt] = Query(x1 - 1,y1 - 1,i,1);
                query[++cnt] = Query(x2,y1 - 1,i,-1);
                query[++cnt] = Query(x1 - 1,y2,i,-1);
                query[++cnt] = Query(x2,y2,i,1);
            }
            sort(g + 1,g + 1 + M,cmp);
            sort(query + 1,query + 1 + cnt,cmp2);
            int s1 = 1,s2 = 1;
            for(int i = 0; i <= N ; i ++){
                while(s1 <= M && g[s1].x == i){
                    add(g[s1].y,g[s1].ans);
                    s1++;
                }
                while(s2 <= cnt && query[s2].x == i){
                    fans[query[s2].id] += query[s2].flag * getsum(query[s2].y);
                    s2++;
                }
            }
            for(int i = 1; i <= Q; i ++) Prl(fans[i]);
        }
    
        
        return 0;
    }

B.1:42:29(-1) solved by gbs

队友说 是裸的指数循环节

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

#include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>
    #include <map>
    #include <set>
    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <vector>
    #include <queue>
    
    
    using namespace std;
    
    typedef long long LL;
    
    int a,b,m;
    LL eular(LL n)
    {
        LL ans = n;
        for (int i = 2; i * i <= n; i++)
        {
            if (n % i == 0)
            {
                ans -= ans / i;
                while (n % i == 0)
                    n /= i;
            }
        }
        if (n != 1)
            ans -=ans / n;
        return ans;
    }
    const LL mod = 1e9 + 7; //¿ìËÙÃÝ
    int quick_mi(LL a, LL k,LL mod)
    {
        if (k == 0)
            return 1;
        if (a<=1)
            return a;
        bool if_over = false;
        LL k1 = 1;
        for (int i=0; i<k; i++)
        {
            k1 = k1*a;
            if (k1>= mod)
            {
                if_over = true;
                break;
            }
        }
        LL ans = 1;
        while (k)
        {
            if (k & 1)
            {
                ans *= a;
                ans %= mod;
            }
            a *= a;
            a %= mod;
            k >>= 1;
        }
        if (if_over)
        {
            ans += mod;
        }
        return ans;
    }
    
    LL dfs(int a,int b,LL mod)
    {
        if (b == 0)
            return 1;
        if (b == 1)
            return a;
        if (mod == 1)
            return 1;
        LL h1=quick_mi(a,dfs(a,b-1,eular(mod)),mod);
        //cout<<mod<<' '<<h1<<endl;
        return h1;
    }
    
    int main()
    {
        int t;
        
        cin >>t;
        while(t--)
        {
            cin >>a>>b>>m;
            int h1 = dfs(a,b,m);
            cout<<h1%m<<endl;;
        }
    
    
    
    
    #ifdef VSCode
        system("pause");
    #endif
        return 0;
    }

D.00:44:59 solved by zcz

![1468815-20190901193435197-594160014.png][]

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

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<vector>
    using namespace std;
    
    double p1[100005],p2[100005];
    int n,m;
    vector<int> e[100005];
    
    double getp2(int u)
    {
        if(p2[u]>=0)    return p2[u];
        int l=e[u].size();
        double rec=0;
        for(int i=0;i<l;i++)
        {
            rec+=getp2(e[u][i])+1;
        }
        p2[u]=(rec+1)/l;
        return p2[u];
    }
    
    double getp1(int u)
    {
        if(p1[u]>=0)    return p1[u];
        int l=e[u].size();
        double rec=0;
        for(int i=0;i<l;i++)
        {
            rec+=getp1(e[u][i])+p2[e[u][i]];
        }
        p1[u]=(rec+p2[u])/l;
        return p1[u];
    }
    
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            cin>>n>>m;
            for(int i=1;i<=n;i++)
            {
                p1[i]=-1,p2[i]=-1;
                e[i].clear();
            }
            p2[n]=1;
            p1[n]=0;
            while(m--)
            {
                int u,v;
                scanf("%d%d",&u,&v);
                e[u].push_back(v);
            }
            getp2(1);
            getp1(1);
            printf("%.2lf\n",p1[1]);
        }
    
    
        return 0;
    }

F. 1:30:28 solved by zcz and hl

线段树维护区间最大值的下标，按照数的大小从小到大询问然后修改

![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;
    int a[maxn],id[maxn];
    int ans[maxn];
    struct node{
        int pos,val;
        node(int pos = 0,int val = 0):pos(pos),val(val){}
        friend node operator + (node a,node b){
            if(a.val < b.val) return b;
            return a;
        }
    };
    struct Tree{
        int l,r;
        node ans;
    }tree[maxn << 2];
    void Pushup(int t){
        tree[t].ans = tree[t << 1].ans + tree[t << 1 | 1].ans;
    }
    void Build(int t,int l,int r){
        tree[t].l = l ; tree[t].r = r;
        tree[t].ans = node(0,0);
        if(l == r){
            tree[t].ans = node(l,0);
            return;
        }
        int m = l + r >> 1;
        Build(t << 1,l,m); Build(t << 1 | 1,m + 1,r);
        Pushup(t);
    }
    node query(int t,int l,int r){
        if(l <= tree[t].l && tree[t].r <= r){
            return tree[t].ans;
        }
        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);
        else{
            return query(t << 1,l,m) + query(t << 1 | 1,m + 1,r);
        }
    }
    void update(int t,int pos){
        if(tree[t].l == tree[t].r){
            tree[t].ans.val = a[pos];
            return; 
        }
        int m = (tree[t].l + tree[t].r) >> 1;
        if(pos <= m)  update(t << 1,pos);
        else update(t << 1 | 1,pos);
        Pushup(t);
    }
    int main(){
        int T = read();
        while(T--){
            Sca2(N,K);
            for(int i = 1; i <= N; i ++) ans[i] = 0;
            for(int i = 1; i <= N ; i ++) Sca(a[i]),id[a[i]] = i;
            Build(1,1,N);
            for(int i = 1; i <= N ; i ++){
                int l = max(1,id[i] - K),r = min(N,id[i] + K);
                node t = query(1,l,r);
                ans[i] = ans[t.val] + 1;
                update(1,id[i]);
            }
            for(int i = 1; i <= N; i ++){
                printf("%d",ans[i]);
                if(i != N) printf(" ");
            }
            puts("");
        }
        return 0;
    }

G.4:35:30(-7) solved by zcz

一个很麻烦的线性规划

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

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    long long f(long long a,long long b,long long c)
    {
        if(a<b)
        {
            long long t=a;
            a=b;
            b=t;
        }
        if(c<0) return 0;
        if(c>=a+b)  return (a+1)*(b+1);
        if(c<=b)    return (c+1)*(c+2)/2;
        if(b<c&&c<a)    return (b+1)*(b+2)/2+(c-b)*(b+1);
        long long t=a+b-c;
        return (a+1)*(b+1)- t*(t+1)/2;
    }
    
    long long f2(long long x)
    {
        return (3*x*(x+1)+x*(x+1)*(2*x+1))/12;
    }
    
    long long f3(long long x)
    {
        return x*(x+1)/2;
    }
    
    long long f4(long long a,long long b,long long c)
    {
        if(a<b)
        {
            long long t=a;
            a=b;
            b=t;
        }
        if(c<0) return 0;
        if(c<=b)    return f2(c+1);
        if(c<=a)    return f2(b+1)+f3(b+1)*(c-b)+f3(c-b)*(b+1);
        long long tem=f4(a,b,a);
        if(c<=a+b)  return tem+f(a,b,a)*(c-a)+b*f3(c-a)-f2(c-a-1);
        return f4(a,b,a+b)+f(a,b,a+b)*(c-(a+b));
    }
    
    int main()
    {
        //cout<<f(2,2,2)<<endl;
        //cout<<f4(3,3,6);
        int T;
        cin>>T;
        while(T--)
        {
            long long l1,l2,l3,l4,r1,r2,r3,r4;
            cin>>l1>>r1>>l2>>r2>>l3>>r3>>l4>>r4;
            if(r1<l1||r2<l2||r3<l3||r4<l4)
            {
                cout<<0<<endl;
                continue;
            }
            long long ans=0;
            for(long long d=l4;d<=r4;d++)
            {
                ans+=f4(r1-l1,r2-l2,r3-d-l1-l2)-f4(r1-l1,r2-l2,l3-d-l1-l2-1);
                ans+=f4(r2-l2,r3-l3,r1-d-l2-l3)-f4(r2-l2,r3-l3,l1-d-l2-l3-1);
                ans+=f4(r1-l1,r3-l3,r2-d-l1-l3)-f4(r1-l1,r3-l3,l2-d-l1-l3-1);
                ans+=f4(r1-l1,r2-l2,d-l1-l2-l3)-f4(r1-l1,r2-l2,d-l1-l2-r3-1);
            }
            ans=(r1-l1+1)*(r2-l2+1)*(r3-l3+1)*(r4-l4+1)-ans;
            cout<<ans<<endl;
        }
    /*
    666
    1 2 1 2 1 2 1 888
    1 888 1 2 1 2 1 2
    */
    
    
        return 0;
    }

H.1:06:48(-1) solved by hl

没有负环的条件是没有一条来的路和加的边加起来为负，所以每次加的边为反向最短路

![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 = 310;
    const int maxm = 710;
    const LL INF = 1e18;
    const int mod = 1e9 + 7; 
    int N,M,K;
    struct Edge{
        int to,next;
        LL dis;
    }edge[maxm * 2];
    int head[maxn],tot;
    void init(){
        for(int i = 0 ; i <= N ; i ++) head[i] = -1;
        tot = 0;
    }
    void add(int u,int v,LL w){
        edge[tot].to = v;
        edge[tot].next = head[u];
        edge[tot].dis = w;
        head[u] = tot++;
    }
    LL dis[1005],vis[1005];
    struct node{
        int pos;
        LL val;
        node(int pos,LL val):pos(pos),val(val){}
        friend bool operator < (node a,node b){
            return a.val > b.val;
        }
    };
    LL Dijkstra(int s,int t){
        for(int i = 0; i <= N ; i ++) dis[i] = INF;
        dis[s] = 0;
        priority_queue<node>Q;
        Q.push(node(s,0));
        while(!Q.empty()){
            node u = Q.top(); Q.pop();
            if(u.val > dis[u.pos]) continue;
            for(int i = head[u.pos]; ~i; i = edge[i].next){
                int v = edge[i].to;
                if(dis[v] > edge[i].dis + u.val){
                    dis[v] = edge[i].dis + u.val;
                    Q.push(node(v,dis[v]));
                }
            }
        }
        return dis[t];
    }
    int main(){
        int T = read();
        while(T--){
            Sca2(N,M); init();
            for(int i = 1; i <= M ; i ++){
                int u = read(),v = read(); LL w = read();
                add(u,v,w);
            }
            for(int i = 1; i <= 6; i ++){
                int u = read(),v = read();
                //S = u,T = v;
                LL ans = -Dijkstra(v,u);
                add(u,v,ans);
                Prl(ans);
            }
        }
        return 0;
    }

I.2:40:04(-5) solved by gbs

已经多次证实两个人敲同一道题的后果就是罚时++

[hl赛后补题][hl]

隐约听到了队友说的类似于玄学，暴力之类的做法

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

#include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>
    #include <map>
    #include <set>
    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <vector>
    #include <queue>
    
    
    using namespace std;
    
    typedef long long LL;
    
    int an[1123456];
    int ans[123456];
    
    int main()
    {
        int N;
        int y;
        while(cin >>N>>y)
        {
            for (int i=0; i<N; i++)
            {
                scanf("%d",&an[i]);
            }
            if (N ==1)
            {
                for (int j=1 ;j<=y; j++)
                {
                    ans[j] = an[0] + j;
                }
            }
            else
            {
                sort(an,an+N);
                int nowi = N-1;
                int now_ans ;
                for (int j=y; j>=1; j--)
                {
                    if (nowi == 0)
                    {
                        ans[j] = an[N-1]+j;
                        continue;
                    }
                    now_ans = max(an[N-1]+j,an[nowi-1]+y);
                    while(an[nowi-1] + j<=an[nowi])
                    {
                        nowi--;
                        if (nowi == 0)
                        {
                            now_ans = an[N-1]+j;
                            break;
                        }  
                        now_ans = max(an[N-1]+j,an[nowi-1]+y);
                    }
                    ans[j] = now_ans;
                }
            }
            for (int j=1; j<=y; j++)
            {
                if (j!=1)
                    printf(" ");
                printf("%d",ans[j]);
            }
            printf("\n");
            
        }
    
    
    
    
    #ifdef VSCode
        system("pause");
    #endif
        return 0;
    }

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

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif
[1468815-20190901193435197-594160014.png]: https://img2018.cnblogs.com/blog/1468815/201909/1468815-20190901193435197-594160014.png
[hl]: https://www.cnblogs.com/Hugh-Locke/p/11447725.html