整理第十届河南省ACM省赛正解

落日映苍穹つ 2022-06-15 03:20 207阅读 0赞

问题A：谍报分析

[题目链接][Link 1]

正解：

#include<stdio.h>
    #include<string.h>
    #include<string>
    #include<map>
    #include<algorithm>
    using namespace std;
    struct Word
    {
        char str[100];
        int count;
    }word[1000];
    int N=0;
    int comp(Word w1,Word w2)
    {
        if(w1.count!=w2.count)
                return w1.count>w2.count;
        else
        {
            int a=strcmp(w1.str,w2.str);
            if(a>0)
                return 0;
            else
                return 1;
        }
    }
    int main()
    {
        map<string,int>m;
        map<string,int>::iterator it;
        char str[100];
        while(scanf("%s",str)!=EOF)
        {
            int len=strlen(str);
            if(str[len-1]==','||str[len-1]=='.')
                str[len-1]='\0';
            string s=str;
            m[s]++;
        }
        for(it=m.begin();it!=m.end();it++)
        {
            string s=it->first;
            int count=it->second;
            strcpy(word[N].str,s.c_str());
            word[N++].count=count;
        }
        sort(word,word+N,comp);
        for(int i=0;i<10;i++)
        {
            printf("%s %d\n",word[i].str,word[i].count);
        }
        return 0;
    }

B：情报传递

[题目链接][Link 2]

正解：

#include<iostream>
    #include<vector>
    #include<queue>
    #include<stdio.h>
    #include<sstream>
    using namespace std;
    int n, m;
    int up[5100];
    int build[5100];
    vector<int> down[5100];
    int Send(int s)
    {
        int ret = 0;
        // 顺着s一直找上级，一直找到0
        while (s)
        {
            if (!build[s])
            {
                build[s] =true;
                ret++;
            }
            s = up[s];
        }
        // 注意0本身也要向上建立通道。
        // 因为样例的第一行 Send 0  输出为 0
        if (!build[0])
        {
            build[0] = true;
            ret++;
        }
        return ret;
    }
     
    int Danger(int s)
    {
        int ret = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty())
        {
            //从队列中拉取一个节点
            s = q.front();
            q.pop();
     
            //看 s 自己是否向上级建立了通道
            if (build[s])
            {
                ret++;
                build[s] =false;
            }
            //遍历 s 所有的下级
            for (int i = 0; i < down[s].size(); ++i)
            {
                // 看这个下级是否建立了通道
                if (build[down[s][i]])
                    q.push(down[s][i]);
            }
        }
        return ret;
    }
     
    int main()
    {
        int i;
        cin >> n;
        for (i = 1; i <n; ++i)
        {
            scanf("%d", &up[i]);     // 设置 i的上级
            down[up[i]].push_back(i); // 设置属于up[i] 的下级
        }
        char buffer[20];
        scanf("%d",&m);
        for (i = 0; i <m; ++i)
        {
            int num;
            scanf("%s", buffer);
            scanf("%d", &num);
            //只用比较第一个字符就可以知道是哪条命令
            if (buffer[0] =='S')
                printf("%d\n", Send(num));
            else
                printf("%d\n", Danger(num));
        }
        return 0;
    }

C：最小秘钥

[题目链接][Link 3]

正解：

#include<stdio.h>
    #include<iostream>
    #include<string.h>
    using namespace std;
    int main()
    {
        int T,n,num[3009];
        scanf("%d",&T);
        int A[20009];
        while(T--)
        {
            int n,flag=0;
            scanf("%d",&n);
            for(int i=0; i<n; i++)
                scanf("%d",&num[i]);
            for(int i=n;;i++)
            {
                flag=0;
                memset(A,0,sizeof(A));
                for(int j=0;j<n;j++)
                {
                    int op=num[j]%i;
                    if(A[op]==0)
                        A[op]=1;
                    else
                    {
                        flag=1;
                        break;
                    }
                }
                if(flag==0)
                {
                    printf("%d\n",i);
                    break;
                }
            }
        }
        return 0;
    }

D：年终奖金

[题目链接][Link 4]

