Codeforces Round #766 (Div. 2) 做题记录

官方题解地址

https://codeforces.com/blog/entry/99067

EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEm.

A. Not Shading

分四种情况讨论：

若第 $r$ 行第 $c$ 列的元素 (以下简称 $A_{i,j}$ ) 初始就是黑色，则需要操作 $0$ 次。
若第 $r$ 行或第 $c$ 列存在至少一个黑色格子，则需要操作 $1$ 次。
若 $n \times m n × m$ 的格子中存在至少一个黑色格子，则需要操作 $2$ 次即可将 $n \times m n × m$ 的所有格子变成黑色。
若 $n \times m n × m$ 的格子中不存在黑色格子，则无解。

//木の葉舞う所に，火は燃ゆる。
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
#include <ext/rope>
#include <unordered_set>
#include <unordered_map>
#define int long long
#define endl '\n'
#define inf 0x3f3f3f3f3f3f3f3f
#define debug printf("Hello World\n")
#define ios ios::sync_with_stdio(false)
using namespace __gnu_cxx;
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int mod1 = 1e9 + 7, mod2 = 998244353;
const double PI = 3.1415926535898, Ee = 2.718281828459;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
inline int read()
{
    int x = 0, f = 1;char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
    return x * f;
}
const int N = 100 + 10, M = 1e6 + 10;

char a[N][N];

void solve()
{
    int n, m, r, c; cin>>n>>m>>r>>c;
    for(int i = 1;i <= n;i ++) cin>>a[i] + 1;
    if(a[r][c] == 'B') cout<<0<<endl;
    else
    {
        for(int i = 1;i <= n;i ++)
            if(a[i][c] == 'B')
            {
                cout<<1<<endl;
                return;
            }
        for(int j = 1;j <= m;j ++)
            if(a[r][j] == 'B')
            {
                cout<<1<<endl;
                return;
            }
        for(int i = 1;i <= n;i ++) for(int j = 1;j <= m;j ++)
            if(a[i][j] == 'B')
            {
                cout<<2<<endl;
                return;
            }
        cout<<-1<<endl;
    }

}

signed main() {
    ios;
    int t = 1;  cin>>t;
    while (t--) solve();
    return 0;
}

B. Not Sitting

结论:无论 $R a h u l$ 事先坐在哪里， $T i n a$ 之后都会坐在四边形的四个角之一以保证距离最远。

证明:略（提示:通常的做法是可以把二维曼哈顿距离分别看出两个一维数轴上的距离之和就可以轻而易举的得出该结论)

枚举每个四边形中每个格子到四个角的最长距离并计数最后从小到大依次输出即可。

//木の葉舞う所に，火は燃ゆる。
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
#include <ext/rope>
#include <unordered_set>
#include <unordered_map>
#define int long long
#define endl '\n'
#define inf 0x3f3f3f3f3f3f3f3f
#define debug printf("Hello World\n")
#define ios ios::sync_with_stdio(false)
using namespace __gnu_cxx;
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int mod1 = 1e9 + 7, mod2 = 998244353;
const double PI = 3.1415926535898, Ee = 2.718281828459;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
inline int read()
{
    int x = 0, f = 1;char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
    return x * f;
}
const int N = 2e5 + 10, M = 1e6 + 10;

int ans[N];

void solve()
{
    int n, m; cin>>n>>m;
    for(int i = 1;i <= n;i ++) for(int j = 1;j <= m;j ++)
            ans[max(abs(i - 1), abs(n - i)) + max(abs(j - 1), abs(m - j))] ++;
    for(int i = n / 2 + m / 2;i <= n + m - 2;i ++)
    {
        for(int j = 1;j <= ans[i];j ++) cout<<i<<" ";
        ans[i] = 0;
    }
    cout<<endl;
}

signed main() {
    ios;
    int t = 1;  cin>>t;
    while (t--) solve();
    return 0;
}

C. Not Assigning

结论 $1$ : 不存在三个以上素数两两之和均为素数

证明: 设三个素数分别为 $a, b, c$

$a = 2$ , 则 $b$ , $c$ 与 $a$ 的和为素数则 $b$ 与 $c$ 必须是奇数，此时 $b + c$ 为奇数 $+$ 奇数 $=$ 偶数且大于 $2$ 所以不是素数。
$a =$ 奇素数，则 $b$ , $c$ 与 $a$ 的和为素数则 $b$ 与 $c$ 必须是偶数，此时 $b + c$ 为偶数 $+$ 偶数 $=$ 偶数且大于 $2$ 所以不是素数。

