Team Round #2：2018CCPC吉林站

发表于 更新于 分类于 阅读次数： 评论数：
本文字数： 842 阅读时长 ≈ 3 分钟
本文记录了Daenerys Stormborn of the House Targaryen.的第02场训练

Team Round(Training)系列：每周六12：15-17：15

这一场是在9月14日打的，是2018CCPC吉林站(搬题人：dqy_)
传送门

Name Origin Solved Upsolved A B C D E F G H I J K L M
#2 2018 CCPC吉林站 4/12 2/8 O O !Ø !Ø ● O ● ● O ● ● ●

过了AFBI
总的来说有点可惜。应该多写几题的。

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
 /************************************************
 # @Author:      miniLCT
 # @DateTime:    2019-09-14 12:16:59
 # @Description: You build it.You run it
 ***********************************************/

// odd  奇数
// even 偶数
#include <bits/stdc++.h>

using namespace std;
#define eps 1e-8
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn = 1e6;
const int INF = 1e9;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
ll mod = 1e9+7;
void dabiao(int x){
	int sum = 0;
	for (int i = 1; i <= x;i++){
		sum += (x/i);
	}
	if(sum & 1)cout << x <<"step=====odd"<<endl;
	else cout << x << "step=====even"<<endl; 
}
int main()
{
	/*for(int i = 1; i <=100; i++){
		dabiao(i);
	}*/
	int t;
	cin >> t;
	for(int kase = 1; kase <= t;kase++){
		int n ;
		cin >> n;
		int m = sqrt(1.0*n);
		if(m & 1)printf("Case %d: odd\n", kase);
		else printf("Case %d: even\n", kase);
	}
}

/******************************************************
 stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?), set tle
  * do smth instead of nothing and stay organized
*******************************************************/

F:乱搞就过了

思路：

我们clone复现赛，然后我做完A之后不久发现F题很快被人过了，然后就看了，其实想不懂为什么，想了很久之后突然发现-2，然后和dqy说，他开始说再想想，到了40分钟之后真的忍不住了就交了，突然ac。

别人思路：csdn
转载自https://blog.csdn.net/aiyouyou_/article/details/89790003

代码：

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
 /************************************************
 # @Author:      miniLCT
 # @DateTime:    2019-09-14 12:28:20
 # @Description: You build it.You run it
 ***********************************************/
#include <bits/stdc++.h>

using namespace std;
#define eps 1e-8
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn = 1e6+10;
const int INF = 1e9;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
ll mod = 1e9+7;
int t , n ;
int a[maxn];
int main()
{
	cin >> t;
	for(int kase = 1; kase <= t;kase++){
		cin >> n;
		int ans = 0;
		for(int i = 1; i <= n;i++){
			cin >> a[i];
		}
		for(int i = 1; i <= n;i++){
			if(a[i] > 2)ans ^= (a[i] - 2);
		}
		printf("Case %d: %d\n", kase,ans);
	}

}

/******************************************************
 stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?), set tle
  * do smth instead of nothing and stay organized
*******************************************************/

B题：模拟题

思路：

有个坑点，好像是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
// Author : Wqr_
// Time : 19/09/14
#include<bits/stdc++.h>
#define iofuck std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int T;
    cin >> T;
    cin.get();
    int chour, cmin;
    int uhour;
    int thour;
    int kase = 0;
    while(T--){
        scanf("%d:%d", &chour, &cmin);
        string ap;
        cin >> ap;
        cin.get();
        if(chour == 12 && ap[0] == 'A'){
            chour = 0;
        }
        if(ap[0] == 'P'){
            if(chour != 12){
                chour += 12;
            }
        }
        string a, b;
        cin >> a >> b;
        if(a[0] == 'B'){
            uhour = chour - 8;
        }else if(a[0] == 'W'){
            uhour = chour + 5;
        }else if(a[0] == 'L'){
            uhour = chour;
        }else if(a[0] == 'M'){
            uhour = chour - 3;
        }
        if (b[0] == 'B') {
            thour = uhour + 8;
        } else if (b[0] == 'W') {
            thour = uhour - 5;
        } else if (b[0] == 'L') {
            thour = uhour;
        } else if (b[0] == 'M') {
            thour = uhour + 3;
        }
        /*
        cout << "---" << endl;
        cout << chour << endl;
        cout << uhour << endl;
        cout << thour << endl;
        cout << "---" << endl;
        */
        int tt = thour;
        int time;
        int pmam;
        //
        if(tt >= 24){
            time = 1;
            tt -= 24;
        }else if (tt < 0){
            time = -1;
            tt += 24;
        }else {
            time = 0;
        }

        if(tt >= 12){
            pmam = 1;
            if(tt > 12){
                tt -= 12;
            }
        }else{
            pmam = 0;
        }
        /******************/
        // yes
        cout << "Case " << ++kase << ": ";
        if(time == -1){
            cout << "Yesterday ";
        }else if(time == 0){
            cout << "Today ";
        }else if(time == 1){
            cout << "Tomorrow ";
        }
        //hour
        if(tt == 0){
            cout << 12;
        }else if(tt == 12){
            cout << 12;
        }else{
            cout << tt;
        }
        cout << ":";
        //min
        if(cmin < 10) cout << 0 << cmin << " ";
        else cout << cmin << " ";
        if(pmam) cout << "PM";
        else cout << "AM";
        cout << endl;
    }
    return 0;
}

