考试整理

比眉伴天荒 2021-12-17 13:57 228阅读 0赞

话说这几天怎么光考试啊aaa

## T1 Jelly的难题1 ##

![1606239-20190701080404129-1443152779.png][]

![1606239-20190701080424973-2096710693.png][]

![1606239-20190701080444025-665537704.png][]

![1606239-20190701080455231-1721009061.png][]

这题是一个纯纯的BFS（其实与马的遍历十分相像【其实改改就行】）

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<iomanip>
    #include<string>
    #include<algorithm>
    #include<cstdlib>
    #include<queue>
    #include<stack>
    //一堆头文件 
    using namespace std;
    inline int read() 
    {
        int X=0,w=1; 
        char c=getchar();
        while(c<'0'||c>'9')
        { 
            if (c=='-')
            {
                w=-1; 
            } 
            c=getchar();
        }
        while(c>='0'&&c<='9')
        {
            X=(X<<3)+(X<<1)+c-'0';
            c=getchar();
        } 
        return X*w;
    }
    //快读
    struct node
    {
        int x,y,step;
        node(int x,int y,int step):x(x),y(y),step(step){};
    };
    //表示当前(x,y)以及当前所花的步数 
    int n,m,sx,sy;
    long long sum,maxn;
    queue<node> q;
    char s[600][600],a;
    int st[600][600];
    int used[600][600];
    int mx[5]={
        0,0,0,1,-1};
    //x的移动 
    int my[5]={
        0,1,-1,0,0}; 
    //y的移动 
    bool check(int x,int y)
    {
        return ((1<=x&&x<=n)&&(1<=y&&y<=m)&&s[x][y]!='o');
    }
    //判断是否出界 
    void bfs()
    {
        used[sx][sy]=1;
        //标记已走 
        q.push(node(sx,sy,0));
        //第一个入队(即开始 BFS) 
        st[sx][sy]=0;
        //起点肯定为 0啊 
        while(!q.empty())
        {
            node u=q.front();
            //取队首,对队列进行操作 
            q.pop();
            //弹出队首 
            for(int i=1;i<=4;i++)
            //四个方向 
            {
                int nx=u.x+mx[i];
                int ny=u.y+my[i];
                if(check(nx,ny)&&!used[nx][ny])
                //表示未走过且满足不出界 
                {
                    used[nx][ny]=1;
                    //标记走过 
                    st[nx][ny]=u.step+1;
                    //步数加 1 
                    q.push(node(nx,ny,u.step+1));
                    //继续入队 
                }
            }
        }
    }
    //就是 BFS,无他,唯手熟尔 
    int main()
    {
        n=read();
        m=read();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                a=getchar();
                while(a!='*'&&a!='o'&&a!='#')
                {
                    a=getchar();
                }
                s[i][j]=a;
                if(s[i][j]=='*')
                {
                    sx=i;
                    sy=j;
                }
            }
        }
        //读入(可能有点麻烦) 
        bfs();
        //进行 BFS 
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(st[i][j]>maxn)
                {
                    maxn=st[i][j];
                }
            }
        }
        //找出最大时间 
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(st[i][j]!=0)
                {
                    st[i][j
                    ]=maxn+1-st[i][j];
                    sum+=st[i][j];
                }
            }
        }
        //通过操作计算总卷数 
        printf("%lld\n%lld",maxn,sum%19260817);
        //不能忘记取模 
        return 0;
    }

## T2【音乐会】二重变革 ##

![1606239-20190701083636609-725032455.png][]

![1606239-20190701083649067-1928458998.png][]

![1606239-20190701083657887-2043203043.png][]

首先我们看到数据范围，发现如果就按照程序这么跑肯定会T成狗

所以我们进行一波分析

如果最后停止（按照所给的程序），则所有数在最后都会相等

那么我们那n为2的情况来模拟一下，发现这tm就是更相减损术啊

那么这题就好做了。

#include<bits/stdc++.h>
    using namespace std;
    inline int read() 
    {
        int X=0,w=1; 
        char c=getchar();
        while(c<'0'||c>'9')
        { 
            if (c=='-')
            {
                w=-1; 
            } 
            c=getchar();
        }
        while(c>='0'&&c<='9')
        {
            X=(X<<3)+(X<<1)+c-'0';
            c=getchar();
        } 
        return X*w;
    }
    int gcd(int a,int b)
    {
        if(b==0)
        {
            return a;
        }
        else
        {
            return gcd(b,a%b);
        }
    }
    int n;
    int x[2];
    int ans;
    int main()
    {
        n=read();
        x[0]=read();
        ans=x[0];
        for(int i=2;i<=n;i++)
        {
            x[1]=read();
            ans=gcd(ans,x[1]);
        }
        ans*=n;
        printf("%d",ans);
        return 0;
    }

边算边gcd就行啊。

## T3【音乐会】道路千万条 ##

