http://acm.bnu.edu.cn/v3/contest_show.php?cid=6626
http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?volumeNo=23
http://acm-icpc.aitea.net/index.php?2011%2FPractice%2F%E5%A4%8F%E5%90%88%E5%AE%BF%2F%E8%AC%9B%E8%A9%95
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，多出来的长度)。。。 正数表示右边多。 然后用记忆化搜索... 在这个 DAG 上 DP。。有环的话返回 -1。。 、、、https://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;
char str[N][M+1]; int slen[N]; VI adj[N], radj[N];
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){
ECH(it, radj[i0]){
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;
ECH(it, adj[i1]){
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){
scanf("%s", str[i]); adj[i].clear(), radj[i].clear();
slen[i] = strlen(str[i]);
}
DO(m){
int a, b; scanf("%d%d", &a, &b); --a, --b;
adj[a].PB(b); radj[b].PB(a);
}
FLC(dp, -1); RST(vis); int z = 0; REP(i, n) REP(j, slen[i]+1){
if (isPalindrome(i, 0, slen[i]-j) && f(i, i, j) >= 0) checkMax(z, f(i, i, j) + slen[i]);
if (isPalindrome(i, j, slen[i]) && f(i, i, -j) >= 0) checkMax(z, f(i, i, -j) + slen[i]);
}
if (z >= INF) z = -1;
printf("%d\n", z);
}
}
