2019ICPC 沈阳网络赛

左手的ㄟ右手 2023-10-10 07:52 44阅读 0赞

A. 2:40:11(-7) solved by zcz

通过旋转使得抓人的在左下角，逃得在右上角

结论是逃得一定在右上 或者 右下 左上被抓住，找到规律枚举一下即可

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

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    #define LL long long
    long long n,m;
    void change(long long &x,long long &y)
    {
        long long t=x;
        x=m+1-y;
        y=t;
    }
    const int now_size = 3;
    const int mod = 1025436931;
    class Matix
    {
      public:
        LL mdata[3][3];
    
        Matix(int value = 0)
        {
            memset(mdata, 0, sizeof(mdata));
            if (value == 1)
            {
                for (int i = 0; i < now_size; i++)
                    mdata[i][i] = 1;
            }
        }
        Matix(const Matix &s1)
        {
            for (int i = 0; i < now_size; i++)
            {
                for (int j = 0; j < now_size; j++)
                {
                    mdata[i][j] = s1.mdata[i][j];
                }
            }
        }
        Matix operator * (const Matix &s1)
        {
            Matix ans;
            for (int i=0; i<now_size; i++)
            {
                for (int j=0; j<now_size; j++)
                {
                    for (int k=0; k<now_size; k++)
                    {
                        ans.mdata[i][j] = (ans.mdata[i][j] + mdata[i][k]* s1.mdata[k][j])%mod;
                    }
                }
            }
    
            return ans;
        }
    };
    
    LL fbnq(LL k)
    {
        Matix p1;
        p1.mdata[0][0] = 1;
        p1.mdata[0][1] = 1;
        p1.mdata[0][2] = 1;
        p1.mdata[1][1] = 1;
        p1.mdata[1][2] = 1;
        p1.mdata[2][1] = 1;
        Matix ans(1);
        k--;
        while (k)
        {
            if (k&1)
                ans = ans *p1;
            p1 = p1*p1;
            k>>=1;
        }
        LL fans = (ans.mdata[0][0] + ans.mdata[0][1]) % mod;
        return fans;
    }
    
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            long long x1,x2,y1,y2;
            cin>>n>>m>>x1>>y1>>x2>>y2;
            if(n==1&&m==1)
            {
                cout<<"countless"<<endl;
                continue;
            }
            if(x1==x2&&y1==y2)
            {
                cout<<0<<endl;
                continue;
            }
            while(!(x1<x2&&y1<=y2))
            {
                change(x1,y1);
                change(x2,y2);
                swap(n,m);
            }
            if(m==1)
            {
                if((x2-x1)%2==0)
                {
                    cout<<fbnq(n-x1-1)<<endl;
                }
                else
                {
                    cout<<fbnq(n-x1)<<endl;
                }
                continue;
            }
            if((x2-x1+y2-y1)%2==1)
            {
                cout<<"countless"<<endl;
                continue;
            }
            long long ans=n-x1+m-y1;
            if(x2-x1>y2-y1)
            {
                ans=max(ans,n-x1+y1-1);
            }
            if(x2-x1<y2-y1)
            {
                ans=max(ans,m-y1+x1-1);
            }
            cout<<fbnq(ans-1)<<endl;
        }
    
    
        return 0;
    }

B.1:28:35(-1) solved by zcz

并查集缩个点 dfs计算贡献

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

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<vector>
    using namespace std;
    
    vector<int> e[100005];
    int M[100005];
    int pre[100005];
    int cnt[100005];
    
    int Find(int x)
    {
        if(x!=pre[x])
        {
            pre[x]=Find(pre[x]);
        }
        return pre[x];
    }
    
    
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            int n,m,k;
            cin>>n>>m>>k;
            for(int i=1;i<=n;i++)
            {
                e[i].clear();
                M[i]=0;
                pre[i]=i;
                cnt[i]=1;
            }
            while(m--)
            {
                int a,b;
                scanf("%d %d",&a,&b);
                e[a].push_back(b);
                e[b].push_back(a);
            }
            while(k--)
            {
                int a;
                scanf("%d",&a);
                M[a]=1;
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=0;j<e[i].size();j++)
                {
                    if(!M[i]&&!M[e[i][j]])
                    {
                        int x=Find(i);
                        int y=Find(e[i][j]);
                        if(x!=y)
                        {
                            pre[x]=y;
                            cnt[y]+=cnt[x];
                        }
                    }
                }
            }
            int p=Find(1);
            double ans=0;
            for(int i=1;i<=n;i++)
            {
                if(M[i])
                {
                    int c2=0;
                    long long c1=0;
                    int l=e[i].size();
                    for(int j=0;j<l;j++)
                    {
                        if(M[e[i][j]])  continue;
                        if(Find(e[i][j])==p)
                        {
                            c2++;
                        }
                        else
                        {
                            c1+=cnt[Find(e[i][j])];
                        }
                    }
                    if(c2>0&&c2<l)
                    {
                        ans=max(ans,1.0*c1/l);
                    }
                }
            }
            printf("%.8lf\n",cnt[p]+ans);
        }
        return 0;
    }

