2013年福建省程序设计竞赛省赛题解
2016-08-17       个评论    来源：qwb的博客
我要投稿

Problem 2140 Forever 0.5传送门

```#include
#include
#include
#include
#include
#include
#include
#define FIN freopen("in.txt","r",stdin);
using namespace std;
typedef unsigned int LL;
const int maxn = 500004;
//int n;
char a[22][22];
int n;
int v[22];
LL color[22][22];
LL ans[1 << 22];
//int vis[(1 << 18) + 1][18];
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
if(n <= 3){
printf("No\n");
continue;
}
printf("Yes\n");
printf("%.6lf %.6lf\n",0.0,0.0);
printf("%.6lf %.6lf\n",0.5,sqrt(3.0)/2.0);
printf("%.6lf %.6lf\n",sqrt(3.0)/2.0,0.5);
printf("%.6lf %.6lf\n",1.0,0.0);
double now = sqrt(3.0)/2.0 + 0.001;
for(int i = 5; i <= n; i++){
printf("%.6lf %.6lf\n",now,sqrt(1.0 - now * now));
now += 0.001;
}
//printf("")
}
return 0;
}```

Problem 2141 Sub-Bipartite Graph传送门

```#include
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define fuck(x) cout<<"["<PII; const int MX = 1e2 + 5; int A[2][MX], sz[2]; int G[MX][MX]; int main() { int T; //FIN; scanf("%d", &T); while(T--) { int n, m; sz[0] = sz[1] = 0; memset(G, 0, sizeof(G)); scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); G[u][v]++; G[v][u]++; } for(int i = 1; i <= n; i++) { int a = 0, b = 0; for(int j = 1; j <= sz[0]; j++) { int v = A[0][j]; if(G[i][v]) a++; } for(int j = 1; j <= sz[1]; j++) { int v = A[1][j]; if(G[i][v]) b++; } if(a > b) A[1][++sz[1]] = i; else A[0][++sz[0]] = i; } printf("%d", sz[0]); for(int i = 1; i <= sz[0]; i++) printf(" %d", A[0][i]); printf("\n%d", sz[1]); for(int i = 1; i <= sz[1]; i++) printf(" %d", A[1][i]); printf("\n"); } return 0; }```

Problem 2142 Center of a Tree传送门

dp[u][i]=∏u?>v(dp[v][i?1]+1)

∑i=1n∑u?>v,j=1子节点个数(cnt1[i][j]?cnt2[i][j])?(dp[v][i]?dp[v][i?1])?suf[i][j+1]

```#include

Problem 2143 Board Game传送门

```#include

Problem 2144 Shooting Game传送门

