【题解】糖果_解数学题

题目描述

　　你和朋友Shary玩一个游戏：在一个无环的、无向的图中，每个节点可以放一些糖果。每次Shary可以从糖果数不少于2的节点上拿2个糖果，吃掉1个，并把另一个糖果放到相邻的某个节点去。如果在某个时候，目标节点T上有了糖果，游戏结束，Shary赢。

　　如果你设计的初始状态，无论如何Shary都赢不了，则Shary输。

　　给定一个图，你能赢的方案中可以放的最多糖果数是多少？如果答案数超过2*10^9，只要输出-1即可。

输入格式

　　(多组数据形式)

　　第1行：一个不超过5 的正整数K，表示有K组任务。

　　下面有K组数据，每组数据格式为：

　　第一行有2个正整数：N 和 T 。N表示节点数，节点编号从0到N-1，N不超过50；T是目标节点编号，范围在[0, N-1]。

　　下面有N行，每行有N个字符，每个字符是”Y”或”N”。第i行第j个字符如果是”Y”就表示第i点和第j点有边相连，如果是”N”就表示第i点和第j点没有边相连。保证图上没有环。

输出格式

　　一个整数。

输入样例

3 2

NYN

YNY

NYN

4 1

NYYY

YNNN

7 0

NYNNNYN

YNYNYNN

NYNYNNN

NNYNNNN

NYNNNNN

YNNNNNY

NNNNNYN

输出样例

题解

　　我们可以把题目中的图看作一棵树，则$t$为根节点。

　　容易想到，如果要让$t$为$0$，则这个点的出点（深度为$2$）的点最多为$1$，出点的出点（深度为$3$)最多为$3$，出点的出点的出点（深度为$4$）最多为$7$……深度为$n$的点最多为$2n-1$。

　　而一组出点中，如果有一个点为$2n-1$，则其他点都为$1$。

　　根据贪心的得，我们要把$2n-1$继承给当前点为根节点的子树的长链。暴力dfs即可。

　　注意判断$t$是否能到达任意点，如果不能，则初始状态可以放正无穷个糖果。

#include <iostream> #include <cstring> #define MAX_N (50 + 5) using namespace std; struct Edge { int to; int next; }; const long long lim = LL; int T; int n, root; char l[MAX_N][MAX_N]; int h[MAX_N]; Edge e[MAX_N]; int cnt; int dep[MAX_N]; long long ans; void Init() { memset(h, 0, sizeof h); memset(e, 0, sizeof e); memset(dep, 0, sizeof dep); cnt = ans = 0; return; } inline void Make_Edge(int u, int v) { e[++cnt].to = v; e[cnt].next = h[u]; h[u] = cnt; return; } void Build(int u, int p) { for(register int v = 1; v <= n; ++v) { if(l[u][v] != 'Y' || v == p) continue; Make_Edge(u, v); Build(v, u); dep[u] = max(dep[u], dep[v]); } ++dep[u]; return; } void DFS(int u, long long val) { int v, p = 0; for(register int i = h[u]; i; i = e[i].next) { v = e[i].to; if(dep[p] < dep[v]) p = v; } if(!p) { ans += val; return; } DFS(p, val << 1 | 1LL); for(register int i = h[u]; i; i = e[i].next) { v = e[i].to; if(p != v) DFS(v, 1LL); } return; } int main() { cin >> T; while(T--) { Init(); cin >> n >> root; ++root; for(register int i = 1; i <= n; ++i) { cin >> l[i] + 1; } Build(root, -1); bool op = false; for(register int i = 1; i <= n; ++i) { if(!dep[i]) { printf("-1\n"); op = true; break; } } if(op) continue; DFS(root, 0); if(ans > lim) cout << "-1\n"; else cout << ans << "\n"; } return 0; }

参考程序

转载于:https://www.cnblogs.com/kcn999/p/10806660.html

今天的文章
【题解】糖果_解数学题分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/60645.html