C.00:44:49(-1) solved by hl

模型都不改的多重背包

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

D.1:07:35 solved by hl

点分治,维护子树余数为0,1,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;
    #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 = 1e4 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    int N,M,K;
    struct Edge{
        int to,next;
        LL dis;
    }edge[maxn << 1];
    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++;
    }
    int root,max_part,SUM;
    bool vis[maxn];
    int size[maxn];
    void dfs_root(int u,int la){
        size[u] = 1;int heavy = 0;
        for(int i = head[u]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(v == la || vis[v]) continue;
            dfs_root(v,u);
            heavy = max(heavy,size[v]);
            size[u] += size[v];
        }
        if(max_part > max(heavy,SUM - heavy)){
            max_part = max(heavy,SUM - heavy);
            root = u;
        }
    }
    LL A,B,C;
    LL distmp[5],dis[5],num[5],numtmp[5];
    void dfs_dis(int t,int la,LL d){
        numtmp[d % 3]++;
        distmp[d % 3] += d;
        for(int i = head[t]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(vis[v] || v == la) continue;
            dfs_dis(v,t,d + edge[i].dis);
        }
    }
    void work(int t){
        num[0]++;
        for(int i = head[t]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(vis[v]) continue;
            dfs_dis(v,t,edge[i].dis);
            for(int k = 0 ; k < 3; k ++){
                for(int j = 0 ; j < 3; j ++){
                    if((k + j) % 3 == 0){
                        A = (A + numtmp[k] * dis[j]) % mod;
                        A = (A + num[k] * distmp[j]) % mod;
                    }else if((k + j) % 3 == 1){
                        B = (B + numtmp[k] * dis[j]) % mod;
                        B = (B + num[k] * distmp[j]) % mod;
                    }else{
                        C = (C + numtmp[k] * dis[j]) % mod;
                        C = (C + num[k] * distmp[j]) % mod;
                    }
                }
            }
            for(int k = 0 ; k < 3; k ++){
                dis[k] += distmp[k]; distmp[k] = 0; dis[k] %= mod;
                num[k] += numtmp[k]; numtmp[k] = 0; num[k] %= mod;
            }
        }
        for(int i = 0 ; i < 3; i ++) dis[i] = num[i] = 0;
    }
    void divide(int t){
        max_part = INF,root = t;
        dfs_root(t,-1);
        vis[root] = 1;
        work(root);
        for(int i = head[root]; ~i; i = edge[i].next){
            int v = edge[i].to;
            if(vis[v]) continue;
            SUM = size[v];
            divide(v);
        }
    }
    int main(){
        while(~Sca(N)){
            init(); A = B = C = 0;
            for(int i = 0 ; i <= N ; i ++) size[i] = vis[i] = 0;
            for(int i = 1; i < N ; i ++){
                int u = read() + 1,v = read() + 1;
                LL w = read();
                add(u,v,w); add(v,u,w);
            }
            SUM = N; divide(1);
            printf("%lld %lld %lld\n",(A * 2) % mod,(B * 2) % mod,(C * 2) % mod);
        }
        return 0;
    }

F.0:25:23 solved by hl

二分枚举最大最小值，特判最大值小于等于最小值的情况即可

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

G.4:08:33(-3) solved by zcz

利用三角形等效变换推来推去推出公式，然后求一个极限，数字过大的时候直接输出极限

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

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    
    char s[1000005];
    
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            long long n;
            double a;
            scanf("%s",s);
            cin>>a;
             double ans=2;
             double x=ans;
            if(strlen(s)<7)
            {
                sscanf(s,"%lld",&n);
                n--;
                while(n--)
                {
                    ans=ans/(1+3*ans)+5.0/3;
                }
            }
            else
            {
                ans=(sqrt(5.0)+1)/2+1.0/3;
            }
            printf("%.10lf\n",(ans-1.0/3)*a);
        }
    
        return 0;
    }

