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。

相关文章

Python实现图片分割的多种方法总结

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)
阅读更多...
Windows Docker端口占用错误及解决方案总结

Windows Docker端口占用错误及解决方案总结

《WindowsDocker端口占用错误及解决方案总结》在Windows环境下使用Docker容器时,端口占用错误是开发和运维中常见且棘手的问题,本文将深入剖析该问题的成因,介绍如何通过查看端口分配... 目录引言Windows docker 端口占用错误及解决方案汇总端口冲突形成原因解析诊断当前端口情况解
阅读更多...
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
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2