训练补题-个人2

auto-gen TOC: {:toc}

# 个人排位赛2补题记录

# GukiZ and GukiZiana (Codeforces 551E)

分块的代码写出来了，结果疯狂Wa3。

赛后去Cf看Testcase 3，检查后找到了出错的地方（找不同?）

// 错误代码
for(int j=belong[le]+1; j<belong[ri] - 1; j++) {
    lazy[j] = min(lazy[j] + x, maxv);
}
// 修正后代码
for(int j=belong[le]+1; j<=belong[ri]- 1; j++) {
    lazy[j] = min(lazy[j] + x, maxv);
}

1
2
3
4
5
6
7
8

然后......就过了

查错能力有待提高

# 10-20-30 (UVA 246)

两个要点

输出要求中，"Win"与其他两个状态的格式不同！
当发现了第 $i$ 种特等组合后，要重新从第一种开始判断

AC代码

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

vector<deque<int> > deck;
set<vector<deque<int> > > hsh;

const int pattern[][3] = { {0, 1, -1}, {0, -2, -1}, {-3, -2, -1} };

bool check(int p, int ptr){
    int sum = 0, sz = deck[ptr].size();
    if(sz < 3) return false;
    for(int i=0, pos; i<3; i++){
        pos = pattern[p][i]>=0?pattern[p][i]:sz+pattern[p][i];
        sum += deck[ptr][pos];
    }
    if(sum % 10 == 0){
        for(int i=0, pos; i<3; i++){
            pos = pattern[p][i]>=0?pattern[p][i]:sz+pattern[p][i];
            deck[7].push_back(deck[ptr][pos]);
        }
        for(int i=0; i<3; i++){
            pattern[p][i] >= 0 ? deck[ptr].pop_front() : deck[ptr].pop_back();
        }
        return true;
    }
    return false;
}

void solve(){
    int ans = 7, state = 2, ptr = 0;
    while(!deck[7].empty()){
        if(deck[7].size() == 52){
            state = 0;
            break;
        }
        
        if(hsh.find(deck) != hsh.end()) {
            state = 1;
            break;
        }
        hsh.insert(deck);
        
        while(deck[ptr].size() == 0) ptr = (ptr + 1) % 7;

        ans++;
        deck[ptr].push_back(deck[7].front());
        deck[7].pop_front();

        bool flag = true;
        while(flag){
            flag = false;
            for(int i=0; i<3 && !flag; i++) flag |= check(i, ptr);
        }
        ptr = (ptr + 1) % 7;
    }
    
    if(state == 0) cout << "Win : " << ans << '\n';
    if(state == 1) cout << "Draw: " << ans << '\n';
    if(state == 2) cout << "Loss: " << ans << '\n';
}

signed main(){
    Android;
    while(true){
        hsh.clear();
        deck.resize(8);
        for(int i=0; i<8; i++) deck[i].clear();

        int tmp; cin >> tmp;
        if(tmp == 0) break;
        deck[0].push_back(tmp);
        for(int i=1; i<7; i++){
            cin >> tmp;
            deck[i].push_back(tmp);
        }
        for(int i=0; i<52-7; i++){
            cin >> tmp;
            deck[7].push_back(tmp);
        }
        solve();
    }
}

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
83

# Cutting a Painted Polygon (URAL 1181)

可知题目一定有解

否则必定可以找到连续三个点，他们的颜色互不相同

然后把这三个点连成三角形，变成n-1的问题，重复步骤

要注意一个特例：某个颜色只剩下一个点

当然，也可以用分治+回溯的方法做

上次更新: 2021/02/24, 03:37:30

← 训练补题-个人10 训练补题-个人5→