AtCoder Regular Contest 089

这场一边吃饭一边打，确实还是很菜的

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 ibetween 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

这个题目不难，就是给你坐标问你能不能到达，首先可以想想能不能到的问题，只要两点需要的步数<=你要走的步数，不直接到的话都是多走偶数步，所以只需要判断奇偶和大小就可以了

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,t=0,x=0,y=0,f=0;
    cin>>n;
    for(int i=0,tt,tx,ty;i<n;i++)
    {
        cin>>tt>>tx>>ty;
        if((abs(tx-x)+abs(ty-y))%2!=(tt-t)%2||abs(tx-x)+abs(ty-y)>(tt-t))
            f=1;
        t=tt,x=tx,y=ty;
    }
    if(!f)cout<<"Yes";
    else cout<<"No";
    return 0;
}

D - Checker

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:

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

Sample Output 1

Copy

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

Sample Input 3

Copy

Sample Output 3

Copy

D题也不难吧，但是自己比较笨，并没有做出来

先讲一下题意吧，就是你有一盘黑白棋，每个正方形黑白块的宽度都是k，但是这个黑白棋的起始位置还没有确定，你现在有一个序列，你需要知道其中最多几个有效

n是很大的啊，但是要注意到k很小，所以起始位置就没那么多了，我们需要做的是去枚举起始位置。

但是怎么去解决那个庞大的n呢，因为如果n不大的话我们就可以直接4*k*k*n的做法了，所以这个题目需要二维前缀和去查询，坐标先%一下，之后加加减减就可以了

#include<bits/stdc++.h>
using namespace std;
int n,k,f[2005][2005],s[2005][2005],t;
int S(int i,int j)
{
    return i>=0&&j>=0?s[min(t-1,i)][min(t-1,j)]:0;
}
int get(int i,int j)
{
    return S(i,j)-S(i,j-k)-S(i-k,j)+S(i-k,j-k);
}
int main()
{
    cin>>n>>k;
    t=k*2;
    string st;
    for(int i=0,x,y; i<n; i++)
    {
        cin>>x>>y>>st;
        if(st=="B")x+=k;
        f[x%t][y%t]++;
    }
    for(int i=0; i<t; i++)
        for(int j=0; j<t; j++)
            s[i][j]=S(i,j-1)+f[i][j];
    for(int i=0; i<t; i++)
        for(int j=0; j<t; j++)
            s[i][j]+=S(i-1,j);
    int ans=0;
    for(int i=0; i<t; i++)
        for(int j=0; j<t; j++)
            ans=max(ans,get(i,j)+get(i-k,j-k)+get(i-k,j+k)+get(i+k,j-k)+get(i+k,j+k)+get(i+t,j)+get(i,j+t));
    printf("%d
",ans);
    return 0;
}