Manthan, Codefest 19 题解

Manthan, Codefest 19

A XORinacci

显然循环节是3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 200006
int n , m , t;
int A[MAXN];
int main() {
int T;cin >> T;
while( T-- ) {
cin >> n >> m >> t;
if( t % 3 == 0 ) cout << n << endl;
else if( t % 3 == 1 ) cout << m << endl;
else cout << (n ^ m) << endl;
}

}

B Uniqueness

又FST了。。。。。

明明显然的单log为了追求速度写了个双log成功fst

实际上是可以二分+check的,开头离散化一下就好了。

其实$n^2log$很好想,只是懒得改了2333

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
#pragma GCC optimize(3)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
#define MAXN 200006
int n , m , t;
int A[MAXN];
int a[MAXN] , M[MAXN];
bool chk( int len ) {
for( int i = 1 ; i <= n - len + 1 ; ++ i ) {
int flg = 0;
memset( M , 0 , sizeof M );
for( int j = 1 ; j <= n ; ++ j ) {
if( j >= i && j <= i + len - 1 ) continue;
if( M[a[j]] ) {flg = 1;break;}
M[a[j]] = 1;
}
if( !flg ) return true;
}
return false;
}
int main() {
cin >> n;
for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&A[i]) , a[i] = A[i];
sort( A + 1 , A + 1 + n );
int sz = unique( A + 1 , A + 1 + n ) - A - 1;
for( int i = 1 ; i <= n ; ++ i ) a[i] = lower_bound( A + 1 , A + 1 + sz , a[i] ) - A;
int l = 0 , r = n;
while( l <= r ) {
int mid = l + r >> 1;
if( chk( mid ) ) r = mid - 1;
else l = mid + 1;
}
cout << l << endl;
}

C Magic Grid

先构造$4 \times 4$矩阵

然后直接把这个矩阵+16 , +32 … 复制$\frac{n}{4} \times \frac{n}{4}$遍就好了

因为每个小矩阵都是0,所以肯定大矩阵也是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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
#define MAXN 1006
int n , data[MAXN][MAXN] , M[6][6];
signed main() {
cin >> n;
int x = 15, tot = 0;
int now = 0;
for (int i = 1; i <= 4; ++i)
for (int j = 1; j <= 4; ++j)
M[i][j] = x - now, now++;
n /= 4;
int cur = 0;
for( int i = 0 ; i < n ; ++ i )
for( int j = 0 ; j < n ; ++ j ) {
for( int k = 1 ; k <= 4 ; ++ k )
for( int kk = 1 ; kk <= 4 ; ++ kk )
data[i*4+k][j*4+kk] = M[k][kk] + cur * 16;
++ cur;
}
for( int i = 1 ; i <= n * 4 ; ++ i ) {
for (int j = 1; j <= n * 4; ++j)
printf("%lld ", data[i][j]);
puts("");
}
}

D Restore Permutation

树状数组+二分

显然最后一个位置可以决定最后一位是多少,然后就变成了个几乎一样的问题,从后往前枚举然后二分一下就好了。

然而题解做法是找到1的位置,然后给后面的位置+1,用了个线段树,虽然是单log优秀一些但是。。不好写啊2333

毕竟cf 2e5显然是随便跑的了

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
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
#define MAXN 200006
#define int long long
int n;

int T[MAXN];
void add( int x , int c ) {
while( x <= n ) T[x] += c , x += x & -x;
}
int que( int x ) {
int ret = 0;
while( x > 0 ) ret += T[x] , x -= x & -x;
return ret;
}
int S[MAXN];
int ans[MAXN];
signed main() {
cin >> n;
for( int i = 1 ; i <= n ; ++ i ) scanf("%lld",&S[i]);
for( int i = 1 ; i <= n ; ++ i ) add( i , i );
for( int i = n ; i >= 1 ; -- i ) {
int l = 0 , r = n;
while( l <= r ) {
int mid = l + r >> 1;
if( que( mid ) > S[i] ) r = mid - 1;
else l = mid + 1;
}
add( l , -l );
ans[i] = l;

}
for( int i = 1 ; i <= n ; ++ i ) printf("%lld ",ans[i]);
}

E Let Them Slide

首先枚举位置 1n

然后我们对每个数组维护一个 LR 表示这个数组在当前位置上可以滑到的区间

显然每个位置的移动次数和是只有$\sum 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
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;
int n, w;
#define MAXN 1000006
typedef long long ll;
int read( ) {
char ch = ' '; int res = 0;
while( ch < '0' || ch > '9' ) ch = getchar();
while( ch <= '9' && ch >= '0' ) { res *= 10 , res += ch - '0' , ch = getchar(); }
return res;
}

ll T[MAXN << 2];
void mdfy(int rt,int l,int r,int L,int R,int valx) {
if(L <= l && r <= R) { T[rt] += valx; return ; }
int m = (l + r) >> 1;
if(m >= L) mdfy( rt << 1 , l , m , L , R , valx );
if(m <= R - 1) mdfy( rt << 1 | 1 , m + 1 , r , L , R , valx);
}
void work(int rt,int l,int r) {
if (l == r) { printf("%lld ", T[rt]); return; }
T[rt << 1] += T[rt] , T[rt << 1 | 1] += T[rt];
int mid = (l + r) >> 1;
work(rt << 1, l, mid) , work(rt << 1 | 1, mid + 1, r);
}

