# 某岛

… : "…アッカリ～ン . .. . " .. .
August 24, 2015

## C

It is guaranteed that, for any pair of rooms in the office, there exists exactly one route between the two rooms''

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define DWN_1(i, b, a) for (int i=b;i>=a;--i)
#define RST(A) memset(A, 0, sizeof(A))
#define FLC(A, x) memset(A, x, sizeof(A))

typedef long long LL;
const int MOD = int(1e9) + 7;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
const int N = int(50) + 9;

char G[N][N];
int a[N][N], b[N][N], c[N][N], vis[N][N], last[N][N];
int n, m, l, T, Z;

bool inGrid(int x, int y){
return x >= 0 && y >= 0 && x < n && y < m;
}

bool dfs(int x, int y, int tx, int ty, int t, int tt){

if (vis[x][y] == tt || G[x][y] == '#') return false;
bool flag = false; vis[x][y] = tt;

if (x == tx && y == ty){
flag = true;
T = t;
}
else{
REP(i, 4){
int xx = x + dx[i], yy = y + dy[i];
if (!inGrid(xx, yy)) continue;
flag |= dfs(xx, yy, tx, ty, t+1, tt);
}
}

if (flag){
if (last[x][y] == -1) Z += b[x][y] + c[x][y];
else Z += min(b[x][y] + c[x][y], a[x][y] * (t - last[x][y]));
last[x][y] = t;
}
return flag;
}

int main(){

#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

while (~scanf("%d%d%d", &n, &m, &l)){
REP(i, n) scanf("%s", G[i]);
REP(i, n) REP(j, m) scanf("%d", &a[i][j]);
REP(i, n) REP(j, m) scanf("%d", &b[i][j]);
REP(i, n) REP(j, m) scanf("%d", &c[i][j]);

int x, y; RST(vis); FLC(last, -1); Z = T = 0; REP(i, l){
int xx, yy; scanf("%d %d", &xx, &yy);
if (i) dfs(x, y, xx, yy, T, i);
x = xx, y = yy;
}
printf("%d\n", Z);
}
}


## D

... 数据范围很小。。。并没有二分的必要。。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define DWN_1(i, b, a) for (int i=b;i>=a;--i)
#define RST(A) memset(A, 0, sizeof(A))
#define FLC(A, x) memset(A, x, sizeof(A))

typedef double DB;

const int N = int(1e2) + 9, M = int(5e1) + 9;
DB p[N][M], sp[N][M], t[N], t0[N];
int n, m, l;

DB f(int i, DB ti){
DB z = 1; REP(j, n) if (i != j){
if (t0[j] + m*t[j] <= ti) return 0;
REP(k, m+1) if (t0[j] + k*t[j] > ti){
z *= (1 - sp[j][k]);
break;
}
}
return z;
}

int main(){

#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

while (~scanf("%d%d%d", &n, &m, &l)){

RST(p); REP(i, n){
int _p, v; scanf("%d%lf%d", &_p, &t[i], &v); t0[i] = (DB) l / v; DB pp = (DB) _p / 100;

p[i][0] = 1; DO(m){
DWN_1(j, m, 1) p[i][j] = p[i][j-1] * pp + p[i][j] * (1-pp);
p[i][0] = p[i][0] * (1-pp);
}

REP_1(j, m) sp[i][j] = sp[i][j-1] + p[i][j-1];
}

REP(i, n){
DB z = 0; REP(j, m+1) z += p[i][j] * f(i, t0[i] + t[i]*j);
printf("%.9f\n", z);
}
}
}


## I

... 因为数据都是整数。。可以尝试。。。小角度枚举。。。

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define REP(i, n) for (int i=0;i<n;++i)
#define MP make_pair
#define PB push_back

typedef double DB;
typedef long long LL;

const DB EPS = 1e-8;
const DB PI = acos(-1);
const DB gg = 9.8;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

inline void checkMin(int &a, int b){
if (b < a) a = b;
}

inline int sgn(double x){
return x < -EPS ? -1 : x > EPS;
}

const int N = int(1e2) + 9;
int n, l[N], b[N], r[N], t[N];
int X, Y; DB V; int low;

inline DB y(DB a, DB x) {
DB t = x/(V*cos(a));
return V*sin(a)*t - 0.5*gg*t*t;
}

