Codeforces Round #594 (Div. 2)

A - Integer Points

题意：给n条斜率为1和m条斜率为-1的直线，求交点在整点的个数。

题解：观察下面给的图，发现截距相差为偶数的点才有交点在整点。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
#ifdef KisekiPurin
    freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        int p[2] = {}, q[2] = {};
        while(n--) {
            int pi;
            scanf("%d", &pi);
            ++p[pi & 1];
        }
        int m;
        scanf("%d", &m);
        while(m--) {
            int qi;
            scanf("%d", &qi);
            ++q[qi & 1];
        }
        printf("%lld\n", 1ll * p[0]*q[0] + 1ll * p[1]*q[1]);
    }
}

B - Grow The Tree

题意：有n根木棍，要从原点开始横竖横竖间隔摆，求离原点最远距离。

题解：很显然不要求间隔摆就直接一根直接插出去，所以可以试试贪心，用最短的一半下整做竖，其他做横。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[100005];

int main() {
#ifdef KisekiPurin
    freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);
    ll sum1 = 0;
    for(int i = 1, c = n / 2; i <= c; ++i)
        sum1 += a[i];
    ll sum2 = 0;
    for(int i = n / 2 + 1; i <= n; ++i)
        sum2 += a[i];
    printf("%lld\n", sum1 * sum1 + sum2 * sum2);
}

C - Ivan the Fool and the Probability Theory

题意：给1e5*1e5级别的棋盘格，称棋盘格“随机”当且仅当它每个格子至多有一个相邻的格子与他同色。

不会写，数据量略大。

补题题解：首先考虑只有1行的情况，非常简单，随便dp一下。

然后有一个引理：当确定第1行之后，后面的行只能和相邻行完全相同或者完全相反。证明：若结论不成立，至少存在一个位置 \(j\) ，使得 \(a_{2,j}\) 与 \(a_{1,j}\) 相同，而 \(a_{2,j+1}\) 与 \(a_{1,j+1}\) 相反，那么：当 \(a_{1,j}\) 与 \(a_{1,j+1}\) 同色，则 \(a_{1,j}\) 有两个相邻同色；当 \(a_{1,j}\) 与 \(a_{1,j+1}\) 相反，则 \(a_{2,j}\) 有两个相邻同色。且显然的，假如第1行出现了至少1个连续的2格组，那么以后都不能选完全相同，只能选完全相反，对于这种情况只需要确定第一行就可以全部统计完毕。另一种情况是，只有完全间隔的格子可以选择复制一行，且下一次必须选择相反复制，那这种情况压缩到一列去观察，发现和这个问题的1*m版本是一样的（但是不能够乘2，以为原本求出的dp数组就已经是包含两种颜色的）。

所以就是 \((dp[m]-2)+dp[n]\)

启发：不会做的话是不是可以dp出一行或者2行的结果看看规律，然后手画几个小样例看看能不能套上去吧。不过下一次应该是学会这样分析了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;
int dp[100005][2];

int main() {
#ifdef KisekiPurin
    freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
    int n, m;
    while(~scanf("%d%d", &n, &m)) {
        if(n > m)
            swap(n, m);
        dp[1][0] = 2;
        for(int i = 2; i <= m; ++i) {
            dp[i][0] = (dp[i - 1][1] + dp[i - 1][0]) % MOD;
            dp[i][1] = dp[i - 1][0];
        }
        printf("%lld\n", ((1ll * dp[m][0] + dp[m][1] - 2ll) % MOD + (1ll * dp[n][0] + dp[n][1]) % MOD) % MOD);
    }
}

Codeforces Round #594 (Div. 2)

原文：https://www.cnblogs.com/KisekiPurin2019/p/11817004.html