正解：

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define MAX 1<<31-1
    #define min(x,y)(x<y?x:y)
    using namespace std;
    int a[110];
    int dp[110];
    int get(int x,int y)
    {
        return (x-y)*(x-y);
    }
    int main()
    {
        int n,k,c,i,j;
        while(scanf("%d%d%d",&n,&k,&c)!=EOF)
        {
            for(i=1;i<=n;i++)
            {
                dp[i]=MAX;
            }
            for(i=1;i<=n;i++)
                scanf("%d",&a[i]);
            sort(a+1,a+1+n);
            dp[0]=0;
            for(i=k;i<=n;i++)
            {
                for(j=0;j<=i-k;j++)
                {
                    if(j<k&&j!=0)
                        continue;
                    dp[i]=min(dp[j]+c+get(a[i],a[j+1]),dp[i]);
                }
            }
            printf("%d\n",dp[n]);
        }
        return 0;
    }

E：GDP值

[题目链接][Link 5]

正解：

#include <iostream>
    #include <cstdio>
    #include <set>
    #include<algorithm>
    #include<cstdlib>
    #include<bitset>
    #include<cstring>
    using namespace std;
    const int MAXN = 1024;
    typedef bitset<MAXN>bst;
    struct node
    {
        int x, next;
        bst v;
    } e[MAXN << 1];
    char ch[MAXN];
    int n, m, P, cnt, len, Link[MAXN], f[MAXN], wh[MAXN], E[MAXN][2];
    bst mat[MAXN], M[MAXN], dis[MAXN], V[MAXN];
    inline int read()
    {
        int x = 0, f = 1;
        char ch = getchar();
        while (!isdigit(ch))
        {
            if (ch == '-')
            {
                f = -1;
            }
            ch = getchar();
        }
        while (isdigit(ch))
        {
            x = x * 10 + ch - '0';
            ch = getchar();
        }
        return x * f;
    }
     
    bst Read()
    {
        bst temp;
        temp.reset();
        scanf("%s", ch + 1);
        int len = (int)strlen(ch + 1);
        for (int i = 1; i <= len; i++)
        {
            temp[len - i] = ch[i] - '0';
        }
        return temp;
    }
     
    void insert(int x, int y, bst v)
    {
        e[++len].next = Link[x];
        Link[x] = len;
        e[len].x = y;
        e[len].v = v;
        e[++len].next = Link[y];
        Link[y] = len;
        e[len].x = x;
        e[len].v = v;
    }
    int find(int x)
    {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    void dfs(int x, int pre)
    {
        for (int i = Link[x]; i; i = e[i].next)
        {
            if (e[i].x != pre)
            {
                dis[e[i].x] = dis[x] ^ e[i].v;
                dfs(e[i].x, x);
            }
        }
    }
    void updata(int x, bst y)
    {
        int pos = 0;
        for (int i = 1; i <= 1000; ++i)
        {
            if (M[i][x] && mat[i].none())
            {
                pos = i;
                break;
            }
        }
        if (!pos)
        {
            for (int i = 0; i <= 1000; ++i)
            {
                if (M[wh[i]][x] && wh[i] != 0)
                {
                    pos = wh[i];
                    wh[i] = 0;
                    break;
                }
            }
        }
        for (int i = 1; i <= 1000; ++i)
        {
            if (pos != i && M[i][x])
            {
                mat[i] = mat[i] ^ mat[pos], M[i] = M[i] ^ M[pos];
            }
        }
        mat[pos] ^= y;
        for (int i = 1000; i >= 0; --i)
        {
            if (mat[pos][i])
            {
                if (!wh[i])
                {
                    wh[i] = pos;
                    break;
                }
                else
                {
                    mat[pos] = mat[pos] ^ mat[wh[i]];
                    M[pos] = M[pos] ^ M[wh[i]];
                }
            }
        }
    }
    void output()
    {
        bst ans;
        ans.reset();
        char ts[MAXN], *tmp;
        for (int i = 1000; i >= 0; --i)
        {
            if (ans[i] == 0 && wh[i])
            {
                ans = ans ^ mat[wh[i]];
            }
        }
        if (ans.none())
        {
            puts("0");
        }
        else
        {
            tmp = ts;
            for (int i = 1000; i >= 0; --i)
            {
                if (ans[i])
                {
                    for (int j = i; j >= 0; --j)
                    {
                        *(tmp++) = ans[j] + '0';
                    }
                    break;
                }
            }
            *(tmp++) = '\0';
            puts(ts);
        }
    }
    int main()
    {
        n = read();
        m = read();
        P = read();
        for (int i = 1; i <= n; ++i)
        {
            f[i] = i;
        }
        for (int i = 1; i <= 1000; ++i)
        {
            M[i][i] = 1;
        }
        for (int i = 1; i <= m; ++i)
        {
            int x = read(), y = read();
            bst value = Read();
            if (find(x) == find(y))
            {
                E[++cnt][0] = x, E[cnt][1] = y, V[cnt] = value;
            }
            else
            {
                f[find(x)] = find(y), insert(x, y, value);
            }
        }
        dfs(1, 0);
        int CASE = cnt;
        for (int i = 1; i <= cnt; ++i)
        {
            updata(i, dis[E[i][0]] ^ dis[E[i][1]] ^ V[i]);
        }
        output();
        for (int i = 1; i <= P; ++i)
        {
            char opt[10];
            scanf("%s", opt);
            if (opt[1] == 'd')
            {
                int x = read(), y = read();
                bst value = Read();
                E[++cnt][0] = x;
                E[cnt][1] = y;
                V[cnt] = value;
                updata(cnt, dis[E[cnt][0]] ^ dis[E[cnt][1]] ^ V[cnt]);
            }
            else if (opt[1] == 'h')
            {
                int x = read();
                bst value = Read();
                updata(x + CASE, V[x + CASE] ^ value);
                V[x + CASE] = value;
            }
            else
            {
                int x = read();
                updata(x + CASE, dis[E[x + CASE][0]] ^ dis[E[x + CASE][1]] ^ V[x + CASE]);
                V[x + CASE] = dis[E[x + CASE][0]] ^ dis[E[x + CASE][1]];
            }
            output();
        }
        return 0;
    }

F：Binary to Prime

[题目链接][Link 6]

正解

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int a[160];
        a[1]=2;
        a[2]=3;
        int k=3;
        for(int i=4;;i++)
        {
            int t=1;
            for(int j=2;j<=sqrt(i);j++)
            {
                if(i%j==0)
                {
                    t=0;
                    break;
                }
            }
            if(t==1)
            {
                a[k]=i;
                k++;
            }
            if(k>155)
                break;
        }
        char b[200];
        while(scanf("%s",b)!=EOF)
        {
            int l=strlen(b);
            int sum=0;
            for(int i=l-1;i>=0;i--)
            {
                if(b[i]=='1')
                {
                    sum=sum+a[l-i];
                }
            }
            printf("%d\n",sum);
        }
        return 0;
    }