(PS：好像fzu跑的比较慢，这份代码必须要用MS C++提交才能过

```#include
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define fuck(x) cout<<"["<PII; const int MX = 1e5 + 5; int n; double R; struct Seg { double l, r; bool operator<(const Seg &P)const { return r < P.r; } } S[MX]; int main() { //FIN; int T, ansk = 0; scanf("%d", &T); while(T--) { printf("Case %d: ", ++ansk); scanf("%d%lf", &n, &R); int sz = 0, ans1 = 0, ans2 = 0; for(int i = 1; i <= n; i++) { double a, b, c, dx, dy, dz; scanf("%lf%lf%lf", &a, &b, &c); scanf("%lf%lf%lf", &dx, &dy, &dz); double A = dx * dx + dy * dy + dz * dz; double B = 2 * a * dx + 2 * b * dy + 2 * c * dz; double C = a * a + b * b + c * c - R * R; double D = B * B - 4 * A * C; if(D >= 0) { D = sqrt(D); double t1 = (-B - D) / (2 * A), t2 = (-B + D) / (2 * A); if(t1 > t2) swap(t1, t2); if(t2 >= 0) { ans1++; t1 = max(t1, 0.0); S[++sz].l = t1; S[sz].r = t2; } } } double pos = -1; sort(S + 1, S + 1 + sz); for(int i = 1; i <= sz; i++) { if(S[i].l <= pos && pos <= S[i].r) continue; else pos = S[i].r, ans2++; } printf("%d %d\n", ans1, ans2); } return 0; }```

Problem 2145 Rock-Paper-Scissors Game传送门

```int s = 11;
void print(int x) {
for(int i = 10; i >= 0; i--) {
printf("%d", (x >> i & 1));
}
puts("");
}
for(int i = s; i; i = (i - 1)&s) {
print(i);
}```

Problem 2146 Easy Game传送门

```#include
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define fuck(x) cout<<"["<PII; const int MX = 1e5 + 5; const int INF = 0x3f3f3f3f; char S[MX]; int main() { //FIN; int T, ansk = 0; scanf("%d", &T); while(T--) { printf("Case %d: ", ++ansk); scanf("%s", S); int n = strlen(S); printf("%s\n", n % 2 == 0 ? "Even" : "Odd"); } return 0; }```

Problem 2147 A-B Game传送门

```#include
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define fuck(x) cout<<"["<PII; const int MX = 1e5 + 5; const int INF = 0x3f3f3f3f; char S[MX]; int solve(LL A, LL B) { int ret = 0; while(A > B) { LL x; if(A % 2 == 0) x = A / 2 + 1; else x = (A + 1) / 2; A = A - (A % x); ret++; } return ret; } int main() { //FIN; int T, ansk = 0; scanf("%d", &T); while(T--) { printf("Case %d: ", ++ansk); LL A, B; scanf("%I64d%I64d", &A, &B); printf("%d\n", solve(A, B)); } return 0; }```

Problem 2148 Moon Game传送门

```#include
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define fuck(x) cout<<"["<PII; const int MX = 1e3 + 5; const int INF = 0x3f3f3f3f; struct Node { double x, y; bool operator<(const Node &b)const { if(x == b.x) return y < b.y; return x < b.x; } } P[MX], R[MX], S[MX]; double cross(Node a, Node b, Node c) { return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y); } int convex(int n, Node P[]) { int m = 0, k; sort(P, P + n); for(int i = 0; i < n; i++) { while(m > 1 && cross(R[m - 1], P[i], R[m - 2]) <= 0) m--; R[m++] = P[i]; } k = m; for(int i = n - 2; i >= 0; i--) { while(m > k && cross(R[m - 1], P[i], R[m - 2]) <= 0) m--; R[m++] = P[i]; } if(n > 1) m--; return m; } int main() { // FIN; int T, ansk = 0; scanf("%d", &T); while(T--) { printf("Case %d: ", ++ansk); int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%lf%lf", &P[i].x, &P[i].y); } int ans = 0; for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) { for(int k = j + 1; k <= n; k++) { for(int l = k + 1; l <= n; l++) { S[0] = P[i]; S[1] = P[j]; S[2] = P[k]; S[3] = P[l]; if(convex(4, S) == 4) ans++; } } } } printf("%d\n", ans); } return 0; }```

Problem 2149 Reverse Game传送门

Y[i]=(i?1)?(n?i)+n?1

W[i]=∑jn[Y[i]?P[j?>i]

1. 最重要的优化：我们能发现这个概率矩阵收敛的很快，第500次之后，就算当n=100，概率的变化也小于10?4，所以我们直接令e=min(e,512)
2. 我们能发现概率左边和右边是对称的，所以我们可以只取一半的矩阵，这样矩阵乘法的复杂度就只有O(50?50?50)了，一下子快了8倍！
3. fzu没有开O2优化，所以用vector之类的会非常慢，改成普通数组的快了不止一点点。

```#include
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define fuck(x) cout<<"["<PII; const int MX = 1e2 + 5; struct matrix { int m, n; double a[105][105]; void init(int _m, int _n) { m = _m; n = _n; for(int i = 0; i <= m; i ++) for(int j = 0; j <= n; j ++) a[i][j] = 0; } matrix operator * (const matrix &p) { matrix c; c.init(m, p.n); for(int i = 1; i <= m; i ++) for(int j = 1; j <= p.n; j ++) for(int k = 1; k <= n; k ++) c.a[i][j] += a[i][k] * p.a[k][j]; return c; } matrix operator ^ (const LL &_x) { matrix b, t = *this; b.init(m, n); LL x = _x; for(int i = 1; i <= m; i ++) b.a[i][i] = 1; while(x) { if(x & 1) b = b * t; t = t * t; x >>= 1; } return b; } }; int n; LL m; int S[MX]; double offer[MX]; matrix save[MX]; bool vis[MX]; inline int TO(int n, int x) { int ret; if(x > (n + 1) / 2) ret = n - x + 1; else ret = x; return ret; } void presolve(int n) { if(vis[n]) return; int nn = (n + 1) / 2; matrix A; A.init(nn, nn); double p = 1.0 / (n * (n - 1) / 2); for(int l = 2; l <= n; l++) { for(int i = 1; i + l - 1 <= n; i++) { int ed = i + l - 1; for(int k = 1; k <= l; k++) { if(i + k - 1 <= nn) A.a[i + k - 1][TO(n, ed + 1 - k)] += p; } for(int k = 1; k <= n; k++) { if(i <= k && k <= i + l - 1) continue; if(k <= nn) A.a[k][TO(n, k)] += p; } } } save[n] = A; vis[n] = 1; /* A = A ^ 2; for(int i = 1; i <= A.m; i++) { for(int j = 1; j <= A.n; j++) fuck(A.a[i][j]); puts(""); }*/ } double solve() { matrix A = save[n]; A = A ^ m; memset(offer, 0, sizeof(offer)); int nn = (n + 1) / 2; for(int i = 1; i <= nn; i++) { matrix B; B.init(nn, 1); B.a[TO(n, i)][1] = 1; B = A * B; for(int j = 1; j <= n; j++) { double tmp; tmp = (j - 1) * (n - j) + n - 1; offer[i] += tmp * B.a[TO(n, j)][1]; } } for(int i = 1; i <= nn; i++) { if(i != nn || n % 2 == 0) offer[i] /= 2; offer[n - i + 1] = offer[i]; } double ans = 0; sort(S + 1, S + 1 + n); sort(offer + 1, offer + 1 + n); for(int i = 1; i <= n; i++) { ans += offer[i] * S[i]; } int tot = n * (n - 1) / 2; return ans / tot; } int main() { //int tim = clock(); int T; //FIN; scanf("%d", &T); for(int t = 1; t <= T; t++) { scanf("%d%I64d", &n, &m); m = min(m, 512LL); presolve(n); for(int i = 1; i <= n; i++) scanf("%d", &S[i]); printf("%.12f\n", solve()); //printf("time:%dms\n", clock() - tim); } return 0; }```

Problem 2150 Fire Game传送门

```#include
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define fuck(x) cout<<"["<PII; const int MX = 10 + 5; const int INF = 0x3f3f3f3f; typedef bitset<105> BT; int n, m; int id[MX][MX], sz; PII Rank[MX * MX]; int tim[MX][MX]; char S[MX][MX]; int dist[][2] = {{0, 1}, {0, -1}, {1, 0}, { -1, 0}}; int solve(int u, int v) { memset(tim, INF, sizeof(tim)); int x, y, nx, ny; queueQ; x = Rank[u].first; y = Rank[u].second; Q.push(Rank[u]); tim[x][y] = 0; if(u != v) { x = Rank[v].first; y = Rank[v].second; Q.push(Rank[v]); tim[x][y] = 0; } int tot = 0; while(!Q.empty()) { PII ftp = Q.front(); Q.pop(); x = ftp.first, y = ftp.second; tot++; if(tot == sz) return tim[x][y]; // if(u == 2 && v == 2) printf("[%d,%d]\n", x, y); for(int k = 0; k < 4; k++) { nx = x + dist[k][0]; ny = y + dist[k][1]; if(nx < 1 || nx > n || ny < 1 || ny > m || S[nx][ny] == '.') continue; //if(u==2&&v==2) printf("[%d,%d]",nx,ny); if(tim[x][y] + 1 < tim[nx][ny]) { tim[nx][ny] = tim[x][y] + 1; Q.push(PII(nx, ny)); } } } return INF; } int main() { //FIN; int T, ansk = 0; scanf("%d", &T); while(T--) { printf("Case %d: ", ++ansk); sz = 0; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%s", S[i] + 1); for(int j = 1; j <= m; j++) { if(S[i][j] == '#') { id[i][j] = sz; Rank[sz] = PII(i, j); sz++; } } } int ans = INF; for(int i = 0; i < sz; i++) { for(int j = i; j < sz; j++) { ans = min(ans, solve(i, j)); } } printf("%d\n", ans == INF ? -1 : ans); } return 0; }```

Problem 2151 OOXX Game传送门

```#include
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define fuck(x) cout<<"["<PII; const int MX = 2e2 + 5; const int INF = 0x3f3f3f3f; char S[MX]; int main() { //FIN; int T, ansk = 0; scanf("%d", &T); while(T--) { printf("Case %d: ", ++ansk); int n, m, cnt = 0; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%s", S + 1); for(int j = 1; j <= m; j++) { if(S[j] == 'O') cnt++; } } printf("%s\n", cnt % 2 ? "Maze" : "Fat brother"); } return 0; }```