频道栏目
首页 > 考试 > 其他 > 正文

2013年福建省程序设计竞赛省赛题解

2016-08-17 09:43:58         来源:qwb的博客  
收藏   我要投稿

Problem 2140 Forever 0.5传送门
思路:构造。首先小于4无解。
大于4的情况,前4个点作为ABCD,之后的点全部放在AD?上就行了
复杂度:O(n)
这里写图片描述

#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传送门
思路:我们依次考虑n个点,假如当前正在考虑第i个节点。
我们算出第i个节点与前i-1个点组成的二分图的左右部分连的边分别是多少。然后看加到哪一边最优,那么就放到哪一边。最后得到的二分图中的边一定会>=m/2
我们稍微可以证明一下:对于第i个节点,往左边加,和右边加,最后它选择的是加的边最大的那个。也就是说,前i-1个节点,与第i个节点,假设他们中间有k条边,那么经过这一次操作,我肯定能多得到>=k条边。对于第i个节点与后面的点所连的边,在考虑后面节点时,会再计算,所以不需要往后面考虑。所以我们每次选的边都大于等这个点上边的一半,所以最后总边数当然会>=m/2
复杂度:O(n+m)

#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传送门
先求出中心点。通过两次DFS很容易求出来。
如果有2个中心,根据常识,两个中心肯定中间有一条边隔开的。
我们用dp[i][j]记录节点i的子树中,高度均<=j的点的子树方案个数。
那么dp[i][j]?dp[i][j?1]就表示u为根节点,高度为j的子树方案个数。
dp[u][i]=∏u?>v(dp[v][i?1]+1)

如果有两个中心,我们认为两个中心中间那条边是断开的。然后我们当成两棵独立的子树来考虑。设两个根节点分别是rt1,rt2。对于这种情况答案就等于∑i=1n(dp[rt1][i]?dp[rt1][i?1])?(dp[rt2][i]?dp[rt2][i?1])
如果只有一个中心,这种情况下维护起来就稍微略有麻烦。令cnt1[i][j]表示前j个子节点,高度<=i的子树方案数,cnt2[i][j]表示前j个子节点高度<=i?1的子树方案数。suf[i][j]表示后i个子节点,高度<=j?1的子树方案数。那么答案就等于
∑i=1n∑u?>v,j=1子节点个数(cnt1[i][j]?cnt2[i][j])?(dp[v][i]?dp[v][i?1])?suf[i][j+1]
复杂度:O(n2)

#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; const int mod = 10086; int Head[MX], erear; struct Edge { int v, nxt; } E[MX * 2]; void edge_init() { erear = 0; memset(Head, -1, sizeof(Head)); } void edge_add(int u, int v) { E[erear].v = v; E[erear].nxt = Head[u]; Head[u] = erear++; } int n, root_dep; PII root; int dmax[MX], dmax2[MX], did[MX]; LL dp[MX][MX]; int DFS1(int u, int f) { dmax[u] = dmax2[u] = 0; did[u] = -1; for(int i = Head[u]; ~i; i = E[i].nxt) { int v = E[i].v; if(v == f) continue; int t = DFS1(v, u) + 1; if(t > dmax[u]) dmax2[u] = dmax[u], dmax[u] = t, did[u] = v; else if(t > dmax2[u]) dmax2[u] = t; } return dmax[u]; } void DFS2(int u, int f, int pre) { int dep = max(max(dmax[u], dmax2[u]), pre); if(dep < root_dep) { root_dep = dep; root = PII(u, -1); } else if(dep == root_dep) { if(root.first == -1) root.first = u; else root.second = u; } for(int i = Head[u]; ~i; i = E[i].nxt) { int v = E[i].v; if(v == f) continue; if(did[u] != v) DFS2(v, u, max(dmax[u], pre) + 1); else DFS2(v, u, max(dmax2[u], pre) + 1); } } void DFS3(int u, int f) { dp[u][0] = 0; for(int i = 1; i <= n; i++) dp[u][i] = 1; for(int i = Head[u]; ~i; i = E[i].nxt) { int v = E[i].v; if(v == f) continue; DFS3(v, u); for(int j = 1; j <= n; j++) { dp[u][j] = dp[u][j] * (dp[v][j - 1] + 1) % mod; } } } int get_ch(int u, int f, vector &ch) { int sz = 0; for(int i = Head[u]; ~i; i = E[i].nxt) { int v = E[i].v; if(v == f) continue; sz++; } ch.resize(sz + 1); sz = 0; for(int i = Head[u]; ~i; i = E[i].nxt) { int v = E[i].v; if(v == f) continue; ch[++sz] = v; } return sz; } int solve() { LL ans; if(root.second != -1) { ans = 0; DFS3(root.first, root.second); DFS3(root.second, root.first); for(int i = 1; i <= n; i++) { ans = ans + (dp[root.first][i] - dp[root.first][i - 1]) * (dp[root.second][i] - dp[root.second][i - 1]) % mod; ans %= mod; } } else { ans = 1; int rt = root.first; DFS3(rt, -1); vector ch; vector suf; int sz = get_ch(rt, -1, ch); suf.resize(sz + 2); for(int i = 1; i <= n; i++) { LL cnt1 = 1, cnt2 = 1; suf[sz + 1] = 1; for(int j = sz; j >= 1; j--) { int v = ch[j]; suf[j] = suf[j + 1] * (dp[v][i - 1] + 1) % mod; } for(int j = 1; j <= sz; j++) { int v = ch[j]; ans = (ans + (cnt1 - cnt2) * (dp[v][i] - dp[v][i - 1]) % mod * suf[j + 1] % mod) % mod; cnt1 = cnt1 * (dp[v][i] + 1) % mod; cnt2 = cnt2 * (dp[v][i - 1] + 1) % mod; } } } ans = (ans + mod) % mod; return ans; } int main() { //FIN; int T, ansk = 0; scanf("%d", &T); while(T--) { scanf("%d", &n); edge_init(); for(int i = 1; i <= n - 1; i++) { int u, v; scanf("%d%d", &u, &v); edge_add(u, v); edge_add(v, u); } root_dep = INF; root = PII(-1, -1); DFS1(1, -1); DFS2(1, -1, 0); printf("Case %d: %d\n", ++ansk, solve()); } return 0; }

