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

2024-09-05 14:58
文章标签 18 原创 ak dream acdream 群赛

本文主要是介绍【ACdream】ACdream原创群赛(18)のAK's dream，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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


暂时只写出7题。。。


A：1196

模拟。。


/*
* 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】ACdream原创群赛(18)のAK's dream的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1139279。

相关文章

react笔记 8-18 事件 方法 定义方法 获取/改变数据 传值

react笔记 8-18 事件 方法 定义方法 获取/改变数据 传值

1、定义方法并绑定 class News extends React.Component {constructor(props) {super(props)this.state = {msg:'home组件'}}run(){alert("我是一个run") //方法写在类中}render() {return (<div><h2>{this.state.msg}</h2><button onCli
阅读更多...
Day18_0.1基础学习MATLAB学习小技巧总结（18）——MATLAB绘图篇（1）

Day18_0.1基础学习MATLAB学习小技巧总结（18）——MATLAB绘图篇（1）

利用空闲时间把碎片化的MATLAB知识重新系统的学习一遍，为了在这个过程中加深印象，也为了能够有所足迹，我会把自己的学习总结发在专栏中，以便学习交流。 参考书目：《MATLAB基础教程 (第三版) (薛山)》 之前的章节都是基础的数据运算用法，对于功课来说更加重要的内容是建模、绘图、观察数据趋势，接下来我会结合自己的使用经验，来为大家分享绘图、建模使用的小技巧。 二维图形绘制 在本章开
阅读更多...
ACdream区域赛指导赛之手速赛系列(4)

ACdream区域赛指导赛之手速赛系列(4)

点击打开题目链接 #include <iostream>#include <map>#include <cstdio>#include <string>using namespace std;int a[501];//题意是能不能把一组两个人分到两个不同的正营里面,关键利用map映射void init(){for(int i = 0; i <= 200; i++){a[i]
阅读更多...
找第K大数(ACdream 1099)

找第K大数(ACdream 1099)

瑶瑶的第K大 Time Limit: 4000/2000MS (Java/Others)  Memory Limit: 256000/128000KB (Java/Others) Submit  Statistic  Next Problem Problem Description 一天，萌萌的妹子--瑶瑶(tsyao)很无聊，就来找你玩。可是你们都不知道玩什么。。。
阅读更多...
18. 4 Sum

18. 4 Sum

题目： 解答： 与之前的三数之和的解法类似，也是先排序，然后不断剔除不可能的条件，最后两个参数，通过两头求和计算得出。 代码： class Solution {public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> result;int len = nums.size
阅读更多...
2024高教社杯全国大学生数学建模竞赛B题原创python代码

2024高教社杯全国大学生数学建模竞赛B题原创python代码

以下均为python代码。先给大家看看之前文章的部分思路： 接下来我们将按照题目总体分析-背景分析-各小问分析的形式来 1 总体分析 题目提供了一个电子产品生产的案例，要求参赛者建立数学模型解决企业在生产过程中的一系列决策问题。以下是对题目的总体分析： 问题一需要企业需要从供应商购买零配件，并且需要设计一个抽样检测方案，来决定是否接受供应商提供的零配件。题目要求设计一个能够尽可能减少检测次
阅读更多...
系统架构师考试学习笔记第三篇——架构设计高级知识（18）面向服务架构设计理论与实践

系统架构师考试学习笔记第三篇——架构设计高级知识（18）面向服务架构设计理论与实践

本章考点：         第18课时主要学习面向服务架构设计理论与实践。根据考试大纲，本课时知识点会涉及单选题型（约占2~5分）和案例题（25分），本课时内容偏重于方法的掌握和应用，根据以往全国计算机技术与软件专业技术资格（水平）考试的出题规律，概念知识的考查内容多数来源于实际应用，还需要灵活运用相关知识点。         本课时知识架构如图18.1所示。 一、SOA的相关概念 （
阅读更多...
怎样写原创内容才能快速被收录呢？

怎样写原创内容才能快速被收录呢？

网站原创文章怎么写才能收录？站长们都知道，文章对SEO的重要性，一篇高质量的原创文章要胜过N篇采集来的文章。那么，我们应该如何根据用户需求写出用户需要的文章呢？下面，曾庆平SEO就为大家讲一下如何写出既符合用户需求，又符合搜索引擎的高质量原创文章。 请牢记，发文章的最终目的是用来解决用户需求而不是一味的满足搜索引擎。请不要为了搜索引擎而刻意的在文章里面大量堆砌关键词，这样做只会让用户感觉文章没
阅读更多...
SEO如何提高原创内容输出增量？

SEO如何提高原创内容输出增量？

对于任何一个网站建设运营而言，我们在一个长周期的运营过程中，在某一个时间点，总会遇到发展瓶颈，比如： 流量停止不前。 百度权重，没有明显变化。 特定关键词排名，长期稳定，不升不降。 这个时候我们就需要思考一个问题，我们该如何推动网站继续前进，是增加品牌影响力，还是持续的拓展更多相关性的栏目，从SEO的角度来讲，我们通常会推荐从横行拓展相关性内容来入手，毕竟这样的运营成本相对是非常低的。
阅读更多...
PHP 验证身份号码 包括15位18位

PHP 验证身份号码 包括15位18位

查了很多资料 发现网上身份证15位的验证并不是那么严谨  今天研究了一下  代码如下 <?phpfunction check_id_card($num){//老身份证长度15位，新身份证长度18位$length = strlen($num);if ($length == 15) { //如果是15位身份证//15位身份证没有字母if (!is_numeric($num)) {return fa
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2