1059A---Cashier
http://codeforces.com/contest/1059/problem/A
题意：
Vasya每天工作\(l\)个小时，每天服务\(n\)个顾客，每个休息时长是\(a\)。给定\(n\)个客人来的时间和时长。问Vasya可以休息多长时间。
思路：
先给客人排个序，然后各个间隔除以休息时间之和就是答案。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
#define N 100010
#define pi 3.1415926535 int n, l, a;
const int maxn = 1e5 + ;
struct node{
int l, len;
}peo[maxn];
bool cmp(node a, node b)
{
return a.l < b.l;
} int main()
{
while(scanf("%d%d%d", &n, &l, &a) != EOF){
for(int i = ; i < n; i++){
scanf("%d%d", &peo[i].l, &peo[i].len);
}
sort(peo, peo + n, cmp); int cnt = peo[].l / a;
for(int i = ; i < n; i++){
cnt += (peo[i].l - peo[i - ].l - peo[i - ].len) / a;
}
cnt += (l - peo[n - ].l - peo[n - ].len) / a;
printf("%d\n", cnt); }
return ;
}
1059B---Forgery
http://codeforces.com/contest/1059/problem/B
题意：
用笔可以填成下面这样。问能不能画出题目给定的样子。
xxx
x.x
xxx
思路：
每个\(.\)是的周围八个是不可以作为落笔的中心的。同时边界上的点也不可以作为边界中心。
而对于每一个\(#\)，周围的八个中至少要有一个是可以作为中心的点。
卡了好久啊我的妈。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
#define N 100010
#define pi 3.1415926535 int n, m;
const int maxn = ;
char g[maxn][maxn];
char graph[maxn][maxn];
bool forbidden[maxn][maxn];
//int mvx[4] = {-1, 1, 0, 0};
//int mvy[4] = {0, 0, -1, 1}; bool inside(int i, int j)
{
return i >= && j >= && i <= n && j <= m;
} int main()
{
while(scanf("%d%d", &n, &m) != EOF){
memset(forbidden, , sizeof(forbidden));
for(int i = ; i <= n; i++){
scanf("%s", g[i] + );
for(int j = ; j <= m; j++){
//graph[i][j] = '.';
if(g[i][j] == '.'){
for(int dx = -; dx <= ; dx++){
for(int dy = -; dy <= ; dy++){
if(dx == && dy == || !inside(i + dx, j + dy))continue;
forbidden[i + dx][j + dy] = true;
}
}
}
}
} bool flag = true;
for(int i = ; i <= n; i++){
for(int j = ; j <= m; j++){
if(g[i][j] == '#'){
int cnt = ;
for(int dx = -; dx <= ; dx++){
for(int dy = -; dy <= ; dy++){
if(dy == && dx == || !inside(i + dx, j + dy))continue;
if(i + dx == || i + dx == n || j + dy == || j + dy == m)continue;
else if(!forbidden[i + dx][j + dy])cnt++;
}
}
if(cnt == ){
flag = false;
break;
}
}
}
if(!flag)break;
}
if(flag){
printf("YES\n");
}
else{
printf("NO\n");
}
}
return ;
}
1059C---Sequence Transformation【递归】
http://codeforces.com/contest/1059/problem/C
题意：
给定一个\(1~n\)的序列，每一次求得这个序列中所有数的最小公因数，然后随机删掉一个。问怎样删可以使得得到的答案序列是字典序最大的。
思路：
因为给定的是\(1~n\)连续的整数，相邻两个数之间肯定是互质的。所以刚开始要去掉相邻的数，这部分的答案都是1
显然我们应该要尽量去掉奇数，因为要让字典序最大，就必须要让除1外的其他数尽快出现。删除奇数是最快的。
剩下来的数就是一堆偶数了。比如我们剩下了\(2,4,6,8\)。他们其实可以看成是\(1*2, 2*2, 3*2, 4*2\)
将他们除以\(2\)之后就又是一个\(1~4\)的子问题了。不断dfs递归下去，直到总数是1、2或3时就可以直接输出答案然后返回了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
#define N 100010
#define pi 3.1415926535 int n; void dfs(int k, int mul)
{
if(k == ){
printf("%d ", mul);
return;
}
else if(k == ){
printf("%d %d ", mul, mul * );
return;
}
else if(k == ){
printf("%d %d %d ", mul, mul, mul * );
return;
} for(int i = ; i < (k + ) / ; i++){
printf("%d ", mul);
}
dfs(k / , mul * ); } int main()
{
while(scanf("%d", &n) != EOF){
dfs(n, );
printf("\n");
}
return ;
}
1059D---Nature Reserve【二分】【好题】
http://codeforces.com/contest/1059/problem/D
题意：
给定n个点，要求找到一个最小的圆覆盖这些点，并且这个圆和横坐标轴有且仅有一个交点。输出最小的半径。
思路：
刚开始想了很久的最小圆覆盖，还去学了一下模板。后来发现是不可以用最小圆覆盖的。因为最小圆覆盖得到的圆有可能和横坐标有两个交点。
正解应该是二分半径。
\(-1\)的情况很简单，只要有点在横坐标两侧或者横坐标上有多于两个点就不可以。
由于和横坐标轴有且仅有一个交点，所以半径一定就是圆心的纵坐标值。
二分半径，然后去看当前半径是不是可以包括所有的点。
这个要怎么判断呢。
假设点$p_{i}$的坐标为$(x_{i}, y_{i})$，当前的半径是$R$
那么圆心$c$的坐标就是$(x, R)$， 其中$x$是一个未知数。
圆心到$p_{i}$的距离要小于等于$R$，我们可以列出一个方程，
求出$x$的取值区间是$[x_{i} - \sqrt{R^{2} - (R-y_{i})^{2}}, x_{i} + \sqrt{R^{2} - (R-y_{i})^{2}}]$
如果$n$个点的这个区间的交集是空集的话，那么这个半径$R$就是不可行的。
输出搞了超级久，烦人。
#include<iostream>
#include<bits/stdc++.h>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
#define N 100010
#define pi 3.1415926535 const int maxn = 1e5 + ;
const double eps = 1e-; int n;
struct node{
double x, y;
}p[maxn]; bool check(double x)
{
double l = -1e18, r = 1e18;
for(int i = ; i < n; i++){
if(p[i].y > * x)return ;
double t=sqrt(p[i].y*(*x-p[i].y));
l = max(l, p[i].x - t);
r = min(r, p[i].x + t);
}
return (l - r + eps) <= ;
} int main()
{
//ios_base::sync_with_stdio(false);
while(scanf("%d", &n) != EOF){
bool negative = false, positive = false;
int zero = ;
for(int i = ; i < n; i++){
cin>>p[i].x>>p[i].y;
if(p[i].y > )positive = true;
if(p[i].y < ){
negative = true;
p[i].y = -p[i].y;
}
if(p[i].y == )zero++;
} if(negative && positive || zero >= ){
printf("-1\n");
}
else{
double st = 0.0, ed = 1e18, ans;
for(int k = ; k < ; k++){
double mid = (st + ed) / ;
if(check(mid)){
ed = mid;
}
else{
st = mid;
}
}
//cout<<st<<endl;
printf("%f\n", st);//cout<<ans<<endl;
}
}
return ;
}