0708HZNU|0708HZNU 2019 Summer training 8 clone 0708HZNU2019Summertraining8clone

目录：
| A | CodeForces 1080A | Petya and Origami |
| B | CodeForces 1080B | Margarite and the best present |
| C | CodeForces 1080C | Masha and two friends |
| D | CodeForces 1080D | Olya and magical square |
| E | CodeForces 1080E | Sonya and Matrix Beauty |

A Petya and Origami Petya is having a party soon, and he has decided to invite his nn friends.
He wants to make invitations in the form of origami. For each invitation, he needs two red sheets, five green sheets, and eight blue sheets. The store sells an infinite number of notebooks of each color, but each notebook consists of only one color with kk sheets. That is, each notebook contains kk sheets of either red, green, or blue.
Find the minimum number of notebooks that Petya needs to buy to invite all nn of his friends.
Input
The first line contains two integers nn and kk (1≤n,k≤1081≤n,k≤108) — the number of Petya's friends and the number of sheets in each notebook respectively.
Output
Print one number — the minimum number of notebooks that Petya needs to buy.
Examples
Input
3 5
Output
10
Input
15 6
Output
38
Note
In the first example, we need 22 red notebooks, 33 green notebooks, and 55 blue notebooks.
In the second example, we need 55 red notebooks, 1313 green notebooks, and 2020 blue notebooks.

思路：这个数是2，5，8的倍数，同时也是k的倍数。乘法得出每种颜色所需要的个数，除以k向上取整
参考：https://blog.csdn.net/wjl_zyl_1314/article/details/84504492

#include #include #include #include #include #include #include #includeusing namespace std; typedef long long ll; const int maxn=100010; const int mod=998244353; const int inf=0x3f3f3f3f; int main() { int n,k,a[maxn],sheet; scanf("%d%d",&n,&k); int r,g,b; r=2*n; g=5*n; b=8*n; int sum=0; sum+=r/k; if(r%k!=0)sum++; sum+=g/k; if(g%k!=0)sum++; sum+=b/k; if(b%k!=0)sum++; printf("%d\n",sum); return 0; }

B Margarite and the best present Little girl Margarita is a big fan of competitive programming. She especially loves problems about arrays and queries on them.
Recently, she was presented with an array aa of the size of 109109 elements that is filled as follows:

a1=?1 a2=2 a3=?3 a4=4 a5=?5 And so on ...

That is, the value of the ii-th element of the array aa is calculated using the formula ai=i?(?1)i
She immediately came up with qq queries on this array. Each query is described with two numbers: ll and rr. The answer to a query is the sum of all the elements of the array at positions from ll to rr inclusive.
Margarita really wants to know the answer to each of the requests. She doesn't want to count all this manually, but unfortunately, she couldn't write the program that solves the problem either. She has turned to you — the best programmer.
Help her find the answers!
Input
The first line contains a single integer qq (1≤q≤103) — the number of the queries.
Each of the next qq lines contains two integers ll and rr (1≤l≤r≤109) — the descriptions of the queries.
Output
Print qq lines, each containing one number — the answer to the query.
Example
Input
5
1 3
2 5
5 5
4 4
2 3
Output
-2
-2
-5
4
-1

Note
In the first query, you need to find the sum of the elements of the array from position 1 to position 3. The sum is equal to a1+a2+a3=?1+2?3=?2
In the second query, you need to find the sum of the elements of the array from position 2 to position 5. The sum is equal to a2+a3+a4+a5 = 2?3+4?5 = ?2
In the third query, you need to find the sum of the elements of the array from position 5 to position 5. The sum is equal to a5=?5
In the fourth query, you need to find the sum of the elements of the array from position 4 to position 4. The sum is equal to a4=4
In the fifth query, you need to find the sum of the elements of the array from position 2 to position 3. The sum is equal to a2+a3=2?3=?1.

思路：如果暴力的话会超时，需要找规律，然后发现公式！分情况讨论哦~

#include #include #include #include #include #include #include #includeusing namespace std; typedef long long ll; const int maxn=100010; const int mod=998244353; const int inf=0x3f3f3f3f; int main() { int l,r,a[maxn],sum; int t; scanf("%d",&t); while(t--){ sum=0; scanf("%d%d",&l,&r); if((l%2==0&&r%2==0)) sum=(l+r)/2; else if(l%2==1&&r%2==1) sum=-(l+r)/2; else { if(l%2==1&&r%2==0){ sum=-(l+r+1)/2+r+1; } if(l%2==0&&r%2==1){ sum=(l+r+1)/2-r-1; } }printf("%d\n",sum); } return 0; }

C Masha and two friends Recently, Masha was presented with a chessboard with a height of nn and a width of mm.
The rows on the chessboard are numbered from 11 to nn from bottom to top. The columns are numbered from 11 to mm from left to right. Therefore, each cell can be specified with the coordinates (x,y)(x,y), where xx is the column number, and yy is the row number (do not mix up).
Let us call a rectangle with coordinates (a,b,c,d)(a,b,c,d) a rectangle lower left point of which has coordinates (a,b)(a,b), and the upper right one — (c,d)(c,d).
The chessboard is painted black and white as follows:

0708HZNU|0708HZNU 2019 Summer training 8 clone

文章图片

