Codeforces Round #483 (Div. 2) （A+B+C+D）

A题 题目链接 （签到）

题意：给定n个数，甲乙两人从甲开始轮流取数，一共取n-1次，甲希望留下的数尽量小，乙希望留下的数尽量大，问最终留下的数是什么
(1<=n<=1e3)

思路：按递增排序，n是偶数的话留下的就是a[n/2]，n否则留下的是a[n/2+1]

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<math.h>
#include<set>
//#include<unordered_map>
using namespace std;
#define LL long long
#define ULL unsigned long long
const LL INF=1e18+7;
const double eps=1e-5;
const int maxn=1e2+7;

int main()
{
//    ios::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
    int n;
    int a[1005];
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    sort(a+1,a+n+1);
    if(n&1) cout<<a[n/2+1];
    else cout<<a[n/2];
   // system("pause");
    return 0;
}

B题题目链接 （签到）

题意：给定一个最多100*100的扫雷图，.代表0，问这个图是否符合扫雷游戏规则。

思路：直接再开一个矩阵，按照雷的分布求出正确的扫雷图，再比较即可

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<math.h>
#include<set>
//#include<unordered_map>
using namespace std;
#define LL long long
#define ULL unsigned long long
const LL INF=1e18+7;
const double eps=1e-5;
const int maxn=1e2+7;
char a[105][105],b[105][105];
int n,m;
bool check(int i,int j)
{
    if(i>=1 && i<=n && j>=1 && j<=m && b[i][j]!='*') return true;
    return false;
}
void cpy(int i,int j)
{
    if(check(i-1,j-1)) b[i-1][j-1]++;
    if(check(i-1,j))   b[i-1][j]++;
    if(check(i-1,j+1)) b[i-1][j+1]++;
    if(check(i,j-1))  b[i][j-1]++;
    if(check(i,j+1)) b[i][j+1]++;
    if(check(i+1,j-1)) b[i+1][j-1]++;
    if(check(i+1,j))   b[i+1][j]++;
    if(check(i+1,j+1)) b[i+1][j+1]++;
}
int main()
{
//    ios::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",a[i]+1);
        for(int j=1;j<=m;j++)
        {
            b[i][j]='0';
            if(a[i][j]=='*') b[i][j]='*';
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='.') a[i][j]='0';
            else if(a[i][j]=='*')
            {
                cpy(i,j);
            }
        }
    }
    bool flag=1;
    for(int i=1;i<=n;i++)
    {
        if(strcmp(a[i]+1,b[i]+1))
        {
            flag=0;
            break;
        }
    }
    if(flag) cout<<"YES";
    else cout<<"NO";
//    system("pause");
    return 0;
}

C题 题目链接（数论）

题意：给顶p q，让你求在b进制下，p/q是不是有限小数，询问q次
(1<=q<=1e5 ,1<=p,q<=1e18 ,2<=b<=10)

思路：首先，一个数是否为有限小数，只和最简分数情形下的分母有关。
然后我们可以根据十进制下，如果最简分数的分母可以分解成(2^n ) * 5^m),则其为有限小数 ，推出如果分母可以化成进制的质因子的乘积，那么它可以化成有限小数。

简而言之，分母的所有质因数都在进制的质因数集合中出现的话，就说明可以化成有限小数。

问题就等价为 是否存在正整数x满足 (b^x) % q==0

但是如果我们从1开始暴力枚举x，那么得tle，我们换一个角度去证明x的存在性。

让q不断约掉q和b的公因数，最终如果只剩下1，那么说明q中的质因数全是b中的质因数，否则就不是。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdlib.h>
#include<math.h>
#include<stdlib.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
const int N=2e5+7;
const LL INF=2e18;
LL gcd(LL a,LL b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
int main()
{
    int n;
    LL p,q,b;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%I64d%I64d%I64d",&p,&q,&b);
        if(p==0)
        {
            printf("Finite\n");
            continue;
        }
        LL x=__gcd(p,q);
        q/=x;
        while(q!=1)
        {
            x=__gcd(q,b);
            if(x==1) break;
            while(q%x==0) q/=x;
        }
        if(q==1) printf("Finite\n");
        else printf("Infinite\n");
    }
    system("pause");
    return 0;
}

D题 题目链接 （找规律+区间dp）

题意：定义一个函数

，给定长度为n的数列，给出q个询问，输入l,r,要求输出[l,r]区间的所有子区间中的f函数最大值。
(1<=n<=5000,1<=q<=1e5)

思路：先找规律，如图

令f(x1,x2,x3)=x1223 ，f(x2,x3,x4)=x2334，那么很容易看出，x1 x2 x3 x4这个序列的函数值为f(x1,x2,x3)^f(x2,x3,x4) 。

所以结合n<=5000，可以用区间dp来求出任意一个区间上的函数值.

dp[i][j]=dp[i+1][j]^dp[i][j-1] (i!=j)
dp[i][j]=a[i] (i==j)

但是做到这里还不够，题目要求的是区间上子区间最大的函数值，每次查询都要O（1），所以再开一个数组ans[i][j]表示[i,j]上的答案。

ans[i][j]=max(ans[i+1][j],ans[i][j-1],dp[i][j]) ,和dp数组一起转移求出

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<math.h>
#include<set>
//#include<unordered_map>
using namespace std;
#define LL long long
#define ULL unsigned long long
const LL INF=1e18+7;
const double eps=1e-5;
const int maxn=5e3+7;
int n,q;
int dp[maxn][maxn];//[i,j]的函数值
int a[maxn];
int ans[maxn][maxn];//[i,j]子区间上dp最大值
int main()
{
//    ios::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        dp[i][i]=a[i];
        ans[i][i]=a[i];
    }
    for(int r=2;r<=n;r++)
    {
        for(int i=1;i<=n-r+1;i++)
        {
            int j=i+r-1;
            dp[i][j]=dp[i+1][j]^dp[i][j-1];
            ans[i][j]=max(dp[i][j],max(ans[i+1][j],ans[i][j-1]));
        }

    }
    scanf("%d",&q);
    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",ans[l][r]);
    }
//    system("pause");
    return 0;
}