H.1:49:00 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 = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7; 
    int N,M,K;
    string t;
    struct node{
        int a,b,c,d;
        node(int a = 0,int b = 0,int c = 0,int d = 0):a(a),b(b),c(c),d(d){}
    };
    struct P{
        string name;
        node val;
    }p[maxn];
    int a[10];
    map<char,int>Q;
    void init(){
        for(int i = 2; i <= 9; i ++) Q[i + '0'] = i;
        Q['A'] = 1; Q['0'] = 10; Q['J'] = 11;
        Q['Q'] = 12; Q['K'] = 13;
    }
    node solve(string t){
        int cnt = 0;
        for(int i = t.size() - 1; i >= 0 ; i --){
            a[++cnt] = Q[t[i]];
            if(t[i] == '0') i--;
        }
        sort(a + 1,a + 1 + cnt);
        if(a[1] == 1 && a[2] == 10 && a[3] == 11 && a[4] == 12 && a[5] == 13) return node(9,1);
        if(a[1] + 1 == a[2] && a[2] + 1 == a[3] && a[3] + 1 == a[4] && a[4] + 1 == a[5]) return node(8,a[5]);
        
        //if(a[1] == a[5]) return node(7,a[1]);
        if(a[1] == a[4]) return node(6,a[1],a[5]);
        if(a[2] == a[5]) return node(6,a[2],a[1]);
        
        if(a[1] == a[3] && a[4] == a[5]) return node(5,a[1],a[4]);
        if(a[3] == a[5] && a[1] == a[2]) return node(5,a[3],a[1]);
        
        if(a[1] == a[3]) return node(4,a[1],a[4] + a[5]);
        if(a[2] == a[4]) return node(4,a[2],a[1] + a[5]);
        if(a[3] == a[5]) return node(4,a[3],a[1] + a[2]);
        
        if(a[2] == a[3] && a[4] == a[5]) return node(3,a[5],a[3],a[1]);
        if(a[1] == a[2] && a[4] == a[5]) return node(3,a[5],a[2],a[3]);
        if(a[1] == a[2] && a[3] == a[4]) return node(3,a[3],a[1],a[5]);
        
        if(a[1] == a[2]) return node(2,a[2],a[3] + a[4] + a[5]);
        if(a[2] == a[3]) return node(2,a[2],a[1] + a[4] + a[5]);
        if(a[3] == a[4]) return node(2,a[3],a[1] + a[2] + a[5]);
        if(a[4] == a[5]) return node(2,a[4],a[1] + a[2] + a[3]);
        
        return node(1,a[1] + a[2] + a[3] + a[4] + a[5]);
    }
    bool cmp(P a,P b){
        node x = a.val,y = b.val;
        if(x.a != y.a) return x.a > y.a;
        if(x.b != y.b) return x.b > y.b;
        if(x.c != y.c) return x.c > y.c;
        if(x.d != y.d) return x.d > y.d;
        return a.name < b.name;
    }
    int main(){
        init();
        while(~Sca(N)){
            for(int i = 1; i <= N ; i ++){
                cin >> p[i].name;
                string tmp; cin >> tmp;
                p[i].val = solve(tmp);
            //    cout << p[i].val.a << endl;
            }
            sort(p + 1,p + 1 + N,cmp);
            for(int i = 1; i <= N ; i ++){
                cout << p[i].name << endl;
            }
        }
        return 0;
    }

J.2:40:35(-1) solved by gbs

队友过的

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

