北京网站改版多少钱,保护环境做网站素材,怎么做网站快捷方式,php微信公众号开发教程题干#xff1a;
B君在围观一群男生和一群女生玩游戏#xff0c;具体来说游戏是这样的#xff1a; 给出一棵n个节点的树#xff0c;这棵树的每条边有一个权值#xff0c;这个权值只可能是0或1。 在一局游戏开始时#xff0c;会确定一个节点作为根。接下来从女生开始
B君在围观一群男生和一群女生玩游戏具体来说游戏是这样的 给出一棵n个节点的树这棵树的每条边有一个权值这个权值只可能是0或1。 在一局游戏开始时会确定一个节点作为根。接下来从女生开始双方轮流进行 操作。 当一方操作时他们需要先选择一个不为根的点满足该点到其父亲的边权为1; 然后找出这个点到根节点的简单路径将路径上所有边的权值翻转即0变成11 变成0 )。 当一方无法操作时(即所有边的边权均为0)另一方就获得了胜利。 如果在双方均采用最优策略的情况下女生会获胜则输出“Girls win!”否则输 出“Boys win!”。 为了让游戏更有趣味性在每局之间可能会有修改边权的操作而且每局游戏指 定的根节点也可能是不同的。 具体来说修改边权和进行游戏的操作一共有m个具体如下 ∙∙“0 x”表示询问对于当前的树如果以x为根节点开始游戏哪方会获得胜利。 ∙∙“1 x y z ”表示将x和y之间的边的边权修改为z。 B君当然知道怎么做啦但是他想考考你。
Input
包含至多5组测试数据。 第一行有一个正整数表示数据的组数。 接下来每组数据第一行有二个空格隔开的正整数n,m分别表示点的个数操 作个数。保证n,m 40000。 接下来n-1行每行三个整数x,y,z表示树的一条边。保证1xn, 1y n, 0 z 1。 接下来m行每行一个操作含义如前所述。保证一定只会出现前文中提到的两 种格式。 对于操作0保证1 x n ;对于操作1保证1 x n, 1 y n, 0 z 1保证树上存在一条边连接x和y。
Output
对于每组数据的每一个询问操作输出一行“Boys win!”或者“Girls win!”。
Sample Input
2
2 3
1 2 0
0 1
1 2 1 1
0 2
4 11
1 2 1
2 3 1
3 4 0
0 1
0 2
0 3
0 4
1 2 1 0
0 1
0 2
0 3
1 3 4 1
0 3
0 4
Sample Output
Boys win!
Girls win!
Girls win!
Boys win!
Girls win!
Boys win!
Boys win!
Girls win!
Girls win!
Boys win!
Girls win! 解题报告
想想他需要不停的换根数据量又如此庞大以至于每次换根后我dfs一遍的时间都没有所以肯定是个找规律题肯定不会给你遍历整棵树的机会的。从必胜态必败态的角度考虑不难发现如果是一条链的情况规律就是根节点相连的那条边的边权如果是1那女生胜反之男生胜。又因为如果是多条链的话链之间互不影响所以可以直接统计和根节点相邻的边的边权和如果是奇数那就是女生获胜反之男生获胜。当然如果先一条链然后分成两条链的情况那其实也问题不大因为发现可以转化成一条链的情况上面。其实可以大胆猜想既然一条链的情况只和根节点相邻的边的边权有关系假设这条边是e那也就是所有 想到达根节点的路径只要需要经过边e那就都和路径上的其他边没关系之和边e相关所以就这样
好吧还是来一发正解
正解是经分析发现无论操作哪个节点这个节点都会使其所在子树中与根直接相连的那条边翻转。那么再根据游戏的规则以及子树的性质会发现若你面对当前这条与根相连的边的权值为1时对方通过子树上任意点来翻转当前边你都能再次进行翻转。如果你面对权值为0那么要么你不能进行操作要么不管你进行什么操作对方都还能进行操作。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includestack
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
vectorPII vv[MAX];
int n,m;
int main()
{int T;cinT;while(T--) {scanf(%d%d,n,m);for(int i 1; in; i) vv[i].clear(); for(int x,y,z,i 1; in-1; i) {scanf(%d%d%d,x,y,z);vv[x].pb(pm(y,z));vv[y].pb(pm(x,z));}for(int i 1; in; i) sort(vv[i].begin(),vv[i].end());int op,u,v,z,ans;while(m--) {scanf(%d,op);if(op 0) {ans0; scanf(%d,u);for(auto x : vv[u]) {if(x.SS 1) ans;}if(ans 1) puts(Girls win!);else puts(Boys win!);}else {scanf(%d%d%d,u,v,z);int pos1 lower_bound(vv[u].begin(),vv[u].end(),pm(v,-1)) - vv[u].begin();int pos2 lower_bound(vv[v].begin(),vv[v].end(),pm(u,-1)) - vv[v].begin();vv[u][pos1] pm(v,z); vv[v][pos2] pm(u,z);}}} return 0 ;
}
关于实现细节
发现对于0操作如果是菊花图的话就炸了。
所以优化一下发现不需要枚举
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includestack
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
vectorPII vv[MAX];
int n,m,in[MAX];
int main()
{int T;cinT;while(T--) {scanf(%d%d,n,m);for(int i 1; in; i) vv[i].clear(),in[i]0; for(int x,y,z,i 1; in-1; i) {scanf(%d%d%d,x,y,z);vv[x].pb(pm(y,z));vv[y].pb(pm(x,z));if(z 1) in[x],in[y]; }for(int i 1; in; i) sort(vv[i].begin(),vv[i].end());int op,u,v,z,ans;while(m--) {scanf(%d,op);if(op 0) {ans0; scanf(%d,u);if(in[u] 1) puts(Girls win!);else puts(Boys win!);}else {scanf(%d%d%d,u,v,z);int pos1 lower_bound(vv[u].begin(),vv[u].end(),pm(v,-1)) - vv[u].begin();int pos2 lower_bound(vv[v].begin(),vv[v].end(),pm(u,-1)) - vv[v].begin();if(vv[u][pos1].SS0 z 1) {vv[u][pos1] pm(v,z); vv[v][pos2] pm(u,z);in[u],in[v];}else if(vv[u][pos1].SS1 z 0) {vv[u][pos1] pm(v,z); vv[v][pos2] pm(u,z);in[u]--,in[v]--;} }}} return 0 ;
}
