【ACdream】ACdream原创群赛(18)のAK’s dream

现在的位置: 首页 > 综合 > 正文

【ACdream】ACdream原创群赛(18)のAK’s dream

2017年10月15日 ⁄ 综合 ⁄ 共 8160字 ⁄ 字号小中大 ⁄ 评论关闭

这次的群赛AK的不少，7题的也很多啊。。Orrrrrrrz。。。。

暂时只写出7题。。。

模拟。。

/*
* this code is made by poursoul
* Problem: 1196
* Verdict: Accepted
* Submission Date: 2014-09-06 19:12:44
* Time: 0MS
* Memory: 1088KB
*/
#include <map>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std ;

#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 CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )

typedef long long LL ;

int n , cur , d ;

void solve () {
	if ( cur == 1 ) printf ( "[<<]" ) ;
	else printf ( "(<<)" ) ;
	if ( cur - d <= 1 ) {
		REP ( i , 1 , cur ) printf ( "(%d)" , i ) ;
	} else {
		printf ( "[...]" ) ;
		REP ( i , cur - d , cur ) printf ( "(%d)" , i ) ;
	}
	printf ( "[%d]" , cur ) ;
	if ( cur + d >= n ) {
		FOR ( i , cur + 1 , n ) printf ( "(%d)" , i ) ;
	} else {
		FOR ( i , cur + 1 , cur + d ) printf ( "(%d)" , i ) ;
		printf ( "[...]" ) ;
	}
	if ( cur == n ) printf ( "[>>]\n" ) ;
	else printf ( "(>>)\n" ) ;
}
 
int main () {
	int cas = 0 ;
	while ( ~scanf ( "%d%d%d" , &n , &cur , &d ) ) {
		printf ( "Case #%d: " , ++ cas ) ;
		solve () ;
	}
	return 0 ;
}

C：1198

要求每个点到起点的路径长度加上到终点的路径长度里最长的最短。

那么可以对起点以及终点分别求一次最短路，路径相加取最长即可。

注意从起点到终点的不用相加。

