Codeforces Round #814 (Div. 2)

A. Chip Game

代码

#include 
using namespace std;

std::mt19937 rng(std::random_device{}());
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef const int& cint;
typedef const ll& cll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;

#define ls (loc<<1)
#define rs ((loc<<1)|1)

const int mod1 = 1e9+7;
const int mod2 = 998244353;
const int inf_int = 0x7fffffff;
const int hf_int = 0x3f3f3f3f;
const ll inf_ll = 0x7fffffffffffffff;
const double ept = 1e-9;

int n, m;

void solve(cint T) {
    cin >> n >> m;
    if((n%2+m%2)%2 == 1) { cout << "Burenka\n"; }
    else { cout << "Tonya\n"; }
}

int main() {
    //freopen("1.in", "r", stdin);
    //cout.flags(ios::fixed); cout.precision(8);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T_=1;
    std::cin >> T_;
    for(int _T=1; _T<=T_; _T++)
        solve(_T);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

B. Mathematical Circus

代码

#include 
using namespace std;

std::mt19937 rng(std::random_device{}());
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef const int& cint;
typedef const ll& cll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;

#define ls (loc<<1)
#define rs ((loc<<1)|1)

const int mod1 = 1e9+7;
const int mod2 = 998244353;
const int inf_int = 0x7fffffff;
const int hf_int = 0x3f3f3f3f;
const ll inf_ll = 0x7fffffffffffffff;
const double ept = 1e-9;

int n, k;

void solve(cint T) {
    cin >> n >> k;
    k %= 4;
    if(k == 0) { cout << "NO\n"; }
    else {
        cout << "YES\n";
        for(int i=1; i<=n; i+=2) {
            if((i+1+k) % 4 == 0) { cout << i+1 << ' ' << i << '\n'; }
            else { cout << i << ' ' << i+1 << '\n'; }
        }
    }
}

int main() {
    //freopen("1.in", "r", stdin);
    //cout.flags(ios::fixed); cout.precision(8);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T_=1;
    std::cin >> T_;
    for(int _T=1; _T<=T_; _T++)
        solve(_T);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

C. Fighting Tournament

思路

只需要注意到是一个排列 , 那么整个过程会卡在一个最大的值上 , 也就是说迭代数不会超过 $n$ , 后面一定都是最大的一直赢 , 模拟即可

代码

#include 
using namespace std;

std::mt19937 rng(std::random_device{}());
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef const int& cint;
typedef const ll& cll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;

#define ls (loc<<1)
#define rs ((loc<<1)|1)

const int mod1 = 1e9+7;
const int mod2 = 998244353;
const int inf_int = 0x7fffffff;
const int hf_int = 0x3f3f3f3f;
const ll inf_ll = 0x7fffffffffffffff;
const double ept = 1e-9;

int n, q;
int a[100100];
int sum[100100];

struct qu {
    int id, i, k, ans;
};

void solve(cint T) {
    cin >> n >> q;
    for(int i=1; i<=n; i++) { cin >> a[i]; }
    for(int i=1; i<=n; i++) { sum[i] = 0; }
    vector<qu> qe;
    int t1, t2, t3;
    for(int i=1; i<=q; i++) {
        cin >> t1 >> t2;
        t3 = 0;
        if(a[t1] == n && t2 >= n) { t3 = t2-n+1; }
        t2 = min(t2, n-1);
        qe.push_back({i, t1, t2, t3});
    }
    // cout << " --- " << endl;
    sort(qe.begin(), qe.end(), [](const qu&a, const qu&b) { return a.k < b.k; } );
    deque<int> r;
    for(int i=1; i<=n; i++) { r.push_back(i); }
    int l = 0;
    for(int i=1; i<n; i++) {
        auto k1 = r.front();
        r.pop_front();
        auto k2 = r.front();
        r.pop_front();
        // cout << k1 << ' ' << k2 << endl;
        if(a[k1] < a[k2]) { swap(k1, k2); }
        ++sum[k1];
        r.push_front(k1);
        r.push_back(k2);
        // cout << k1 << ' ' << k2 << ' ' << sum[k1] << ' ' << l << ' ' << qe[0].i << endl;
        while(l < q && qe[l].k == i) { 
            qe[l].ans += sum[qe[l].i]; 
            ++l; 
            // cout << l << ' ' << qe[l-1].ans << ' ' << qe[l-1].i << ' ' << k1 << ' ' << k2 << ' ' << sum[k1] << endl;
        }
        // cout << qe[0].k << ' ' << l << endl;
        // cout << qe[l-1].i << ' ' << sum[qe[l-1].i] << ' ' << qe[l-1].ans << ' ' << l-1 << endl;
    }
    sort(qe.begin(), qe.end(), [](const qu&a, const qu&b) { return a.id < b.id; } );
    for(int i=1; i<=q; i++) { cout << qe[i-1].ans << '\n'; }
}

int main() {
    //freopen("1.in", "r", stdin);
    //cout.flags(ios::fixed); cout.precision(8);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T_=1;
    std::cin >> T_;
    for(int _T=1; _T<=T_; _T++)
        solve(_T);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

D. Burenka and Traditions

思路

1. 异或满足交换律 , 所以我们可以从左向右贪心考虑
2. 因为任何长度的异或都可以表示成长度为 $1$ 和 $2$ 的异或的一个组合 , 且不会更劣 , 所以我们只用考虑长度为 $1$ 或 $2$
3. 如果 $1$ 在 $2$ 之中 , 那么 $2$ 可以拆成两个 $1$ , 且不会更劣 , 所以选择的区间不会出现包含关系
4. 那么从左往右一个点如果是 $0$ , 最优解一定是直接考虑下一个点 , 如果不是 $0$ , 那么有两种选择 , 要么选 $1$ 然后到下一个点 , 要么选 $2$ 把下一个点异或当前点的值然后到下一个点
5. 如果一直选 $2$ , 那么停止的唯一条件就是当前点和下一个点的值相等 , 下一个点在异或后变成 $0$
6. 如果记两端为 $l,r$ , 那么有 $a_l\oplus a_{l+1}\oplus \cdots \oplus a_r=0$ , 这可以使用前缀异或和维护

代码

#include 
using namespace std;

std::mt19937 rng(std::random_device{}());
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef const int& cint;
typedef const ll& cll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;

#define ls (loc<<1)
#define rs ((loc<<1)|1)

const int mod1 = 1e9+7;
const int mod2 = 998244353;
const int inf_int = 0x7fffffff;
const int hf_int = 0x3f3f3f3f;
const ll inf_ll = 0x7fffffffffffffff;
const double ept = 1e-9;

int n;
int a[100100];
int ans[100100];

void solve(cint T) {
    cin >> n;
    map<int, int> e;
    for(int i=1; i<=n; i++){ cin >> a[i]; }
    for(int i=1; i<=n; i++) { ans[i] = 0; }
    int sum = 0;
    e[0] = 0;
    for(int i=1; i<=n; i++) {
        sum ^= a[i];
        ans[i] = ans[i-1] + 1;
        if(e.find(sum) != e.end()) {
            ans[i] = min(ans[i], e[sum]+i-1);
        }
        else { e[sum] = ans[i] - i; }
        e[sum] = min(e[sum], ans[i]-i);
    }
    cout << ans[n] << '\n';
}

int main() {
    //freopen("1.in", "r", stdin);
    //cout.flags(ios::fixed); cout.precision(8);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T_=1;
    std::cin >> T_;
    for(int _T=1; _T<=T_; _T++)
        solve(_T);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

E. Fibonacci Strings

思路

实际上最重要的等式是 ${\sum }_{i=1}^n{f}_i=f_{n+2}-1$ , 这告诉我们每次构造时都必须要贪心的选择个数最多的段 .

代码

#include 
using namespace std;

std::mt19937 rng(std::random_device{}());
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef const int& cint;
typedef const ll& cll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;

#define ls (loc<<1)
#define rs ((loc<<1)|1)

const int mod1 = 1e9+7;
const int mod2 = 998244353;
const int inf_int = 0x7fffffff;
const int hf_int = 0x3f3f3f3f;
const ll inf_ll = 0x7fffffffffffffff;
const double ept = 1e-9;

int k;
int c[101];
ll fib[51];

void init() {
    fib[1] = fib[2] = 1;
    for(int i=3; i<=50; i++) { fib[i] = fib[i-1] + fib[i-2]; }
    // cout << fib[50] << endl;
}

void solve(cint T) {
    cin >> k;
    for(int i=1; i<=k; i++) { cin >> c[i]; }
    ll num = 0, sum = 0;
    for(int i=1; i<=k; i++) {
        if(c[i]) {
            ++num;
            sum += c[i];
        }
    }
    int id = 0;
    for(int i=1; i<=48; i++) { if(fib[i+2]-1 == sum) { id = i; break; } }
    if(num > id) { cout << "NO" << '\n'; return; }
    priority_queue<pii> q;
    for(int i=1; i<=k; i++) { if(c[i]) { q.push({c[i], i}); } }
    int lst = 0;
    for(int i=id; i>=1; i--) {
        if(q.empty()) { cout << "NO\n"; return; }
        auto k = q.top();
        q.pop();
        if(k.second == lst) {
            if(q.empty()) { cout << "NO\n"; return; }
            auto r = q.top();
            q.pop();
            q.push(k);
            k = r;
        }
        lst = k.second;
        if(k.first >= fib[i]) {
            k.first -= fib[i];
            if(k.first > 0) { q.push({k.first, k.second}); }
        }
        else { cout << "NO\n"; return; }
    }
    cout << "YES\n";
}

int main() {
    //freopen("1.in", "r", stdin);
    //cout.flags(ios::fixed); cout.precision(8);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T_=1;
    std::cin >> T_;
    init();
    for(int _T=1; _T<=T_; _T++)
        solve(_T);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

F. Tonya and Burenka-179

题意

给定长度为 $n$ 的循环数组 $a$ (下标从 $0$ 开始), 定义 $f(s,t)$ 为 ${\sum }_{i=0}^{n-1}{a}_{(s+i\ast t)\%n}$ , 其中 $0\le s\le n-1$ , $1\le t\le n-1$ , 现在有 $q$ 次修改 , 每次给定 $i$ 和 $x$ , 将 $a_i$ 修改为 $x$ , 在每次修改后输出最大的 $f(s,t)$ .

复杂度 $\Theta (q{\log }^{2}n+n\log n)$

思路

不妨先考虑 $s=0$ 的情况 , 这里只考虑最短的循环节

此时考虑下标数组 $0\%n,t\%n,2t\%n,\cdots ,(n-1)t\%n$ , 令 $r=\gcd (n,t)$ , 如果可以证明前述数组的循环节长度为 $n/r$ . 那么因为 $0\%n,r\%n,2r\%n,\cdots ,(n-1)r\%n$ 的循环节长度显然为 $n/r$ 且 $tx+ny=cr$ 对 $0\le c\le n-1$ 一定有解(裴蜀定理) , 所以其下标之间一定存在一个双射 , 这意味着可以用 $r$ 代替 $t$.

简略证明一下 , 首先因为 $n\mid t(n/r)$ , 所以 $n/r$ 一定是循环节长度的倍数 , 否则令 $s$ 为反例 , 那么使用裴蜀定理可以不断构造出更小的 $s$ , 最后容易得到 $t=n$ , 矛盾 . 其次如果存在更小的循环节长度 , 不妨设为 $c$ , 那么 $n/c>n/r$ 且有 $n\mid t(n/(n/c))$ , 这说明存在比 $r$ 更大的公因数 , 矛盾 .

实际上 , 如果使用群论的相关知识 , 上述证明可以描述为下面的一段话 . 考虑循环群 ${\mathbb{Z}}_n=⟨\bar{1}⟩$ , 那么 $⟨\bar{t}⟩$ 为其子群 , 且为循环群 , 其阶数为 $r=\gcd (n,t)$ . 又循环群每一阶的子群唯一 , 所以 $⟨\bar{t}⟩=⟨\bar{r}⟩$ .

这说明对于 $1\le t\le n-1$ , 我们只需要考虑 $\gcd (n,1),\gcd (n,2),\cdots ,\gcd (n,n-1)$ , 这实际上就是 $n$ 的所有因数的集合 , 所以说循环节长度最多只有 $\sqrt{n}$ 种有意义 , 又因为对于循环节长度 $c$ , 一定有 $0c\%n=0$ 和 $nc\%n=0$ , 再观察式子 , 可以发现最后所有的长度的循环一定都是一个完整的最小循环重复若干遍 , 所以对于初始的 $s$ 只用枚举 $0\sim c-1$ , 而显然其一定重复了 $c$ 遍 . 下面我们来考虑如何修改 . (这里暂时不用考虑复杂度)

我们使用 $val[k][c]$ 表示循环节长度为 $k$ 且 $s=c$ 的答案 , 如果现在要将 $a[i]$ 从 $x$ 改到 $y$ , 那么每一个循环节长度里仅会有一个初始点的答案受到影响 , 其为 $\forall k,val[k][x\%k]$ , 因为这些点才会在加上一些相应的 $k$ 后到达 $x$ , 所以每一次修改的复杂度为循环节长度的集合的大小 , 但是问题出现在 $q\ast \sqrt{n}$ 的复杂度过高 , 我们需要优化复杂度 , 也就是减少有效循环节长度的数量 .

考虑长度为 $2$ 和 $4$ 且从 $0$ 开始枚举的循环节 , 在 $0\sim n$ 这一段里 , $4$ 包含了 $2$ 的一半点 , 而另一半点就是从 $2$ 开始枚举的长度为 $4$ 的循环节 , 显然 , 这两段一定有一个大小关系 , 不妨假设前面的一半点的和大于后面一半点的和 , 那么我们只会选择前面的一半 , 也就是在假设下 , 选择从 $0$ 开始枚举长度为 $4$ 的循环节得到的答案一定大于从 $2$ 开始枚举长度为 $4$ 的循环节 , 又长度为 $2$ 重复两轮 , 长度为 $4$ 重复 $4$ 轮 , 所以自然也大于从 $0$ 开始枚举长度为 $2$ 的循环节得到的答案 . 这说明对于循环节长度 $a$ , $b$ 若有 $a\mid b$ , 那么 $b$ 产生的贡献的最大值一定会大于 $a$ 产生的贡献的最大值 , 这告诉我们如果一个长度的倍数在集合中 , 那么枚举他就没有意义 , 为了简化思路 , 对于长度 $c$ 我们考虑 $n/c$ , 那么上述实际上告诉我们 , 只需要枚举 $n$ 的质因数即可 , 那么循环节长度集合的个数就是 $\log$ 级别 .

我们再用一个 $set$ 用来动态维护修改时的 $val[k][c]$ 的最大值即可 . 此时总复杂度 $\Theta (q{\log }^{2}n)$

此时初始构造的复杂度就是 $\Theta (sum\ast t\ast n/t)=\Theta (sum\ast n)$ , 其中 $sum$ 是循环节长度集合大小 , 所以大致为 $\Theta (n\log n)$ .

(复杂度其实有一点出入 , 但不大)

代码

#include 
using namespace std;

std::mt19937 rng(std::random_device{}());
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef const int& cint;
typedef const ll& cll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;

#define ls (loc<<1)
#define rs ((loc<<1)|1)

const int mod = 1e9+7;
const int inf_int = 0x7fffffff;
const int hf_int = 0x3f3f3f3f;
const ll inf_ll = 0x7fffffffffffffff;
const double ept = 1e-9;

int n, q;
int a[200200];
bool vis[200200];
vector<ll> val[200200];

void init() {
    vis[1] = 1;
    for(int i=2; i<=200000; i++) {
        if(vis[i]) { continue; }
        for(int j=i+i; j<=200000; j+=i) { vis[j] = 1; }
    }
}

bool solve(cint T) {
    cin >> n >> q;
    for(int i=0; i<n; i++) { cin >> a[i]; }
    for(int i=0; i<=n; i++) { val[i].clear(); }
    int tmp = n;
    vector<int> e;
    for(int i=2; i<=sqrt(n); i++) { if(vis[i] == 0 && (tmp % i == 0)) { e.push_back(i); } while(tmp % i == 0) { tmp /= i; } }
    if(tmp > 1) { e.push_back(tmp); }
    multiset<ll> p;
    for(auto &k: e) {
        int t = n/k;
        for(int i=0; i<t; i++) {
            ll sum = 0;
            for(int j=0; j<k; j++) { sum += a[(j*t+i)%n]; }
            sum = sum * t;
            val[k].push_back(sum);
            p.insert(-sum);
        }
    }
    cout << -*p.begin() << '\n';
    ll x, y;
    for(int i=1; i<=q; i++) {
        cin >> x >> y;
        --x;
        for(auto &k: e) {
            int t = n/k;
            ll s = val[k][x%t];
            p.erase(p.find(-s));
            s += (y-a[x])*t;
            val[k][x%t] = s;
            p.insert(-s);
        }
        a[x] = y;
        cout << -*p.begin() << '\n';
    }
    return true;
}

int main() {
    //freopen("1.in", "r", stdin);
    //cout.flags(ios::fixed); cout.precision(8);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T_=1;
    std::cin >> T_;
    init();
    for(int _T=1; _T<=T_; _T++) { if(solve(_T) == 0) { break; } }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82