struct node {
ll val;
int pos;
node( ) { val = pos = 0; }
}A[1000500];

bool cmp( node a , node b ) {
return a.val > b.val;
}

set<int> st;
int main() {
n = read() , w = read();
for (int i = 1 , l; i <= n; ++i) {
st.clear();
l = read();
for (int j = 1; j <= l; ++j) A[j].pos = j, scanf("%lld", &A[j].val);
int que = l , len = w - l + 1;
sort(A + 1, A + 1 + l , cmp);
for (int j = 1; j <= l; ++j) {
int l = A[j].pos, r = A[j].pos + len - 1;
auto it = st.lower_bound(A[j].pos), it1 = it;
if (A[j].val < 0) r = min(r, que) , l = max(l, w - que + 1);
if (it != st.end()) r = min(r, (*(it)) - 1);
if (it1 != st.begin()) l = max(l, (*(--it1)) + len);
if (l <= r) mdfy(1, 1, w, l, r, A[j].val);
st.insert(A[j].pos);
}
}
work(1, 1, w);
}

F Bits And Pieces

这个题很有意思

我们考虑维护一个数据结构(其实就是暴力),支持插入,查询 某个数字 作为 子集 的数 可不可以被当前集合内部的数通过 操作得到

由于只需要查询是否可以被与得到,我们知道,如果一个数字$a$是两个集合内的数字的子集,那么它显然可以通过与得到一个数使得$a$是它的子集。

那么考虑对一个数 用dfs 的方法来枚举子集。如果这个数的某个子集已经出现了两次,就不用继续枚举这个数字的子集了,因为它的所有子集必定已经被以前枚举过两次了。

所以总复杂度是$2 v$的!

那么放到这个题,从后往前插入,然后对每个数字考虑它来或,先把当前决定从与集合中拿出的数字置0,或的时候可以从高位到低位看看这位是否有1,如果没有就找找当前值把这位变1能不能通过两个数字与得到,如果可以就把当前值这一位变成1。

具体实现可以看代码,很nb的一个思路。。

(然而我根本不知道啥是题解说的sosdp)

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN 2097156

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

int cnt[MAXN];
void insert( int x , int y ) {
if( cnt[x | y] >= 2 ) return;
if( x == 0 ) { ++ cnt[y]; return; }
insert( x & x - 1 , y | ( x & -x ) ) ,
insert( x & x - 1 , y );
}
int n , ans = 0;
int A[MAXN];
int main() {
cin >> n;
for( int i = 1 ; i <= n ; ++ i ) A[i] = read();
for( int i = n , cur ; i >= 1 ; -- i ) {
if( i <= n - 2 ) {
cur = 0;
for( int j = 21 ; j >= 0 ; -- j ) if( ( ~ A[i] >> j & 1 ) && cnt[ cur | ( 1 << j ) ] == 2 )
cur |= ( 1 << j );
ans = max( ans , A[i] | cur );
}
insert( A[i] , 0 );
}
cout << ans << endl;
}

G Polygons

首先,我们拿的图形完全可以拥有同一个顶点(感性理解)

考虑拿了 k 边形,那么肯定会拿 k 的约数边形状,毕竟点的个数不增加嘛~

考虑我们当前想要拿 x 边形,在此之前我们显然已经把 x 的约数边形拿完了(不然为啥不拿约数边形呢?),此时点的个数的增加量明显是$\phi(x)$,因为可以把每个点看成是$1/x , 2/x , 3/x …$,其中不互质的在约数时候已经拿过了呢。

明显,二边形和一边形是不存在的,

  • 一边形 明显,直接答案+1就好了
  • 二边形 当我们选择了一个偶数边形,就意味着我们选择了二边形。也就是说,除非只选正三角形,都是会把二边形选上的。只选择正三角形的情况只有一种,只需要特判$k = 1$即可。

综上所述,当$k = 1$可以直接输出 3 , 其他时候对$\phi$排序,然后从小到大拿$k + 2$个就好了。

由于一个显然的结论,$\phi(d) \leq \phi( x )$其中$d$是$x$的约数,我们一定会在选择$x$边形前选择完所有的$x$约数边形。

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 1000006
#define int long long
int n , k;

int p[MAXN] , cnt , phi[MAXN];
void init( ) {
phi[1] = 1;
for( int i = 2 ; i < MAXN ; ++ i ) {
if( !p[i] ) p[++cnt] = i , phi[i] = i - 1;
for( int j = 1 ; j <= cnt && p[j] * i < MAXN ; ++ j ) {
p[p[j] * i] = 1;
if( i % p[j] == 0 ) { phi[ p[j] * i ] = phi[i] * ( p[j] ); break; }
phi[p[j] * i] = phi[i] * ( p[j] - 1 );
}
}
}

signed main() {
init();
cin >> n >> k;
if( k == 1 ) return puts( "3" ) , 0;
sort( phi + 1 , phi + 1 + n );
int res = 0;
for( int i = 1 ; i <= k + 2 ; ++ i ) res += phi[i];
cout << res << endl;
}

H Red Blue Tree

它没有鸽

文章作者: yijan
文章链接: https://yijan.co/2019/09/12/old76/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog