NOIP模拟题 DAY2

第一题 贪吃蛇

【题目描述】
　你正在玩贪吃蛇。游戏在一个$n\times m$的棋盘上进行。每块可能是空地，也可能是障碍。蛇的长度为$k$，占据了$k$个空地，从前往后编号为$1$到$k$。给你一个地图和一个终点，问你蛇最少走多少步能走到终点。如果不能走到终点则输出$-1$。
【输入格式】
　　第一行有两个整数$n,m$；
　　接下来$n$行每行有$m$个字符，第$i$行的第$j$个字符表示第$i$行的第$j$个空地的状态：
　　　'@'：终点
　　　'#'：障碍
　　　'.'：空地
　　　'1'~'9'：蛇的身体
【输出格式】
　　输出一个整数：答案。
【样例输入1】

4 5
##...
..1#@
432#.
...#.

【样例输出1】

4

【样例输入2】

4 4
#78#
.612
.543
..@.

【样例输出2】

6

【样例输入3】

3 2
3@
2#
1#

【样例输出3】

-1

【数据范围】

　　对于100%的数据：$1\leq n,m\leq15,1\leq k\leq9$，保证地图合法；

第二题 字符串

【题目描述】
　　你有一个$map<string,int> a$。初始值都为$0$。有$m$个操作，分为$3$种：
　　　$1~s$：$a[s]++$；
　　　$2~s$；$a[s]--$；
　　　$3~s$：计算$\sum_t{a[t]\times t在s中出现的次数}$；
　　为了增加难度，本题强制在线。你需要维护一个变量$mask$，初始值为$0$。每次读入一个数$y$，真正的操作类型是$y~xor~mask$。查询后，设答案为$ans$，你要把$mask$异或上$|ans|$。
【输入格式】
　　第一行有一个整数$m$；
　　接下来$m$行每行有一个操作。
【输出格式】
　　对于每一个$3$操作，输出一行一个数：答案。
【样例输入】

5
1 abc
3 abcabc
0 abc 
3 aba
1 abababc

【样例输出】

2
2

【样例解释】
　　解密后的输入是：

5
1 abc
3 abcabc
2 abc
1 aba
3 abababc

【数据范围】
对于$10\%$的数据：$m\leq 100,\sum{|s|}\leq100$；
对于$50\%$的数据：$m\leq 1000,\sum{|s|}\leq1000$；
对于$70\%$的数据：$m\leq 100000,\sum{|s|}\leq100000$；
对于$100\%$的数据：$m\leq 1000000,\sum{|s|}\leq1000000$；

第三题 都城

【题目描述】
　　XFZ准备带领他的小朋友独立了。XFZ管辖着$n$个城市，有的城市之间有一条双向道路连接，一共有$n-1$条，任何一个城市都能通过这些道路到达任意一个其他城市。XFZ准备在独立后把每条双向道路的其中一个方向修成高速公路（另外一个方向还是普通道路）。XFZ还要选出一个都城。为了管理方便，都城必须能够只通过高速公路到达任意一个其他城市。给你XFZ的计划，XFZ想知道他以每个点为都城时最少需要更改多少条计划才能满足要求。
【输入格式】
　　第一行有一个整数$n$；
　　接下来$n-1$行每行有两个整数$x,y$，表示$x$城与$y$城之间有一条双向道路连接，XFZ计划把$x$城到$y$城的这条路改成高速公路。
【输出格式】
　　$n$行，每行一个整数，第$i$行输出XFZ最少要更改多少条计划才能使$i$成为都城。
【 样例输入】

4
1 4
2 4
3 4

【样例输出】

2
2
2
3

【数据范围】
对于$10\%$的数据：$n\leq10$；
对于$30\%$的数据：$n\leq{10}^3$；
对于$50\%$的数据：$n\leq{10}^5$；
对于$100\%$的数据：$2\leq n\leq {10}^6,1\leq x,y\leq n$；