Codeforces---125--div2--总结

2023-12-11 11:19
文章标签 总结 codeforces div2 125

本文主要是介绍Codeforces---125--div2--总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A题：

http://codeforces.com/contest/199/problem/A

因为0也属于fibonacci数列，所以直接输出0， 0， n；

另外也可以用递推的方法，代码：

/*
收获：
*/
#include<iostream>
#include<cstdlib>
#include<vector>
#include<map>
#include<cstring>
#include<set>
#include<string>
#include<algorithm>
#include<sstream>
#include<ctype.h>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<stack>
#include<queue>
#include<ctime>
//#include<conio.h>
using namespace std;const int INF_MAX=0x7FFFFFFF;
const int INF_MIN=-(1<<31);const double eps=1e-10;
const double pi=acos(-1.0);#define pb push_back   //a.pb( )
#define chmin(a,b) ((a)<(b)?(a):(b))
#define chmax(a,b) ((a)>(b)?(a):(b))template<class T> inline T gcd(T a,T b)//NOTES:gcd({if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<class T> inline T lcm(T a,T b)//NOTES:lcm({if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
int dir_4[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
int dir_8[8][2]={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};
//下，左下，左，左上，上，右上，右，右下。//******* WATER ****************************************************************long long find(long long k)
{long long a = 0;long long b = 1;long long c = 1;while(c != k){a = b;b = c;c = a + b;}return b;
}int main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);long long k;cin>>k;if(k == 0) cout<<"0 0 0"<<endl;else if(k == 1) cout<<"0 0 1"<<endl;else{long long kk = find(k);cout<<2 * k - 3 * kk<<" "<<2 * kk - k<<" "<<kk<<endl;}return 0;//printf("%.6f\n",(double)clock()/CLOCKS_PER_SEC);
}


B题：

http://codeforces.com/contest/199/problem/B

需要讨论一个圆和一个环的几种关系：

1.圆在圆环内部。

  

                            情况1


                             情况2

2. 圆在圆环外部

                                              情况1


                                                 情况2

其他的情况均是有相交的不完整的情况。

只要对四个圆和两个圆环分别代入写的子函数中返回是否相交，就可以得出答案。

小技巧：比较中含有根号的时候可以同时平方来比较。

code：

/*
收获：
*/
#include<iostream>
#include<cstdlib>
#include<vector>
#include<map>
#include<cstring>
#include<set>
#include<string>
#include<algorithm>
#include<sstream>
#include<ctype.h>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<stack>
#include<queue>
#include<ctime>
//#include<conio.h>
using namespace std;const int INF_MAX=0x7FFFFFFF;
const int INF_MIN=-(1<<31);const double eps=1e-10;
const double pi=acos(-1.0);#define pb push_back   //a.pb( )
#define chmin(a,b) ((a)<(b)?(a):(b))
#define chmax(a,b) ((a)>(b)?(a):(b))template<class T> inline T gcd(T a,T b)//NOTES:gcd({if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<class T> inline T lcm(T a,T b)//NOTES:lcm({if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
int dir_4[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
int dir_8[8][2]={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};
//下，左下，左，左上，上，右上，右，右下。//******* WATER ****************************************************************typedef struct
{int x, y;int r;
}circle;int judge_intersecotiono(circle a, circle b)
{double dis = sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );if(fabs(dis - abs(a.r + b.r)) < eps) return 2;else if(fabs(dis - abs(a.r - b.r)) < eps) return 3;else if( dis > abs(a.r - b.r) && dis < abs(a.r + b.r)) return 1;//相交else if(dis > abs(a.r + b.r) ) return 2;//相离else return 3;//内含
}int judge_in(circle a, circle b, circle c)
{if(judge_intersecotiono(a, b) == 2 && judge_intersecotiono(a, c) == 3) return 1;//被覆盖else return 0;//未覆盖
}int judge_cover(circle a, circle b, circle c)
{double dis1 = sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );double dis2 = sqrt( (a.x - c.x) * (a.x - c.x) + (a.y - c.y) * (a.y - c.y) );if(b.r < a.r && dis1 < fabs(a.r - b.r) + eps && c.r > a.r && dis2 < fabs(a.r - c.r) + eps) return false;else return true;
}bool judge_ok(circle a, circle b, circle c)
{if(judge_in(a, b, c) == 0 && judge_intersecotiono(a, b) != 1 && judge_intersecotiono(a, c) != 1 && judge_cover(a, b, c)) return true;else return false;
}int main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);circle a1, a2;circle b1, b2;int a, b, c, d;cin>>a>>b>>c>>d;a1.x = a2.x = a;a1.y = a2.y = b;a1.r = c;a2.r = d;cin>>a>>b>>c>>d;b1.x = b2.x = a;b1.y = b2.y = b;b1.r = c;b2.r = d;int ans = 0;if(judge_ok(a1, b1, b2)) ans++;if(judge_ok(a2, b1, b2)) ans++;if(judge_ok(b1, a1, a2)) ans++;if(judge_ok(b2, a1, a2)) ans++;cout<<ans<<endl;//printf("%.6f\n",(double)clock()/CLOCKS_PER_SEC);
}

C题：

http://codeforces.com/contest/199/problem/C

考虑 第一种情况经历s时间后第一次超过了t，那么从这个时候开始就可以了。

trick：要用long long ，因为有乘法运算会超出int界。


