首页 代码 OI

持续六天的新生赛终于落下了帷幕，打了 8 道题，第 21 名，对于两年没有碰过 oi 的我来说已经是一个不错的成绩了，如果运气好的话还能水到一等奖，怎么说都血赚。
但不得不说的是，我这次的状态比两年前打 CSPS 要好太多了，如果以我现在的心理素质和之前的知识水平去打，那肯定是不同的结果了。
这次比赛原本想用 Amentiraz 这个昵称去打，但思来想去还是用了最开始的 dsfly 昵称去打，一来这个名称短（够装 B），二来这个名称是我最开始打 oi 时的昵称，意味着一个新的开始吧。
说是六天，实际上就打了前三天，主要是还有本职的学习工作，第二是因为小说太好看了（笑）。还是把除了 J 题以外的所有题都摸了一遍，可以说除了 J 题我做不出来，其余的花时间都能做出来，放了 H 题和 K 题，H 题是因为纯模拟暴力，太恶心了，不想写，K 题是让你直接输出时间复杂度，搞了几下没出来，又不想去看资料，于是就放了。（留着时间看番不香吗）

# T1 位运算

题意：输入 a，b，输出 a&b,a|b,a^b 的二进制表示
签到题，特判值为 0 的情况，没啥说的
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std ;

void deal ( int x ) {
    if ( x == 0 ) { cout << "0" << endl ; return ; }
    int a[10000] , len = 1 ;
    while ( x ) {
        a[len++] = x & 1 ; x >>= 1 ;
    }
    for ( int i = len - 1 ; i >= 1 ; i -- ) cout << a[i] ;
    cout << endl ; return ;
}

int main ( ) {
    int a , b ; scanf ( "%d%d" , & a , & b ) ;
    int ans1 = a & b , ans2 = a | b , ans3 = a ^ b ;
    deal ( ans1 ) ; deal ( ans2 ) ; deal ( ans3 ) ;
    return 0 ;
}

# T21931

题面：

歌颂我们伟大的母校 90 周年的题目。
一眼看不出来，先打表枚举找规律。大胆猜想最佳情况是把每一张劵平摊开，尽可能的覆盖到每一次买套餐，小心求证列几个数学公式就出来了，这题不难。关键是你要眼尖的看出如果不买饭那么就不花钱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>

using namespace std ;

int main ( ) {
    int T ; scanf ( "%d" , & T ) ;
    while ( T -- ) {
        int n , m ; scanf ( "%d%d" , & n , & m ) ;
        int a[1000] , tot = 0 ;
        for ( int i = 1 ; i <= n ; i ++ ) scanf ( "%d" , & a[i] ) , tot += a[i] ;
        if ( m > n ) {
            cout << tot * 2 * ( m - n ) + tot * n - tot << endl ;
        }
        else if ( m == 0 ) cout << "0" << endl ;
        else cout << m * tot - tot << endl ;
    }
    return 0 ;
}

# T3 等级展示

