持续六天的新生赛终于落下了帷幕，打了8道题，第21名，对于两年没有碰过oi的我来说已经是一个不错的成绩了，如果运气好的话还能水到一等奖，怎么说都血赚。
但不得不说的是，我这次的状态比两年前打CSPS要好太多了，如果以我现在的心理素质和之前的知识水平去打，那肯定是不同的结果了。
这次比赛原本想用Amentiraz这个昵称去打，但思来想去还是用了最开始的dsfly昵称去打，一来这个名称短（够装B），二来这个名称是我最开始打oi时的昵称，意味着一个新的开始吧。
说是六天，实际上就打了前三天，主要是还有本职的学习工作，第二是因为小说太好看了（笑）。还是把除了J题以外的所有题都摸了一遍，可以说除了J题我做不出来，其余的花时间都能做出来，放了H题和K题，H题是因为纯模拟暴力，太恶心了，不想写，K题是让你直接输出时间复杂度，搞了几下没出来，又不想去看资料，于是就放了。（留着时间看番不香吗）
T1位运算
题意：输入a，b，输出a&b,a|b,a^b的二进制表示
签到题，特判值为0的情况，没啥说的
代码：
#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周年的题目。
一眼看不出来，先打表枚举找规律。大胆猜想最佳情况是把每一张劵平摊开，尽可能的覆盖到每一次买套餐，小心求证列几个数学公式就出来了，这题不难。关键是你要眼尖的看出如果不买饭那么就不花钱。
#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给出等级，输出图标
签到题，简单的一批，直接上代码
#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多名，后面排名基本上是只升不降，说明大部分人开始卡住了。
#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的轻音梦碎了）
代码：
#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)
代码：
#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啊，那么最终的赢家只由字符串的大小决定
#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
#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循环的时间复杂度就是最内层之积，对于递归就是递归的次数*每次递归的时间复杂度。同样的，有题解再做吧。