/*
收获：
*/
#include<iostream>
#include<cstdlib>
#include<vector>
#include<map>
#include<cstring>
#include<set>
#include<string>
#include<algorithm>
#include<sstream>
#include<ctype.h>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<stack>
#include<queue>
#include<ctime>
//#include<conio.h>
using namespace std;const int INF_MAX=0x7FFFFFFF;
const int INF_MIN=-(1<<31);const double eps=1e-10;
const double pi=acos(-1.0);#define pb push_back   //a.pb( )
#define chmin(a,b) ((a)<(b)?(a):(b))
#define chmax(a,b) ((a)>(b)?(a):(b))template<class T> inline T gcd(T a,T b)//NOTES:gcd({if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<class T> inline T lcm(T a,T b)//NOTES:lcm({if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
int dir_4[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
int dir_8[8][2]={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};
//下，左下，左，左上，上，右上，右，右下。//******* WATER ****************************************************************LL timee(LL k, LL b, LL n, LL t)
{LL ret = 0;LL now = 1;while(now <= t){now = now * k + b;ret++;}return ret - 1;
}int main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);LL k, b, n, t;cin>>k>>b>>n>>t;if(n >= timee(k, b, n, t)) cout<<n - timee(k, b, n, t)<<endl;else cout<<0<<endl;//printf("%.6f\n",(double)clock()/CLOCKS_PER_SEC);
}


D题：

http://codeforces.com/contest/199/problem/D

这个题目需要用BFS来做，当时我用的是DFS，是不对的，因为DFS会搜索很多重复的边，而且很多边不能记录对它最早的搜索，导致了TLE。

code由于是看别人的，在此不粘贴了。


E题：

http://codeforces.com/contest/199/problem/E

需要用二分的方法，求得不过圆的最近距离，分两种情况：

1. AB线段不过圆。

2. AB线段过圆，这时候沿着圆走，具体开始地点进行二分。

code未写，方法如上。

这篇关于Codeforces---125--div2--总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

java常见报错及解决方案总结

java常见报错及解决方案总结

《java常见报错及解决方案总结》：本文主要介绍Java编程中常见错误类型及示例,包括语法错误、空指针异常、数组下标越界、类型转换异常、文件未找到异常、除以零异常、非法线程操作异常、方法未定义异常... 目录1. 语法错误 (Syntax Errors)示例 1:解决方案：2. 空指针异常 (NullPoi
阅读更多...
Java反转字符串的五种方法总结

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》：本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一：使用StringBuilder的reverse()方法方法二：使用字符数组方法三：使用自
阅读更多...
Python依赖库的几种离线安装方法总结

Python依赖库的几种离线安装方法总结

《Python依赖库的几种离线安装方法总结》：本文主要介绍如何在Python中使用pip工具进行依赖库的安装和管理,包括如何导出和导入依赖包列表、如何下载和安装单个或多个库包及其依赖,以及如何指定... 目录前言一、如何copy一个python环境二、如何下载一个包及其依赖并安装三、如何导出requirem
阅读更多...
Rust格式化输出方式总结

Rust格式化输出方式总结

《Rust格式化输出方式总结》Rust提供了强大的格式化输出功能,通过std::fmt模块和相关的宏来实现,主要的输出宏包括println!和format!,它们支持多种格式化占位符,如{}、{:?}... 目录Rust格式化输出方式基本的格式化输出格式化占位符Format 特性总结Rust格式化输出方式
阅读更多...
Python中连接不同数据库的方法总结

Python中连接不同数据库的方法总结

《Python中连接不同数据库的方法总结》在数据驱动的现代应用开发中,Python凭借其丰富的库和强大的生态系统,成为连接各种数据库的理想编程语言,下面我们就来看看如何使用Python实现连接常用的几... 目录一、连接mysql数据库二、连接PostgreSQL数据库三、连接SQLite数据库四、连接Mo
阅读更多...
Git提交代码详细流程及问题总结

Git提交代码详细流程及问题总结

《Git提交代码详细流程及问题总结》：本文主要介绍Git的三大分区,分别是工作区、暂存区和版本库,并详细描述了提交、推送、拉取代码和合并分支的流程,文中通过代码介绍的非常详解,需要的朋友可以参考下... 目录1.git 三大分区2.Git提交、推送、拉取代码、合并分支详细流程3.问题总结4.git push
阅读更多...
Kubernetes常用命令大全近期总结

Kubernetes常用命令大全近期总结

《Kubernetes常用命令大全近期总结》Kubernetes是用于大规模部署和管理这些容器的开源软件-在希腊语中,这个词还有“舵手”或“飞行员”的意思,使用Kubernetes（有时被称为“... 目录前言Kubernetes 的工作原理为什么要使用 Kubernetes？Kubernetes常用命令总
阅读更多...
Python中实现进度条的多种方法总结

Python中实现进度条的多种方法总结

《Python中实现进度条的多种方法总结》在Python编程中,进度条是一个非常有用的功能,它能让用户直观地了解任务的进度,提升用户体验,本文将介绍几种在Python中实现进度条的常用方法,并通过代码... 目录一、简单的打印方式二、使用tqdm库三、使用alive-progress库四、使用progres
阅读更多...
Android数据库Room的实际使用过程总结

Android数据库Room的实际使用过程总结

《Android数据库Room的实际使用过程总结》这篇文章主要给大家介绍了关于Android数据库Room的实际使用过程,详细介绍了如何创建实体类、数据访问对象（DAO）和数据库抽象类,需要的朋友可以... 目录前言一、Room的基本使用1.项目配置2.创建实体类（Entity）3.创建数据访问对象（DAO
阅读更多...
Java向kettle8.0传递参数的方式总结

Java向kettle8.0传递参数的方式总结

《Java向kettle8.0传递参数的方式总结》介绍了如何在Kettle中传递参数到转换和作业中,包括设置全局properties、使用TransMeta和JobMeta的parameterValu... 目录1.传递参数到转换中2.传递参数到作业中总结1.传递参数到转换中1.1. 通过设置Trans的
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2