结论 $2$ : 符合题目条件的树只能是一条链

证明: 反证法: 若不是一条链的树，则必有一个结点度数 $deg\geq3$ ,当有 $3$ 条边连接到一个结点时三条边的权值应均为素数且两两之和均为素数，由结论 $1$ 可知这是不可能实现的。

判断是否有度数 $deg\geq3$ 的结点，若有则无解，否则一定是一条链，按照染色法给边逐一染色即可，任选一组可行解均可，我这里选的 $2$ 和 $5$ .

//木の葉舞う所に，火は燃ゆる。
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
#include <ext/rope>
#include <unordered_set>
#include <unordered_map>
#define int long long
#define endl '\n'
#define inf 0x3f3f3f3f3f3f3f3f
#define debug printf("Hello World\n")
#define ios ios::sync_with_stdio(false)
using namespace __gnu_cxx;
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int mod1 = 1e9 + 7, mod2 = 998244353;
const double PI = 3.1415926535898, Ee = 2.718281828459;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
inline int read()
{
    int x = 0, f = 1;char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
    return x * f;
}
const int N = 2e5 + 10, M = 1e6 + 10;

vector<PII> e[N];
int deg[N];
int ans[N];
int num[2] = {2, 5};

void dfs(int u, int fa, int idx)
{
    for(auto &p : e[u])
    {
        int v = p.first, id = p.second;
        if(v == fa) continue;
        ans[id] = num[idx];
        dfs(v, u, 1 - idx);
    }
}

void solve()
{
    int n; cin>>n;
    for(int i = 1;i <= n;i ++) deg[i] = 0, e[i].clear();
    for(int i = 1;i < n;i ++)
    {
        int u, v; cin>>u>>v;
        e[u].push_back({v, i});
        e[v].push_back({u, i});
        deg[u] ++;
        deg[v] ++;
    }
    for(int i = 1;i <= n;i ++)
        if(deg[i] >= 3)
        {
            cout<<-1<<endl;
            return;
        }

    for(int i = 1;i <= n;i ++)
        if(deg[i] == 1)
        {
            dfs(i, 0, 0);
            break;
        }
    for(int i = 1;i < n;i ++) cout<<ans[i]<<" "; cout<<endl;
}

signed main() {
    ios;
    int t = 1;  cin>>t;
    while (t--) solve();
    return 0;
}

D. Not Adding

从大到小枚举每个数查询是否存在一组数的gcd等于该数，合法的一组数一定均为当前数的倍数。枚举所有当前数的倍数求GCD的和，若该GCD和等于当前数，则当前数可加入列表中。

该题正确性证明请去看官方题解，Wo TCL。

//木の葉舞う所に，火は燃ゆる。
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
#include <ext/rope>
#include <unordered_set>
#include <unordered_map>
#define int long long
#define endl '\n'
#define inf 0x3f3f3f3f3f3f3f3f
#define debug printf("Hello World\n")
#define ios ios::sync_with_stdio(false)
using namespace __gnu_cxx;
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int mod1 = 1e9 + 7, mod2 = 998244353;
const double PI = 3.1415926535898, Ee = 2.718281828459;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
inline int read()
{
    int x = 0, f = 1;char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
    return x * f;
}
const int N = 1e6 + 10, M = 1e6 + 10;

bool vis[N];

int gcd(int x, int y)
{
    if(x % y == 0) return y;
    return gcd(y, x % y);
}

void solve()
{
    int n; n = read();
    for(int i = 1;i <= n;i ++) vis[read()] = true;
    int mx = 1e6, ans = 0;
    for(int i = mx;i >= 1;i --)
    {
        if(!vis[i])
        {
            int tot = 0;
            for(int j = i + i;j <= mx;j += i)
            {
                if(vis[j]) tot = gcd(tot, j);
            }
            if(tot == i) vis[i] = true, ans ++;
        }
    }
    printf("%lld\n", ans);
}

signed main() {
//    ios;
    int t = 1;  // cin>>t;
    while (t--) solve();
    return 0;
}

E. Not Escaping

不会。