inline DB getM(DB a){
DB t = V*sin(a)/gg;
return V*cos(a)*t;
}

bool ck(DB a) {

DB h = y(a, X); if (sgn(h-Y) < 0 || sgn(h-low) > 0 ) return false;
DB mx = getM(a), my = y(a, mx);

REP(i, n){

DB h1 = y(a, l[i]), h2 = y(a, r[i]);

if (l[i] <= mx && mx <= r[i]){
if (!(h1 <= b[i] && h2 <= b[i] && my <= b[i] || h1 >= t[i] && h2 >= t[i] && my >= t[i])) return false;
}
else{
if (!(h1 <= b[i] && h2 <= b[i] || h1 >= t[i] && h2 >= t[i])) return false;
}
}
return true;
}

bool ck() {

REP(i, n){
if (l[i] == 0 && b[i] == 0) return false;
if (l[i] <= X && X <= r[i]  && b[i] <= Y && Y <= t[i]) return false;
}

DB d = PI/2/10000;
for (DB a=d;a<=PI/2;a+=d) if (ck(a)) return true;
return false;
}

int main() {
//freopen("in.txt", "r", stdin);
while (~scanf("%d%lf%d%d", &n, &V, &X, &Y)) {
low = INF; REP(i, n){
scanf("%d%d%d%d", &l[i], &b[i], &r[i], &t[i]);
if (l[i] > X){
--i; --n;
continue;
}
if (r[i] >= X){
if (b[i] >= Y) checkMin(low, b[i]);
r[i] = X;
}
}
puts(ck() ? "Yes" : "No");
}
}


## I

DAG DP。。。。。不错哦。。。
dp[][][]。。。 从中间开始向两边不断添加回文串， 状态时 (左边 ID，右边 ID，多出来的长度)。。。 正数表示右边多。

、、、http://www.shuizilong.com/house/archives/andrew-stankevichs-contest-2/ ？
、、、http://m.blog.csdn.net/blog/u010709592/39025279？

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;

#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define DWN_1(i, b, a) for (int i=b;i>=a;--i)
#define ECH(it, A) for (__typeof(A.begin()) it = A.begin(); it != A.end(); ++it)
#define RST(A) memset(A, 0, sizeof(A))
#define FLC(A, x) memset(A, x, sizeof(A))
#define PB push_back

template<class T> void checkMax(T &a, T b){
if (b > a) a = b;
}

typedef double DB;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;

const int N = int(1e2) + 9, M = 20;

int vis[N][N][M+M+1]; int dp[N][N][M+M+1];
int n, m;

int f(int i0, int i1, int j){

int &z = dp[i0][i1][j+M], &v = vis[i0][i1][j+M];

if (v == 3) return z;

if (v == 1){
v = 2;
return -INF;
}

v = 1; z = j ? -INF : 0;

if (j > 0){
int i00 = *it; bool ok = true;

int up = min(j, slen[i00]); REP(k, up){
if (str[i00][slen[i00]-1-k] != str[i1][slen[i1]-j+k]){
ok = false;
break;
}
}

if (!ok) continue;
checkMax(z, f(i00, i1, j-slen[i00]) + slen[i00]);
}
}
else{

j = -j;

int i11 = *it; bool ok = true;

int up = min(j, slen[i11]); REP(k, up){
if (str[i0][j-1-k] != str[i11][k]){
ok = false;
break;
}
}

if (!ok) continue;
checkMax(z, f(i0, i11, slen[i11]-j) + slen[i11]);
}
}

if (z >= 0 && v == 2) z = INF;
v = 3;

//if (z >= 0)
//cout << ")" << i0 << " " << i1 << " " << j << " " << v << " "<< z << endl;
//cout << i0 << " " <<i1 << " " << j << ": " << z << " "<<v << endl;
return z;
}

bool isPalindrome(int i0, int l, int r){
int len = r-l;
REP(i, len/2) if (str[i0][l+i] != str[i0][r-1-i]) return false;
return true;
}

int main(){

#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

while (~scanf("%d%d", &n, &m)){

REP(i, n){
slen[i] = strlen(str[i]);
}

DO(m){
int a, b; scanf("%d%d", &a, &b); --a, --b;