Fork me on GitHub

20191107模拟赛题解

德州扑克真好玩.jpg

德州扑克

思路

模拟有啥思路其实可以考虑把所有的手牌的类型开一个桶存起来,然后再从大顺到单牌挨个判断牌型,同牌型比较大小的时候可以考虑把贡献大的乘以一个比较大的数,然后直接比较分数即可.

代码

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include <bits/stdc++.h>

using namespace std;

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

const int N = 1e5 + 10;

int n;
struct Player {
int id;
int point;
string name;
char card[12];
int num[6];
int buck[14];
} player[N];

inline void FindCard () {
for ( int i = 1 ; i <= n ; i++ )
for ( int j = 1 ; j <= 5 ; j++ )
printf ( "%d%c" , player[i].num[j] , j == 5 ? '\n' : ' ' );
return;
}

inline void DefHandCard ( int now ) {
int len = strlen ( player[now].card + 1 );
int cnt = 0;
for ( int i = 1 ; i <= len ; i++ ) {
if ( player[now].card[i] == '0' )
continue;
if ( player[now].card[i] == '1' && player[now].card[i + 1] == '0' )
player[now].num[++cnt] = 10;
else if ( player[now].card[i] == 'A' )
player[now].num[++cnt] = 1;
else if ( player[now].card[i] >= '2' && player[now].card[i] <= '9' )
player[now].num[++cnt] = player[now].card[i] - '0';
else if ( player[now].card[i] == 'J' )
player[now].num[++cnt] = 11;
else if ( player[now].card[i] == 'Q' )
player[now].num[++cnt] = 12;
else if ( player[now].card[i] == 'K' )
player[now].num[++cnt] = 13;
}
return;
}
inline void PreKind ( int now ) {
for ( int i = 1 ; i <= 5 ; i++ )
player[now].buck[player[now].num[i]]++;
return;
}

#define NowPlayer player[now]
inline int FindStraight ( int now ) {
int flag = 0;
for ( int i = 1 ; i <= 9 ; i++ )
if ( NowPlayer.buck[i] && NowPlayer.buck[i + 1] && NowPlayer.buck[i + 2] && NowPlayer.buck[i + 3] && NowPlayer.buck[i + 4] ) {
flag = i + i + 1 + i + 2 + i + 3 + i + 4;
break;
}
if ( flag )
return flag;
else return false;
}
inline int FindFour ( int now ) {
int flag = 0;
Player tmp = NowPlayer;
for ( int i = 1 ; i <= 13 ; i++ )
if ( tmp.buck[i] == 4 ) {
tmp.buck[i] = 0;
flag = i;
break;
}
if ( !flag )
return 0;
flag *= 10000;
for ( int i = 1 ; i <= 13 ; i++ )
if ( tmp.buck[i] ) {
flag += i;
break;
}
return flag;
}
inline int FindHouse ( int now ) {
int flag = 0;
Player tmp = NowPlayer;
for ( int i = 1 ; i <= 13 ; i++ )
if ( tmp.buck[i] == 3 ) {
tmp.buck[i] = 0;
flag = i;
break;
}
if ( !flag )
return 0;
int ff = 0;
for ( int i = 1 ; i <= 13 ; i++ )
if ( tmp.buck[i] == 2 ) {
tmp.buck[i] = 0;
ff = i;
break;
}
if ( !ff )
return 0;
return flag * 10000 + ff;
}
inline int FindThree ( int now ) {
int flag = 0;
Player tmp = NowPlayer;
for ( int i = 1 ; i <= 13 ; i++ )
if ( tmp.buck[i] == 3 ) {
tmp.buck[i] = 0;
flag = i;
break;
}
if ( !flag )
return 0;
flag *= 10000;
for ( int i = 1 ; i <= 13 ; i++ )
if ( tmp.buck[i] )
flag += i;
return flag;
}
inline int FindTwo ( int now ) {
int flag[3] , num = 0;
Player tmp = NowPlayer;
for ( int i = 1 ; i <= 13 ; i++ )
if ( tmp.buck[i] == 2 ) {
tmp.buck[i] = 0;
flag[++num] = i;
}
if ( num != 2 )
return 0;
int ans = max ( flag[1] , flag[2] ) * 50000 + min ( flag[1] , flag[2] ) * 200;
int tdp = 0;
for ( int i = 1 ; i <= 13 ; i++ )
if ( tmp.buck[i] ) {
tmp.buck[i] = 0;
tdp = i;
break;
}
return ans + tdp;
}
inline int FindPair ( int now ) {
int flag = 0;
Player tmp = NowPlayer;
for ( int i = 1 ; i <= 13 ; i++ )
if ( tmp.buck[i] == 2 ) {
flag = i;
break;
}
if ( !flag )
return 0;
flag *= 10000;
for ( int i = 1 ; i <= 13 ; i++ )
if ( tmp.buck[i] ) {
tmp.buck[i] = 0;
flag += i;
}
return flag;
}
inline int FindOne ( int now ) {
int flag = 0;
for ( int i = 1 ; i <= 13 ; i++ )
while ( NowPlayer.buck[i] ) {
NowPlayer.buck[i]--;
flag += i;
}
return flag;
}

inline bool cmp ( Player x , Player y ) {
if ( x.id != y.id )
return x.id > y.id;
if ( x.point != y.point )
return x.point > y.point;
return x.name < y.name;
}