/*
* this code is made by poursoul
* Problem: 1198
* Verdict: Accepted
* Submission Date: 2014-09-07 10:02:52
* Time: 304MS
* Memory: 4232KB
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
 
#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 )
 
typedef long long LL ;
 
const int MAXN = 1005 ;
const int MAXE = 200005 ;
const int INF = 0x3f3f3f3f ;
 
struct Edge {
	int v , c ;
	Edge* next ;
} E[MAXE] , *H[MAXN] , *cur ;
 
int Q[MAXN] , head , tail ;
bool vis[MAXN] ;
int d[2][MAXN] ;
int n , m , s , t ;
 
void clear () {
	cur = E ;
	CLR ( H , 0 ) ;
}
 
void addedge ( int u , int v , int c ) {
	cur -> v = v ;
	cur -> c = c ;
	cur -> next = H[u] ;
	H[u] = cur ++ ;
}
 
void spfa ( bool o , int s ) {
	CLR ( vis , 0 ) ;
	CLR ( d[o] , INF ) ;
	head = tail = 0 ;
	Q[tail ++] = s ;
	d[o][s] = 0 ;
	while ( head != tail ) {
		int u = Q[head ++] ;
		if ( head == MAXN ) head = 0 ;
		vis[u] = 0 ;
		travel ( e , H , u ) {
			int v = e -> v ;
			if ( d[o][v] > d[o][u] + e -> c ) {
				d[o][v] = d[o][u] + e -> c ;
				if ( !vis[v] ) {
					if ( d[o][v] < d[o][Q[head]] ) {
						if ( head == 0 ) head = MAXN ;
						Q[-- head] = v ;
					} else {
						Q[tail ++] = v ;
						if ( tail == MAXN ) tail = 0 ;
					}
					vis[v] = 1 ;
				}
			}
		}
	}
}
 
void solve () {
	int u , v , c ;
	clear () ;
	scanf ( "%d%d" , &n , &m ) ;
	REP ( i , 0 , m ) {
		scanf ( "%d%d%d" , &u , &v , &c ) ;
		addedge ( u , v , c ) ;
		addedge ( v , u , c ) ;
	}
	scanf ( "%d%d" , &s , &t ) ;
	spfa ( 0 , s ) ;
	spfa ( 1 , t ) ;
	int ans = 0 ;
	REP ( i , 0 , n ) {
		//printf ( "s-%d:%d t-%d:%d\n" , i , d[0][i] , i , d[1][i] ) ;
		if ( i == s || i == t ) ans = max ( ans , d[0][i] ) ;
		else ans = max ( ans , d[0][i] + d[1][i] ) ;
	}
	printf ( "%d\n" , ans ) ;
}
 
int main () {
	int T , cas = 0 ;
	scanf ( "%d" , &T ) ;
	while ( T -- ) {
		printf ( "Case #%d: " , ++ cas ) ;
		solve () ;
	}
	return 0 ;
}

D：1199

对人以及装备按升序排序，因为排在前面能拿的装备排在后面的一定能拿，令f[ i ]为排在第i位的人能拿的装备数，则ans = f[ 1 ] * ( f[ 2 ] - 1 ) * ( f[ 3 ] - 2 ) * ... * ( f[ n ] - ( n - 1 ) )

/*
* this code is made by poursoul
* Problem: 1199
* Verdict: Accepted
* Submission Date: 2014-09-07 10:19:39
* Time: 508MS
* Memory: 1868KB
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
 
#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 )
 
typedef long long LL ;
 
const int MAXN = 100005 ;
const int mod = 1e9 + 7 ;
 
int a[MAXN] ;
int b[MAXN] ;
int n ;
 
void solve () {
	scanf ( "%d" , &n ) ;
	FOR ( i , 1 , n ) scanf ( "%d" , &a[i] ) ;
	FOR ( i , 1 , n ) scanf ( "%d" , &b[i] ) ;
	sort ( a + 1 , a + n + 1 ) ;
	sort ( b + 1 , b + n + 1 ) ;
	int j = 0 , cnt = 0 ;
	LL ans = 1 ;
	FOR ( i , 1 , n ) {
		while ( j < n && a[j + 1] <= b[i] ) ++ j ;
		ans = ( ans * ( j - i + 1 ) ) % mod ;
	}
	printf ( "%d\n" , ans ) ;
}
 
int main () {
	int T , cas = 0 ;
	scanf ( "%d" , &T ) ;
	while ( T -- ) {
		printf ( "Case #%d: " , ++ cas ) ;
		solve () ;
	}
	return 0 ;
}

G：1202

直接字符串读进来判断就好了。。

/*
* this code is made by poursoul
* Problem: 1202
* Verdict: Accepted
* Submission Date: 2014-09-06 19:21:16
* Time: 0MS
* Memory: 1088KB
*/
#include <map>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std ;
 
#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 CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )
 
typedef long long LL ;
 
const int MAXN = 33 ;
 
char s[MAXN] ;
 
