2022年中国大学生程序设计竞赛女生专场 – I. 宠物对战
题目 题目链接 链接 题目大意 给你两个序列a,b每个序列中都有一些字符串，再给一个目标串s，问你这个s是否能由ababab或者babab类似这种形式组成，a表示a序列里面的字符串，b表示b里面的字符串。 题解 这个题目刚开始想直接凑就行，但是写的过程中想到一…
Category: 题目题解
Codeforces Round 712 (Div. 1) – B. 3-Coloring
题目 题目链接 链接 题目大意 题目意思是给你一个你n * n的棋盘，你有三种棋子，每次给你一种棋子，你不能放这种棋子这次，放的棋子相邻不相同，问你怎么放，每次输出放的棋子种类和位置 题解 刚开始的想法是直接暴力找，然后超时，然后用vector存起来每次没有使…
Prime
prime 模板 /* S:当前已经在联通块中的所有点的集合 1. dist[i] = inf 2. for n 次 t<-S外离S最近的点 利用t更新S外点到S的距离 st[t] = true n次迭代之后所有点都已加入到S中 联系：Dijkstra算…
Educational Codeforces Round 99 (Rated for Div. 2) – D. Sequence and Swaps
题目 题目链接 链接 题目大意 这道题给你一个序列，然后然你把他变成一个非严格上升序列，给你一个数x，满足x > a[i]才能换。问你最少多少次操作能把序列变成上升的，如果不能输出-1 题解 看了题解，我的想法是排序，然后判断 for(int i = 1…
Manthan, Codefest 18 (rated, Div. 1 + Div. 2) – D. Valid BFS? time limit per test2 seconds
题目 题目大意 给你一堆双向边，保证能够形成一个树，再给你一个一个序列，问你这个序列和给出的边形成的树一样不？ 题目链接 链接 题解 刚开始想的是先bfs，然后计算出下一层的儿子的位置在哪，然后这个这么太难写了，所以瞅了眼题解重新写一下。思路是把bfs的顺序重…
Codeforces Round 578 (Div. 2) – E. Compress Words
题目链接 题目链接 题目大意 题目的意思是把字符串删去连续的两个字母，问剩下的字符串拼起来有多少种？ 题解 #include <algorithm> #include <bitset> #include <cmath> #i…
Codeforces Round 256 (Div. 2) – D. Multiplication Table
题目链接 题目链接 题目大意 给你一个n,m问你n*m中第k大的数是多少 题解 刚开始想着如何数出来是第几个，然后虽然想暴力但是压根存不了，5e5*5e5太大了，看了题解后二分，二分这个答案，我们查的数是第几个。 如果当前数是x,那么我们推算他比小的数的个数，…
AcWing – 1488. 最短距离
题目链接 链接 题目大意 这道题问你，给你n个村庄，有些村庄有商店，有些村庄没商店，问你从某个村庄出发，找到一个商店最短距离是多少。 题解 这题一眼顶针。没看出来，本来想的是从询问的点开始每次spfa一次，但是，但是，肯定会超时的啦。然后就有一个很骚的操作，把…
Codeforces Round 861 (Div. 2) – C. Unlucky Numbers
题目链接 链接 题目大意 给你一个区间L, R问你这个区间内最不幸运的数是多少，答案可能有多个，最不幸运的定义是一个数里面最大位减去最小位差值最小。 题解 这个题刚开始想着dfs搜索，分两种情况。 位数不同位数不同直接遍历 位数相同如果这一位相同，就往下找，如…
AcWing – 3696. 构造有向无环图
题目链接 题目链接 题目大意 这道题就是给你一堆边，有些边是确定方向的，有些边是不确定方向的，问你将这些不确定方向的边怎么放满足这个图是一个有向无环图 题解 这道题问是不是有向无环图，那么就是问是不是拓扑图，所以要进行拓扑排序，如果已有的边已经不是拓扑图，那么…