时间戳

首页 > 技术文章 > AtCoder Beginner Contest 086 （ABCD）

AtCoder Beginner Contest 086 （ABCD）

wydxry 2018-03-01 11:25 原文

A - Product

题目链接：https://abc086.contest.atcoder.jp/tasks/abc086_a

Time limit : 2sec / Memory limit : 256MB

Score : 100 points

Problem Statement

AtCoDeer the deer found two positive integers, a and b. Determine whether the product of a and b is even or odd.

Constraints

  • 1 ≤ a,b ≤ 10000
  • a and b are integers.

Input

Input is given from Standard Input in the following format:

a b

Output

If the product is odd, print Odd; if it is even, print Even.

Sample Input 1

Copy
3 4

Sample Output 1

Copy
Even

As 3×4=12 is even, print Even.

Sample Input 2

Copy
1 21

Sample Output 2

Copy
Odd

As 1×21=21 is odd, print Odd.

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3  
 4 int main()
 5 {
 6     int a,b;
 7     while(cin>>a>>b){
 8         if((a*b)%2==0) cout<<"Even"<<endl;
 9         else cout<<"Odd"<<endl;
10     }
11     return 0;
12 }
View Code

B - 1 21

题目链接：https://abc086.contest.atcoder.jp/tasks/abc086_b

Time limit : 2sec / Memory limit : 256MB

Score : 200 points

Problem Statement

AtCoDeer the deer has found two positive integers, a and b. Determine whether the concatenation of a and b in this order is a square number.

Constraints

  • 1 ≤ a,b ≤ 100
  • a and b are integers.

Input

Input is given from Standard Input in the following format:

a b

Output

If the concatenation of a and b in this order is a square number, print Yes; otherwise, print No.

Sample Input 1

Copy
1 21

Sample Output 1

Copy
Yes

As 121 = 11 × 11, it is a square number.

Sample Input 2

Copy
100 100

Sample Output 2

Copy
No

100100 is not a square number.

Sample Input 3

Copy
12 10

Sample Output 3

Copy
No

 题解：直接判断是否能开方

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 bool prime(int x)
 4 {
 5     int y=sqrt(x);
 6     return y*y==x;
 7 }
 8 int main()
 9 {
10     int a,b;
11     while(cin>>a>>b){
12         if(a<b) swap(a,b);
13         int flag=0;
14         if(a<10&&b<10){
15             if(prime(a+10*b)||prime(a*10+b)) flag=1;
16         }
17         else if(a>=10&&a<100&&b<10){
18             if(prime(a+100*b)||prime(a*10+b)) flag=1;
19         }
20         else if(a>=10&&a<100&&b>=10&&b<100){
21             if(prime(a+100*b)||prime(a+100*b)) flag=1;
22         }
23         else if(a==100&&b>=10&&b<100){
24             if(prime(a+1000*b)||prime(a*100+b)) flag=1;
25         }
26         if(flag) cout<<"Yes"<<endl;
27         else cout<<"No"<<endl;
28     }
29     return 0;
30 }
View Code

C - Traveling

题目链接：https://abc086.contest.atcoder.jp/tasks/arc089_a

C - Traveling

Time limit : 2sec / Memory limit : 256MB

Score : 300 points

Problem Statement

AtCoDeer the deer is going on a trip in a two-dimensional plane. In his plan, he will depart from point (0,0) at time 0, then for each i between 1 and N (inclusive), he will visit point (xi,yi) at time ti.

If AtCoDeer is at point (x,y) at time t, he can be at one of the following points at time t+1: (x+1,y), (x−1,y), (x,y+1) and (x,y−1). Note that he cannot stay at his place. Determine whether he can carry out his plan.

Constraints

  • 1 ≤ N ≤ 105
  • 0 ≤ xi ≤ 105
  • 0 ≤ yi ≤ 105
  • 1 ≤ ti ≤ 105
  • ti < ti+1 (1 ≤ i ≤ N−1)
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

N
t1 x1 y1
t2 x2 y2
:
tN xN yN

Output

If AtCoDeer can carry out his plan, print Yes; if he cannot, print No.

Sample Input 1

Copy
2
3 1 2
6 1 1

Sample Output 1

Copy
Yes

For example, he can travel as follows: (0,0), (0,1), (1,1), (1,2), (1,1), (1,0), then (1,1).

Sample Input 2

Copy
1
2 100 100

Sample Output 2

Copy
No

It is impossible to be at (100,100) two seconds after being at (0,0).

Sample Input 3

Copy
2
5 1 1
100 1 1

Sample Output 3

Copy
No

题解：判断纵坐标和横坐标之后是否大于t 如果大于再减去t判断是否能够被我整除
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 bool test(int t,int x,int y)
 4 {
 5     int z=x+y;
 6     if(t<z) return 0;
 7     else{
 8         if((t-z)%2==0) return 1;
 9         else return 0;
10     }
11 }
12 int main()
13 {
14     int n;
15     while(cin>>n){
16         int t,x,y;
17         int flag=1;
18         while(n--){
19             cin>>t>>x>>y;
20             if(!test(t,x,y)) flag=0;
21         }
22         if(flag) cout<<"Yes"<<endl;
23         else cout<<"No"<<endl;
24     }
25     return 0;
26 }