G:Plumbing the depth of lake

[题目链接][Link 7]

正解：

#include <cstdio>
    #include <cstring>
    int map[55][55];
    int dx[8] = {-1,-1,-1,0,0,1,1,1};
    int dy[8] = {-1,0,1,-1,1,-1,0,1};
    int max;
    void search(int i,int j)
    {
        int k;
        if(map[i][j]==-1) return ;
     
        if(max >= map[i][j]) return ;
     
        for(k=0; k<8; k++)
        {
            if(map[i][j] == map[i + dx[k]] [j + dy[k]]) //八个方向找一下,有就更新 max
            {
                max = map[i][j];
                break;
            }
        }
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            max = -1;
            int i,j,m,n;
            scanf("%d%d",&m,&n);
            memset(map,-1,sizeof(map));
            for(i=1; i<=m; i++)
            {
                for(j=1; j<=n; j++)
                {
                    scanf("%d",&map[i][j]);
                }
            }
            for(i=1; i<=m; i++)
            {
                for(j=1; j<=n; j++)
                {
                    search(i,j);
                }
            }
            printf("%d\n",max);
        }
        return 0;
    }

H:Intelligent Parking Building

[题目链接][Link 8]

正解：

#include<stdio.h>
    #include<string>
    #include<string.h>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    struct Node
    {
        int floor;
        int num;
    } node[2509];
    int main()
    {
        int T,n,m,Max;
        scanf("%d",&T);
        while(T--)
        {
            Max=-1;
            memset(node,NULL,sizeof(node));
            int Tu[52][52];
            scanf("%d%d",&n,&m);
            for(int i=1; i<=n; i++)
            {
                 Tu[i][0] = 1;
                for(int j=1; j<=m; j++)
                {
                    scanf("%d",&Tu[i][j]);
                    if(Tu[i][j]!=-1)
                    {
                        if(Tu[i][j]>Max)
                            Max=Tu[i][j];
                        node[Tu[i][j]].floor=i;
                        node[Tu[i][j]].num=j;
                    }
                }
            }
            int  sum=0,flag;
            for(int i=1; i<=Max; i++)
            {
                sum+=(node[i].floor-1)*10*2;
                // cout<<"sum1==="<<sum<<endl;
                int mm=min(node[i].num-1,1+m-node[i].num);
                int res = min(abs(node[i].num - Tu[node[i].floor][0]),m- abs(node[i].num - Tu[node[i].floor][0]));   //在同行中 找距离左右两边最近的那个。
                sum += res * 5;
                Tu[node[i].floor][0]=node[i].num;
            }
            printf("%d\n",sum);
        }
        return 0;
    }

