Codeforces Round #594 (Div. 2) ABC题

A题

题意：给出 n 条 y = x + pi ， m 条 y = - x + qi，求n + m条直线的交点有多少横纵坐标都是整数。

思路：一个简单数学题，将两个方程联立，即可求出x和y，x为整数则y一定为整数，所以只用看x。

　　　x = ( p - q ) / 2 奇数减奇数为偶数，偶数减偶数为偶数，则在读入的时候统计奇偶数的个数，直接相乘即可

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <cstring>
 6 #include <vector>
 7 #include <cmath>
 8  
 9 using namespace std;
10 const int N = 1e5 + 5;
11 int p[N], q[N];
12  
13 int main(){
14     int t;
15     scanf("%d", &t);
16     while(t -- ){
17         int n, m;
18         long long flag11 = 0, flag12 = 0, flag21 = 0, flag22 = 0;
19         scanf("%d", &n);
20         for(int i = 0; i < n; i ++ ){
21             scanf("%d", &p[i]);
22             if(p[i] % 2 == 0)
23                 flag12 ++ ;
24             else
25                 flag11 ++ ;
26         }
27         scanf("%d", &m);
28         for(int i = 0; i < m; i ++ ) {
29             scanf("%d", &q[i]);
30             if (q[i] % 2 == 0)
31                 flag22 ++ ;
32             else
33                 flag21 ++ ;
34         }
35         long long ans = flag11 * flag21 + flag22 * flag12;
36         printf("%I64d
", ans);
37     }
38     return 0;
39 }

View Code

B题

题意：给n根棍子，要把它们首尾相连构成一条折线，且相连的两条线必须垂直。

　　　求从(0, 0)到折线尾部点的距离平方。

思路：要使两个数平方和最大，则两个数的差应该尽量大。

　　　读入之后排序，前一半相加为最小，后一半相加为最大，则两数相减最大

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <cstring>
 6 #include <vector>
 7 #include <cmath>
 8  
 9 using namespace std;
10 const int N = 1e5 + 5;
11 int a[N];
12  
13 int main() {
14     int n;
15     scanf("%d", &n);
16     for (int i = 0; i < n; i++) {
17         scanf("%d", &a[i]);
18     }
19     sort(a, a + n);
20     long long sum1 = 0, sum2 = 0;
21     for (int i = 0; i < n / 2; i++)
22         sum1 += a[i];
23     for (int i = n / 2; i < n; i++)
24         sum2 += a[i];
25     long long ans = sum1 * sum1 + sum2 *sum2;
26     printf("%I64d", ans);
27     return 0;
28 }

View Code

C题

题意：给出n*m的矩形，要满足的条件为，相邻的格子颜色不同或最多两个颜色相同。

　　　求满足条件的方法数。

思路：我是找规律写的……是一个类斐波那契数列然后再进行运算。

　　　f(1) = 1, f(2) = 2, f(3) = f(2) + f(1), ……

　　　ans = 2 * (f(n) + f(m) - 1)

证明过程在评论区有大佬给出来了：

只考虑有相同颜色相邻的情况，考虑对称只算一半的情况。将每个格子看成一个点，进行连线，线不能相交，于是可以发现没有同时有相垂直的两条边的情况，所以答案是(没有水平边的数量)+(没有垂直边的数量)-(没有边缘的数量)。分解之后就好算多了，推一下就出来了（

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <cstring>
 6 #include <vector>
 7 #include <cmath>
 8 
 9 using namespace std;
10 const int N = 1e5 + 5;
11 long long f[N];
12 const int mod = 1e9 + 7;
13 
14 void init(){
15     f[1] = 1;
16     f[2] = 2;
17     for(int i = 3; i < N; i ++ ){
18         f[i] = (f[i - 1] + f[i - 2]) % mod;
19     }
20 }
21 
22 int main() {
23     int n, m;
24     scanf("%d %d", &n, &m);
25     init();
26     long long ans = 2ll * (f[n] + f[m] - 1) % mod;
27     printf("%I64d", ans);
28     return 0;
29 }

View Code

注意取模和f[N]的数据类型