#include<bits/stdc++.h>

 using namespace std;

 bool prime(int x)

 {

     int y=sqrt(x);

     return y*y==x;

 }

 int main()

 {

     int a,b;

     while(cin>>a>>b){

         if(a<b) swap(a,b);

         int flag=;

         if(a<&&b<){

             if(prime(a+*b)||prime(a*+b)) flag=;

         }

         else if(a>=&&a<&&b<){

             if(prime(a+*b)||prime(a*+b)) flag=;

         }

         else if(a>=&&a<&&b>=&&b<){

             if(prime(a+*b)||prime(a+*b)) flag=;

         }

         else if(a==&&b>=&&b<){

             if(prime(a+*b)||prime(a*+b)) flag=;

         }

         if(flag) cout<<"Yes"<<endl;

         else cout<<"No"<<endl;

     }

     return ;

 }

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.

Sample Input 1

2

3 1 2

6 1 1

Sample Output 1

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

1

2 100 100

Sample Output 2

No

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

Sample Input 3

2

5 1 1

100 1 1

Sample Output 3

No

题解：判断纵坐标和横坐标之后是否大于t 如果大于再减去t判断是否能够被我整除

 #include<bits/stdc++.h>

 using namespace std;

 bool test(int t,int x,int y)

 {

     int z=x+y;

     if(t<z) return ;

     else{

         if((t-z)%==) return ;

         else return ;

     }

 }

 int main()

 {

     int n;

     while(cin>>n){

         int t,x,y;

         int flag=;

         while(n--){

             cin>>t>>x>>y;

             if(!test(t,x,y)) flag=;

         }

         if(flag) cout<<"Yes"<<endl;

         else cout<<"No"<<endl;

     }

     return ;

 }

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:

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宫格里黑色的个数，以及斜对角的矩形里黑色的个数，因为斜对角的颜色相同，横竖相邻的区域颜色相异。
计算二维前缀和需要用离散学的容斥定理，最后求单独区域需要前缀和相减，也要用到容斥定理。

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <iomanip>

 using namespace std;

 int v[][];

 int n,k;

 int num(int x1,int y1,int x2,int y2){

     return v[x2][y2] - v[x2][y1] - v[x1][y2] + v[x1][y1];///前缀和 减去左边 下边和左下边的k宫格前缀和  容斥定理：左边和下边都包含了左下边 需要加上一个左下边

 }

 int main()

 {

     int x,y,ans = ,sum;

     char ch;

     scanf("%d%d",&n,&k);

     for(int i = ;i <= n;i ++){

         scanf("%d%d %c",&x,&y,&ch);

         x %=  * k;///把所有点都移动到 2k * 2k 的区域

         y %=  * k;

         x += k * (ch == 'W');///x可以变成y W 也可以变成 B 这里白色都变成黑色的 如果转换后的黑色是满足的那么原来的白色也一定是满足的

         v[x % ( * k) + ][y % ( * k) + ] ++;///求前缀和要求从（1,1）开始

     }

     for(int i = ;i <=  * k;i ++)///求前缀和

         for(int j = ;j <=  * k;j ++)

             v[i][j] += v[i - ][j] + v[i][j - ] - v[i - ][j - ];///加上左边下边和左下角的和  容斥定理：左边和下边的都包含了左下边的  要减去一个左下边的for(int i = 1;i <= k;i++)///k * k个格子依次做为起点构成新的k宫格 也就是移动k宫格 看看有几个黑色点包含在内 （默认黑色 可互换）

         for(int j = 1;j <= k;j++)

         {

             ///斜对角的k宫格是相同颜色 2k * 2k区域最多有五个这样的区域

             sum = num(,,i,j) + num(i,j,k + i,k + j) + num(k + i,k + j, * k, * k) + num(k + i,, * k,j) + num(,k + j,i, * k);

             ans = max(ans,max(sum,n - sum));///黑白色可以互换

         }

     printf("%d\n",ans);

 }