2019 ICPC 上海网络赛

深藏阁楼爱情的钟 2023-10-10 07:51 50阅读 0赞

摸了一整场的鱼，签了个到，做了个FFT还忘记初始化赛后才发现

B.00:16:52 solved by hl

很显然前缀和搞搞就行了，但是卡O(N),要O(M)

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

C.unsolved by hl

小范围n²logn的树状数组常规暴力

大范围三次FFT解决a,b,c三个元作为最大值的情况，加上a,b,c三个元有两个同时作为最大值的情况，加上三个数一样的情况即可.

![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 = 4e5 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    int N,M,K;
    LL a[maxn],b[maxn],c[maxn];
    struct complex{
        double x,y;
        complex(){}
        complex(double x,double y):x(x),y(y){}
        inline friend complex operator - (complex a,complex b){
         return complex(a.x - b.x,a.y - b.y);}
        inline friend complex operator + (complex a,complex b){
         return complex(a.x + b.x,a.y + b.y);}
        inline friend complex operator * (complex a,complex b){
         return complex(a.x * b.x - a.y * b.y,a.x * b.y + a.y * b.x);}
    }A[maxn << 2],B[maxn << 2];
    int r[maxn << 2],limit;
    inline void FFT(int limit,complex *A,int *r,int type){  
        for(register int i = 0 ; i < limit; i ++) if(i < r[i]) swap(A[i],A[r[i]]);
        for(register int mid = 1; mid < limit; mid <<= 1){  
            complex Wn(cos(PI / mid),type * sin(PI / mid)); 
            int len = mid << 1;   
            for(register int j = 0; j < limit; j += len){ 
                complex w(1,0);
                for(register int k = 0 ; k < mid; k ++, w = w * Wn){
                    complex x = A[j + k],y = w * A[j + mid + k];
                    A[j + k] = x + y;
                    A[j + mid + k] = x - y;
                }
            }
        }
    }
    LL pre[maxn];
    LL tmp[maxn],cnt[maxn];
    LL x[maxn],y[maxn],z[maxn];
    inline LL cul(LL *a,LL *b,LL *c){
        for(register int i = 0 ; i <= M ; i ++) tmp[i] = cnt[i] = 0;
        for(register int i = 1; i <= N ; i ++) tmp[b[i]]++;
        for(register int i = 1 ; i <= M ; i ++) tmp[i] += tmp[i - 1];
        for(register int i = 1; i <= N ; i ++) cnt[a[i]]++;
        LL sum = 0;
        for(register int i = 1; i <= N ; i ++) sum += cnt[c[i]] * tmp[c[i] - 1];
        return sum;
    }
    inline LL solve(LL *a,LL *b,LL *c){
        LL ans = 0;
        int cnt1 = 1,cnt2 = 1;
        for(register int i = 0 ; i < limit; i ++) A[i].y = B[i].y = A[i].x = B[i].x = 0;
        for(register int i = 1; i <= N ; i ++) A[b[i]].x++;
        for(register int i = 1; i <= N ; i ++) B[c[i]].x++;
        FFT(limit,A,r,1); FFT(limit,B,r,1);
        for(register int i = 0; i < limit ; i ++) A[i] = A[i] * B[i];
        FFT(limit,A,r,-1); pre[limit] = 0;
        for(register int i = 0 ; i < limit ; i ++) pre[i] = (LL)(A[i].x / limit + 0.5);
        for(register int i = limit - 1; i >= 0; i --) pre[i] += pre[i + 1];
        for(register int i = 1; i <= N ; i ++){
            while(cnt1 <= N && b[cnt1] < a[i]) cnt1++;
            while(cnt2 <= N && c[cnt2] < a[i]) cnt2++;
            LL v = N + 1 - cnt1,u = N + 1 - cnt2;
            ans += pre[a[i]] - v * N - u * N + v * u;
        }
        return ans;
    }
    LL tree[maxn];
    inline void add(int u,int x){
        for(;u <= M + M; u += u & -u) tree[u] += x;
    }
    inline int getsum(int x){
        int ans = 0;
        for(;x > 0; x -= x & -x) ans += tree[x];
        return ans;
    }
    inline LL solve2(LL *a,LL *b,LL *c){
        for(int i = 1; i <= N ; i ++){
            add(c[i],1);
        }
        LL ans = 0;
        for(int i = 1; i <= N ; i ++){
            for(int j = 1; j <= N ; j ++){
                int r = a[i] + b[j],l = abs(a[i] - b[j]);
                ans += getsum(r);
                if(l > 0) ans -= getsum(l - 1);
            }
        }
        for(int i = 1; i <= N ; i ++) add(c[i],-1);
        return ans;
    }
    int main(){
        int T = read();
        int Case = 1;
        while(T--){
            Sca(N); M = 0;
            for(int i = 1; i <= N ; i ++) a[i] = read(),M = max((LL)M,a[i]);
            for(int i = 1; i <= N ; i ++) b[i] = read(),M = max((LL)M,b[i]);
            for(int i = 1; i <= N ; i ++) c[i] = read(),M = max((LL)M,c[i]);
            sort(a + 1,a + 1 + N);
            sort(b + 1,b + 1 + N);
            sort(c + 1,c + 1 + N);
            if(N <= 1000){
                printf("Case #%d: ",Case++);
                LL ans = solve2(a,b,c);
                Prl(ans);
                continue;
            } 
            limit = 1;
            int l = 0; while(limit <= M + M) limit <<= 1,l++;
            for(int i = 0 ; i < limit; i ++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
            
            LL ans = 0;
            ans += solve(a,b,c);
            ans += solve(b,c,a);
            ans += solve(c,a,b);
            LL sum = 0;
            sum += cul(a,b,c);
            sum += cul(b,c,a);
            sum += cul(c,a,b);
            ans += sum;
            for(int i = 0 ; i <= M ; i ++) x[i] = y[i] = z[i] = 0;
            for(int i = 1; i <= N ; i ++){
                x[a[i]]++; y[b[i]]++; z[c[i]]++;
            }
            for(int i = 0; i <= M ; i ++) ans += x[i] * y[i] * z[i];
            printf("Case #%d: ",Case++);
            Prl(ans);
        }
        return 0;
    }

D.12:43:08 solved by zcz

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

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<vector>
    using namespace std;
    
    
    long long ans[3005];
    int vis[3005];
    long long A[3005];
    long long maxn=3000;
    long long mod=1e9+7;
    vector<long long> v;
    long long q_p(long long a,long long b){
        long long ans = 1;
        while(b){
            if(b & 1)ans = ans * a % mod;
            b >>= 1;
            a = a * a % mod;
        }
        return ans;
    }
    long long inv(long long a){
        return q_p(a,mod - 2);
    }
    void dfs(long long sum,long long s,long long t)
    {
        long long cnt1=s-sum;
        if(cnt1+v.size()+1>maxn) return ;
        v.push_back(t);
        vis[t]++;
        long long fz=0;
        long long fm=1;
        for(int i=0;i<v.size();i++)
        {
            if(i==0||v[i]!=v[i-1])
            {
                fm*=A[vis[v[i]]];
                fm%=mod;
            }
        }
        fm*=A[cnt1];
        fm%=mod;
        fz=A[cnt1+v.size()];
    
        ans[cnt1+v.size()]+=fz*inv(fm);
        ans[cnt1+v.size()]%=mod;
        for(int i=t;i<=maxn;i++)
        {
            dfs(sum+i,s*i,i);
        }
        v.pop_back();
        vis[t]--;
    }
    
    
    int main()
    {
    
        A[0]=1;
        for(int i=1;i<=maxn;i++)
        {
            A[i]=A[i-1]*i;
            A[i]%=mod;
        }
        for(int i=2;i<=maxn;i++)
        {
            dfs(i,i,i);
        }
        int T;
        cin>>T;
        while(T--)
        {
            int n;
            cin>>n;
            cout<<ans[n]<<endl;
        }
    
        return 0;
    }

F.3:38:14(-2) 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 __int128 LL;
    
    void scan(__int128 &x)//输入
    {
        x = 0;
        int f = 1;
        char ch;
        if((ch = getchar()) == '-') f = -f;
        else x = x*10 + ch-'0';
        while((ch = getchar()) >= '0' && ch <= '9')
            x = x*10 + ch-'0';
        x *= f;
    }
    void print(__int128 x)
    {
        if (!x) return ;
        if (x < 0) putchar('-'),x = -x;
        print(x / 10);
        putchar(x % 10 + '0');
    }
    
    char stra[30];
    //LL dp[30][30][30];
    
    //LL dp[30][30];
    LL fdp[30][30][30];
    LL sdp[30][30];
    int main()
    {
        for (int j=1; j<=29; j++)
            sdp[0][j] = 1;
        for (int i=1; i<=28; i++)
        {
            if (i == 1)
            {
                //第一个数的最大值是j
                for (int j=1; j<=28; j++)
                    fdp[i][j][j] = 1,fdp[i][j][j-1] = j-1,sdp[i][j] += j;
                continue;
            }
            for (int j=1; j+i-1<=28; j++)//防止爆26
            {
                //cout<<"!!"<<i<<' '<<j<<endl;
                for (int k =max(1,j-1); k<=j+i-1; k++)
                {
                    fdp[i][j][k] = fdp[i-1][j][k] * k + fdp[i-1][j][k-1];
                    //cout<<"@"<<fdp[i][j][k]<<endl;
                    //if (i==2 && j==2)
                    //    cout<<k<<' '<<fdp[i][j][k]<<' '<<fdp[i-1][j][k]<<' '<<fdp[i-1][j][k-1]<<endl;
                    sdp[i][j] += fdp[i][j][k];
                }
            }
        }
        //cout<<sdp[24][1]<<endl;;
        //cout<<sdp[25][1]<<endl;;
        //print(sdp[26][1]);
        int T;
        int n;
        LL m;
        int casen = 1;
        cin >>T;
    
        while(T--)
        {
            cin>>n;
            getchar();
            scan(m);
            stra[n] = 0;
            stra[0] = 'A';
            //m--;
            int now_bit = 1;//目前位
            int now_c;
            for (int i=1; i<n; i++)
            {
                now_c = 1;
                //cout<<"!!!!"<<n-1-i<<' '<<now_bit+1<<' '<<sdp[n-i-1][now_bit+1]<<endl;
                while(m > sdp[n-i-1][now_bit+1])
                {
                    //cout<<"("<<i<<' '<<now_bit<<' '<<sdp[n-i-1][now_bit]<<endl;
                    m-=sdp[n-i-1][now_bit+1];
                    now_c++;
                    
                    now_bit = max(now_c,now_bit);
                    //!!!!!!!
                }
                
                stra[i] = 'A' +now_c-1;
                //cout<<"!!"<<now_c<<stra[i]<<endl;
            }
    
    
    
            printf("Case #%d: %s\n",casen++,stra);
        }
    
    
    
    
    #ifdef VSCode
        system("pause");
    #endif
        return 0;
    }
    /*for (int i=1; i<=26; i++)
        {
            dp[i][0][0] = 1;
            for (int j=1; j<= i; j++)
            {
                for (int k = 1;k<=j; k++)
                {
                    dp[i][j][k] += dp[i][j-1][k] *k + dp[i][j-1][k-1];
                    //cout<<i<<' '<<j<<' '<<k<<" "<<dp[i][j][k]<<endl;
                }
                
            }
        }
        int n1;
        while(cin >>n1)
        {
            LL lltest = 0;
            for (int i=1; i<=n1; i++)
                lltest += dp[n1][n1][i],cout<<i<<"*"<<dp[n1][n1][i]<<endl;;
            cout<<lltest<<endl;
        }*/
        /*dp[1][1] = 1;
        for (int i=2; i<=26; i++)
        {
            dp[i][1] = 1;
            for (int j=2; j<=i-1; j++)
            {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]*j;
            }
            dp[i][i] = 1;
        }
        for (int i=1; i<=26; i++)
        {
            cout<<i<<":"<<dp[26][i]<<endl;
        }*/

I.3:33:45(-4) solved by zcz

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

J.00:24:30 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 an[100];
    LL nowpower[100];
    LL num[100];
    
    int nowbit = 0;
    int T;
    int n,b;
    LL the_ans()
    {
        nowpower[0] = 0;
        num[0] = 1;
        LL ans = 0;
        LL before = 0;
        for (int i=1; i<=nowbit; i++)
        {
            nowpower[i] = nowpower[i-1] * b + (b-1)*b/2*num[i-1];
            num[i] = num[i-1] *b;
        }
        for (int i = nowbit -1; i>=0; i--)
        {
            //cout<<":"<<i<<' '<<an[i]<<endl;
            int t1 = an[i];
            if (t1 >0)
            {
                ans += t1 * nowpower[i];
                ans += ((t1 -1)*t1/2 ) *num[i] + before * t1 * num[i];
                before += t1;
                ans += t1;
            }
        }
    
        return ans;
    }
    
    int main()
    {
        cin >>T;
        int casen = 1;
        while(T--)
        {
            scanf("%d%d",&n,&b);
            int n1= n;
            nowbit = 0;
            while(n1)
            {
                //cout<<n1<<' '<<nowbit<<endl;
                an[nowbit++] = n1%b;
                n1/=b;
            }
            printf("Case #%d: %lld\n",casen++,the_ans());
        }
    
    
    
    
    #ifdef VSCode
        system("pause");
    #endif
        return 0;
    }

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

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