A. Cashier
题意：给n个时间段（不会有交叉），在总时间L下，有多少个a的时间段可以抽烟。
#include <bits/stdc++.h> using namespace std; struct Line { int l,r; bool operator < (const Line & rhs) const { return r < rhs.r; } }; int main() { int n,l,a; vector<Line> v; //freopen("in.txt","r",stdin); scanf("%d%d%d",&n,&l,&a); for(int i = 0; i < n; i++) { int l,t; scanf("%d%d",&l,&t); v.push_back(Line{l,l+t}); } sort(v.begin(),v.end()); int ans = 0; for(int i = 0; i < (int)v.size()-1; i++) { ans += (v[i+1].l - v[i].r)/a; } if(n>0) { if(l>v[n-1].r) { ans+=(l-v[n-1].r)/a; } if(v[0].l>0) ans+=v[0].l/a; } else { ans += l/a; } cout<<ans<<endl; return 0; }
B. Forgery
题意：给一副图，可以每次画一个3*3的去中心图（此图需要完全在图中），问可否完成这幅图。
#include <bits/stdc++.h> using namespace std; const int maxn = 1000+5; char maps[maxn][maxn]; int n,m; int dx[8] = {-1,-1,-1,0,0,1,1,1}; int dy[8] = {-1,0,1,-1,1,-1,0,1}; bool inside(int x,int y) { bool flag = true; if(x>=1&&x<(n-1)&&y>=1&&y<(m-1)) { for(int i = 0; i < 8; i++) { int dr = x + dx[i]; int dc = y + dy[i]; if(maps[dr][dc]=='.') flag = false; } } else flag = false; return flag; } bool calc(int i,int j) { if(inside(i-1,j-1)) return true; if(inside(i-1,j)) return true; if(inside(i-1,j+1)) return true; if(inside(i,j-1)) return true; if(inside(i,j+1)) return true; if(inside(i+1,j-1)) return true; if(inside(i+1,j)) return true; if(inside(i+1,j+1)) return true; return false; } int main() { //freopen("in.txt","r",stdin); scanf("%d%d",&n,&m); for(int i = 0; i < n; i++) scanf("%s",maps[i]); bool flag = true; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(maps[i][j]=='#') { if(!calc(i,j)) { flag = false; break; } } } if(!flag) break; } printf("%s ",flag ? "YES":"NO"); return 0; }
C. Sequence Transformation
题意：给定1~n个数，每次求gcd，任意删掉其中一个数，求所得gcd序列的字典序最大。
分析：要求字典序最大，先删掉所有奇数，再出2，依次类推，需注意当个数<=3时，需要特判，等于3时，依顺序出。
#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d",&n); int res = 1; while(n>3) { for(int i = 1; i <= (n+1)/2; i++) printf("%d ",res); res*=2; n/=2; } if(n==1) printf("%d ",res); else if(n==2) printf("%d %d ",res,res*2); else if(n==3) printf("%d %d %d ",res,res,res*3); return 0; }
D. Nature Reserve
题意：给定N个点坐标，找到一个最小半径的，和x轴相切的圆，包含着所有点。
分析：二分答案，对于确定半径，包含着一个点，其圆心坐标有一个区间，这个半径应满足所有点坐标。
本题答案判断正确的方案很奇葩，二分到精确值会TLE，二分很多次即可。
#include<bits/stdc++.h> using namespace std; double x[100010],y[100010]; int N; bool check(long double k) { long double l=-100000000000000000.0,r=100000000000000000.0,t; for(int i=1;i<=N;i++) { if(y[i]>k*2) return 0; t=sqrt(k*k-(k-y[i])*(k-(y[i]))); if(l < x[i]-t) l = x[i]-t; if(r > x[i]+t) r = x[i]+t; } return l<r; } int main() { //freopen("in.txt","r",stdin); scanf("%d",&N); for(int i=1;i<=N;i++)scanf("%lf %lf",&x[i],&y[i]); for(int i=1;i<=N;i++) if(y[i]*y[N]<0) { puts("-1"); return 0; } else y[i]=y[i]>0?y[i]:-y[i]; long double l=0,r=100000000000000000.0,m; for(int i=1;i<=100;i++) { m=(l+r)/2.0; if(check(m)) r=m; else l=m; } printf("%.10Lf",m); return 0; }