Problem 2143 Board Game传送门
思路:这种棋盘两个相邻点的方式,其实就是一种二分图。如果我们把(i+j)%2来把点分类,那么相当于棋盘被黑白染色,最后就形成了一个二分图。我们可以发现,两个相邻的棋子刚好在二分图的两侧。
所以我们把超级汇点S连奇点,把偶点连超级汇点T,上面这个证明了这种建图的可行性。
对于两个相邻的点,我们建一条边,容量为INF,费用为0
对于所有的奇数点u,假如坐标为(i,j),我们连k条边S?>u,容量为1,第t条边费用为2?t?1?2?A[i][j],相当于把平方和展开了。
对于所有的偶数点u,假如左边为(i,j),我们连k条边u?>T,容量为1,第t条边费用为2?t?1?2?A[i][j]
然后我们跑费用流,把最后的ans等于 最小费用+∑in∑jmA[i][j]2
还要注意的是,这个应该是可行流,并不是要求最大流,而是要求费用最小。
这里我们有两种修改方法。
方案一:把超级汇点S连向S2,容量为INF,费用为0。把S2连向T,容量为INF,费用为0。然后用现在的S2代替上面的S点即可。
方案二:在增广时,如果发现费用的最短路>=0,那么此时后面的增广只会使费用增大,所以我们直接返回停止增广。
复杂度:O(玄学)


