AtCoder Tenka1 Programmer Beginner Contest 解题报告

赛时写了ABC，D实在没啥思路，然后C又难调...然后就从写完AB时的32名掉到了150+名

T_T

码力不够，思维不行，我还是AFO吧

比赛链接

A - Measure

sb模拟，奇数串倒着输出偶数串正着输出

#include <bits/stdc++.h>

#define ll long long
#define inf 0x3f3f3f3f 
#define il inline 

#define in1(a) a=read()
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
#define out(a) printf( "%d" , a ) 
#define outn(a) out(a),putchar('
')

#define I_int int 
inline I_int read() {
    
    I_int x = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) {
        if( c == '-' ) f = -1 ;
        c = getchar() ;
    }
    while( c >= '0' && c <= '9' ) {
        x = (x << 1) + (x << 3) + c - 48 ;
        c = getchar() ;
    }
    return x * f ;
}
#undef I_int

using namespace std ;

#define N 100010

char s[ N ] ;

int main() {
    scanf( "%s" , s + 1 ) ;
    int len = strlen( s+1 ) ;
    if( len == 2 ) puts( s + 1 ) ;
    else {
        for( int i = len ; i ; i -- ) putchar( s[ i ] ) ;
    }
}

B - Exchange

还是模拟...按着题意的要求来就好，奇数一种情况偶数一种情况

然后一边$+frac{1}{2}$，一边$-frac{1}{2}$就好

#include <bits/stdc++.h>

#define ll long long
#define inf 0x3f3f3f3f 
#define il inline 

#define in1(a) a=read()
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
#define out(a) printf( "%d" , a ) 
#define outn(a) out(a),putchar('
')

#define I_int int 
inline I_int read() {
    
    I_int x = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) {
        if( c == '-' ) f = -1 ;
        c = getchar() ;
    }
    while( c >= '0' && c <= '9' ) {
        x = (x << 1) + (x << 3) + c - 48 ;
        c = getchar() ;
    }
    return x * f ;
}
#undef I_int

using namespace std ;

#define N 100010
int a[ 3 ] , k ;

int main() {
    in2( a[ 1 ] , a[ 0 ] ) ; in1( k ) ;
    for( int i = 1 ; i <= k ; i ++ ) {
        if( a[ i % 2 ] % 2 ) a[ i % 2 ] -- ;
        a[ ( i % 2 ) ^ 1 ] += a[ i % 2 ] / 2 ;
        a[ i % 2 ] -= a[ i % 2 ] / 2 ;
    }
    out( a[ 1 ] ) , putchar(' ') , outn( a[ 0 ] ) ; 
}

C - Align

很恶心的分类讨论

首先要知道一个结论，最中间的数一定是最大或者最小的，然后我们可以在旁边依次填入最大/次大/最小/次小的数

对串的奇偶分开讨论（取mid的不同）

然后对于中间填最大还是填最小也要分开讨论

然后综合几种情况取个最优就行

写的有点长，实际上应该不用这么多代码的QAQ

#include <bits/stdc++.h>

#define ll long long
#define inf 0x3f3f3f3f 
#define il inline 

#define in1(a) a=read()
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
#define out(a) printf( "%d" , a ) 
#define outn(a) out(a),putchar('
')

#define I_int int 
inline I_int read() {
    
    I_int x = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) {
        if( c == '-' ) f = -1 ;
        c = getchar() ;
    }
    while( c >= '0' && c <= '9' ) {
        x = (x << 1) + (x << 3) + c - 48 ;
        c = getchar() ;
    }
    return x * f ;
}
#undef I_int

using namespace std ;

#define N 100010

int n ;
int b[ N ] ;
int a[ N ] ;
ll ans = 0 ;