void solve () {
	if ( s[0] == '-' ) {
		int len = strlen ( s ) - 1 ;
		REP ( i , 0 , len ) s[i] = s[i + 1] ;
		if ( len < 5 ) printf ( "short\n" ) ;
		else if ( len == 5 ) {
			int flag = strcmp ( s , "32768" ) ;
			if ( flag <= 0 ) printf ( "short\n" ) ;
			else printf ( "int\n" ) ;
		}
		else if ( len < 10 ) printf ( "int\n" ) ;
		else if ( len == 10 ) {
			int flag = strcmp ( s , "2147483648" ) ;
			if ( flag <= 0 ) printf ( "int\n" ) ;
			else printf ( "long long\n" ) ;
		}
		else if ( len < 19 ) printf ( "long long\n" ) ;
		else if ( len == 19 ) {
			int flag = strcmp ( s , "9223372036854775808" ) ;
			if ( flag <= 0 ) printf ( "long long\n" ) ;
			else printf ( "It is too big!\n" ) ;
		}
		else printf ( "It is too big!\n" ) ;
	} else {
		int len = strlen ( s ) ;
		if ( len < 5 ) printf ( "short\n" ) ;
		else if ( len == 5 ) {
			int flag = strcmp ( s , "32767" ) ;
			if ( flag <= 0 ) printf ( "short\n" ) ;
			else printf ( "int\n" ) ;
		}
		else if ( len < 10 ) printf ( "int\n" ) ;
		else if ( len == 10 ) {
			int flag = strcmp ( s , "2147483647" ) ;
			if ( flag <= 0 ) printf ( "int\n" ) ;
			else printf ( "long long\n" ) ;
		}
		else if ( len < 19 ) printf ( "long long\n" ) ;
		else if ( len == 19 ) {
			int flag = strcmp ( s , "9223372036854775807" ) ;
			if ( flag <= 0 ) printf ( "long long\n" ) ;
			else printf ( "It is too big!\n" ) ;
		}
		else printf ( "It is too big!\n" ) ;
	}
}
 
int main () {
	while ( ~scanf ( "%s" , s ) ) solve () ;
	return 0 ;
}

H：1203

不忍吐嘈我这傻逼了。。。高中白学了T U T

首先给底边AB一个值，然后求出了AC、BC、AD、DC、BE、EC、AE。

白痴的事来了！我竟然逗比到用海伦公式来求边DE！通过化简(a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c)/16 = 0.5*CD*DE*sin(ACB)来求。。。。简直无语了。。。明明用余弦定理可以很轻松的。。。

还是不多说了。。智商不能暴露的太多。。

