省选江苏夏令营noi模拟1task

1、注意事项：1、用机：CPU：2.4GHz；512M；操作系统：WinXP2.所有题目的选手输出必须与标准严格相同(全文比较)才能得分3.请选手注意输入输出文件名，不区分大小写4.选手提交的源程序必须放在以自己命名的目录的根目录下Otoci提交文件：otoci.exe输入文件：otoci.in输出文件：otoci.out问题描述：给出 n 个节点以及每个点对应的权值 wi。起始时点与点之间没有连边。有 3 类操作：1、bridge A B：询问节点 A 与节点 B 是否连通。如果是则输出“no”。否则输出“yes”，题目名称OtociNecklacs提交文件Otoci.?Necklace.?/输

2、入文件Otoci.inNecklace.inscs1.inscs10.in输出文件Otoci.outNecklace.outscs1.outscs10.out时间限制4s2s/内存限制128MB256MB/分值100100100并且在节点A 和节点 B 之间连一条无向边。2、penguins A X：将节点A 对应的权值 wA 修改为 X。3、excurA B：如果节点 A 和节点 B 不连通，则输出“imsible”。否则输出节点A 到节点 B 的路径上的点对应的权值的和。给出 q 个操作，要求处理所有操作。输入：第一行包含一个整数n(1 n 30000)，表示节点的数目。第二行包含n 个整

3、数，第 i 个整数表示第 i 个节点初始时对应的权值。第三行包含一个整数q(1 n 300000)，表示操作的数目。以下 q 行，每行包含一个操作，操作的类别见题目描述。任意时刻每个节点对应的权值都是 1 到 1000 的整数。输出：输出所有 bridge 操作和excur操作对应的输出，每个一行。样例输入：61 2 3 4 5 610bridge 1 2bridge 2 3bridge 4 5excur1 3excur1 5bridge 3 4excur1 5penguins 3 10excur1 3bridge 1 5样例输出：yesyesyes6imsibleyes1513noNeckl

4、ace提交文件：necklace.exe输入文件：necklace.in输出文件：necklace.out问题描述：有一串由 n 珠子的环形珠链。珠链上的每个珠子要么黑色要么白色。每个珠子都能感应到它左边的 k 个珠子以及右边的 k 个珠子。每一秒珠子都会尝试改变自己的颜色，对于一个珠子，如果它感应到的 2k 个珠子中有奇数个是黑色，那么它会改变自己的颜色，否则它会保持自己原来的状态。所有要改变颜色的珠子都会在同一时刻改变自己的颜色。下面是一个例子。由于珠链是环形的，因此，对于两条珠链，如果其中一条可以通过旋转（不能翻转）变成另外一条，那么这两条珠链是本质相同的。给出 n、k、t 以及一条长度为 n 的珠链的珠子的颜色，问有多少条本质不同的珠链能够在 t 秒之后变成给出的珠链。输入：输入的首行包含一个整数 T(1 T 20 )，表示数据的组数。下面包含 T 组数据，每组占两行。第一行包含 3 个整数n、k、t(1 n 200, 1 t 200, 1 k (n - 1) / 2)，定义见题目描述。第二行包含一个长度为 n 的字符串，描述 t 秒后珠链的珠子的颜色，其中”w”表示白色，”b”表示黑色。输出：共 T 行，每行包含一个整数，依次表示对于每组输入数据，最开始本质不同的珠链有多少条。由于这个数可能很大，只需要输出 mod 9973 的结果就可以了。样例输入 1：3