写在前面
自闭ing...
A.玛雅文字
刚开始打了一个非常zz的代码，具体多zz看代码就知道了:
//zz般的代码
#include <bits/stdc++.h>
using namespace std ;
const long long BASE = 13331 ;
const int MAXS = 3000000 + 5 , MAXT = 3000 + 5 ;
int n , m ;
long long res , ret ;
int ans ;
char s[ MAXS ] , t[ MAXT ] ;
inline long long hsh ( char ch ) {
return ( long long ) ch * BASE ;
}
signed main () {
freopen ( "mayan.in" , "r" , stdin ) ;
freopen ( "mayan.out" , "w" , stdout ) ;
scanf ( "%d%d" , &m , &n ) ;
scanf ( "%s%s" , t + 1 , s + 1 ) ;
int l = 1 , r = m ;
for ( int i = l ; i <= r ; i ++ ) {
res += hsh ( s[ i ] ) ;
ret += hsh ( t[ i ] ) ;
}
if ( res == ret ) ans ++ ;
while ( r <= n ) {
l ++ ; r ++ ;
res -= hsh ( s[ l - 1 ] ) ;
res += hsh ( s[ r ] ) ;
if ( res == ret ) ans ++ ;
// cout << l << " " << r << " " << res << " " << ret << endl ;
}
printf ( "%d
" , ans ) ;
return 0 ;
}
对此代码进行分析，发现(hash)的碰撞率(approx 1)
但是我竟然还有20分...
于是打了一个正差的(hash)(在复杂化的道路上一去不复返...)
#include <bits/stdc++.h>
using namespace std ;
const int MAXS = 3000000 + 5 , MAXT = 3000 + 5 ;
int n , m ;
long long res , ret ;
int ans ;
char s[ MAXS ] , t[ MAXT ] ;
long long base[ 130 ] ;
inline long long hsh ( char ch ) {
return ( long long ) ch * base[ ch ] ;
}
signed main () {
freopen ( "mayan.in" , "r" , stdin ) ;
freopen ( "mayan.out" , "w" , stdout ) ;
scanf ( "%d%d" , &m , &n ) ;
scanf ( "%s%s" , t + 1 , s + 1 ) ;
int l = 1 , r = m ;
base[ 'a' ] = 3001 ;
for ( int i = 1 ; i <= 25 ; i ++ )
base[ i + 'a' ] = base[ i + 'a' - 1 ] * 3001 ;
base[ 'A' ] = 3001 * 28 ;
for ( int i = 1 ; i <= 25 ; i ++ )
base[ i + 'A' ] = base[ i + 'A' - 1 ] * 3001 ;
for ( int i = l ; i <= r ; i ++ ) {
res += hsh ( s[ i ] ) ;
ret += hsh ( t[ i ] ) ;
}
if ( res == ret ) ans ++ ;
while ( r <= n ) {
l ++ ; r ++ ;
res -= hsh ( s[ l - 1 ] ) ;
res += hsh ( s[ r ] ) ;
if ( res == ret ) ans ++ ;
// cout << l << " " << r << " " << res << " " << ret << endl ;
}
printf ( "%d
" , ans ) ;
return 0 ;
}
唉，第一题TMD搞死我了（话说第一题我想那么复杂干嘛）
以后写(hash)还是要悠着点
B.奇怪的字符串
观察可得，所谓的奇怪字符串要么是全都是同一个字符，要么就是两串相同的字符拼接起来的。
eg.aaaaaaa bbb aabbbbb bbba ccccaaaaaaa
那么就比较简单了
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std ;
#define int long long
const int MAXN = 2e5 + 5 , MAXM = 35 ;
int n , res , p[ MAXM ] ;
int tot , len[ MAXN ] , l[ MAXN ] ;
char ch[ MAXN ] ;
vector < pair < int , int > > v[ MAXM ][ MAXM ] ;
signed main () {
scanf ( "%s" , ch + 1 ) ;
n = strlen ( ch + 1 ) ;
for ( int i = 1 ; i <= n ; i ++ ) ch[ i ] -= 'a' ;
tot = 1 ; l[ 1 ] = 1 ;
for ( int i = 2 ; i <= n + 1 ; i ++ ) {
if ( ch[ i ] != ch[ l[ tot ] ] || i > n ) {
len[ tot ] = i - l[ tot ] ;
p[ ch[ l[ tot ] ] ] = max ( p[ ch[ l[ tot ] ] ] , len[ tot ] ) ;
l[ ++ tot ] = i ;
}
}
for ( int i = 0 ; i < 26 ; i ++ ) res += p[ i ] ;
for ( int i = 2 ; i < tot ; i ++ ) v[ ch[ l[ i - 1 ] ] ][ ch[ l[ i ] ] ].push_back ( make_pair ( len[ i - 1 ] , len[ i ] ) ) ;
for ( int i = 0 ; i < 26 ; i ++ )
for ( int j = 0 ; j < 26 ; j ++ ) {
int mx = 0 , tot = v[ i ][ j ].size () ;
if ( !tot ) continue ;
sort ( v[ i ][ j ].begin () , v[ i ][ j ].end () ) ;
for ( int k = tot - 1 ; k >= 0 ; k -- ) {
mx = max ( mx , v[ i ][ j ][ k ].se ) ;
if ( k > 0 ) res += mx * ( v[ i ][ j ][ k ].fi - v[ i ][ j ][ k - 1 ].fi ) ;
else res += mx * v[ i ][ j ][ k ].fi ;
}
}
printf( "%lld
" , res ) ;
return 0 ;
}
C.超级跳棋
对于一个数 (x) ,应该有以下方案
T x T||x T T||T T x (T需要有两个以上)
S T x||S x T||x S T (S,T无大小关系)
x T x||x x T||T x x (x需要有两个以上)
x x x (x需要有3个以上)
#include <bits/stdc++.h>
#define int long long
using namespace std ;
const int MAXN = 100000 + 5 ;
int n , k , tot ;
long long ans ;
int a[ MAXN ] , c[ MAXN ] , w[ MAXN ] ;
inline int read () {
int tot = 0 , f = 1 ; char c = getchar () ;
while ( c < '0' || c > '9' ) { if ( c == '-' ) f = -1 ; c = getchar () ; }
while ( c >= '0' && c <= '9' ) { tot = tot * 10 + c - '0' ; c = getchar () ; }
return tot * f ;
}
signed main () {
n = read () ; k = read () ;
for ( int i = 1 ; i <= n ; i ++ )
a[ i ] = read () ;
sort ( a + 1 , a + 1 + n ) ;
c[ tot = 1 ] = 1 ;
for ( int i = 2 ; i <= n ; i ++ ) {
if ( a[ i ] == a[ i - 1 ] ) c[ tot ] ++ ;
else a[ ++ tot ] = a[ i ] , c[ tot ] = 1 ;
}
for ( int i = 1 ; i <= tot ; i ++ ) {
w[ i ] = lower_bound ( a + 1 , a + i , a[ i ] / k + ( a[ i ] % k != 0 ) ) - a ;
if ( i - w[ i ] >= 2 ) ans += ( i - w[ i ] ) * ( i - w[ i ] - 1 ) / 2 * 6 ;
}
for ( int i = 1 ; i <= tot ; i ++ ) {
if ( c[ i ] < 2 ) continue ;
if ( i - w[ i ] >= 1 ) ans += ( i - w[ i ] ) * 3 ;
int x = upper_bound ( a + i , a + tot + 1 , a[ i ] * k ) - a - 1 ;
x = min ( x , tot ) ;
if ( x - i >= 1 ) ans += ( x - i ) * 3 ;
}
for ( int i = 1 ; i <= n ; i ++ )
if ( c[ i ] >= 3 ) ans ++ ;
printf ( "%lld
" , ans ) ;
return 0 ;
}