2018年南京站题目解析
题目思路解析
通过枚举n≤5的情况可以发现，只有当k==1且n为偶数时或者n==0时后手胜，其他的都是先手胜。
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
typedef pair<int, LL> pil;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x<&x
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"] "<endl
#define FIN freopen("D://code//in.txt", "r", stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)
const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 2000 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
int n, k;
int main() {
scanf("%d%d", &n, &k);
if(n == 0 || (k == 1 && n % 2 == 0)) printf("Austin\n");
else printf("Adrien\n");
return 0;
}
最小球覆盖算法
使用最小球覆盖或三分套三分再套三分的方法。
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
typedef pair<int, LL> pil;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x<&x
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"] "<endl
#define FIN freopen("D://code//in.txt", "r", stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)
const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 1e6 + 7;
const int mx = 8e4 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
int n;
struct Point {
int x, y, z;
} pp[107];
struct Point1 {
double x, y, z;
} nw;
double dis(Point1 a, Point b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
}
double solve(int n) {
int idx = 1;
nw.x = nw.y = nw.z = 0;
double tmp = 10000.0, ans = 1e30;
while(tmp > eps) {
for(int i = 1; i <= n; i++) {
if(dis(nw, pp[i]) - dis(nw, pp[idx]) >= eps) {
idx = i;
}
}
double cnt = dis(nw, pp[idx]);
if(ans - cnt >= eps) ans = cnt;
nw.x += (pp[idx].x - nw.x) / cnt * tmp;
nw.y += (pp[idx].y - nw.y) / cnt * tmp;
nw.z += (pp[idx].z - nw.z) / cnt * tmp;
tmp *= 0.99;
}
return ans;
}
int main() {
#ifndef ONLINE_JUDGE
FIN;
#endif
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d%d%d", &pp[i].x, &pp[i].y, &pp[i].z);
}
printf("%.9f\n", solve(n));
return 0;
}
组合数学问题
计算组合数C(n+3, 4)。
#include <set>
#include <map>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pli;
typedef pair<int, LL> pil;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x<&x
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"] "<endl
#define FIN freopen("D://code//in.txt", "r", stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)
const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 1e5 + 7;
const double pi = acos( -1 );
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
int t;
LL n;
int Mod_Pow(int x, int n) {
int res = 1;
while(n) {
if(n & 1) res = 1LL * x * res % mod;
x = 1LL * x * x % mod;
n >= 1;
}
return res;
}
int main() {
int tmp = Mod_Pow(24, mod - 2);
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
printf("%lld\n",((((n+3)*(n+2)%mod)*(n+1)%mod)*(n)%mod * tmp) % mod);
}
return 0;
}