![1606239-20190701084553819-1258916862.png][]

![1606239-20190701084604275-1553944224.png][]

![1606239-20190701084648459-1985063892.png][]

![1606239-20190701084709898-2086275417.png][]

![1606239-20190701084719349-577658264.png][]

这题我看到说明的时候就不想做了，后来发现好像可以线段树

#include<bits/stdc++.h>
    using namespace std;
    inline int read()
    {
        int X=0,w=1;
        char c=getchar();
        while(c<'0'||c>'9')
        {
            if (c=='-')
            {
                w=-1;
            }
            c=getchar();
        }
        while(c>='0'&&c<='9')
        {
            X=(X<<3)+(X<<1)+c-'0';
            c=getchar();
        }
        return X*w;
    }
    inline char gc()
    {
        char c;
        do
        {
            c=getchar();
        }
        while(c==' '||c=='\n'||c=='\r'||c=='\0'||c=='\t');
    }
    int n;
    char s[501],ops[501];
    long long t[501][501],f[501][501];
    const int mod=998244353;
    pair<long long,long long>exgcd(long long a,long long b)
    {
        if(b==0)
        {
            return make_pair<long long,long long>(1,0);
        }
        pair<long long,long long>rtn=exgcd(b,a%b);
        rtn.first^=rtn.second^=rtn.first^=rtn.second;
        rtn.second-=a/b*rtn.first;
        return rtn;
    }
    int main()
    {
        n=read();
        for(int i=1;i<=n-1;i++)
        {
            s[i]=gc();
            ops[i]=gc();
        }
        s[n]=gc();
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='t')
            {
                t[i][i]=1,f[i][i]=0;
            }
            else
            {
                f[i][i]=1,t[i][i]=0;
            }
        }
        for(int len=2;len<=n;len++)
        {
            for(int i=1;i+len-1<=n;i++)
            {
                int j=i+len-1;
                for(int k=i;k<j;k++)
                {
                    if(ops[k]=='&')
                    {
                        t[i][j]=(t[i][j]+(t[i][k]*t[k+1][j])%mod)%mod;
                        f[i][j]=(f[i][j]+(t[i][k]*f[k+1][j])%mod+(f[i][k]*t[k+1][j])%mod+(f[i][k]*f[k+1][j])%mod)%mod;
                    }
                    if(ops[k]=='|')
                    {
                        t[i][j]=(t[i][j]+(t[i][k]*f[k+1][j])%mod+(f[i][k]*t[k+1][j])%mod+(t[i][k]*t[k+1][j])%mod)%mod;
                        f[i][j]=(f[i][j]+(f[i][k]*f[k+1][j])%mod)%mod;
                    }
                    if(ops[k]=='^')
                    {
                        t[i][j]=(t[i][j]+(t[i][k]*f[k+1][j])%mod+(f[i][k]*t[k+1][j])%mod)%mod;
                        f[i][j]=(f[i][j]+(f[i][k]*f[k+1][j])%mod+(t[i][k]*t[k+1][j])%mod)%mod;
                    }
                }
            }
        }
        cout<<(t[1][n]*((exgcd(t[1][n]+f[1][n]%mod,mod).first%mod+mod)%mod))%mod;
        return 0;
    }

最后才只有205分。。。（第三题的大骗分竟然才5分）

转载于:https://www.cnblogs.com/gongcheng456/p/11112225.html

[1606239-20190701080404129-1443152779.png]: /images/20211217/fe2f5a7aa15048d787d870025a70a31f.png
[1606239-20190701080424973-2096710693.png]: /images/20211217/52724b2075924b6fbe4438c685e6baa9.png
[1606239-20190701080444025-665537704.png]: /images/20211217/546765e0fe1d491288b9864c82c3f1fa.png
[1606239-20190701080455231-1721009061.png]: /images/20211217/4d82d93dc63048048393b6f222075c32.png
[1606239-20190701083636609-725032455.png]: /images/20211217/0c535170cbd74f9fb15dc8b37ef38638.png
[1606239-20190701083649067-1928458998.png]: /images/20211217/09ef1a836fcd4374949109ca4112a32a.png
[1606239-20190701083657887-2043203043.png]: /images/20211217/2c5e36f52b004b2190b9c3f308080283.png
[1606239-20190701084553819-1258916862.png]: /images/20211217/21964c1098734f0e9782f54f5e5522d4.png
[1606239-20190701084604275-1553944224.png]: /images/20211217/ac1557fe3b3c4b5a9ed774928533d415.png
[1606239-20190701084648459-1985063892.png]: /images/20211217/1175dec6ba0d4da28f21d81971876857.png
[1606239-20190701084709898-2086275417.png]: /images/20211217/139c0d61cf884d3d9ec45ea518295c47.png
[1606239-20190701084719349-577658264.png]: /images/20211217/cab9a21d38d24ae7bc42c8f90c65024d.png