Codeforces 430(div.2)

Posted on | In , | Visitors:

This is my blog.
2017-08-29 codeforces round #430(div.2)
本蒟篛第二次玩cf，惨败。进行中，A题竟被hack，无语到家。今天一早一看，只能怪夜深人静？？！B题是一道几何题，没有往下拉看到图释，用蹩脚的英语，画画弄弄了许久。c题，想用数组加dfs，奈何数据太大，竟忘记了set的存在，看来还需复习一下STL了。d题有点像，之前看到的博弈论，读题读了很久，Perform the bitwise addition operation modulo 2 (xor) of each array element with the number x.这是异或啊！懒惰的询问google，变成模2，所以是google的锅？？！e题连题目都没看。这次水题都没切过，真的是郁闷纠结烦躁。

A Kirill And The Game（枚举）

题目：A Kirill And The Game
题意：药水有两个性质：经验a(l<=a<=r)和价值b(x<=b<=y)。其中效率为经验和价值的比值（纠结了一下谁比谁，英语啊），现在给定一个效率k，问能否配出此效率k的药水。
坑点：1.最大数据为1e7，应该用long long
2.能配出的药水效率不是连续的，如15 16 2 4 7，能配出的是7.5 8 5 5.33 3.75
附上AC代码：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
long long l,r,x,y,k;
scanf("%I64d %I64d %I64d %I64d %I64d",&l,&r,&x,&y,&k);
// wa代码，这样做的原因是觉得加法比乘法快
//    long long z;
//    z=(x-1)*k;
//    long long a;
//    a=y-x;
//    for(long long i=0;i<=a;i++){
//        z+=k;
//        if(z>r){
//            printf("NO\n");
//            return 0;
//        }
//        else if(z<l){
//            continue;
//        }
//        else break;
//    }
//    printf("YES\n");
//经过修改后，以下代码也ac
//    long long z;
//    z=(x-1)*k;
//    long long a;
//    a=y-x;
//    for(long long i=0;i<=a;i++){
//        z+=k;
//        if(z>r){
//            printf("NO\n");
//            return 0;
//        }
//        else if(z<l){
//            continue;
//        }
//        else break;
//    }
//    if(z>=l)
//    printf("YES\n");
//    else
//    printf("NO\n");
      for(long long i=x;i<=y;i++){
            long long tmp=i*k;
            if(l<=tmp&&tmp<=r){
                printf("YES\n");
                return 0;
            }
      }
      printf("NO\n");
      return 0;
}

B. Gleb And Pizza（几何）

题目：B. Gleb And Pizza
题意：gleb不喜欢吃披萨的皮，披萨是一个中心在原点，半径为r的圆，皮是r-d到r的环（这个理解了许久🤦‍♂️），现在有香肠放在披萨上面，香肠也是圆形的，给出每一片香肠的中心坐标和半径，问有几片香肠完整的在皮上。（看图就很好理解）
B.Gleb And Pizza
B.Gleb And Pizza
坑点：半径居然都是可以为0，不符合常理啊！（所以不可以想当然）
附上AC代码：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int dist(int x,int y){
    return (x*x+y*y);
}
int main(){
    int r,d;
    scanf("%d %d",&r,&d);
    d=r-d;
    int n;
    scanf("%d",&n);
    int ans;
    ans=0;
    for(int i=0;i<n;i++){
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        int k;
        k=dist(x,y);
        if(k<(d+z)*(d+z)) continue;
        //下面两个用数学简单推导一下就知道没有必要判断了
        //if(k>(r+z)*(r+z))continue;
        //if(k<(d-z)*(d-z))continue;
        if(k>(r-z)*(r-z))continue;
        ans++;
    }
    printf("%d\n",ans);
    return 0;
}

C. Ilya And The Tree（set vector bfs gcd）

题目：C. Ilya And The Tree
题意：给你一颗n个节点的树，每个点的魅力值定义为从根节点到这个点的路径上的所有权值（包括它自己）的最大公约数。另外你可以把任意一个点改为0.现在求每一个点的魅力值。
附上AC代码：

1
not finished

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