题意：
类比于 qq 的等级，对应星星、月亮、太阳、皇冠有 *,(,0,W 给出等级，输出图标
签到题，简单的一批，直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>

using namespace std ; 

int main ( ) {
    int n ; scanf ( "%d" , & n ) ; 
    for ( int i = 1 ; i <= n / 64 ; i ++ ) cout << "W" ; n %= 64 ; 
    for ( int i = 1 ; i <= n / 16 ; i ++ ) cout << "O" ; n %= 16 ; 
    for ( int i = 1 ; i <= n / 4 ; i ++ ) cout << "(" ; n %= 4 ; 
    for ( int i = 1 ; i <= n ; i ++ ) cout << "*" ; 
    return 0 ; 
}

# T4 边权之和

题意：n 个点的无向完全图，对于每个点有点权 ai，对于两个点 i，j 的边权为 | ai-aj|，统计边权之和对于 998244353 取模值
考虑把绝对值去掉，先把数组给排序，计算它们的和，如何整体计算即可，也不难。
至此，新生赛所有的送分题以及送完了，后面的题或多或少都有些难度，这四道题基本上是所有接触过 c 的人都能写出来的，只是快慢罢了。
我新生赛来迟了 30min，我写到这道题时排位 30 多名，后面排名基本上是只升不降，说明大部分人开始卡住了。

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std ; 
const long long mod = 998244353 ;
long long a[1000006] ;

bool cmp ( int x , int y ) { return x > y ; }  

int main ( ) {
    int n ; long long ans = 0 , tot = 0 ; scanf ( "%d" , & n ) ;
    for ( int i = 1 ; i <= n ; i ++ ) {
        scanf ( "%lld" , & a[i] ) ;
        tot += a[i] ; 
    }
    sort ( a + 1 , a + 1 + n , cmp ) ; 
    for ( int i = 1 ; i <= n ; i ++ ) {
        tot -= a[i] ; 
        ans += ( ( long long ) ( n - i ) ) * a[i] - tot ;
        ans %= mod ; 
    }
    cout << ans ; 
    return 0 ; 
}

# T5tsy 的轻音梦

（没想到在这都能见到轻音厨，但可惜的是这个轻音厨太坑了）
题面：

请大家先看看那位交了 48 次都没过的大佬：

怎么说呢，从第一天开始我就仰望大佬的英姿，虽然最后大佬跟我 A 的题是一个数，但就凭这道题我就不得不佩服他。我一度怀疑他在整活，但看到他在比赛终都没有 A 掉这题，不由得对他产生崇高的敬意。
我开始也被绕进去了，很明显，我们可以联想到幻方，幻方似乎是斜着放，中间是最中间的数，然后呈现一定规律依次放入数，但是我们怎么类比推理都无法得出正确的解法，特别是输出 - 1 给我了很大的迷惑，是不是要考虑奇数次项的奇偶关系？是不是对称放？等等，然而这些都是放屁。想出来正解后我觉得自己是个傻逼。
正解：对于奇数次项考虑对角线为分隔除了正中间的一定为偶其余的依次按从大到小的顺序从对角线依次填入，保证左边是偶右边是奇就行。
对于偶数次项直接依次填入即可
（ls 的轻音梦碎了）
代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std ; 

int a[1005][1005] ; 

int main ( ) {
	int n ; scanf ( "%d" , & n ) ; 
	if ( n % 2 == 0 ) {
		for ( int i = 1 ; i <= n * n ; i ++ ) {
			cout << i << " " ; 
			if ( i % n == 0 ) cout << endl ; 
		}
	}
	else if ( n == 1 ) cout << "1" ; 
	else {
		for ( int i = 1 ; i <= n / 2 ; i ++ ) {
			a[i][i] = i * 2 ; 
			a[i][i+1] = i * 2 + 1 ; 	
		}
		a[1][3] = 1 ; 
		a[n/2+1][n/2] = n + 1 ; 
		for ( int i = 1 ; i <= n / 2 + 1 ; i ++ ) {
			int x = n / 2 + i , y = n / 2 + i ; 
			a[x][y] = n + 1 + i * 2 - 1 ; 
			a[x+1][y] = n + 1 + i * 2 ;	
		}
		int cur1 = n + 1 + ( n / 2 + 1 ) * 2 + 1 ;
		int cur2 = cur1 - 1 ;  
		for ( int i = 1 ; i <= n ; i ++ ) {
			for ( int j = 1 ; j <= n ; j ++ ) {
				if ( ! a[i][j] ) {
					if ( i > j ) a[i][j] = cur2 , cur2 += 2 ; 
					if ( j > i ) a[i][j] = cur1 , cur1 += 2 ; 	
				}
				cout << a[i][j] << " " ; 
			}
			cout << endl ; 
		}
	}
	return 0 ; 
}

# T6 奇怪的排序

题意：

这题是很有意思的一道题，考察算法线段树和逆序对，只能说挺难想的吧，难度估计有提高组 D2T1 的难度。
我们发现这个神奇的算法是把每个最大的数抬到第 i 个位置上并对前 i 个数排序，第 i+1 个数按照大小顺序交换到自己的位置上，交换的次数为这个数不重复的逆序对。
本身分析到这里我以为套个逆序对就完了，结果发现是不重复的，然后我就弄了一个小暴力，把这些重复的数强制给删掉，结果时间复杂度为 O (n^2*logn) 比他原来的还大，emmm。
对于常见的求逆序对的方法归并和树状数组我都不是很熟悉，于是我就用最无脑的线段树去做，依次判断这个数是否读入过然后决定是否加入到逆序对的计算，最后加起来就行。时间复杂度为 O (nlogn)
代码：

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>

using namespace std ;
typedef long long LL ;
const int maxn = 200005 ;
struct L {
    int val , add ;
} t[maxn<<2] ;
int n , m ; LL sum = 0 ;
struct M {
    int val , id ;
} a[maxn] ;
int vis[maxn] , arank[maxn] ;

bool cmp ( M x , M y ) {
    if ( x.val == y.val ) return x.id < y.id ;
    return x.val < y.val ;
}

void spread ( int p , int l , int r ) {
    if ( t[p].add ) {
        int mid = ( l + r ) >> 1 ;
        t[p<<1].val = ( t[p<<1].val + t[p].add * ( mid - l + 1 ) ) , t[p<<1].add += t[p].add ;
        t[p<<1|1].val = ( t[p<<1|1].val + t[p].add * ( r - mid ) ) , t[p<<1|1].add += t[p].add ;
        t[p].add = 0 ;
    }
}

void change ( int p , int l , int r , int x , int y , int z ) {
   if ( x <= l && r <= y ) { t[p].val += z * ( r - l + 1 ) ; t[p].add += z ; return ; }
   int mid = ( l + r ) >> 1 ; spread ( p , l , r ) ;
   if ( x <= mid ) change ( p << 1 , l , mid , x , y , z ) ;
   if ( y > mid ) change ( p << 1 | 1 , mid + 1 , r , x , y , z ) ;
   t[p].val = t[p<<1].val + t[p<<1|1].val ;
}

int ask ( int p , int l , int r , int x , int y ) {
    if ( x <= l && r <= y ) { return t[p].val ; }
    int mid = ( l + r ) >> 1 ; spread ( p , l , r ) ; int ans = 0 ;
    if ( x <= mid ) ans = ans + ask ( p << 1 , l , mid , x , y ) ;
    if ( y > mid ) ans = ans + ask ( p << 1 | 1 , mid + 1 , r , x , y ) ;
    return ans ;
}
int main ( ) {
    scanf ( "%d" , & n ) ; int maxn = 0 , site = 0 ;
    for ( int i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d" , & a[i].val ) ;
        if ( a[i].val > maxn ) maxn = a[i].val , site = i ;
    }
    for ( int i = 1 ; i <= site ; i ++ ) {
        if ( a[i].val > a[1].val ) {
            swap ( a[i].val , a[1].val ) ; sum += 1LL ;
        }
    }
    for ( int i = 1 ; i <= n ; i ++ ) a[i].id = i ;
    sort ( a + 1 , a + 1 + n , cmp ) ;
    int cur = 2 ;
    for ( int i = 1 ; i <= n ; i ++ ) {
        if ( a[i].val == a[i-1].val ) cur -- ;
        arank[a[i].id] = cur ++ ;
    }
    for ( int i = 1 ; i <= n ; i ++ ) {
        sum += ( LL ) ( ask ( 1 , 1 , n , arank[i] , arank[i] ) ) ;
        if ( vis[arank[i]] ) continue ;
        vis[arank[i]] ++ ;
        change ( 1 , 1 , n , 1 , arank[i] - 1 , 1 ) ;
    }
    cout << sum ;
    return 0 ;
}

# T7 更高更妙的字符游戏

题面：

对于我来说，博弈论分为两种，一种是简单的，一种是做不出来的。
我在比赛中惊喜的发现居然有超过 5 个人做出来了这道题，我稍加思索，然后大胆假设，也没小心求证，直接交了然后就 A 了，www。
考虑两种必死的情况，也就是之差一个的和不差的，直接判断就行。对于其它情况，我们从上帝视角来看，如果是我发现下一步我可能会输，我们直接把那个字符删了就行，但是万一删了还是必死呢。我们假设有 abcabc 这种情况，我们肯定不可能删 b，删了就死，但我们可以删最边上的 a 和 c 啊，那么最终的赢家只由字符串的大小决定

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std ; 

int main ( ) {
    int T ; scanf ( "%d" , & T ) ; 
    int flag = 2 ; 
    while ( T -- ) {
        flag = 2 ; 
        int n ; scanf ( "%d" , & n ) ; 
        char a[1000006] ; a[n+1] = 0 ; 
        scanf ( "%s" , a + 1 ) ; 
        for ( int i = 1 ; i <= n - 1 ; i ++ ) {
            if ( a[i] == a[i+1] ) flag = 0 ;
            if ( a[i] == a[i+2] && i + 2 <= n ) flag = min ( flag , 1 ) ; 
        }
        if ( flag == 0 ) cout << "pllj" << endl ; 
        else if ( flag == 1 ) cout << "freesin" << endl ; 
        else {
            flag = n % 2 ; 
            if ( flag == 0 ) cout << "pllj" << endl ;
            else if ( flag == 1 ) cout << "freesin" << endl ; 
        }
    }
    return 0 ; 
}

# T8 内存占用计算


纯模拟，利用高精的思想去比较，乘法就先判断位数够不够如果正好就逐位比较，想了思路感觉很恶心没写代码，如果说错了还请谅解。

# T9tsy 的排序

题面：

三年 oi 一场空，不开 long long 见祖宗

每个数只出现一次，我们可以计算它们的逆序对，然后就可以算出它们的正序对等等数据，所以我们只需枚举中间两位，答案就是对于每个逆序对，求两个数左边比他们小的和右边比它们大的数的积。
但这个算法的复杂度还是 O (n^2)，我们把每个数从大到小丢入线段树中，把标号大于它本身的数都加上它的正序对的个数，强制强制把时间复杂度压缩到 O (nlogn)，再一次性乘起来就行。
注意一定要开 longlong

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std ; 
typedef long long LL ; 
const int maxn = 300005 ; 
const int mod = 35198030 ; 
struct L {
    LL add , val ;
} t[maxn<<2] ; 
int a[maxn] ;
struct M {
    int val , id ;
} f[maxn] ; 
LL g[maxn] ;

void spread ( int p , int l , int r ) {
    if ( t[p].add ) {
        int mid = ( l + r ) >> 1 ; 
        t[p<<1].val = ( t[p<<1].val + t[p].add * ( mid - l + 1 ) ) % mod , t[p<<1].add += t[p].add ; t[p<<1].add %= mod ;
        t[p<<1|1].val = ( t[p<<1|1].val + t[p].add * ( r - mid ) ) % mod , t[p<<1|1].add += t[p].add ; t[p<<1|1].add %= mod ;
        t[p].add = 0 ; 
    }
}

void change ( int p , int l , int r , int x , int y , LL z ) {
    if ( x <= l && r <= y ) { t[p].val += z * ( r - l + 1 ) ; t[p].add += z ; t[p].val %= mod , t[p].add %= mod ; return ; }
   int mid = ( l + r ) >> 1 ; spread ( p , l , r ) ; 
   if ( x <= mid ) change ( p << 1 , l , mid , x , y , z ) ; 
   if ( y > mid ) change ( p << 1 | 1 , mid + 1 , r , x , y , z ) ; 
   t[p].val = ( t[p<<1].val + t[p<<1|1].val ) % mod ;
}

LL ask ( int p , int l , int r , int x , int y ) { 
    if ( x <= l && r <= y ) { return t[p].val % mod ; } 
    int mid = ( l + r ) >> 1 ; spread ( p , l , r ) ; LL ans = 0 ; 
    if ( x <= mid ) ans = ( ans + ask ( p << 1 , l , mid , x , y ) ) % mod ;
    if ( y > mid ) ans = ( ans + ask ( p << 1 | 1 , mid + 1 , r , x , y ) ) % mod ;
    return ans ; 
}

int main ( ) {
    int n ; scanf ( "%d" , & n ) ; 
    for ( int i = 1 ; i <= n ; i ++ ) scanf ( "%d" , & a[i] ) ; 
    for ( int i = 1 ; i <= n ; i ++ ) {
        f[a[i]].val = ask ( 1 , 1 , n , a[i] , a[i] ) ; f[a[i]].id = i ; 
        change ( 1 , 1 , n , a[i] , n , 1 ) ; 
    }
    for ( int i = 0 ; i <= ( n << 2 ) ; i ++ ) t[i].add = t[i].val = 0 ; 
    for ( int i = n ; i >= 1 ; i -- ) {
        int ind = f[i].id ; 
        g[i] = ( ask ( 1 , 1 , n , ind , ind ) ) % mod ; 
        change ( 1 , 1 , n , ind , n , f[i].val ) ; 
    }
    LL ans = 0 ; 
    for ( int i = 1 ; i <= n ; i ++ ) {
        LL num = ( ( n - a[i] ) - ( i - f[a[i]].val - 1 ) ) % mod ;
        ans = ( ans + ( num * g[a[i]] ) ) % mod ; 
    }
    cout << ans ; 
    return 0 ; 
}

# T10 璀璨星空

题意：

没去做，也没有想，全场也只有六个做出来了，后面如果它们发题解再补吧。（还得补高数欠下的）

# T11 复杂度理论初步

题意：




提交了几次没对就没提交了。有几个结论还是可以记下来：对于 for 循环的时间复杂度就是最内层之积，对于递归就是递归的次数 * 每次递归的时间复杂度。同样的，有题解再做吧。