/*
* this code is made by poursoul
* Problem: 1203
* Verdict: Accepted
* Submission Date: 2014-09-07 11:23:05
* Time: 0MS
* Memory: 1276KB
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std ;
  
const double pi = acos ( -1.0 ) ;
  
int a , b , c , d ;
  
double rd ( int x ) {
	return x * pi / 180.0 ;
}
  
void solve () {
	int A = a + b ;
	int B = c + d ;
	int C = 180 - A - B ;
	int ADB = 180 - A - c ;
	int AEB = 180 - b - B ;
	if ( !a || !c ) printf ( "%.2f\n" , 0.0 ) ;
	else if ( !b ) printf ( "%.2f\n" , 0.0 + c ) ;
	else if ( !d ) printf ( "%.2f\n" , 0.0 + b + c ) ;
	else {
		double AB = 100.0 ;
		double AC = AB / sin ( rd ( C ) ) * sin ( rd ( B ) ) ;
		double BC = AB / sin ( rd ( C ) ) * sin ( rd ( A ) ) ;
		double AD = AB / sin ( rd ( ADB ) ) * sin ( rd ( c ) ) ;
		double BE = AB / sin ( rd ( AEB ) ) * sin ( rd ( b ) ) ;
		double AE = AB / sin ( rd ( AEB ) ) * sin ( rd ( B ) ) ;
		double CD = AC - AD ;
		double CE = BC - BE ;
		double S_CDE = 0.5 * CD * CE * sin ( rd ( C ) ) ;//S = 0.5absin(C)
		
		//求根公式
		double _b = - 2.0 * ( CD * CD + CE * CE ) ;
		double ac = 16.0 * S_CDE * S_CDE + pow ( CE * CE - CD * CD , 2.0 ) ;
		double x1 = 0.5 * ( -_b - sqrt ( _b * _b - 4.0 * ac ) ) ;
		double x2 = 0.5 * ( -_b + sqrt ( _b * _b - 4.0 * ac ) ) ;
		double DE = sqrt ( ( C <= 90 ? x1 : x2 ) ) ;
		
		double cos_AED = ( AE * AE + DE * DE - AD * AD ) / ( 2 * AE * DE ) ;
		double AED = acos ( cos_AED ) / pi * 180.0 ;
		printf ( "%.2f\n" , AED ) ;
	}
}
  
int main () {
	while ( ~scanf ( "%d%d%d%d" , &a , &b , &c , &d ) ) solve () ;
	return 0 ;
}

I：1204

用下gcd就行了，注意可能为负数即可。

/*
* this code is made by poursoul
* Problem: 1204
* Verdict: Accepted
* Submission Date: 2014-09-07 09:16:14
* Time: 20MS
* Memory: 1088KB
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
 
#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 CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )
 
typedef long long LL ;
 
int n ;
 
int gcd ( int a , int b ) {
	return a == 0 ? b : gcd ( b % a , a ) ;
}
 
void solve () {
	int x , y ;
	REP ( i , 0 , n ) {
		scanf ( "%d%d" , &x , &y ) ;
		++ y ;
		bool flag = 0 ;
		if ( x < 0 ) flag = 1 , x = -x ;
		int tmp = gcd ( x , y ) ;
		if ( flag ) x = -x ;
		printf ( "%d" , x / tmp ) ;
		if ( y != tmp ) printf ( "/%d" , y / tmp ) ;
		printf ( " " ) ;
		printf ( "%d" , y ) ;
		if ( i < n - 1 ) printf ( " " ) ;
		else printf ( "\n" ) ;
	}
}
int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}

J：1205

这题我开了一个disappear[ ]数组记录这个点是否被淹没，如果块[ i ]被淹没则disappear[ i ] = 1 , 否则disappear[ i ] = 0。首先将所有块按照高度从低到高排个序，然后按照时间顺序依次访问小于等于当前时间的高度的块，将该块标记为被淹没（disappear[] = 1），然后看他的左边和右边是否有被淹没的块，如果左右都没有被淹没，则肯定这个块被淹没以后，一个块分成了两个块，计数+1。如果左边和右边都被淹没，则这个块也被淹没，则少了一个块，计数-1。

/*
* this code is made by poursoul
* Problem: 1205
* Verdict: Accepted
* Submission Date: 2014-09-07 09:32:53
* Time: 1636MS
* Memory: 9876KB
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
 
#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 CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )

typedef long long LL ;

const int MAXN = 1000005 ;

struct Block {
	int h ;
	int idx ;
	bool operator < ( const Block& a ) const {
		return h < a.h ;
	}
} b[MAXN] ;


bool disappear[MAXN] ;
int n , m ;

void solve () {
	int s ;
	scanf ( "%d%d" , &n , &m ) ;
	FOR ( i , 1 , n ) {
		scanf ( "%d" , &b[i].h ) ;
		b[i].idx = i ;
		disappear[i] = 0 ;
	}
	disappear[0] = disappear[n + 1] = 1 ;
	sort ( b + 1 , b + n + 1 ) ;
	int now = 1 ;
	int cnt = 1 ;
	while ( m -- ) {
		scanf ( "%d" , &s ) ;
		while ( now <= n && b[now].h <= s ) {
			int idx = b[now].idx ;
			disappear[idx] = 1 ;
			if ( !disappear[idx - 1] && !disappear[idx + 1] ) ++ cnt ;
			else if ( disappear[idx - 1] && disappear[idx + 1] ) -- cnt ;
			now ++ ;
		}
		printf ( "%d%c" , cnt , m ? ' ' : '\n' ) ;
	}
}

int main () {
	int T , cas = 0 ;
	scanf ( "%d" , &T ) ;
	while ( T -- ) {
		printf ( "Case #%d: " , ++ cas ) ;
		solve () ;
	}
	return 0 ;
}

【上篇】【ACdream】1070 神奇的%系列二
【下篇】【ACDream】 1093 女神的正多面体矩阵快速幂

作者: blase

该日志由 blase 于7年前发表在综合分类下，最后更新于 2017年10月15日.
转载请注明: 【ACdream】ACdream原创群赛(18)のAK’s dream | 学步园 +复制链接

抱歉!评论已关闭.

学步园

【ACdream】ACdream原创群赛(18)のAK’s dream

作者: blase

书签

最新文章New

本站推荐

返回首页