赛时写了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('\n') #define I_int int
inline I_int read() { I_int x = , f = ; char c = getchar() ;
while( c < '' || c > '' ) {
if( c == '-' ) f = - ;
c = getchar() ;
}
while( c >= '' && c <= '' ) {
x = (x << ) + (x << ) + c - ;
c = getchar() ;
}
return x * f ;
}
#undef I_int using namespace std ; #define N 100010 char s[ N ] ; int main() {
scanf( "%s" , s + ) ;
int len = strlen( s+ ) ;
if( len == ) puts( s + ) ;
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('\n') #define I_int int
inline I_int read() { I_int x = , f = ; char c = getchar() ;
while( c < '' || c > '' ) {
if( c == '-' ) f = - ;
c = getchar() ;
}
while( c >= '' && c <= '' ) {
x = (x << ) + (x << ) + c - ;
c = getchar() ;
}
return x * f ;
}
#undef I_int using namespace std ; #define N 100010
int a[ ] , k ; int main() {
in2( a[ ] , a[ ] ) ; in1( k ) ;
for( int i = ; i <= k ; i ++ ) {
if( a[ i % ] % ) a[ i % ] -- ;
a[ ( i % ) ^ ] += a[ i % ] / ;
a[ i % ] -= a[ i % ] / ;
}
out( a[ ] ) , putchar(' ') , outn( a[ ] ) ;
}
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('\n') #define I_int int
inline I_int read() { I_int x = , f = ; char c = getchar() ;
while( c < '' || c > '' ) {
if( c == '-' ) f = - ;
c = getchar() ;
}
while( c >= '' && c <= '' ) {
x = (x << ) + (x << ) + c - ;
c = getchar() ;
}
return x * f ;
}
#undef I_int using namespace std ; #define N 100010 int n ;
int b[ N ] ;
int a[ N ] ;
ll ans = ; int main() {
in1( n ) ;
for( int i = ; i <= n ; i ++ ) in1( a[ i ] ) ;
sort( a+ , a+n+ ) ;
int l = , r = n , mid = ( l + r ) >> ;
if( n % ) {
b[ mid ] = a[ r -- ] ;
for( int i = mid - ; i ; i -- ) {
if( ( mid - i ) % ) b[ i ] = a[ l ++ ] , b[ mid + mid - i ] = a[ l ++ ] ;
else b[ i ] = a[ r -- ] , b[ mid + mid - i ] = a[ r -- ] ;
}
ll sum = ;
for( int i = ; i <= n ; i ++ ) sum += abs( b[ i ] - b[ i - ] ) ;
ll t = sum ;
l = , r = n ;
b[ mid ] = a[ l ++ ] ;
for( int i = mid - ; i ; i -- ) {
if( ( mid - i ) % == ) b[ i ] = a[ l ++ ] , b[ mid + mid - i ] = a[ l ++ ] ;
else b[ i ] = a[ r -- ] , b[ mid + mid - i ] = a[ r -- ] ;
}
sum = ;
for( int i = ; i <= n ; i ++ ) sum += abs( b[ i ] - b[ i - ] ) ;
printf( "%lld\n" , max( t , sum ) ) ;
return ;
}
b[ mid ] = a[ r -- ] ;
b[ mid + ] = a[ l ++ ] ;
for( int i = mid - ; i ; i -- ) {
if( ( mid - i ) % ) b[ i ] = a[ l ++ ] , b[ n - i + ] = a[ r -- ] ;
else b[ i ] = a[ r -- ] , b[ n - i + ] = a[ l ++ ] ;
}
ll sum = , t = ;
for( int i = ; i <= n ; i ++ ) {
sum += abs( b[ i ] - b[ i - ] ) ;
}
t = sum ;
l = , r = n ;
b[ mid + ] = a[ r -- ] ;
b[ mid ] = a[ l ++ ] ;
for( int i = mid - ; i ; i -- ) {
if( ( mid - i ) % == ) b[ i ] = a[ l ++ ] , b[ n - i + ] = a[ r -- ] ;
else b[ i ] = a[ r -- ] , b[ n - i + ] = a[ l ++ ] ;
}
sum = ;
for( int i = ; i <= n ; i ++ ) {
sum += abs( b[ i ] - b[ i - ] ) ;
}
printf( "%lld\n" , 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 = ;
for( int i = ; i < k ; i ++ ) {
for( int j = i + ; 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('\n') #define I_int int
inline I_int read() { I_int x = , f = ; char c = getchar() ;
while( c < '' || c > '' ) {
if( c == '-' ) f = - ;
c = getchar() ;
}
while( c >= '' && c <= '' ) {
x = (x << ) + (x << ) + c - ;
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 = - ;
for( int i = ; i < ; i ++ )
if( i * ( i - ) / == n ) { k = i ; break ; }
if( k == - ) { return puts("No"),; }
int x = ;
for( int i = ; i < k ; i ++ ) {
for( int j = i + ; j < k ; j ++ ) {
x ++ ;
s[ i ].push_back( x ) ;
s[ j ].push_back( x ) ;
}
}
puts("Yes"); outn(k);
for( int i = ; i < k ; i ++ ) {
out((int)s[i].size());
int len = s[ i ].size();
for( int j = ; j < len ; j ++ ) {
out_(s[i][j]);
}
putchar('\n');
}
return ;
}
还是太菜，还是要继续努力啊QAQ