I：Trainsmit information

[题目链接：][Link 9]

正解：

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<map>
    #define inf 0x3f3f3f3f
     
    using namespace std;
     
    typedef long long ll;
    const int maxn = 110;
    int N,M,S,E;   ///经过N个间谍传播，M道路条数，
    struct matrix
    {
        ll a[maxn][maxn];
    }dis,ans;
    matrix flody(matrix A,matrix B,int n)
    {
        matrix tmp;
        for(int i = 1; i < n; i++)
            for(int j = 1; j < n; j++)
                tmp.a[i][j] = inf;
        for(int k = 1; k < n; k++)
            for(int i = 1; i < n; i++)
                for(int j = 1; j < n; j++)
                    if(tmp.a[i][j]>A.a[i][k]+B.a[k][j])
                        tmp.a[i][j] = A.a[i][k] + B.a[k][j];
        return tmp;
    }
    void solve(int n,int s,int e)
    {
        for(int i = 1; i < n; i++)
            for(int j = 1; j < n; j++)
                ans.a[i][j] = dis.a[i][j];
        N--;  ///因为ans[i][j]是一步的距离，相当于已经传给一个间谍了
        while(N)
        {
            if(N&1)
            {
                ans = flody(ans,dis,n);
            }
            dis = flody(dis,dis,n);
            N = N>>1;
        }
        if(ans.a[s][e] < inf)
            printf("%lld\n",ans.a[s][e]);
    }
    int main()
    {
        int T,len,x,y;
        scanf("%d",&T);
        while(T--)
        {
            map<int,int>m;
            int num = 1;
            scanf("%d%d%d%d",&N,&M,&S,&E);
            for(int i = 0; i < maxn; i++)
                for(int j = 0; j < maxn; j++)
                    dis.a[i][j] = inf;
            for(int i = 1; i <= M; i++)
            {
                scanf("%d%d%d",&len,&x,&y);
                if(m[x]==0)
                {
                    m[x] = num++;
                }
                int xi = m[x];
                if(m[y]==0)
                {
                    m[y] = num++;
                }
                int yi = m[y];
                if(len < dis.a[xi][yi])
                    dis.a[xi][yi] = dis.a[yi][xi] = len;
            }
            solve(num,m[S],m[E]);
        }
        return 0;
    }

[Link 1]: http://211.69.26.100/problem.php?id=1777
[Link 2]: http://211.69.26.100/problem.php?id=1778
[Link 3]: http://211.69.26.100/problem.php?id=1779
[Link 4]: http://211.69.26.100/problem.php?id=1780
[Link 5]: http://211.69.26.100/problem.php?id=1781
[Link 6]: http://211.69.26.100/problem.php?id=1782
[Link 7]: http://211.69.26.100/problem.php?id=1783
[Link 8]: http://211.69.26.100/problem.php?id=1784
[Link 9]: http://211.69.26.100/problem.php?id=1785