练习第二阶段

ACM

练习

  1. 注意及时的清空初始的状态，，，
  2. 英文题面好好读题，区域赛教训。。。
  3. 暴力骗分！

filp the tile

枚举搜索，注意初始状态的还原。

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = (1<<16)+10;
int mp[20][20];
int n, m;
int temp[20][20];
int method[20][20];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool check(int x, int y){
    if(x<0||x>=n||y<0||y>=m) return false;
    return true;
}
bool have(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(mp[i][j])return false;
        }
    }
    return true;
}
void print_graph(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++) cout<<mp[i][j]<<" ";
        cout<<endl;
    }
    cout<<"----------------"<<endl;
}
void solve(){
    bool flag = false;
    for(int i=0; i<n; i++) for(int j=0; j<m; j++) temp[i][j] = mp[i][j];
    for(int sta=0; sta<=(1<<m)-1; sta++){
        cls(method, 0);
        for(int a=0; a<n; a++) for(int b=0; b<m; b++) mp[a][b] = temp[a][b];
        for(int j=0; j<m; j++){
            if((sta>>j)&1){
                mp[0][j] ^= 1;
                method[0][j] = 1;
                for(int a= 0; a<4; a++){
                    int nx = dx[a]+0;
                    int ny = dy[a]+j;
                    if(check(nx, ny)){
                        mp[nx][ny] ^= 1;
                    }
                }
            }
        }
        for(int j=1; j<n; j++){
            for(int col=0; col<m; col++){
                int nx = j;
                int ny = col-1;
                {
                    //cout<<"test "<<j<<" "<<col<<endl;
                    nx = j-1, ny=col;
                    if(check(nx, ny) && mp[nx][ny]){
                        method[j][col] = 1;
                        for(int c=0; c<4; c++){
                            nx = j+dx[c], ny = col+dy[c];
                            if(check(nx, ny)) mp[nx][ny] ^=1;
                        }
                        mp[j][col] ^= 1;
                    }
                }
                //print_graph();
            }
        }
        if(have()){
            flag = true;
            break;
        }
    }
    if(flag){
        for(int i=0; i<n; i++){
            for(int j=0; j<m-1; j++) cout<<method[i][j]<<" ";
            cout<<method[i][m-1]<<endl;
        }
    }
    else cout<<"IMPOSSIBLE"<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++) cin>>mp[i][j];
        }
        solve();
    }
    return 0;
}

hdu A计划

到传送点的时候，必须直接的上去或者下来，不能在经过传送点到达其他的地方，我一开始没有想到

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 10+10;
char mp[10][maxn][maxn];
int n, m, t;
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, -1, 1, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
struct Node{
    int num[3];
    int ans = 0;
};
int tx, ty, tz;
bool vis[maxn][maxn][maxn];
bool check(int x, int y, int z){
    if(z<0||z>=2||x<0||x>=n||y<0||y>=m) return false;
    if(mp[z][x][y] == '*') return false;
    if(vis[z][x][y]) return false;
    return true;
}
queue<Node> q;
void bfs(){
    Node temp;
    temp.num[0] = temp.num[1] = temp.num[2] = 0;
    temp.ans = 0;
    cls(vis, 0);
    while(!q.empty()) q.pop();
    q.push(temp);
    while(!q.empty()){
        temp = q.front();
        q.pop();
        int x = temp.num[0], y = temp.num[1], z = temp.num[2];
        //cout<<x<<" "<<y<<" "<<z<<" "<<temp.ans<<endl;
        if(vis[z][x][y]) continue;
        if(temp.num[0] == tx &&temp.num[1] == ty && temp.num[2] == tz){
            if(temp.ans<=t) {
                //cout<<temp.ans<<endl;
                cout<<"YES"<<endl;
                return ;
            }
            else continue;
        }
        vis[z][x][y] = true;
        Node temp1;
        for(int i=0; i<6; i++){
            int nx = dx[i]+x;
            int ny = dy[i]+y;
            int nz = dz[i]+z;
            if(dz[i] && check(nx, ny, nz)&&mp[z][x][y] == '#'&&mp[nz][nx][ny]!='#'){
                temp1.ans = temp.ans;
                temp1.num[0] = nx, temp1.num[1] = ny, temp1.num[2] = nz;
                q.push(temp1);
            }
            else if(dz[i] == 0&&check(nx, ny, nz)&&(mp[z][x][y] !='#')){
                temp1.ans = temp.ans+1;
                temp1.num[0] = nx, temp1.num[1] = ny, temp1.num[2] = nz;
                q.push(temp1);
            }
        }
    }
    cout<<"NO"<<endl;
    return ;
}
int main(){
    ios::sync_with_stdio(false);
    int _;
    cin>>_;
    while(_--){
        cin>>n>>m>>t;
        for(int c=0; c<2; c++) for(int i=0; i<n; i++) for(int j=0; j<m; j++) {
            cin>>mp[c][i][j];
            if(mp[c][i][j] == 'P') tx=i, ty=j, tz=c;
        }
        bfs();
    }
    return 0;
}
/*
1
5 5 14
S*#*.
.#...
.....
****.
...#.
..*.P
#.*..
***..
...*.
*.#*.
*/

dna sequence

如果暴力枚举最多4^40，我们要进行相应的剪枝优化。

瑞士轮（排序）

