边与边权1
需积分: 0 117 浏览量
2022-08-08
19:54:46
上传
评论
收藏 19KB DOCX 举报
256MB,2S,eaw.xxx
边与边权
问题描述
草木灰公社社员们在学会了曳光弹开发之后决定出一道曳光弹题目。
曳光弹是指机枪的弹链中除了实弹之外还夹杂的会在空中发光以让射击手
调整弹道的特殊子弹。而曳光弹开发指的是并不求一次性将整个工程完成，而是
一项功能一项功能地完成，并随完成，随评估效果。
有个游戏，叫做边与边权，游戏是一张 N 条边的带权无向图，所有节点都在
一个简单环中。一开始棋子位于起始节点，每条边上的权值非负，Alice 和 Bob
轮流操作，每次可以向与棋子有一条正权边直接相连的节点移动，移动后该边权
值减少至一个非负整数，减少量由操作者决定，减少量必须为正整数。若轮到一
个人操作时无法操作即与棋子当前所在节点不存在正权边与之相连时该人失败，
另一个人胜利。假设两人都能选择最优策略。
游戏初始时有 N 条边，Q 次修改。
修改有以下形式
1 R V 将从起始节点顺时针方向第 R 条边权值改为 V
2 R V 在起始节点顺时针方向第 R 条边的位置插入权值为 V 的边
3 R 删除从起始节点顺时针方向第 R 条边。
输入描述
第一行 2 个整数 N，Q
接下来用空格隔开的 N 个整数 Vi，表示从起始节点。
输出描述
一共 Q+1 行，每行为 0 或 1，1 表示先手必胜，0 表示先后必败。
第一行表示初始时的状态，
接下来 Q 行，第 i 行表示第 i 次修改之后的状态。
评论0