I题：贪心

思路：

看能不能过最高的， 用大的打小的。

Author：dqy_

代码：

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
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define IN freopen("in.txt", "r", stdin);
#define endl '\n'
#define mp make_pair
#define pb push_back
#define lowb lower_bound
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define mem0(a) memset((a), 0, sizeof(a))
#define mem(a, b) memset((a), (b), sizeof(a))
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+10;

int a[maxn], b[maxn], d[maxn];
pii c[maxn];
map<int, int> msk;

VI vec1, vec2;

int main(){
    //IOS;
    //IN;
    int t; scanf("%d", &t);
    int cnt = 1;
    while(t--){
        int n, m;
        cin>>n>>m;
        for(int i = 0; i < n; i ++){
            scanf("%d", &a[i]);
            d[i] = a[i];
            msk[a[i]]++;
        }
        sort(d, d+n);
        sort(a, a+n);
        for(int i = 0; i < m; i++){
            scanf("%d", &b[i]);
        }
        for(int i = 0; i < m; i++){
            int x;
            scanf("%d", &x);
            if(x == 0)vec1.eb(b[i]);
            else vec2.eb(b[i]);
            c[i] = {b[i], x};
        }
        sort(c, c+m);
        sort(all(vec2));
        bool f = 0;
        for(auto it : vec2){
            int tmp = it;
            bool kk = 0;
            while(1){
                int zz = lower_bound(a, a+n, tmp) - a;
                if(zz == n){
                    f = 1;
                    break;
                }else{
                    if(msk[a[zz]]){
                        msk[a[zz]]--;
                        kk = 1;
                    }else{
                        tmp = a[zz]+1;
                    }
                    if(kk)break;
                }
            }
        }
        sort(a, a+n, greater<ll>());
        int zz = 0;
        ll ans1 = 0, ans2 = 0;
        for(int i = 0; i < m; i++){
            if(c[i].se == 1)continue;
            if(a[zz]<c[i].fi)break;
            else{
                ans1 += a[zz++]-c[i].fi;
            }
        }
        if(!f){
            zz = 0;
            int i;
            for(i = 0; i < m; i++){
                if(c[i].se == 1)continue;
                else{
                    for(int j = zz; j < n; j++){
                        if(a[j] < c[i].fi){
                            f = 1;
                            break;
                        }
                        if(msk[a[j]]){
                            msk[a[j]]--;
                            ans2 += a[j]-c[i].fi;
                            zz = j;
                            break;
                        }
                    }
                    if(f)break;
                }
            }
            if(i == m){
                for(int i = 0; i < n; i++){
                    ans2 += msk[a[i]]*a[i];
                    msk[a[i]] = 0;
                }
            }
        }
        printf("Case %d: %lld\n", cnt++, max(ans1, ans2));
    }
    return 0;
}

总结：

后面时间再想C和D，C题很接近正解了但是代码还是没实现，d题概率dp还没触及，有点可惜把。

八题金，六题银，四题铜 我们还需要努力啊，GKD！

赛后dqy_说：没有数据结构啊！(最近在搞数据结构，)然，，然而H题Lovers就是线段树😱…