Masha was very happy with the gift and, therefore, invited her friends Maxim and Denis to show off. The guys decided to make her a treat — they bought her a can of white and a can of black paint, so that if the old board deteriorates, it can be repainted. When they came to Masha, something unpleasant happened: first, Maxim went over the threshold and spilled white paint on the rectangle (x1,y1,x2,y2)(x1,y1,x2,y2). Then after him Denis spilled black paint on the rectangle (x3,y3,x4,y4)(x3,y3,x4,y4).
To spill paint of color colorcolor onto a certain rectangle means that all the cells that belong to the given rectangle become colorcolor. The cell dyeing is superimposed on each other (if at first some cell is spilled with white paint and then with black one, then its color will be black).
【0708HZNU|0708HZNU 2019 Summer training 8 clone】Masha was shocked! She drove away from the guests and decided to find out how spoiled the gift was. For this, she needs to know the number of cells of white and black color. Help her find these numbers!
Input
The first line contains a single integer tt (1≤t≤1031≤t≤103) — the number of test cases.
Each of them is described in the following format:
The first line contains two integers nn and mm (1≤n,m≤1091≤n,m≤109) — the size of the board.
The second line contains four integers x1x1, y1y1, x2x2, y2y2 (1≤x1≤x2≤m,1≤y1≤y2≤n1≤x1≤x2≤m,1≤y1≤y2≤n) — the coordinates of the rectangle, the white paint was spilled on.
The third line contains four integers x3x3, y3y3, x4x4, y4y4 (1≤x3≤x4≤m,1≤y3≤y4≤n1≤x3≤x4≤m,1≤y3≤y4≤n) — the coordinates of the rectangle, the black paint was spilled on.
Output
Output tt lines, each of which contains two numbers — the number of white and black cells after spilling paint, respectively.
Example
Input
5
2 2
1 1 2 2
1 1 2 2
3 4
2 2 3 2
3 1 4 3
1 5
1 1 5 1
3 1 5 1
4 4
1 1 4 2
1 3 4 4
3 4
1 2 4 2
2 1 3 3
Output
0 4
3 9
2 3
8 8
4 8
Note
Explanation for examples:
The first picture of each illustration shows how the field looked before the dyes were spilled. The second picture of each illustration shows how the field looked after Maxim spoiled white dye (the rectangle on which the dye was spilled is highlighted with red). The third picture in each illustration shows how the field looked after Denis spoiled black dye (the rectangle on which the dye was spilled is highlighted with red).
In the first test, the paint on the field changed as follows:

文章图片

In the second test, the paint on the field changed as follows:

文章图片

In the third test, the paint on the field changed as follows:

文章图片

In the fourth test, the paint on the field changed as follows:

文章图片

In the fifth test, the paint on the field changed as follows:

文章图片

题意：给你一个n*m的棋盘，最初(1,1)上为白色，而且每个相邻的块颜色都不同。
之后有两次操作，
第一次操作给出x1,y2,x2,y2
将(x1,y1,x2,y2)这个矩形涂为白色
第二次操作给出x3,y3,x4,y4
将(x3,y3,x4,y4)这个矩形涂为黑色
后涂得会覆盖之前的颜色。问最终的棋盘上黑色和白色的个数
参考博客：https://blog.csdn.net/qq_41021816/article/details/84453969
题解:
1.先调用函数求出所给区域中白色快的数量
2.未考虑重合部分白色块的数量=总的白色块数量+(第一次选定区域的整个部分-第一次选定区域中的白色部分)(因为全部被染成白色了)-第二次选定区域中的白色部分(因为被染成黑色了)
3.考虑重合部分
一共有五种可能，其中能重合的只有四种，画画图就会发现关系
xx1=max(x1,x3);
xx2=min(x2,x4);
yy1=max(y1,y3);
yy2=min(y2,y4);
要想保证重合需要满足(xx1<=xx2 && yy1<=yy2)
答案=未考虑重合部分白色块的数量-整个重叠部分+重叠部分中白色的部分
注意:这个题有个坑点，对于初始状态白色块与黑色快的数量不相同！
ans=((x2-x1+1)*(y2-y1+1)+1)/2; 向上取整的操作 cile(m/n)=(m+n-1)/n;

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define pi acos(-1.0) #define inf 0x3f3f3f3f #define linf 0x3f3f3f3f3f3f3f3fLL #define ms(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; ll ws(ll x1,ll y1,ll x2,ll y2) { ll ans=0; if((x2-x1+1)%2==0 || (y2-y1+1)%2==0) ans=(x2-x1+1)*(y2-y1+1)/2; else if((x1+y1)%2) ans=(x2-x1+1)*(y2-y1+1)/2; else ans=(x2-x1+1)*(y2-y1+1) - (x2-x1+1)*(y2-y1+1)/2; return ans; }int main() { int t; ll n,m; ll x1,y1,x2,y2; ll x3,y3,x4,y4; scanf("%d",&t); while(t--) { scanf("%lld%lld",&n,&m); scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2); scanf("%lld%lld%lld%lld",&x3,&y3,&x4,&y4); ll ans1; ans1=ws(1,1,n,m)+((x2-x1+1)*(y2-y1+1)-ws(x1,y1,x2,y2))-ws(x3,y3,x4,y4); ll xx1=max(x1,x3); ll xx2=min(x2,x4); ll yy1=max(y1,y3); ll yy2=min(y2,y4); if(xx1<=xx2 && yy1<=yy2) { ans1-=(xx2-xx1+1)*(yy2-yy1+1); ans1+=ws(xx1,yy1,xx2,yy2); } ll ans2=n*m-ans1; printf("%lld %lld\n",ans1,ans2); } return 0; }