A：Keyboard
按照题目的意思模拟即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std ;
typedef long long LL ;
#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define For( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , n
#define mid ( ( l + r ) >> 1 )
#define rt o , l , r
const int MAXN = 200 ;
char s[31] = "qwertyuiopasdfghjkl;zxcvbnm,./" ;
char c[5] ;
char buf[MAXN] ;
void solve () {
scanf ( "%s" , buf ) ;
if ( c[0] == 'R' ) {
for ( int i = 0 ; buf[i] ; ++ i ) {
rep ( j , 0 , 30 ) {
if ( buf[i] == s[j] ) printf ( "%c" , s[j - 1] ) ;
}
}
} else {
for ( int i = 0 ; buf[i] ; ++ i ) {
rep ( j , 0 , 30 ) {
if ( buf[i] == s[j] ) printf ( "%c" , s[j + 1] ) ;
}
}
}
printf ( "\n" ) ;
}
int main () {
while ( ~scanf ( "%s" , c ) ) solve () ;
return 0 ;
}
B：Worms
二分查找的应用。返回大于等于该数的最小值的下标。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std ;
typedef long long LL ;
#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define For( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , n
#define mid ( ( l + r ) >> 1 )
#define rt o , l , r
const int MAXN = 100005 ;
int a[MAXN] ;
int n , m ;
int search ( int x ) {
int l = 1 , r = n ;
while ( l < r ) {
int m = mid ;
if ( a[m] >= x ) r = m ;
else l = m + 1 ;
}
return l ;
}
void solve () {
int x ;
a[0] = 0 ;
For ( i , 1 , n ) scanf ( "%d" , &a[i] ) , a[i] += a[i - 1] ;
scanf ( "%d" , &m ) ;
while ( m -- ) {
scanf ( "%d" , &x ) ;
printf ( "%d\n" , search ( x ) ) ;
}
}
int main () {
while ( ~scanf ( "%d" , &n ) ) solve () ;
return 0 ;
}
题目大意：每个点有一个初始坐标以及一个中心轴坐标，该点可绕中心轴逆时针旋转90度，每旋转90度算一步移动。现在给你四个点，问最少需要多少步可以得到一个由这四个点旋转后的坐标（可以不旋转）构成的正方形。
首先我们知道每个点最多走三步，多了就回到原来的状态了。那么我们处理出每个点不走，走一步，走两步，走三步后的坐标，然后4*4*4*4判断是否有解，有解取步数最少。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std ;
typedef long long LL ;
#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define For( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , n
#define mid ( ( l + r ) >> 1 )
#define rt o , l , r
const int MAXN = 100005 ;
const int INF = 0x3f3f3f3f ;
struct Node {
int x , y ;
void input () {
scanf ( "%d%d" , &x , &y ) ;
}
void show () {
printf ( "%d %d\n" , x , y ) ;
}
} p[4][4] , home[4] ;
LL d[6] ;
LL dist ( const Node& a , const Node& b ) {
LL x = a.x - b.x ;
LL y = a.y - b.y ;
return x * x + y * y ;
}
void solve () {
int ans = INF ;
int flag = 0 ;
rep ( i , 0 , 4 ) {
p[i][0].input () ;
home[i].input () ;
p[i][3].x = home[i].x - home[i].y + p[i][0].y ;
p[i][3].y = home[i].y + home[i].x - p[i][0].x ;
p[i][2].x = home[i].x + home[i].x - p[i][0].x ;
p[i][2].y = home[i].y + home[i].y - p[i][0].y ;
p[i][1].x = home[i].x + home[i].x - p[i][3].x ;
p[i][1].y = home[i].y + home[i].y - p[i][3].y ;
}
//rep ( i , 0 , 4 ) p[2][i].show () ;
rep ( i , 0 , 4 ) {
rep ( j , 0 , 4 ) {
rep ( k , 0 , 4 ) {
rep ( l , 0 , 4 ) {
d[0] = dist ( p[0][i] , p[1][j] ) ;
d[1] = dist ( p[1][j] , p[2][k] ) ;
d[2] = dist ( p[2][k] , p[3][l] ) ;
d[3] = dist ( p[3][l] , p[0][i] ) ;
d[4] = dist ( p[0][i] , p[2][k] ) ;
d[5] = dist ( p[1][j] , p[3][l] ) ;
sort ( d , d + 6 ) ;
if ( d[0] == 0 ) continue ;
else if ( d[0] == d[1] && d[1] == d[2] && d[2] == d[3] && d[4] == 2 * d[0] && d[4] == d[5] ) {
flag = 1 ;
//p[0][i].show () ;
//p[1][j].show () ;
//p[2][k].show () ;
//p[3][l].show () ;
ans = min ( ans , i + j + k + l ) ;
}
}
}
}
}
if ( flag ) printf ( "%d\n" , ans ) ;
else printf ( "-1\n" ) ;
}
int main () {
int T ;
scanf ( "%d" , &T ) ;
while ( T -- ) solve () ;
return 0 ;
}
D：Flowers
每个白色花连续的数目一定是k的整数倍。
设dp[0][i]表示长度为i以白色花结尾的方案数，dp[1][i]表示长度为i以红色花结尾的方案数。
dp[0][i] = dp[0][i-k] + dp[1][i-k]
dp[1][i] = dp[0][i-1] + dp[1][i-1]
然后由于满足区间减法，我们求一遍前缀和预处理，每次询问O（1）输出。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std ;
typedef long long LL ;
#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define For( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , n
#define mid ( ( l + r ) >> 1 )
#define rt o , l , r
const int MAXN = 100005 ;
const int mod = 1e9 + 7 ;
int dp[2][MAXN] ;
int sum[MAXN] ;
int T , k ;
void fun () {
int tmp = 0 ;
clr ( dp , 0 ) ;
clr ( sum , 0 ) ;
dp[0][k] = 1 ;
For ( i , 1 , k ) dp[1][i] = 1 ;
tmp = 1 ;
For ( i , k + 1 , 100000 ) {
dp[0][i] = ( dp[1][i - k] + dp[0][i - k] ) % mod ;
dp[1][i] = ( tmp + 1 ) % mod ;
tmp = ( tmp + dp[0][i] ) % mod ;
}
For ( i , 1 , 100000 ) sum[i] = ( ( sum[i - 1] + dp[0][i] ) % mod + dp[1][i] ) % mod ;
}
void solve () {
int a , b ;
scanf ( "%d%d" , &a , &b ) ;
printf ( "%d\n" , ( sum[b] - sum[a - 1] + mod ) % mod ) ;
}
int main () {
scanf ( "%d%d" , &T , &k ) ;
fun () ;
while ( T -- ) solve () ;
return 0 ;
}
E：Pillars
首先将高度排序离散化，以离散化后的元素个数N为下标建立线段树，线段树每个下标表示一个高度，对于所有下标i<j，满足hi<hj。线段树中每个区间保存区间内的最大长度以及最大长度对应的结尾元素标号。
然后我们从左到右处理每个点（未离散化之前的点），对于第i个点，设其高度为hi，则我们在高度1~hi-K内找到一个最长长度，在hi+K~N内找到一个最长长度，取最优的一个，长度+1用以更新当前点，同时记录前驱。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std ;
typedef long long LL ;
#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define For( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , cnt
#define mid ( ( l + r ) >> 1 )
#define rt o , l , r
const int MAXN = 100005 ;
LL maxv[MAXN << 2] ;
int pos[MAXN << 2] ;
LL num[MAXN] ;
LL a[MAXN] , cnt ;
int pre[MAXN] ;
int S[MAXN] , top ;
int n , k ;
int unique ( int n ) {
int cnt = 1 ;
sort ( a + 1 , a + n + 1 ) ;
For ( i , 2 , n ) if ( a[i] != a[cnt] ) a[++ cnt] = a[i] ;
return cnt ;
}
int Rsearch ( LL x ) {
int l = 1 , r = cnt ;
while ( l < r ) {
int m = ( l + r ) / 2 ;
if ( a[m] >= x ) r = m ;
else l = m + 1 ;
}
return l ;
}
int Lsearch ( LL x ) {
int l = 1 , r = cnt ;
while ( l < r ) {
int m = ( l + r + 1 ) / 2 ;
if ( a[m] <= x ) l = m ;
else r = m - 1 ;
}
return r ;
}
void update ( int x , int v , int i , int o , int l , int r ) {
if ( l == r ) {
if ( v > maxv[o] ) {
maxv[o] = v ;
pos[o] = i ;
}
return ;
}
int m = mid ;
if ( x <= m ) update ( x , v , i , lson ) ;
else update ( x , v , i , rson ) ;
if ( maxv[ls] > maxv[rs] ) {
pos[o] = pos[ls] ;
maxv[o] = maxv[ls] ;
} else {
pos[o] = pos[rs] ;
maxv[o] = maxv[rs] ;
}
}
int query_max , query_pos ;
void query ( int L , int R , int o , int l , int r ) {
if ( L > R ) return ;
if ( L <= l && r <= R ) {
if ( query_max < maxv[o] ) {
query_max = maxv[o] ;
query_pos = pos[o] ;
}
return ;
}
int m = mid ;
if ( L <= m ) query ( L , R , lson ) ;
if ( m < R ) query ( L , R , rson ) ;
}
void print ( int n ) {
if ( pre[n] ) print ( pre[n] ) ;
S[top ++] = n ;
}
void solve () {
int max_len = 1 , idx = 1 ;
clr ( maxv , 0 ) ;
clr ( pre , 0 ) ;
For ( i , 1 , n ) scanf ( "%I64d" , &num[i] ) , a[i] = num[i] ;
cnt = unique ( n ) ;
update ( Lsearch ( num[1] ) , 1 , 1 , root ) ;
pre[1] = 0 ;
For ( i , 2 , n ) {
int L = Lsearch ( num[i] - k ) ;
int R = Rsearch ( num[i] + k ) ;
query_max = 0 , query_pos = 0 ;
if ( a[L] + k <= num[i] ) {
//printf ( "%I64d %I64d\n" , num[i] , a[L] ) ;
query ( 1 , L , root ) ;
}
if ( num[i] + k <= a[R] ) {
//printf ( "%I64d %I64d\n" , num[i] , a[R] ) ;
query ( R , cnt , root ) ;
}
update ( Lsearch ( num[i] ) , query_max + 1 , i , root ) ;
pre[i] = query_pos ;
if ( query_max + 1 > max_len ) {
max_len = query_max + 1 ;
idx = i ;
}
}
printf ( "%d\n" , max_len ) ;
top = 0 ;
print ( idx ) ;
rep ( i , 0 , top ) printf ( "%d%c" , S[i] , i < top - 1 ? ' ' : '\n' ) ;
}
int main () {
while ( ~scanf ( "%d%d" , &n , &k ) ) solve () ;
return 0 ;
}
又是线段树，不过比E还简单。
我们可以知道如果区间【L，R】内所有数的gcd！=该区间内最小的数minv，则对于区间内的每个数都至少有一个数不是其倍数，那么每个数的v值都不可能等于r-l，所以所有的蚂蚁都要被吃掉（统统吃掉）。
现在如果gcd=minv，那么对于所有的等于minv的数，所有的数都是他的倍数，对于所有的不等于minv的数，至少有一个不是他的倍数（比如minv），所以答案就是r-l+1-minv的个数。
既然明白了原理，那么我们就好做了。
建立一棵线段树，维护区间gcd，区间内最小值以及最小值出现的次数即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std ;
typedef long long LL ;
#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define For( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , n
#define mid ( ( l + r ) >> 1 )
#define rt o , l , r
const int MAXN = 100005 ;
const int INF = 0x3f3f3f3f ;
int minv[MAXN << 2] ;
int num[MAXN << 2] ;
int GCD[MAXN << 2] ;
int n ;
int gcd ( int a , int b ) {
return b ? gcd ( b , a % b ) : a ;
}
void build ( int o , int l , int r ) {
if ( l == r ) {
scanf ( "%d" , &minv[o] ) ;
num[o] = 1 ;
GCD[o] = minv[o] ;
return ;
}
int m = mid ;
build ( lson ) ;
build ( rson ) ;
if ( minv[ls] < minv[rs] ) {
minv[o] = minv[ls] ;
num[o] = num[ls] ;
} else if ( minv[ls] > minv[rs] ) {
minv[o] = minv[rs] ;
num[o] = num[rs] ;
} else {
minv[o] = minv[ls] ;
num[o] = num[ls] + num[rs] ;
}
GCD[o] = gcd ( GCD[ls] , GCD[rs] ) ;
}
int query_min , query_num , query_gcd ;
void query ( int L , int R , int o , int l , int r ) {
if ( L <= l && r <= R ) {
if ( query_min > minv[o] ) {
query_min = minv[o] ;
query_num = num[o] ;
} else if ( query_min == minv[o] ) query_num += num[o] ;
query_gcd = gcd ( query_gcd , GCD[o] ) ;
return ;
}
int m = mid ;
if ( L <= m ) query ( L , R , lson ) ;
if ( m < R ) query ( L , R , rson ) ;
}
void solve () {
int m , l , r ;
build ( root ) ;
scanf ( "%d" , &m ) ;
while ( m -- ) {
scanf ( "%d%d" , &l , &r ) ;
query_min = INF ;
query_num = 0 ;
query_gcd = 0 ;
query ( l , r , root ) ;
if ( query_gcd != query_min ) printf ( "%d\n" , r - l + 1 ) ;
else printf ( "%d\n" , r - l + 1 - query_num ) ;
}
}
int main () {
while ( ~scanf ( "%d" , &n ) ) solve () ;
return 0 ;
}
后记：比赛的时候先去搞E，结果想了N多行不通的方法。。耽搁了不少时间，然后才回去写C，写完C回来看E突然就会写了。。好吧，只有半个小时了赶紧敲。。还好没敲出什么错误，不需要怎么debug，最后险而又险的在比赛结束四分钟内提交并且过了初测（运气真好），不过也因为这样没时间看F了，没想到F比E还容易些。。最后在评测的时候写了F，赛后提交一边AC~不过蛋疼的是写的C因为爆int了挂了FST。。原因是：虽然每个点的坐标的绝对值不大于1e4，但是旋转后两点之间的横坐标以及纵坐标的差值的最大值都能达4e4，所以距离的平方也就是3.2e9。。妥妥的爆int有木有？。。