cf483-div2

ACM

cf补题

C

数学题
一开始是模拟进制转换，发现c++的精度不够，然后就用python写了一发，T。
最后列出来一个式子：\(\frac{b^x·p}{q}\)，若能整除，则为可以有限表示的数字。
然而，还是没有想到特例，gcd在除的时候会发生变化。

最后记得一定要关同步

ac code

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
41
42
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n;
    ios::sync_with_stdio(false);
    cin>>n;
    ll p, q;
    ll b;
    while(n--){
        cin>>p>>q>>b;
        ll num = p/q;
        p -= num*q;
        ll com = __gcd(p, q);
        p /= com;
        q /= com;
        bool flag = false;
        ll gc = __gcd(q, b);
        if(p == 0){
            flag = true;
        }
        else{
            while(q%gc == 0&&gc!=1){
                q /= gc;
                gc = __gcd(q, gc);
            }
            if(q!=1){
                flag = false;
            }
            else flag = true;
        }
        if(!flag){
            printf("Infinite\n");
        }
        else {
            printf("Finite\n");
        }
    }
    return 0;
}

D

dp, 有点st表的感觉。
注意答案数组和记录数组的区别

ac code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e3+10;
ll num[maxn];
ll dp[maxn][maxn];//答案
ll mem[maxn][maxn];//记录合并区间的值
int n;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>num[i];
        dp[i][i] = num[i];
        mem[i][i] = num[i];
    }
    for(int l=2; l<=n; l++){
        for(int i=1; i+l-1<=n; i++){
            dp[i][i+l-1] = max(mem[i][i+l-2]^mem[i+1][i+l-1],
                               max(dp[i][i+l-2], dp[i+1][i+l-1]));
            mem[i][i+l-1] = mem[i][i+l-2]^mem[i+1][i+l-1];
        }
    }
    int q;
    cin>>q;
    int ll, rr;
    for(int i=0; i<q; i++){
        cin>>ll>>rr;
        cout<<dp[ll][rr]<<endl;
    }
    return 0;
}

未解决的问题

本文标题:cf483-div2

文章作者:Babydragon

发布时间:2018-05-16, 12:19:57

最后更新:2018-05-16, 12:41:02

原始链接:http://baolintian.github.io/2018/05/16/cf483-div2/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. C
    1. 1.1. ac code
  2. 2. D
    1. 2.1. ac code
  3. 3. 未解决的问题
{{ live2d() }}