要是用O(n)的归并排序

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
struct Node{
    int id, score, w;
    bool operator < (const Node &b) const{
        if(score!=b.score) return score>b.score;
        return id<b.id;
    }
}node[maxn<<1], a[maxn<<1], b[maxn<<1];
bool cmp(Node a, Node b){
    if(a.score!=b.score) return a.score>b.score;
    return a.id<b.id;
}
int n, r, q;
void solve(){
    int ai=1, bi=1;
    for(int i=1; i<=2*n; i+=2){
        if(node[i].w>node[i+1].w){
            node[i].score++;
            a[ai++] = node[i];
            b[bi++] = node[i+1];
        }
        else {
            node[i+1].score++;
            a[ai++] = node[i+1];
            b[bi++] = node[i];
        }
    }
    ai=1, bi=1;
    int k=1;
    while(ai<=n&&bi<=n){
        if(cmp(a[ai], b[bi])) node[k++] = a[ai++];
        else node[k++] = b[bi++];
    }
    while(ai<=n) node[k++] = a[ai++];
    while(bi<=n) node[k++] = b[bi++];
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>r>>q){
        for(int i=1; i<=2*n; i++){
            node[i].id = i;
            cin>>node[i].score;
        }
        for(int i=1; i<=2*n; i++) cin>>node[i].w;
        sort(node+1, node+1+2*n);
        for(int i=1; i<=r; i++){
            solve();
        }
        cout<<node[q].id<<endl;
    }
    return 0;
}

sticks

memset(val, 0, sizeof(val)) 怎么比for快？ 是数组越界的锅！

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 65;
int n;
int stick[maxn];
bool vis[maxn];
int totlen;
int num_stick;
int len;
bool dfs(int now, int idx, int tot){
    if(tot == num_stick) return true;
    if(now == len) return dfs(0, 0, tot+1);
    int i;
    int pre = 0;
    for(i=idx; i<n; i++){
        if(vis[i] == false &&stick[i]+now<=len&&stick[i]!=pre){
            vis[i] = true;
            pre = stick[i];
            if(dfs(now+stick[i], i+1, tot)){
                break;
            }
            vis[i] = false;
            if(idx == 0) return false;
        }
    }
    if(i==n) return false;
    else return true;
}
int main(){
    while(cin>>n, n != 0){
        totlen = 0;
        for(int i=0; i<n; i++){
            cin>>stick[i];
            totlen += stick[i];
        }
        sort(stick, stick+n, greater<int>());
        for(len = stick[0]; len<=totlen/2; len++){
            if(totlen%len == 0){
                num_stick = totlen/len;
                //for(int i=0; i<num_stick; i++) vis[i] = false;
                memset(vis, 0, sizeof(vis));
                if(dfs(0, 0, 0)){
                    break;
                }
            }
        }
        if(len>totlen/2) cout<<totlen<<endl;
        else cout<<len<<endl;
    }
    return 0;
}

The buses

有可能有重合的，所以搜的时候下标还是从当前路线搜索。

1
dfs(i, deep+1, remain-route[i].num);//i不是i+1
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
struct Route{
    int start, gap, num;
    bool operator < (const Route &b) const{
        if(num == b.num) return start<b.start;
        return num>b.num;
    }
}route[100000+10];
int cnt;
int vis[120], tim[310];
int n;
bool check(int start, int gap){
    for(int i=start; i<60; i+=gap){
        if(vis[i]<=0) return false;
    }
    return true;
}
int ans = inf;
void dfs(int now, int deep, int remain){
    if(now>=cnt+1) return;
    //cout<<"test "<<route[now].num<<endl;
    assert(now<100000);
    if(remain/route[now].num+deep>=ans) return;
    if(remain == 0){
        ans = min(ans, deep);
        return;
    }
    //cout<<now<<" "<<deep<<" "<<remain<<" "<<ans<<endl;
    for(int i=now; i<=cnt; i++){
        //cout<<i<<endl;
        if(check(route[i].start, route[i].gap)&&remain>=route[i].num){
            for(int j=route[i].start; j<60; j+=route[i].gap) vis[j]--;
            dfs(i, deep+1, remain-route[i].num);
            for(int j=route[i].start; j<60; j+=route[i].gap) vis[j]++;
        }
    }
    //cout<<"ge"<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n){
        cnt = 0;
        ans = inf;
        cls(vis, 0);
        for(int i=1; i<=n; i++) cin>>tim[i], vis[tim[i]]++;
        for(int i=0; i<30; i++){
            for(int j=1+i; i+j<60; j++){
                if(check(i, j)){
                    int temp=0;
                    for(int k=i; k<60; k+=j){
                        temp++;
                    }
                    cnt++;
                    route[cnt].start = i, route[cnt].gap = j;
                    route[cnt].num = temp;
                }
            }
        }
        //cout<<cnt<<endl;
        sort(route+1, route+1+cnt);
        dfs(1, 0, n);
        cout<<ans<<endl;
    }
    return 0;
}

未解决的问题

本文标题:练习第二阶段

文章作者:Babydragon

发布时间:2019-07-08, 10:38:21

最后更新:2019-07-11, 22:56:49

原始链接:http://baolintian.github.io/2019/07/08/练习第二阶段/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. filp the tile
  2. 2. hdu A计划
  3. 3. dna sequence
  4. 4. 瑞士轮（排序）
  5. 5. sticks
  6. 6. The buses
  7. 7. 未解决的问题
{{ live2d() }}