Fork me on GitHub

20191104模拟赛题解

为什么老是考原题啊😥

快乐传递政治正确版

找到一个规律,发现对于每一个人$i$,它能使所有和它的编号mod $gcd$相同的数字变的快乐.
所以我们可以按照$gcd$分组,先求出$n,m,k$三个人的$gcd$,然后对于每一个快乐的人,标记一下它所在的分组即$i$ $mod$ $gcd$.最后我们只需要判断一下是不是所有的分组都被标记了即可.

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e6 + 10;
int n , m , k , b , g , t;
long long base;
bool used[M];
int main ( void ) {
freopen ( "happy2.in" , "r", stdin );
freopen ( "happy2.out" ,"w",stdout);
int T;
scanf ( "%d" , &T );
while ( T-- ) {

memset ( used , 0 , sizeof ( used ) );
scanf ( "%d%d%d" , &n , &m, &k);
base = __gcd ( n * 1ll , __gcd ( m * 1ll , k * 1ll ) );
if ( base >= 10 * N ) {
puts ( "No" );
continue;
}
scanf ( "%d" , &b );
for ( int i = 1 ; i <= b ; i++ ) {
int x;
scanf ( "%d" , &x );
used[x % base] = 1;
}

scanf ( "%d" , &g );
for ( int i = 1 ; i <= g ; i++ ) {
int x;
scanf ( "%d" , &x );
used[x % base] = 1;
}

scanf ( "%d" , &t );
for ( int i = 1 ; i <= t ; i++ ) {
int x;
scanf ( "%d" , &x );
used[x % base] = 1;
}
bool flag = 1;
for ( int i = 0 ; i < base ; i++ ) {
if ( !used[i] ) {
flag = 0;
break;
}
}
if ( flag )
puts ( "Yes" );
else
puts ( "No" );
}
return 0;
}

嫌疑人

我们先考虑一个显然错误的贪心:我们对于每个人被统计了多少次直接开桶统计,然后把统计的个数从大到小排序之后可以二分找到每一个需要被计入答案的数量.
貌似一眼发现不了什么错误但是这个真的错了.
我们发现对于一个人$i$,如果它要搞$j,k$的话,那么假设有一个投票,要投票的人是$j,k$,那么$i$这个人就会对这个计数方案贡献$2$的同意数.而这显然与一个人只能对一个方案有$1$的贡献不相符.
所以我们考虑把多算的这一部分从原答案中减去,我们发现对于一个人,它只能对某一组特定的方案有$2$的赞同数,所以我们可以使用$map$套一个$pair$来对多统计的组数的贡献,然后我们遍历所有我们标记了的组合,如果本来它的赞同数$>=p$并且它的赞同数$-$多统计的赞同数小于$p$的话,我们就需要让答案减少$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
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 3e5 + 10;

int n , p;
int cnt[N] , rc[N];
long long xdd;
map < pair < int , int > , int > mp;

signed main ( void ) {
freopen ( "suspect.in" , "r", stdin );
freopen ( "suspect.out" ,"w",stdout);
scanf ( "%lld%lld" , &n , &p );

if ( p == 0 ) {
printf ( "%lld\n" , 1ll * n * ( n - 1 ) / 2 );
return 0;
}

for ( int i = 1 ; i <= n ; i++ ) {
int x , y;
scanf ( "%lld%lld" , &x , &y );
cnt[x]++;
cnt[y]++;
if ( x > y )
swap ( x , y );
rc[x]++;
rc[y]++;
mp[make_pair ( x , y )]++;
}
sort ( cnt + 1 , cnt + 1 + n );

for ( int i = 1 ; i <= n ; i++ ) {
int l = i + 1 , r = n , ans = -1;
while ( l <= r ) {
int mid = ( l + r ) >> 1;
if ( cnt[mid] + cnt[i] >= p ) {
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
if ( ans != -1 )
xdd = xdd + n - ans + 1;
}
for ( map < pair < int , int > , int > :: iterator it = mp.begin () ; it != mp.end () ; it++ )
if ( rc[it -> first.first] + rc[it -> first.second] >= p && rc[it -> first.first] + rc[it -> first.second] - it -> second < p )
xdd--;

printf ( "%lld\n" , xdd );

return 0;
}

Xor

发现在某个区间中出现过偶数次数字的异或和=区间中出现过的数字的异或和异或区间中出现了奇数次数字的异或和.
而某个区间中出现了奇数次数字的异或和显然等于这个区间的异或和(因为出现了偶数次的数字异或起来的值为$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
#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 = 3e5 + 10;

int n , m;
int val[N] , tree[N] , fro[N];
map < int , int > flag;
struct Que {
int l , r;
int id;
} query[N];
int ans[N];

inline bool cmp ( Que x , Que y ) {
return x.r < y.r;
}

inline int lowbit ( int x ) {
return x & -x;
}
inline void add ( int pos , int x ) {
while ( pos <= n ) {
tree[pos] ^= x;
pos += lowbit ( pos );
}
return;
}
inline int check ( int pos ) {
int res = 0;
while ( pos ) {
res ^= tree[pos];
pos -= lowbit ( pos );
}
return res;
}

int main ( void ) {
n = read ();
for ( int i = 1 ; i <= n ; i++ ) {
val[i] = read ();
fro[i] = fro[i - 1] ^ val[i];
}
m = read ();
for ( int i = 1 ; i <= m ; i++ ) {
query[i].l = read () , query[i].r = read ();
query[i].id = i;
}
sort ( query + 1 , query + 1 + m , cmp );
int now = 0;
for ( int i = 1 ; i <= m ; i++ ) {
while ( now < query[i].r ) {
now++;
if ( !flag[val[now]] )
flag[val[now]] = now;
else {
add ( flag[val[now]] , val[now] );
flag[val[now]] = now;
}
add ( now , val[now] );
}
ans[query[i].id] = check ( query[i].r ) ^ check ( query[i].l - 1 ) ^ fro[query[i].r] ^ fro[query[i].l - 1];
}
for ( int i = 1 ; i <= m ; i++ )
printf ( "%d\n" , ans[i] );
return 0;
}

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

本文标题:20191104模拟赛题解

文章作者:KRrrrrrrrr

发布时间:2019年11月05日 - 09:11

最后更新:2019年11月05日 - 10:11

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

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