Codeforces Round 940 (Div. 2) and CodeCraft-23 (补题中的小白)

youhualiuh / 2024-04-23 / 原文

A. Stickogon

思路(题意):

输出满足规则的正多边形的最大数量,所以满足最多的正多边形,那我们就需要枚举最小的正多边形,也就是正三角形,所以我们要计算这个满足最小的正三角形的数量即可我这里使用的是map 储存看Code。

Code:

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

void solve() {
    int n; cin >> n;
    map <int, int> mp;
    for (int i = 1, x; i <= n; i++) {
        cin >> x; mp[x] ++;
    }
    int ans = 0;
    for (const pair <int, int> &i : mp) {
        ans += i.second / 3;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B. A BIT of a Construction

思路(题意):

给你n个数,k代表和,其次你要理解一个二进制的一个小妙招的一个小性质.看图

最大化你要的 a1 | a2 | a3 | ... | an 中1的个数看图你就知道只要枚举 1 << i - 1的极限即可这就是你需要求出的最大值

/*
当它们 -1 时
2^0 --- 00000001 1位 0  
2^1 --- 00000010 1位 1
2^2 --- 00000100 1位 2
2^3 --- 00001000 1位 3
2^4 --- 00010000 1位 4
2^5 --- 00100000 1位 5
2^6 --- 01000000 1位 6
2^7 --- 10000000 1位 7
.....
所以你会发现有个规律
可以得出一个小结论 遍历 (1 << i - 1) 只要它大于k的时候截止 且下一个值是 k - (1 << i - 1) 在后面就00000即可构造 
不过要单独判断一下 n == 1的时候
*/

Code:

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

void solve() {
    int n, k, x = 1; cin >> n >> k;
    if (n == 1) {
        cout << k << '\n';
        return ;
    }
    while ((x << 1 | 1) < k) {
        x = x << 1 | 1;
    } 
    cout << x << ' ' << k - x << ' ';
    for (int i = 3; i <= n; i++) cout << 0 << ' ';
    cout << '\n'; 

}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C. How Does the Rook Move?

思路(题意):

在一个n * n 的棋牌分别放置白车和黑车且保证它不在同行同列作为他的有效棋步否则摆起失败给你个k -> (r, c) 代表放的位置你如过白车放在这里那么黑车就在 (c, r) 如果r = c 那么我们就跳过这个回合你和这个计算机下了k步棋你需要继续知道不满足有效的棋步继续下棋有多少方案取模1e9

了解了题意之后你会发现它的摆棋是n皇后问题的摆法在这里你的摆起就类似于在对角线放置只要横向和这个都不满足即可

那么这题就好分析首先它是由两中可能

1- 
r == c -> 一行一列
2-
r != c 两行两列

首先我们使用递归的思想来证明一下这个dp[i] = dp[i - 1] + dp[i - 2] * (i - 1) * 2

先不管取模
come
经过了某一些操作 我们使得 剩下 {1, 5, 8, 9, 10} -- 假设

那么我们应该这么去排呢 应该是 挑一个 不如 {} 中的任意一个 dp[i - 1] * 1
那么剩下的不久应该在 dp[i - 2] * 2 * (n - 1) 在这里找 为什么 这里*2 是因为(i, j) --- (j, i) 他们有两种情况
看图

dp[i - 2] * (i - 1) * 2
{1, 2, 3, 4, 5}
(1, ...) 不应该是有i - 1中可能加上(..., 1) 所以有两种可能所以它的结论是这个

dp[i - 1] * 1
是因为他只有一种 他不挑所以它的结论是这个 请看Code

Code(递归):

#include<bits/stdc++.h>
    
using namespace std;
const int mod = 1e9 + 7, N = 3e5 + 5;

int dp[N], n, k;
void init() {
    for (int i = 1; i <= n; i++) {
        dp[i] = -1;
    }
}

long long check(int n) {
    if (n <= 1) return 1LL;
    if (dp[n] != -1) return (dp[n] % mod) * 1LL;
    return dp[n] = ((check(n - 1) % mod + check(n - 2) % mod * (n - 1) % mod * 2LL % mod) % mod) * 1LL;
}

void solve() {
    cin >> n >> k;
    set <int> st;
    for (int i = 1, x, y; i <= k; i++) {
        cin >> x >> y; st.insert(x); st.insert(y);
    }
    int m = n - st.size();
    init();
    cout << check(m) << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

#include<bits/stdc++.h>
    
using namespace std;
const int mod = 1e9 + 7, N = 3e5 + 5;

long long dp[N]; int n, k;  

void init() {
    for (int i = 1; i <= n; i++) dp[i] = 0;
    dp[0] = dp[1] = 1;
}

void solve() {
    cin >> n >> k;
    set <int> st;
    for (int i = 1, x, y; i <= k; i++) {
        cin >> x >> y; st.insert(x); st.insert(y);
    }
    int m = n - st.size();
    init();
    for (int i = 1; i <= m; i++) {
        dp[i] = (dp[i - 1] % mod + dp[i - 2] % mod * (i - 1) % mod * 2LL % mod) % mod;
    }
    cout << dp[m] << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D. A BIT of an Inequality

思路(题意):

给你一个数组找到(x, y, z)三元组满足 x, y, z >= 1&&<=n 且 f(x, y) ^ f(y, z) > f(x, z) 定义了f(l, r) = al^al+1^...^ar 输出满足的元素的个数

通过异或前缀和来写统计1的个数枚举a[y] 考虑00 11得出最终结果

Code:

/*
f(x, y) ^ f(y, z) > f(x, z)
-->这里的y被计算了两次以此S(z) ^ S(x - 1) ^a[y]
把它换成异或前缀和 
--> S(z) ^ S(x - 1) ^ a[y] > S(z) ^ S(x - 1)
所以需要去枚举a[y] 只有是1 才可以去改变
*/
#include<bits/stdc++.h>
    
using namespace std;
const int N = 1e5 + 5, M = 35;
using i64 = long long;

int s[N], a[N];
i64 c[M][N];

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; s[i] = s[i - 1] ^ a[i];
        for (int j = 0; j < 30; j++) {
            c[j][i] = c[j][i - 1] + (s[i] >> j & 1);
        }
    }
    i64 ans = 0;
    for (int i = 1; i <= n; i++) {
        int k = 29; k++;
        while (k >= 0 && (a[i] >> k & 1) == 0) k--;
        if (k == -1) continue;
        ans += (c[k][n] - c[k][i - 1]) * c[k][i - 1];
        ans += (n - i + 1 - (c[k][n] - c[k][i - 1])) * (i - c[k][i - 1]);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}