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。

相关文章

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的
阅读更多...
C# Task Cancellation使用总结

C# Task Cancellation使用总结

《C#TaskCancellation使用总结》本文主要介绍了在使用CancellationTokenSource取消任务时的行为,以及如何使用Task的ContinueWith方法来处理任务的延... 目录C# Task Cancellation总结1、调用cancellationTokenSource.
阅读更多...
HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
git使用的说明总结

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库：创建新文件夹，进入文件夹目录，执行指令 git init ，用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的
阅读更多...
二分最大匹配总结

二分最大匹配总结

HDU 2444  黑白染色 ，二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter
阅读更多...
整数Hash散列总结

整数Hash散列总结

方法：    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候，依次探查(h(k)+i) mod S, i=1,2,3…，直到找到空的存储单元为止。其中，S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000
阅读更多...
状态dp总结

状态dp总结

zoj 3631  N 个数中选若干数和（只能选一次）<=M 的最大值 const int Max_N = 38 ;int a[1<<16] , b[1<<16] , x[Max_N] , e[Max_N] ;void GetNum(int g[] , int n , int s[] , int &m){ int i , j , t ;m = 0 ;for(i = 0 ;
阅读更多...
Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2