目录
题目描述
你有一个字符串 \(S\) 和一个字符串 \(T\)。
你把 \(S\) 中的字母按顺序一个一个写在黑板上,写完一遍后接着写第二遍、第三遍,以此类推 \(\cdots\)
当黑板上的字符串恰好是 \(T\) 时,你会停下,否则你会一直写下去。但是你有一次反悔的机会,即可以在某一个时刻在黑板上修改一个字母。
比如 \(S=\tt abc\):
现在有 \(q\) 组询问,请你按照如下要求输出每个询问的答案:
0
;-1
。输入格式
输入第一行,一个整数 \(q\),表示测试数据组数;
对于每组数据,输入一行包含两个字符串 \(S\) 和 \(T\)。
输出格式
输出共 \(q\) 行,第 \(i\) 行的输出表示第 \(i\) 组测试数据的结果。
样例输入
3
abc abcab
abc aa
abc aab
样例输出
0
2
-1
数据范围
时间限制:\(\rm 1s\)
空间限制:\(\rm 512MB\)
对于 \(S_{0\dots n-1}\),\(T_{0\dots m}\)
检查 \(T_i\) 是否等于 \(S_{i\bmod n}\)
0
;-1
.时间复杂度 \(O(|T|)\),足以通过本题。
题目描述
小鸿最近学会了因数分解和二进制。她发现有一类数很神奇,这个数可以表示成两个数 \(a\) 和 \(b\) 的乘积,并且 \(a\) 和 \(b\) 的二进制表示(无前导 \(0\))中 \(0\) 的个数相同,\(1\) 的个数也相同。
例如:\(30\) 可以表示成 \(5\times 6\),且 \(5\) 的二进制表示是 \(101\),\(6\) 的二进制表示是 \(110\),都有一个 \(0\) 和两个 \(1\),所以 \(30\) 是一个神奇的数。\(a\) 和 \(b\) 可以相等,即平方数一定是神奇的。
现在小鸿想知道第 \(k\) 小的神奇的数是多少,请你帮帮她!
输入格式
输入第一行,一个整数 \(q\),表示询问个数;
接下来 \(q\) 行,每行一个整数 \(k\),表示一个询问。
输出格式
输出共 \(q\) 行,每行表示对应询问的答案。
样例数据 \(1\)
input1
5
1
2
3
4
5
output1
1
4
9
16
25
样例数据 \(2\)
input2
3
10
100
1000
output2
81
1750
26460
数据规模与约定
时间限制:\(\rm 1s\)
空间限制:\(\rm 512MB\)
找出所有的二进制 \(0\) 和 \(1\) 个数相等的数乘一下预处理即可。
关于找二进制数中 \(1\) 的个数,可以线性递推:
令 \(cnt_i\) 为 \(i\) 二进制中 \(1\) 的个数,则
\[cnt_i=cnt_{i\text{ shr }1}+(i\text{ and }1)
\]
其中 \(\text{shr}\) 表示右移,在 C/C++ 中为 >>
,在 pascal 中为 shr
,参见 Wikipedia - Bitwise operation - Bit shift - Arithmetic shift;\(\text{and}\) 表示按位与符号,在 C/C++ 中为 &
,在 pascal 中为 and
,参见 Wikipedia - Bitwise operation - AND .
即 \(i\) 丢掉最后一位二进制中 \(1\) 的个数与最后一位是否为 \(1\)。
经过简单的验证,可以发现 \(k\le 10^6\) 时,\(a,b\le 2^{13}\)
枚举 \(0\) 的个数与 \(1\) 的个数再乘就可以了。
注意乘的时候要排序和去重,用 sort+unique
即可。
题目描述
小鸿把 \(n\) 个珠子排成一排,想用 \(m\) 种颜料给它们染色。
这些颜料不一定要都用上,但是她希望染色后的珠子满足:任意连续三个珠子的颜色互不相同。
因为珠子染色后还有可能首尾相连串成项链,所以小鸿还想知道在满足上述条件的方案中,第一个珠子的颜色和最后一个珠子的颜色不同的方案数。
由于答案可能很大,请输出答案对 \(p\) 取模后的结果。
输入格式
输入仅一行,包含三个整数 \(n,m,p\) .
输出格式
输出两个数,第一个数是首尾颜色不同的方案数,第二个数是首尾颜色无限制的方案数。
注意输出的是答案对 \(p\) 取模后的结果。
样例数据 \(1\)
input
4 4 1000
output
24 48
样例解释
前三个珠子颜色互不相同,一共有 \(4×3×2=24\) 种选法,第四个珠子的颜色不能和第二、第三颗相同,有 \(2\) 种选法。这两种选法中,一种和第一颗珠子颜色相同,一种不同,所以第一个答案(首尾颜色不同的方案数)是 \(24\),第二个答案(总方案数)是 \(48\)。
样例数据 \(2\)
input
20 20 1000000
output
342920 661120
数据规模与约定
请注意 \(n,m\) 都大于等于 \(3\) .
时间限制:\(\rm 1s\)
空间限制:\(\rm 512MB\)
爆搜:20pts
记录颜色的 dp:
令 \(dp_{i,j,k}\) 为现在染第 \(i\) 个珠子,上个颜色是 \(j\),当前颜色是 \(k\)。
枚举下一个珠子的颜色 \(p\)(\([j\neq k]\land [p\neq k]\)),此时 \(dp_{i+1,k,p} = dp_{i+1,k,p}+dp_{i,j,k}\) .
状态是 \(O(nm^2)\) 的,转移是 \(O(m)\) 的,总复杂度 \(O(nm^3)\),40pts .
用前缀和优化转移,此时转移为
\[dp_{i+1,k,p}=dp_{i,1\sim m,1\sim m}-dp_{i,j,k}\qquad([j=p] \lor [k=p])
\]
这转移是 \(O(1)\) 的,总复杂度 \(O(nm^2)\),60pts .
这个 \(m\) 太冗余了,显然如果前两个随便选最后一个就有 \(m-2\) 种可能,考虑不计颜色。
设第一个珠子颜色是「1」,第二个珠子颜色是「2」,最后答案乘上 \(m(m-1)\) 即可(因为这两个珠子的方案是 \(m(m-1)\))
Sol 1:令 \(dp_{i,j,k}\) 为现在染第 \(i\) 个珠子,上个颜色状态是 \(j\),当前颜色状态是 \(k\) 的方案数。
颜色状态:
考虑转移(乘上方案数):
\([0][0] \gets (m-3)[1][0]+[2][0]+(m-4)[0][0]\)
\([1][2] \gets [0][1]\)
\([2][1] \gets [0][2]\)
\([0][1] \gets [2][0]+[0][0]\)
\([0][2] \gets [1][0]+[0][0]\)
\([1][0] \gets (m-2)[2][1]+(m-3)[0][1]\)
\([2][0] \gets (m-2)[1][2]+(m-3)[0][2]\)
答案是 \(\text{sum}\{dp_{n,i,j}\}\)(\(0 ≤ i,j ≤ 2\) 且 \(j ≠ 1\)) 和 \(\text{sum}\{dp_{n,i,j}\}\)(\(0 ≤ i,j ≤ 2\))
时间复杂度 \(O(n)\),100pts。
Sol 2:令 \(dp_{i,j}\) 为第 \(i\) 个位置,颜色状态为 \(j\) 的方案数。
颜色状态:
与 Sol 1 类似,转移为:
\(dp_{i,0} = dp_{i-1,2}\)
\(dp_{i,1} = (m-2)dp_{i-1,0}\)
\(dp_{i,2} = (m-2)dp_{i-1,1}+(m-3)dp_{i-1,2}\)
答案即为 \(dp_{n,1}+dp_{n,2}\) 与 \(dp_{n,0}+dp_{n,1}+dp_{n,2}\) .
时间复杂度 \(O(n)\),100pts .
题目描述
H 国里有 \(n\) 个城市,\(m\) 条双向道路连接着这些城市。
两个城市之间可能有多条道路连接。任意两个城市之间都至少存在一条路径使它们互相可达。
有一天,一种神奇的病毒突然在 \(start\) 号城市出现了,我们称之为 \(0−\) 型病毒。这种病毒的扩散方式很神奇,如果在某一天,城市 \(u\) 中有 \(k−\) 型病毒,次日,病毒就会从该城市转移到所有与城市 \(u\) 相邻的城市,并变异成 \((k+1)−\) 型病毒。
已知 \(0−\) 型病毒可能从任意一个奇数编号的城市(即 \(start\) 是一个在 \([1,n]\) 中的奇数)出现。现在你想知道,无论 \(0−\) 型病毒第一次从哪个城市出现,H 国是否都一定会被病毒吞噬。H 国被病毒吞噬的定义是:存在某一天,所有城市中都有相同类型的病毒。
对于下图,如果 \(0−\) 型病毒在第一天出现在 \(1\) 号城市,那么第二天 \(2\) 号和 \(3\) 号城市中都会出现 \(1−\) 型病毒,第三天 \(1\) 号、\(2\) 号、\(3\) 号城市都会出现 \(2−\) 型病毒(\(2\) 号城市的 \(1−\) 型病毒使得 \(1\) 号和 \(3\) 号城市出现了 \(2−\) 型病毒,\(3\) 号城市的 \(1−\) 型病毒使得 \(1\) 号和 \(2\) 号城市出现了 \(2−\) 型病毒)。如果 \(0−\) 型病毒在第一天出现在 \(3\) 号城市,同理,第三天 \(1\) 号、\(2\) 号、\(3\) 号城市都会出现 \(2−\) 型病毒。因此 H 国一定会被病毒吞噬。
[1]----[2]
\ /
\ /
\/
[3]
对于下图,如果 \(0−\) 型病毒第一天出现在 \(1\) 号城市,那么第二天 \(2\) 号城市中出现 \(1−\) 型病毒,第三天 \(1\) 号城市中出现 \(2−\) 型病毒 \(\cdots\) 每天都只有一个城市有病毒,H 国不会被病毒吞噬。
[1]----[2]
现在你获得了 H 国的地图,请你计算一下,H 国是否会被病毒吞噬。如果会,请输出 Yes
,否则请输出 No
。
输入描述
输入第一行,一个整数 \(T\),表示测试数据组数;
对于每组数据,第一行两个整数 \(n,m\),接下来 \(m\) 行,每行两个整数 \(u,v\) 表示 \(u\) 号城市和 \(v\) 号城市有一条道路相连。
输出描述
输出共 \(T\) 行,第 \(i\) 行的输出表示第 \(i\) 组测试数据的结果。
样例输入
2
3 3
1 2
2 3
3 1
2 1
1 2
样例输出
Yes
No
数据范围
时间限制:\(\rm 1s\)
空间限制:\(\rm 512MB\)
显然从一个城市能吞噬整个城市,那么从每个城市都能吞噬整个城市。
可以很显然的看出来这就是判图中有没有奇环,染个色即可,100pts。
下面讲 70pts 做法:
如果一个城市 \(u\) 在第 \(t\) 天有 \(t-1\) 型病毒存在,说明存在 \(u\to start\) 的长度为 \(t\) 的路径(显然)。
如果一个城市在第 \(t\) 天有 \(t-1\) 型病毒存在,那么它在第 \(t+2\) 天一定也有 \(t+1\) 型病毒(显然 too)。
所以只需要判断 \(start\) 到每个点是否都可以通过奇数步和偶数步到达,就说明答案是 Yes
。
时间复杂度 \(O(n(n+m))\),70pts。
存图:
Problem 1:信息传递(NOIp2015;洛谷 P2661;loj 2421)
有 \(n\) 个同学(编号为 \(1\) 到 \(n\))正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 \(i\) 的同学的信息传递对象是编号为 \(T_i\) 的同学。
游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自己的生日时,游戏结束。请问该游戏一共可以进行几轮?
求最小环,直接遍历每个点即可。
时间复杂度 \(O(n)\)
Problem 2:寻找道路(NOIp2014;洛谷 P2296;loj 2502)
在有向图 \(G\) 中,每条边的长度均为 \(1\),现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件:
- 路径上的所有点的出边所指向的点都直接或间接与终点连通。
- 在满足条件 \(1\) 的情况下使路径最短。
注意:图 \(G\)中可能存在重边和自环,题目保证终点没有出边。
请你输出符合条件的路径的长度。
先从终点反向 bfs 得到所有能间接到达终点的点
检查每个点的出边指向的点是否是上面的点
在所有满足条件的点中求最短路即可
时间复杂度 \(O(n+m)\)
拓扑排序:
对于一 DAG,每次删去入度为 \(0\) 的点,最后形成拓扑序。
只有无环图才有拓扑序。
Problem 3:车站分级(NOIp2013;洛谷 P1983)
一条单向的铁路线上,依次有编号为 \(1,2,…,n\) 的 \(n\) 个火车站。每个火车站都有一个级别,最低为 \(1\) 级。现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 \(x\),则始发站、终点站之间所有级别大于等于火车站 \(x\) 的都必须停靠。(注意:起始站和终点站自然也算作事先已知需要停靠的站点)
例如,下表是 \(5\) 趟车次的运行情况。其中,前 \(4\) 趟车次均满足要求,而第 \(5\) 趟车次由于停靠了 \(3\) 号火车站(\(2\) 级)却未停靠途经的 \(6\) 号火车站(亦为 \(2\) 级)而不满足要求。
现有 \(m\) 趟车次的运行情况(全部满足要求),试推算这 \(n\) 个火车站至少分为几个不同的级别。
不停的站比停的站级别低,若 \(a\) 比 \(b\) 级别低,连一条 \(a\to b\) 的有向边,
求出这个有向无环图中的最长路就是答案。
时间复杂度 \(O(n^2m)\)
每辆火车建立一个虚点,边数可以优化到 \(O(nm)\)
01 最短路
给定一个图 \(G\),边权只有 \(0\) 和 \(1\),求 \(s\) 到 \(t\) 的最短路。
显然边权里只有 \(1\) 的话可以 bfs。
若边权里还有 \(0\) 直接 bfs 就不行了,如:
此时那条边权为 \(1\) 的边会直接更新点 \(3\) 的最短路,答案就错了。
可以修改一下 bfs,采用如下策略(使用双端队列(deque)):
时间复杂度 \(O(n+m)\)
因为队列里要让路径长度最短,因走 \(0\) 没有改变长度,显然更短,所以放队头,走 \(1\) 长度变长了,所以放队尾。
分层图
把图复制两遍,放在两个平面上(奇平面和偶平面),然后连上边。
Problem 4:加工零件(CSP2019;洛谷 P5663)
凯凯的工厂正在有条不紊地生产一种神奇的零件,神奇的零件的生产过程自然也很神奇。工厂里有 \(n\) 位工人,工人们从 \(1 \sim n\) 编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。
如果 \(x\) 号工人想生产一个被加工到第 \(L (L \gt 1)\) 阶段的零件,则所有与 \(x\) 号工人有传送带直接相连的工人,都需要生产一个被加工到第 \(L - 1\)阶段的零件(但 \(x\) 号工人自己无需生产第 \(L - 1\) 阶段的零件)。
如果 \(x\) 号工人想生产一个被加工到第 \(1\) 阶段的零件,则所有与 \(x\) 号工人有传送带直接相连的工人,都需要为 \(x\) 号工人提供一个原材料。
轩轩是 1 号工人。现在给出 \(q\) 张工单,第 \(i\) 张工单表示编号为 \(a_i\) 的工人想生产一个第 \(L_i\) 阶段的零件。轩轩想知道对于每张工单,他是否需要给别人提供原材料。他知道聪明的你一定可以帮他计算出来!
求走奇数次的路径和走偶数次的路径即可。
因为走一次必改变奇偶性,所以每个平面之间不会有连边,但是跨越两个平面会有连边。
Problem 5:飞行路线(JLOI2011;洛谷 P4568)
简述:给一个图 \(G\),有 \(k\) 次机会可以将某条边的边权变为 \(0\),求 \(s\) 到 \(t\) 的最短路径。
建分层图,上下自己建个图,然后从上到下建有向边,边权为 \(0\) 即可。
Problem 6:冻结(Beijing wc2012;洛谷 P4822)
简述:给一个图 \(G\),有 \(k\) 次机会可以将某条边的边权减半,求 \(s\) 到 \(t\) 的最短路径。
同 Problem 5
Problem 7:无向图的最小环问题(洛谷 P6175)
给定一张无向图,求图中一个至少包含 \(3\) 个点的环,环上的节点不重复,并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中,你需要输出最小的环的边权和。若无解,输出
No solution.
。
Floyd 滚动数组前那个第 \(2\) 维 [k]
是点的最大值,所以说再连一条边即可求出一个环,对每个最短路都求一遍环即可。
手机扫一扫
移动阅读更方便
你可能感兴趣的文章