这一套题为2013年长沙网络赛。
A - So Easy!
三张图说明一切。。。
1.
2.
3.
但是第三张有个地方错了，
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define N 2
#define MAXN 500
#define OT printf
#define LL long long
#define INF 0x7f7f7f7f
#define RUN(x) freopen(#x, "r", stdin);
#define REP(i, n) for(i = 0; i < n; i++)
#define FOR(i, s, e) for(i = s; i <= e; i++)
#define DWN(i, s, e) for(i = e; i >= s; i--)
LL a, b;
int n, mod;
struct Matrix
{
int mat[N][N], r, c;
Matrix() {}
void clr() { memset(mat, 0, sizeof(mat)); }
Matrix E()
{
Matrix e;
e.clr();
int i;
REP(i, N) e.mat[i][i] = 1;
return e;
}
Matrix operator *(const Matrix &argu)
{
int i, j, k;
Matrix ret; ret.clr();
REP(i, N) REP(j, N) REP(k, N)
{
ret.mat[i][j] += mat[i][k] * argu.mat[k][j];
ret.mat[i][j] %= mod;
}
return ret;
}
Matrix Pow(int n)
{
Matrix p = (*this), res = E();
while(n)
{
if(n & 1) res = res * p;
p = p * p;
n >>= 1;
}
return res;
}
void out()
{
int i, j;
REP(i, N)
{
REP(j, N) OT("%d ", mat[i][j]);
puts("");
}
}
};
Matrix p;
int main()
{
// RUN(A.in);
while(~scanf("%I64d%I64d%d%d", &a, &b, &n, &mod))
{
if(n == 1) { OT("%I64d\n", 2 * a % mod); continue; }
p.mat[0][0] = 2 * a % mod; p.mat[0][1] = (b - a * a % mod + mod) % mod;
p.mat[1][0] = 1; p.mat[1][1] = 0;
Matrix k = p.Pow(n - 2);
// k.out();
LL ans = ((b + a * a % mod) % mod * 2 * k.mat[0][0] % mod + 2 * a * k.mat[0][1] % mod) % mod;
OT("%I64d\n", ans);
}
return 0;
}
C - Brilliant Programmers Show
给出黑客们的初始排名，排名相邻的黑客间可以互相挑战，低位向高位挑战成功则两人名次调换，否则不变。
按照初始排名给出每个黑客挑战成功的次数，问谁是最后的冠军。
1.首先挑战成功次数最多的那个肯定是冠军；
2.冠军打败了在他前面所有的人；
3.冠军会打败后面向他挑战的所有人；
4.后来者能向冠军挑战，也必须打败他们之间的所有人。
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define MAXN 1000100
#define LL __int64
template <class T>
inline int RD(T &x)
{
x = 0;
char ch = getchar();
while(!isdigit(ch)) { ch = getchar(); if(ch == EOF) return 0; }
while(isdigit(ch)) { x *= 10; x += ch - '0'; ch = getchar(); }
return 1;
}
int n;
LL a[MAXN];
void solve()
{
LL l = 0, r = 0, tmp = 0;
int p;
for(int i = 0; i < n; i++)
{
if(a[i] >= l) p = i;
l += 1 + a[i];
}
l = 0;
for(int i = 0; i < p; i++) l += 1 + a[i];
for(int i = p + 1; i < n; i++)
{
r += (0 > a[i] - tmp ? 0 : a[i] - tmp);
tmp += (a[i] <= tmp);
}
if(a[p] > r + l) puts("Bad Rescue");
else if(a[p] == r + l) printf("%d\n", p + 1);
else puts("Unknown");
}
int main()
{
// freopen("C.in", "r", stdin);
int t = 0;
while(~scanf("%d", &n))
{
t++;
if(t >= 40) continue;
for(int i = 0; i < n; i++) RD(a[i]);
solve();
}
return 0;
}
I - Throw the Stones
加入哪一个点时，凸包体积增量最大。
注意重点，所有点共线，所有点共面的情况。
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define eps 1e-9
#define MAXN 10010
inline int sig(double x)
{
return (x > eps) - (x < -eps);
}
typedef struct Point
{
double x, y, z;
Point(double _x = 0.0, double _y = 0.0, double _z = 0.0):
x(_x), y(_y), z(_z) {}
double dis(const Point &argu) const
{
return sqrt((x - argu.x) * (x - argu.x) + (y - argu.y) * (y - argu.y) + (z - argu.z) * (z - argu.z));
}
Point operator ^(const Point &argu) const
{
return Point(y * argu.z - z * argu.y, z * argu.x - x * argu.z, x * argu.y - y * argu.x);
}
double operator *(const Point &argu) const
{
return x * argu.x + y * argu.y + z * argu.z;
}
Point operator +(const Point &argu) const
{
return Point(x + argu.x, y + argu.y, z + argu.z);
}
Point operator -(const Point &argu) const
{
return Point(x - argu.x, y - argu.y, z - argu.z);
}
double len() const
{
return sqrt(x * x + y * y + z * z);
}
double dis_line(Point &a0, Point &a1)
{
return ((*this - a0) ^ (a1 - a0)).len() / (a1 - a0).len();
}
double dis_seg(Point &a0, Point &a1)
{
if(sig((*this - a0) * (a1 - a0)) >= 0 && sig((*this - a1) * (a0 - a1)) >= 0) return dis_line(a0, a1);
return min(dis(a0), dis(a1));
}
double V6(Point a0, Point a1, Point a2)
{
return (((a0 - *this) ^ (a1 - *this)) * (a2 - *this));
}
int side(const Point &a0, const Point &a1, const Point &a2) { return sig(V6(a0, a1, a2)); }
void in()
{
scanf("%lf%lf%lf", &x, &y, &z);
}
void out()
{
printf("%.10lf %.10lf %.10lf\n", x, y, z);
}
}Vector;
Point p[MAXN];
struct Face
{
int a, b, c;
bool flag;
Face() {}
Face(int a, int b, int c, bool flag): a(a), b(b), c(c), flag(flag) {}
bool cansee(const Point &argu)
{
return p[a].side(p[b], p[c], argu) > 0;
}
};
Face fac[MAXN * 10];
struct Hull
{
double diffv;
int cnt, mat[MAXN][MAXN];
void init()
{
cnt = 0;
for(int i = 0; i < 4; ++i)
{
Face temp = Face((i + 1) % 4, (i + 2) % 4, (i + 3) % 4, true);
if(temp.cansee(p[i])) swap(temp.a, temp.c);
mat[temp.a][temp.b] = mat[temp.b][temp.c] = mat[temp.c][temp.a] = cnt;
fac[cnt++] = temp;
}
}
void deal(int k, int a, int b)
{
int f = mat[a][b];
if(fac[f].flag)
{
if(fac[f].cansee(p[k])) dfs(k, f);
else
{
mat[b][a] = mat[a][k] = mat[k][b] = cnt;
fac[cnt++] = Face(b, a, k, true);
}
}
}
void dfs(int k, int f)
{
diffv += p[fac[f].a].V6(p[fac[f].b], p[fac[f].c], p[k]);
fac[f].flag = false;
deal(k, fac[f].b, fac[f].a);
deal(k, fac[f].c, fac[f].b);
deal(k, fac[f].a, fac[f].c);
}
double update(int k)
{
diffv = 0;
for(int i = 0; i < cnt; ++i)
{
if(!fac[i].flag || !fac[i].cansee(p[k])) continue;
dfs(k, i);
break;
}
return diffv;
}
double vol()
{
double res = 0;
for(int i = 0; i < cnt; ++i) if(fac[i].flag)
res -= p[fac[i].a].V6(p[fac[i].b], p[fac[i].c], Point(0, 0, 0));
return res;
}
}thrower;
int n, k;
void work()
{
int king = 0;
double ans = 0;
for(int i = 1, tag = 1; i < n; ++i)
{
if(tag == 1)
{
tag += sig((p[0] - p[i]).len());
if(tag > 1) swap(p[1], p[i]);
}
else if(tag == 2)
{
tag += sig(((p[1] - p[0]) ^ (p[i] - p[0])).len());
if(tag > 2) swap(p[2], p[i]);
}
else if(tag == 3)
{
tag += (sig(p[0].V6(p[1], p[2], p[i])) != 0);
if(tag > 3)
{
swap(p[3], p[i]);
thrower.init();
for(int j = 4; j <= i; ++j) thrower.update(j);
king = i, ans = thrower.vol();
}
}
else
{
double v = thrower.update(i);
if(sig(v - ans) > 0)
{
ans = v;
king = i;
}
}
}
printf("%d %.2f\n", king + 1, ans / 6.0);
}
int main()
{
// freopen("I.in", "r", stdin);
k = 0;
while(scanf("%d", &n) != EOF)
{
for(int i = 0; i < n; ++i) p[i].in();
printf("Case #%d:\n", ++k);
work();
}
}