int main() {
    in1( n ) ;
    for( int i = 1 ; i <= n ; i ++ ) in1( a[ i ] ) ;
    sort( a+1 , a+n+1 ) ;
    int l = 1 , r = n , mid = ( l + r ) >> 1 ; 
    if( n % 2 ) {
        b[ mid ] = a[ r -- ] ;
        for( int i = mid - 1 ; i ; i -- ) {
            if( ( mid - i ) % 2 ) b[ i ] = a[ l ++ ] , b[ mid + mid - i ] = a[ l ++ ] ;
            else b[ i ] = a[ r -- ] , b[ mid + mid - i ] = a[ r -- ] ;
        }
        ll sum = 0 ;
        for( int i = 2 ; i <= n ; i ++ ) sum += abs( b[ i ] - b[ i - 1 ] ) ;
        ll t = sum ;
        l = 1  , r = n ;
        b[ mid ] = a[ l ++ ] ;
        for( int i = mid - 1 ; i ; i -- ) {
            if( ( mid - i ) % 2 == 0 ) b[ i ] = a[ l ++ ] , b[ mid + mid - i ] = a[ l ++ ] ;
            else b[ i ] = a[ r -- ] , b[ mid + mid - i ] = a[ r -- ] ;
        }
        sum = 0 ;
        for( int i = 2 ; i <= n ; i ++ ) sum += abs( b[ i ] - b[ i - 1 ] ) ;
        printf( "%lld
" , max( t , sum ) ) ;
        return 0 ;
    }
    b[ mid ] = a[ r -- ] ;
    b[ mid + 1 ] = a[ l ++ ] ;
    for( int i = mid - 1 ; i ; i -- ) {
        if( ( mid - i ) % 2 ) b[ i ] = a[ l ++ ] , b[ n - i + 1 ] = a[ r -- ] ;
        else b[ i ] = a[ r -- ] , b[ n - i + 1 ] = a[ l ++ ] ;
    }
    ll sum = 0 , t = 0 ;
    for( int i = 2 ; i <= n ; i ++ ) {
        sum += abs( b[ i ] - b[ i - 1 ] ) ;
    }
    t = sum ;
    l = 1 , r = n ;
    b[ mid + 1 ] = a[ r -- ] ;
    b[ mid ] = a[ l ++ ] ;
    for( int i = mid - 1 ; i ; i -- ) {
        if( ( mid - i ) % 2 == 0 ) b[ i ] = a[ l ++ ] , b[ n - i + 1 ] = a[ r -- ] ;
        else b[ i ] = a[ r -- ] , b[ n - i + 1 ] = a[ l ++ ] ;
    }
    sum = 0 ;
    for( int i = 2 ; i <= n ; i ++ ) {
        sum += abs( b[ i ] - b[ i - 1 ] ) ;
    }
    printf( "%lld
" , max( sum , t ) ) ; 
}

D - Crossing

写这题之前一定要先读懂题意

我比赛时一直读错题意，到结束时脑子里想的还是错误的题意....然后就炸了

令k为所选子集的数量。

任何两个子集的交集大小为1，并且为1,2，...，N中的任何一个元素也使用了两次

对于选出来的子集的限制就是这样的

我们不妨把这些子集抽象成点，交集抽象成边，于是$1-n$这些元素就是边的种类

那么不难看出整个图有$frac{k(k-1)}{2}$条边，并且边的数目要等于n

于是可以枚举出来这个k先，qzz大佬好像推了一个式子$O(1)$求出了这个k，不过我数学比较菜就直接枚举了T_T

然后如果这个k枚举不出来就说明无解（一个比较玄学的地方，我从1枚举到n来判会WA掉第一个点，其他都没问题，然后从1枚举到500就没问题，不知道是怎么回事）

然后来连边

因为每个元素要沟通两个子集

所以类似于完全图那样连边就好

int x = 0 ;
for( int i = 0 ; i < k ; i ++ ) {
    for( int j = i + 1 ; j < k ; j ++ ) {
        x ++ ;
        s[ i ].push_back( x ) ;
        s[ j ].push_back( x ) ;
    }
}

然后就没了

所以说这题的主要难度在于读懂题意T_T

#include <bits/stdc++.h>

#define ll long long
#define inf 0x3f3f3f3f 
#define il inline 

#define in1(a) a=read()
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
#define out(a) printf( "%d" , a ) 
#define out_(a) printf( " %d" , a )
#define outn(a) out(a),putchar('
')

#define I_int int 
inline I_int read() {

    I_int x = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) {
        if( c == '-' ) f = -1 ;
        c = getchar() ;
    }
    while( c >= '0' && c <= '9' ) {
        x = (x << 1) + (x << 3) + c - 48 ;
        c = getchar() ;
    }
    return x * f ;
}
#undef I_int

using namespace std ;

#define N 100010

int n , k ;

vector<int>s[N]; 

int main() {
    in1( n ) ;
    k = -1 ;
    for( int i = 1 ; i < 500 ; i ++ ) 
        if( i * ( i - 1 ) / 2 == n ) { k = i ; break ; }
    if( k == -1 ) { return puts("No"),0; }
    int x = 0 ;
    for( int i = 0 ; i < k ; i ++ ) {
        for( int j = i + 1 ; j < k ; j ++ ) {
            x ++ ;
            s[ i ].push_back( x ) ;
            s[ j ].push_back( x ) ;
        }
    }
    puts("Yes"); outn(k);
    for( int i = 0 ; i < k ; i ++ ) {
        out((int)s[i].size());
        int len = s[ i ].size();
        for( int j = 0 ; j < len ; j ++ ) {
            out_(s[i][j]);
        }
        putchar('
');
    }
    return 0 ;
}

还是太菜，还是要继续努力啊QAQ