trainning

ACM

trainning

非常可乐

要定义一个三元组记录状态来map，注意排序是如何定义的！这样会影响map的hash的判断。

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#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;
int s, n, m;
struct Node{
    int num[3];
    int ans;
    bool operator < (const Node &b) const {
        if(num[0]!=b.num[0]) return num[0]<b.num[0];
        else if(num[1]!=b.num[1]) return num[1]<b.num[1];
        return num[2]<b.num[2];
    }
};
map<Node, bool> mp;
bool check(Node x){
    int hal = s/2;
    if(x.num[0] == hal && x.num[1] == hal) return true;
    if(x.num[0] == hal && x.num[2] == hal) return true;
    if(x.num[1] == hal && x.num[2] == hal) return true;
    return false;
}
void bfs(){
    Node temp;
    temp.num[0] = s, temp.num[1] = 0, temp.num[2] = 0;
    temp.ans = 0;
    queue<Node> q;
    q.push(temp);
    Node t;
    bool has = false;
    while(!q.empty()){
        temp = q.front();
        //cout<<temp.num[0]<<" "<<temp.num[1]<<" "<<temp.num[2]<<endl;
        q.pop();
        if(mp[temp]) continue;
        mp[temp] = true;
        if(check(temp)){
            cout<<temp.ans<<endl;
            has = true;
            break;
        }
        if(temp.num[0]){
            t = temp;
            if(temp.num[0]+temp.num[1]<=n){
                t.num[1] += t.num[0];
                t.num[0] = 0;
                if(!mp[t])
                    t.ans++, q.push(t);
            }
            else {
                int res = n-t.num[1];
                t.num[0] -= res;
                t.num[1] = n;
                if(mp[t] == false)
                    t.ans++, q.push(t);
            }
            t = temp;
            if(temp.num[0]+temp.num[2]<=m){
                t.num[2] += t.num[0];
                t.num[0] = 0;
                if(!mp[t])
                    t.ans++, q.push(t);
            }
            else {
                int res = m-t.num[2];
                t.num[0] -= res;
                t.num[2] = m;
                if(!mp[t])
                    t.ans++, q.push(t);
            }
        }
        if(temp.num[1]){
            t = temp;
            if(temp.num[1]+temp.num[0]<=s){
                t.num[0] += t.num[1];
                t.num[1] = 0;
                if(!mp[t])
                    t.ans++, q.push(t);
            }
            else {
                int res = s-t.num[0];
                t.num[1] -= res;
                t.num[0] = s;
                if(!mp[t])
                    t.ans++, q.push(t);
            }
            t = temp;
            if(temp.num[1]+temp.num[2]<=m){
                t.num[2] += t.num[1];
                t.num[1] = 0;
                if(!mp[t])
                    t.ans++, q.push(t);
            }
            else {
                int res = m-t.num[2];
                t.num[1] -= res;
                t.num[2] = m;
                if(!mp[t])
                    t.ans++, q.push(t);
            }
        }
        if(temp.num[2]){
            t = temp;
            if(temp.num[0]+temp.num[2]<=s){
                t.num[0] += t.num[2];
                t.num[2] = 0;
                if(!mp[t])
                    t.ans++, q.push(t);
            }
            else {
                int res = s-t.num[0];
                t.num[2] -= res;
                t.num[0] = s;
                if(!mp[t])
                    t.ans++, q.push(t);
            }
            t = temp;
            if(temp.num[1]+temp.num[2]<=n){
                t.num[1] += t.num[2];
                t.num[2] = 0;
                if(!mp[t])
                    t.ans++, q.push(t);
            }
            else {
                int res = n-t.num[1];
                t.num[2] -= res;
                t.num[1] = n;
                if(!mp[t])
                    t.ans++, q.push(t);
            }
        }
    }
    if(!has) cout<<"NO"<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>s>>n>>m){
        if(s+m+n == 0) break;
        if(s%2) {
            cout<<"NO"<<endl;
            continue;
        }
        mp.clear();
        bfs();
    }
    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
#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 = 2000+10;
int n;
int a[maxn], b[maxn];
int solve(int a[], int b[]){
    int ans = 0;
    int l1=1, r1=n, l2=1, r2 = n;
    while(l1<=r1&&l2<=r2){
        if(b[r2]> a[r1]) r2--, r1--, ans+=3;
        else if(b[l2]>a[l1]) l1++, l2++, ans+=3;
        else if(b[l2] == a[r1]) r1--, l2++, ans += 2;
        else r1--,l2++,ans++;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n){
        if(n == 0) break;
        for(int i=1; i<=n; i++) cin>>a[i];
        for(int i=1; i<=n; i++) cin>>b[i];
        sort(a+1, a+1+n);
        sort(b+1, b+1+n);
        cout<<solve(a, b)<<" "<<4*n-solve(b, a)<<endl;
    }
    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
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
117
118
119
120
//#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 = 2000+10;
//int num[maxn];
//int n;
//priority_queue<double, vector<double>, greater<double> > pq;
//
//int main(){
//    ios::sync_with_stdio(false);
//    int _;
//    cin>>_;
//    while(_--){
//        cin>>n;
//        for(int i=1; i<=n; i++){
//            cin>>num[i];
//        }
//        sort(num+1, num+1+n);
//        int ans = 0;
//        if(n == 1){
//            cout<<num[1]<<endl;
//        }
//        else if(n == 2){
//            cout<<max(num[1], num[2])<<endl;
//        }
//        else if(n == 3){
//            cout<<num[1]+num[2]+num[3]<<endl;
//        }
//        else{
//            ans = 0;
//            int i;
//            for(i=3; i<=n&&i+1<=n; i+=2){
//                ans += (num[1]+num[2]);
//                ans += num[i+1];
//                ans += num[2];
//            }
//            if(i == n){
//                ans += num[n];
//
//            }
//            if(i == n+1){
//                ans += num[2];
//            }
//            int ans1 = 0;
//            for(int i=2; i<=n; i++){
//                ans1+=num[i];
//                if(i!=n)ans1 += num[1];
//            }
//            cout<<min(ans, ans1)<<endl;
//        }
//
//
//    }
//
//    return 0;
//}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int A[1005];
int n,tim;
int f(int m)
{
    if(m == 0) return 0;
    if(m==1) return A[1];
	if(m==2)
	{
		return A[2];
	}
	if(m==3)
	{
		return A[1]+A[2]+A[3];
	}
	int sum=0;
	for(int i=2;i<=m;i++)
	{
		sum += A[i];
	}
	return min(sum+A[1]*(m-2),A[1]+A[2]*2+A[m]+f(m-2));
}
int main()
{
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&A[i]);
		}
		sort(A+1,A+n+1);
		tim=f(n);
		printf("%d\n",tim);
		memset(A,0,sizeof(A));
		tim=0;
	}
}

未解决的问题

本文标题:trainning

文章作者:Babydragon

发布时间:2019-07-17, 10:46:23

最后更新:2019-07-25, 18:47:48

原始链接:http://baolintian.github.io/2019/07/17/trainning/

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

文章目录
  1. 1. 非常可乐
  2. 2. 拼点游戏
  3. 3. 商人过河问题
  4. 4. 未解决的问题
{{ live2d() }}