就是要把题目都过一遍吧，听说赛中F题不是全场题，我们全靠歪的榜加上瞎猜过的。。要提升硬实力啊。

补题：

C题：码力不足啊小老弟

题意：

给定一个序列k1,k2,k3…kn，每个代表1/(2^ki)要求把这n个数分成两堆，使得每一堆的值都大于1/2

思路：

首先可以肯定，如果能凑成两个1，那么肯定有解，然后我们知道2个x，可以凑成一个(x-1)，

我们凑两个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
 /************************************************
 # @Author:      miniLCT
 # @DateTime:    2019-09-17 20:00:35
 # @Description: You build it.You run it
 ***********************************************/
#include <bits/stdc++.h>

using namespace std;
#define eps 1e-8
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn = 1e6;
const int INF = 1e9;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
ll mod = 1e9+7;
int n , vis[maxn];
struct node{
	int id , val;
}a[maxn];
int cmp(node a, node b){
	return a.val < b.val;
}
int main()
{
	int t ;
	cin >> t;
	for(int kase = 1; kase <= t;kase++){
		printf("Case %d: ", kase);
		cin >> n;
		for(int i = 1; i <= n;i++){
			cin >> a[i].val;
			a[i].id = i;
		}
		memset(vis,0,sizeof(vis));
		sort(a+1 , a+1+n , cmp);
		int flag = 1,pre = 1,cnt2 = 1, cnt1= 1;
		for(int i = 1; i <= n;i++){
			while(cnt1+cnt2 <= n+1-i&&pre < a[i].val){//转化当前这个数字，更新需要的数量
				cnt1 *= 2;
				cnt2 *= 2;
				pre++;
			}
			if(cnt1+cnt2 > n-i+1){ //剩下的数的数量无法满足
				flag = 0;
				break;
			}
			if(cnt1){
				cnt1--;
				vis[a[i].id] = 1;
			}
			else {
				cnt2--;
			}
			if(!cnt1 && !cnt2)break;//两个都满足了
		}
		if(flag==0||cnt1||cnt2)cout << "NO"<<endl;
		else {
			cout << "YES\n";
			for(int i = 1; i <= n;i++)cout<<vis[i];
			cout << endl;
		}
	}

}

/******************************************************
 stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?), set tle
  * do smth instead of nothing and stay organized
*******************************************************/

D题：概率dp GKD啊小xiongdei

题意：

1.起初物品掉落率q=2%;

2.玩家进行一次游戏，有p的概率获胜。

3.如果获胜了，有q的概率掉落一个叫Beta Pack的物品。如果获胜，q+=2%;否则，q+=1.5%。

重复2和3。

求得到一个物品 进行游戏场次的期望。

思路：

倒着推。1.5是小数，扩大两倍。没做过概率，，，好像是全场题。。。

代码：
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
//概率dp
//倒着推   
//因为q最高为100%，所以初始状态为dp[100]，但是因为如果游戏输了的话是p+1.5
//数组下标不能是小数， 整体扩大两倍，dp[200]  根据几何分布期望公式 dp[200]=1/p 
//状态转移方程 ：dp[q] = p*(1-q)dp[min(q+4,400)]+(1-p)dp[min(q+3,200)]+1
//1是当前局，p*(1-q)dp[min(q+4,400)]为游戏获胜但是未中奖的期望，(1-p)dp[min(q+3,200)]为游戏失败时候的期望，
//三者之和为概率为q时候的期望
#include <bits/stdc++.h>
//https://blog.csdn.net/qq_41746268/article/details/96170255
using namespace std;
#define eps 1e-8
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn = 1e6;
const int INF = 1e9;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
int t;
double p;
ll mod = 1e9+7;
int main()
{
	cin >> t;
	for(int kase = 1;kase <= t;kase++){
		cin >> p;
		double dp[300] = {0.0};
		p /= 100; 
		dp[200] = 1.0/p;
		for(int i = 199; i >= 4;i--){
			dp[i] = 1.0 + p*(1.0-1.0*i/200)*dp[min(i+4,200)] + (1.0-p)*dp[min(i+3,200)]; 
		}
		printf("Case %d: %.10f\n",kase, dp[4] );
	}
}
-------------本文结束感谢您的阅读-------------