Codeforces Round 483 (Div. 2)

发表于 | 分类于 ，

Codeforces Round #483 (Div. 2)

已经是条只会签到全靠补题的咸鱼了

A.Game

题意

两方轮流删最大、最小的数，求最后剩下的值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
    int n,a[1005];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    sort(a,a+n);
    if(n%2) printf("%d\n",a[n/2]);
    else printf("%d\n",a[n/2-1]);
    return 0;
}

B. Minesweeper

题意

给一张扫雷地图，判断标记数字有没有出现错误。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>

using namespace std;

int m,n;
char a[105][105];
int dx[8]={-1,0,1,-1,1,-1,0,1};
int dy[8]={1,1,1,0,0,-1,-1,-1};

int sum(int x,int y)
{
    int ans=0;
    for(int i=0;i<8;i++)
    {
        int fx=x+dx[i],fy=y+dy[i];
        if(fx>=0&&fx<n&&fy>=0&&fy<m&&a[fx][fy]=='*') ans++;
    }
    return ans;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%s",a[i]);
    int tmp;
    bool flag=true;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(a[i][j]=='*') continue;
            if(a[i][j]=='.') tmp=0;
            else tmp=a[i][j]-'0';
            if(tmp!=sum(i,j)) flag=false;
        }
    }
    printf("%s\n",flag?"YES":"NO");
    return 0;
}

C. Finite or not?

题意

给出三个整数p,q,b,判断p/q在b进制下是否是一个有限小数。

解法

数论题。

首先在10进制下，一个分数在化为最简分数的情况下，如果它的分母只含有2和5两个质因数，这个分数就能化简为有限小数。

推广得在b进制下，如果化简后的p/q中的分母只含有b的质因数，那么该分数是一个有限小数。即q在与b的公因数的不断整除下，q能否被化简为1.

需要注意这里如果每步直接取tmp=gcd(q,b)则会导致tle，由$$gcd(\frac{p}{gcd(b,p)},b)=gcd(\frac{p}{gcd(b,p)},gcd(b,p))$$,则只需要取tmp=gcd(q,tmp)并不断整除q,tmp的公因数直到q=1（p/q为有限小数）或tmp=1（p≠1且不能继续化简，p/q为无限小数）即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>

inline long long gcd(long long a,long long b)
{
    return b==0?a:gcd(b,a%b);
}

int main()
{
    int t;
    long long p,q,b;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&p,&q,&b);
        long long tmp=gcd(p,q);
        q/=tmp;
        tmp=gcd(q,b);
        while(q>1&&tmp>1)
        {
            tmp=gcd(q,tmp);
            q/=tmp;
        }
        printf("%s\n",q==1?"Finite":"Infinite");
    }
}

D. XOR-pyramid

题意

对于长度为m的数组b，定义函数$$f$$如下

$$f(b) = \begin{cases} b[1] & \quad \text{if } m = 1 \ f(b[1] \oplus b[2],b[2] \oplus b[3],\dots,b[m-1] \oplus b[m]) & \quad \text{otherwise,} \end{cases}$$

其中⊕为异或运算，例：

$f(1,2,4,8)=f(1\oplus2,2\oplus4,4\oplus8)=f(3,6,12)=f(3\oplus6,6\oplus12)=f(5,10)=f(5\oplus10)=f(15)=15$

给定一个数组和一系列询问，求区间$$[l,r]$$内$$f$$的最大值。

解法

打表记录左右区间为$$[l,r]$$的$$f$$值dp[l][r]，i=l=r的值即为a[i]本身，通过dp[l][r]=dp[l][r-1]^dp[l+1][r]依次求出区间长度为1～n的f值（区间长度为k=r-l），再通过dp[l][r]=max(dp[l+1][r],dp[l][r],dp[l][r-1])逐步更新最大值。

其实就是个数塔形式的dp，计算过程中取左下方和右下方的值求异或和并记录，dp更新过程中取三者的最大值更新就可以了，如下

$f(1,2,4,8)=f(1\oplus2,2\oplus4,4\oplus8)=f(3,6,12)=f(3\oplus6,6\oplus12)=f(5,10)=f(5\oplus10)=f(15)=15$

$$15$$

$$5\qquad10$$

$$3\qquad6\qquad12$$

$$1\qquad2\qquad4\qquad8$$

与下方左右两数比较并更新后

$$15$$

$$[6]\qquad[12]$$

$$3\qquad6\qquad12$$

$$1\qquad2\qquad4\qquad8$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn=5000+10;
int dp[maxn][maxn];

int main()
{
    int n,l,r,t;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&dp[i][i]);
    for(int k=1;k<n;k++)
        for(int i=1;i+k<=n;i++)
            dp[i][i+k]=dp[i][i+k-1]^dp[i+1][i+k];
    for(int k=1;k<=n;k++)
        for(int i=1;i+k<=n;i++)
        dp[i][i+k]=max(max(dp[i+1][i+k],dp[i][i+k]),dp[i][i+k-1]);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&l,&r);
        printf("%d\n",dp[l][r]);
    }
    return 0;
}

E. Elevator

那我哪会