#include 
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define fuck(x) cout<<"["<PII; const int MX = 400 + 5; const int MM = 1e4 + 5; const int INF = 0x3f3f3f3f; struct Edge { int to, next, cap, flow, cost; Edge() {} Edge(int _to, int _next, int _cap, int _flow, int _cost) { to = _to; next = _next; cap = _cap; flow = _flow; cost = _cost; } } E[MM]; int Head[MX], tol; int pre[MX]; int dis[MX]; bool vis[MX]; int N; void init(int n) { tol = 0; N = n + 2; memset(Head, -1, sizeof(Head)); } void edge_add(int u, int v, int cap, int cost) { E[tol] = Edge(v, Head[u], cap, 0, cost); Head[u] = tol++; E[tol] = Edge(u, Head[v], 0, 0, -cost); Head[v] = tol++; } bool spfa(int s, int t) { queueq; for (int i = 0; i < N; i++) { dis[i] = INF; vis[i] = false; pre[i] = -1; } dis[s] = 0; vis[s] = true; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for (int i = Head[u]; i != -1; i = E[i].next) { int v = E[i].to; if (E[i].cap > E[i].flow && dis[v] > dis[u] + E[i].cost) { dis[v] = dis[u] + E[i].cost; pre[v] = i; if (!vis[v]) { vis[v] = true; q.push(v); } } } } if(dis[t] >= 0) return false; if (pre[t] == -1) return false; else return true; } int minCostMaxflow(int s, int t, int &cost) { int flow = 0; cost = 0; while (spfa(s, t)) { int Min = INF; for (int i = pre[t]; i != -1; i = pre[E[i ^ 1].to]) { if (Min > E[i].cap - E[i].flow) Min = E[i].cap - E[i].flow; } for (int i = pre[t]; i != -1; i = pre[E[i ^ 1].to]) { E[i].flow += Min; E[i ^ 1].flow -= Min; cost += E[i].cost * Min; } flow += Min; } return flow; } int n, m, p; int A[20][20]; inline int ID(int x, int y) { return (x - 1) * m + y; } int dic[][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; int main() { int T, ansk = 0; //FIN; scanf("%d", &T); while(T--) { scanf("%d%d%d", &n, &m, &p); int op = 0, ed = n * m + 1; init(ed + 1); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { scanf("%d", &A[i][j]); if((i + j) % 2 == 0) { for(int k = 0; k < 4; k++) { int nx = i + dic[k][0], ny = j + dic[k][1]; if(nx < 1 || nx > n || ny < 1 || ny > m) continue; edge_add(ID(i, j), ID(nx, ny), INF, 0); } } } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if((i + j) % 2 == 0) { //入 for(int k = 1; k <= p; k++) edge_add(op, ID(i, j), 1, 2 * k - 1 - 2 * A[i][j]); } else { for(int k = 1; k <= p; k++) edge_add(ID(i, j), ed, 1, 2 * k - 1 - 2 * A[i][j]); } } } int cost; minCostMaxflow(op, ed, cost); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) cost += A[i][j] * A[i][j]; } printf("Case %d: %d\n", ++ansk, cost); } return 0; }

Problem 2144 Shooting Game传送门
思路:我们通过设未知数t,表示蚊子恰好飞入范围时的时间。那么可以解出这个二元一次方程组。不过要注意,如果解中有<0的,应该取等于0。
那么我们就处理出了一个蚊子飞入飞出的时间区间。那么有多少个这样的合法区间,就是第一部分的答案。
第二部分的答案就转换成了,我至少需要多少个点,才能把这些区间全部覆盖掉,所以变成了一道经典的贪心题。
我们按区间的右端点排序,之后记录上一次选择攻击的时间,记为p。p初始化为0。然后我们依次枚举区间,如果p不在这个区间内,那么我们就选这个区间的右端点作为开枪时间,把答案+1,并把p记录为当前区间右端点,依次操作完sz个区间。
(PS:好像fzu跑的比较慢,这份代码必须要用MS C++提交才能过
复杂度O(nlogn)

#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传送门
思路:状压概率dp。
这里有一种很神奇的枚举状态子集的方法。

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);
}

你能惊讶的发现这段代码能枚举出s的所有子集!
那么按上面这种方法我们就能做到从子集转移状态到本身了。
枚举的复杂度为O(3n)
代码:待补充…


Problem 2146 Easy Game传送门
思路:判断字符串奇偶性
复杂度:O(|S|)

#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传送门
思路:贪心,我们每次都让A变成一半,那么很快就能小于等于B了
复杂度:O(logA)

#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传送门
思路:直接n4枚举出所有的四边形,然后再用凸包检查四边形是否是凸四边形即可。
复杂度:O(n4)

#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传送门
思路:首先,我们预处理出最刚开始在位置i,经过一次翻转后,后来在位置j的概率。这个很容易通过n^3枚举来完成。
题目需要翻转E次,有了这个概率矩阵后,我们直接利用快速幂,就能求出翻转E次有的矩阵了。有了这个矩阵,就相当于我们知道了最刚开始在位置i,经过E次翻转后,后来在位置j的概率。

设S为原位置对应的数字大小
所以第i个位置上,后来的期望值为∑jnS[j]?P[j?>i]
我们再求出,第i个位置,对最后答案的贡献系数,即随便选一个区间[L,R](L,位置i出现在这个区间中的概率,记为Y[i]
Y[i]=(i?1)?(n?i)+n?1
那么,最后的答案为∑inY[i]?∑jnS[j]?P[j?>i]n?(n?1)/2
然后我们转换一下,就能得到原位置i的数字对答案的贡献系数,记为W[i]
W[i]=∑jn[Y[i]?P[j?>i]
最后的答案等于∑W[i]?S[i]n?(n?1)/2
所以,我们只需要算出W数组,并从小到大排序,然后把S数组也从小到大排序。然后让他们一一对应,答案就是最大辣。
但是仅仅这样还是通过不了的,这里还有2种优化。
1. 最重要的优化:我们能发现这个概率矩阵收敛的很快,第500次之后,就算当n=100,概率的变化也小于10?4,所以我们直接令e=min(e,512)
2. 我们能发现概率左边和右边是对称的,所以我们可以只取一半的矩阵,这样矩阵乘法的复杂度就只有O(50?50?50)了,一下子快了8倍!
3. fzu没有开O2优化,所以用vector之类的会非常慢,改成普通数组的快了不止一点点。
复杂度:O(n3?min(e,512))

#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传送门
思路:先找出所有的草坪,大小记为sz,然后O(sz^2)枚举出哪两个作为火源,然后同时丢入队列跑BFS,看最后访问了sz个点时的是时间是多少,取最小值即可。
复杂度:O(n3m3)

#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传送门
思路:很明显谁赢只跟地图中O出现的次数的奇偶性有关。
复杂度:O(n?m)

#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; }
上一篇:POJ1054 The Troublesome Frog
下一篇:HDU1026 Ignatius and the Princess I
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站