K.1:26: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 long long LL;
    
    const int mod = 1e9+7;
    int now_size;
    int gaosi[100][100];
    int n;
    LL k;
    int an[200];
    LL suman[200];
    LL fin_ans[100];
    class Matix
    {
      public:
        LL mdata[75][75];
    
        Matix(int value = 0)
        {
            memset(mdata, 0, sizeof(mdata));
            if (value == 1)
            {
                for (int i = 0; i < now_size; i++)
                    mdata[i][i] = 1;
            }
        }
        Matix(const Matix &s1)
        {
            for (int i = 0; i < now_size; i++)
            {
                for (int j = 0; j < now_size; j++)
                {
                    mdata[i][j] = s1.mdata[i][j];
                }
            }
        }
        Matix operator * (const Matix &s1)
        {
            Matix ans;
            for (int i=0; i<now_size; i++)
            {
                for (int j=0; j<now_size; j++)
                {
                    for (int k=0; k<now_size; k++)
                    {
                        ans.mdata[i][j] = (ans.mdata[i][j] + mdata[i][k]* s1.mdata[k][j])%mod;
                    }
                }
            }
    
            return ans;
        }
        void out ()
        {
            for (int i=0; i<now_size; i++)
            {
                for (int j=0; j<now_size ;j++)
                {
                    cout<<mdata[i][j]<<'\t';
                }
                cout<<endl;
            }
            cout<<endl;
        }
    };
    int quick_mi(LL a, LL k)
    {
        LL ans = 1;
        while (k)
        {
            if (k & 1)
            {
                ans *= a;
                ans %= mod;
            }
            a *= a;
            a %= mod;
            k >>= 1;
        }
        return ans;
    }
    inline int inva(int a)
    {
        return quick_mi(a,mod-2);
    }
    inline int domod(int a)
    {
        return  (a%mod+mod)%mod;
    }
    inline LL domod(LL a)
    {
        return  (a%mod+mod)%mod;
    }
    void gaosixiaoyuan(int hang,int lie)
    {
        for (int i =0; i<n; i++)
        {
            //cout <<i <<"^"<<endl;
            for (int j = i; j< hang; j++)
            {
    
                if (gaosi[j][i] != 0)
                {
                    if (i != j)
                    {
                        for (int k1 = 0; k1<lie; k1++)
                            swap(gaosi[j][k1],gaosi[i][k1]);
                    }
                    break;
                }
            }
            int qmod = inva(gaosi[i][i]);
            //cout<<qmod<<"*"<<endl;
            for (int k1 = 0; k1<lie; k1++)
                gaosi[i][k1] = domod(gaosi[i][k1] *1LL *qmod);
            for (int j= i+1; j<hang ;j++)
            {
                if (gaosi[j][i] != 0)
                {
                    int p1 = gaosi[j][i];
                    for (int k1 = i; k1<lie; k1++)
                        gaosi[j][k1] = domod(gaosi[j][k1] -1LL * p1 *gaosi[i][k1]);
                }
            }
        }
    
        for (int i= n-1; i>=0; i--)
        {
            LL nowans = gaosi[i][n];
            for (int j = n-1; j>i; j--)
            {
                nowans = domod(nowans - fin_ans[j] * gaosi[i][j]);
            }
            fin_ans[i] = nowans;
        }
    
        /*for (int i=0; i<hang; i++)
        {
            for (int j=0; j<lie ;j++)
            {
                cout<<gaosi[i][j]<<'\t';
            }
            cout<<endl;
        }
        cout<<endl;
        cout<<"%%";
        for (int j=0; j<n ;j++)
        {
            cout<<fin_ans[j]<<'\t';
        }
        cout<<endl;*/
    
    }
    
    int main()
    {
        int t;
        //cout<<(2*inva(2))%mod<<endl;
        cin >> t;
        while (t--)
        {
            cin >> n >> k;
            for (int i = 0; i < 2 * n; i++)
            {
                scanf("%d", &an[i]);
                if (i==0)
                {
                    suman[i] = an[i];
                }
                else
                {
                    suman[i] = domod(an[i] +suman[i-1]);
                }
                
            }
            if (k<=2*n)
            {
                k--;
                printf("%lld\n",suman[k]);
                continue;
            }
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j <= n; j++)
                {
                    gaosi[i][j] = an[i + j];
                }
            }
            for (int j = 0; j <= n; j++)
                gaosi[n][j] = 1;
            gaosixiaoyuan(n+1,n+1);
            now_size = n+2;
            Matix simp1;
            simp1.mdata[0][0] = 1;
            //simp1.mdata[0][1] = 1;
            for (int i=0; i<n; i++)
            {
                simp1.mdata[0][i+1] = fin_ans[n-1-i];
                simp1.mdata[1][i+1] = fin_ans[n-1-i];
            }
            for (int i =2 ; i<=n+1; i++)
            {
                simp1.mdata[i][i-1] = 1;
            }
            //simp1.out();
            Matix ans1(1);
            k -= n;
            while(k)
            {
                if (k&1)
                {
                    ans1 = ans1 *simp1;
                }
                k>>=1;
                simp1 = simp1 *simp1;
                //simp1.out();
            }
            LL the_ans = suman[n-1];
            //cout<<"&"<<the_ans<<endl;
            for (int i = 1; i<=n; i++)
            {
                the_ans = domod(the_ans + an[n-i] *ans1.mdata[0][i]);
            }
            printf("%lld\n",the_ans);
    
        }
    
    #ifdef VSCode
        system("pause");
    #endif
        return 0;
    }

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

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