int main ( void ) {
freopen ( "dezhou.in" , "r" , stdin );
freopen ( "dezhou.out" , "w" , stdout );
n = read ();
for ( int i = 1 ; i <= n ; i++ ) {
cin >> player[i].name;
scanf ( "%s" , player[i].card + 1 );
DefHandCard ( i );
}

for ( int i = 1 ; i <= n ; i++ )
PreKind ( i );

for ( int i = 1 ; i <= n ; i++ ) {
if ( player[i].buck[10] && player[i].buck[11] && player[i].buck[12] && player[i].buck[13] && player[i].buck[1] )
player[i].id = 8;
else if ( FindStraight ( i ) )
player[i].point = FindStraight ( i ) , player[i].id = 7;
else if ( FindFour ( i ) )
player[i].point = FindFour ( i ) , player[i].id = 6;
else if ( FindHouse ( i ) )
player[i].point = FindHouse ( i ) , player[i].id = 5;
else if ( FindThree ( i ) )
player[i].point = FindThree ( i ) , player[i].id = 4;
else if ( FindTwo ( i ) )
player[i].point = FindTwo ( i ) , player[i].id = 3;
else if ( FindPair ( i ) )
player[i].point = FindPair ( i ) , player[i].id = 2;
else
player[i].point = FindOne ( i ) , player[i].id = 1;
}
sort ( player + 1 , player + 1 + n , cmp );
for ( int i = 1 ; i <= n ; i++ )
cout << player[i].name << endl;;
return 0;
}

三元组

思路

首先考虑$O(n^2)$怎么做:我们枚举一下每个三元组的中间值,对于每个$i$,我们考虑所有的$j$小于$i$中$val_j$大于$val_i$的个数和$val_j$小于$val_i$的个数.然后对于所有的$j>i$也考虑一下.
发现只要$val_k$大于$val_j$,$val_j$大于$val_i$那么$val_k$一定大于$val_i$.所以我们可以用$O(n^2)$的复杂度来统计出对于每个$i$中前边/后边的大于/小于它的个数.这样可以得到$50$分.
然后我们想一下怎么优化这个过程.我们注意到倒数第二档部分分,它的权值非常的小.所以我们考虑怎么在权值上进行操作.然后对于所有的情况,我们离散化即可.
我们发现,如果我们把权值看成一个序列,那么我们在某个$val_i$,查询大于它的数或者小于它的数,就相当于这个权值序列某段区间的和.然后每次扫过去时在这段区间中$val_i$加一.
这个操作需要我们动态的单点修改区间求和.显然可以树状数组(或者其他什么数据结构).
而因为我们这个树状数组是权值树状数组,所以还需要离散化一下即可通过该题.

代码

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
#include <bits/stdc++.h>
#define int long long

using namespace std;

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

const int HA = 1e9 + 7;
const int N = 200005;

int n;
int high[N] , tree[N];
struct Lsh {
int val;
int pos;
} lsh[N];

inline bool cmp ( Lsh x , Lsh y ) {
return x.val < y.val;
}

inline void Pre () {
int cnt = 0;
lsh[0].val = -1;
for ( int i = 1 ; i <= n ; i++ ) {
if ( lsh[i].val != lsh[i - 1].val )
cnt++;
high[lsh[i].pos] = cnt;
}
return;
}

inline int lowbit ( int x ) {
return x & -x;
}
inline void add ( int x , int pos ) {
while ( pos <= n ) {
tree[pos] += x;
pos += lowbit ( pos );
}
return;
}
inline int query ( int pos ) {
int res = 0;
while ( pos ) {
res += tree[pos];
pos -= lowbit ( pos );
}
return res;
}
int fromin[N] , fromax[N] , behmin[N] , behmax[N];

signed main ( void ) {
freopen ( "triple.in" , "r" , stdin );
freopen ( "triple.out" , "w" , stdout );
n = read ();
for ( int i = 1 ; i <= n ; i++ ) {
lsh[i].val = read ();
lsh[i].pos = i;
}
sort ( lsh + 1 , lsh + 1 + n , cmp );
Pre ();
for ( int i = 1 ; i <= n ; i++ ) {
fromin[i] = query ( high[i] - 1 );
fromax[i] = query ( n ) - query ( high[i] );
add ( 1 , high[i] );
}
memset ( tree , 0 , sizeof ( tree ) );
for ( int i = n ; i >= 1 ; i-- ) {
behmin[i] = query ( high[i] - 1 );
behmax[i] = query ( n ) - query ( high[i] );
add ( 1 , high[i] );
}
int ans = 0;
for ( int i = 1 ; i <= n ; i++ )
ans = ( ans + ( behmin[i] * fromax[i] ) % HA + ( behmax[i] * fromin[i] ) % HA ) % HA;
printf ( "%lld\n" , ans );
// for ( int i = 1 ; i <= n ; i++ )
// printf ( "%d %d %d %d\n" , fromin[i] , fromax[i] , behmin[i] , behmax[i] );
return 0;
}

多边形

思路

听说是在环上DP,真的不会x

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:20191107模拟赛题解

文章作者:KRrrrrrrrr

发布时间:2019年11月08日 - 08:11

最后更新:2019年11月09日 - 08:11

原始链接:http://krrrr.xyz/2019/11/08/20191107模拟赛题解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。