D - Checker （前缀和）

题目链接：https://abc086.contest.atcoder.jp/tasks/arc089_b

Time limit : 2sec / Memory limit : 256MB

Score : 500 points

Problem Statement

AtCoDeer is thinking of painting an infinite two-dimensional grid in a checked pattern of side K. Here, a checked pattern of side K is a pattern where each square is painted black or white so that each connected component of each color is a K × K square. Below is an example of a checked pattern of side 3:

cba927b2484fad94fb5ff7473e9aadef.png

AtCoDeer has N desires. The i-th desire is represented by xi, yi and ci. If ci is B, it means that he wants to paint the square (xi,yi) black; if ci is W, he wants to paint the square (xi,yi) white. At most how many desires can he satisfy at the same time?

Constraints

  • 1 ≤ N ≤ 105
  • 1 ≤ K ≤ 1000
  • 0 ≤ xi ≤ 109
  • 0 ≤ yi ≤ 109
  • If i ≠ j, then (xi,yi) ≠ (xj,yj).
  • ci is B or W.
  • N, K, xi and yi are integers.

Input

Input is given from Standard Input in the following format:

N K
x1 y1 c1
x2 y2 c2
:
xN yN cN

Output

Print the maximum number of desires that can be satisfied at the same time.

Sample Input 1

Copy
4 3
0 1 W
1 2 W
5 3 B
5 4 B

Sample Output 1

Copy
4

He can satisfy all his desires by painting as shown in the example above.

Sample Input 2

Copy
2 1000
0 0 B
0 1 W

Sample Output 2

Copy
2

Sample Input 3

Copy
6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W

Sample Output 3

Copy
4

 题解：思路是对的 但是暴力过不了 看看大佬的解法 转自：https://www.cnblogs.com/8023spz/p/8409399.html

这道题数据挺大的，首先是移动到2k*2k的框框里，不影响坐标（也就是横纵坐标都移动2k的整数倍,如果只移动k的整数倍不能保证颜色不变）。
最初先默认数黑色或者白色都可以，这里先默认数黑色，白色的通过变色移动（横或纵坐标+k）映射到黑色的位置，然后整个图里只剩下黑色的。
最后求出结果，只需要取sum 和 n - sum中大的那个就行了，因为默认是黑色，黑白可以互换。
然后是移动k宫格在不同位置，一共有k*k种情况，直接在2k*2k的框框里操作，需要计算二维前缀和，之前是一个一个点去判断超时了，想想也不能一味的暴力啊，肯定得用点妙招，然后移动x轴，计算一维前缀和时间勉强没超。
k宫格是从左下角开始移动就是从（0,0）开始，需要记录的是k宫格里黑色的个数，以及斜对角的矩形里黑色的个数，因为斜对角的颜色相同，横竖相邻的区域颜色相异。
计算二维前缀和需要用离散学的容斥定理，最后求单独区域需要前缀和相减，也要用到容斥定理。
 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <cmath>
 7 #include <iomanip>
 8 
 9 using namespace std;
10 
11 int v[2001][2001];
12 int n,k;
13 int num(int x1,int y1,int x2,int y2){
14     return v[x2][y2] - v[x2][y1] - v[x1][y2] + v[x1][y1];///前缀和 减去左边 下边和左下边的k宫格前缀和  容斥定理：左边和下边都包含了左下边 需要加上一个左下边
15 }
16 int main()
17 {
18     int x,y,ans = 0,sum;
19     char ch;
20     scanf("%d%d",&n,&k);
21     for(int i = 1;i <= n;i ++){
22         scanf("%d%d %c",&x,&y,&ch);
23         x %= 2 * k;///把所有点都移动到 2k * 2k 的区域
24         y %= 2 * k;
25         x += k * (ch == 'W');///x可以变成y W 也可以变成 B 这里白色都变成黑色的 如果转换后的黑色是满足的那么原来的白色也一定是满足的
26         v[x % (2 * k) + 1][y % (2 * k) + 1] ++;///求前缀和要求从（1,1）开始
27     }
28     for(int i = 1;i <= 2 * k;i ++)///求前缀和
29         for(int j = 1;j <= 2 * k;j ++)
30             v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1];///加上左边下边和左下角的和  容斥定理：左边和下边的都包含了左下边的  要减去一个左下边的for(int i = 1;i <= k;i++)///k * k个格子依次做为起点构成新的k宫格 也就是移动k宫格 看看有几个黑色点包含在内 （默认黑色 可互换）
31         for(int j = 1;j <= k;j++)
32         {
33             ///斜对角的k宫格是相同颜色 2k * 2k区域最多有五个这样的区域
34             sum = num(0,0,i,j) + num(i,j,k + i,k + j) + num(k + i,k + j,2 * k,2 * k) + num(k + i,0,2 * k,j) + num(0,k + j,i,2 * k);
35             ans = max(ans,max(sum,n - sum));///黑白色可以互换
36         }
37     printf("%d\n",ans);
38 }

 

推荐阅读