牛客练习赛95 A~E A：Duplicate Strings 给你一个字符串，有两个操作： 把这个复制复制若干次接在后面，或者输出一个字符在这个串中的出现次数。 思路 可以一开始直接记录每个字符的出现次数，然后每操作一遍每个的出现次数就乘上 x+1x+1x+1（xxx 是复制的次数） 然后询问就可以直接输出了。 代码 #include<cstdio> #define ll long long #define mo 1000000007 using namespace std; int n, q, x; ll num[26], t; char c; int main() { ...

牛牛防疫情 题目链接：nowcoder 225285 到主站看：https://blog.csdn.net/weixin_43346722/article/details/120521191 题目大意 给你一个二维网格图，然后有一些特殊点，它每隔一个时刻让它四边的点变成特殊点。然后你可以在两个点之间建一个屏障使得无法转变。然后使得一个普通点变成特殊点要费用 c，建立屏障是要 1 费用。要你最小化总费用。 思路 这道题我们考虑用网络流来做。 这么一想之后你就会发现这题确实可以网络流。相当于搞最小割，所有点向汇点连边流量是 表示被感染，然后本身被感染的点连向源点流量 INF 表示被感染。然后点和...

牛牛小数点 题目链接：nowcoder 225284 到主站看：https://blog.csdn.net/weixin_43346722/article/details/120518181 题目大意 定义一个函数 f(i) 为 1/i 循环节从小数点后第几位开始，位数作为函数的结果。如果是不循环的小数，那 f(i)=0。然后要你求 f(1)~f(n) 的和。 思路 首先丢出两个结论：（其实比赛的时候推一推猜一猜都能有）如果 质因子分解之后只有 ，那它就是不循环的。（这个显然） 然后如果 是循环的，它的循环节开始维护就是 。（ 是质因数分解 之后 这个质数的个数） 这里给一下网上看到的...

牛牛种小树 题目链接：nowcoder 225544 到主站看：https://blog.csdn.net/weixin_43346722/article/details/120517394 题目大意 要你构造一个 n 个节点的数，然后给出你 f(i)，要你最大化 ∑i=1~n f(d[i])。其中 d[i] 为 i 点的度数。 思路 我们考虑转换一下题意。 由于一个树的边数是 ，那所有点的度数之和就是 。 那就相当于我们要用 个数凑出 ，而且这些数都要在 之间。 那不难看出这是个完全背包，但是它规定了数选的个数一定要是 啊。 那我们考虑用这么一个方法，就是在背包的过程中保证它的个数不变...

牛牛吃豆人 题目链接：nowcoder 225282 到主站看：https://blog.csdn.net/weixin_43346722/article/details/120516824 题目大意 给你一个 n*3 的图，然后保证每一列至少一个障碍，保证左上右下没有障碍。然后问你是否能找到两条路径，从左上到右下，而且每次只能向右或者向下，而且这两个路径除了左上和右下都没有交。 思路 麻了打比赛的时候没看懂题，以为是求一条路径，然后就直接：属于是直接狂暴。（后来问了题意，一问 某Q 搞懂题就过了） 好了好了不讲了，讲正题。 考虑要两条路径，而且不能有交。那我们考虑一下，贪心一下就会发现： 一...

牛牛嚯可乐 题目链接：nowcoder 225278 到主站看：https://blog.csdn.net/weixin_43346722/article/details/120516597 题目大意 给你一个 8 个长度的字符串，你每次操作可以交换一对字符的位置。然后问你最少要多少次操作使得字符串变成 cocacola。保证一定可以变成。 思路 考虑直接进行 dfs。 就直接从左到右依次把字符拼好。如果当前已经是对的字符，就直接继续。否则就在后面还没有拼好的里面选一个交换，而且显然是要选交换这个位置就好了的位置。不然的话你还要再换，就亏了。 然后在每一个可能换的地方都试一下，然后取最小值就可...

牛牛吃米粒 题目链接：nowcoder 225271 到主站看：https://blog.csdn.net/weixin_43346722/article/details/120505244 题目大意 给你一些数，从 ，但中间缺失了一些数，缺失的会告诉你是哪些。问你是否能凑出数 s。 思路 你考虑都是 ，不难想到二进制。 那这些二进制是不会进位的，因为每个的个数都是 。 那我们就看每个缺失的是否恰好是 二进制上要的。还有一种不行的情况就是 的位数大于 ，那后面大于的那些位就凑不了了。 代码 #include<map> #include<queue> #include...

Determine the Photo Position 题目链接：nowcoder 223608 到主站看：https://blog.csdn.net/weixin_43346722/article/details/118911415 题目大意 给你一个矩阵，问你有多少个地方有连续的 x 个 0，一定要在一行中。 思路 直接暴力模拟枚举找就可以了。记录一个 为当前这一行最后出现了多少个连续的 ，那如果接下来是 ，就 加一，否则就变成 。然后每次搞完看一下，如果 大于等于 就答案加一，表示以这个点结束的一个位置是连续的 个 。 代码 #include<cstdio> u...

Ball Dropping 题目链接：nowcoder 223572 找主站看：https://blog.csdn.net/weixin_43346722/article/details/118903362 题目大意 给你一个中间空的等腰梯形。然后有一个圆，问你是否能从中间穿过梯形。 思路 看看题目给的图，很明显，数学题。 首先分析要看能不能通过，用脚想一想可以知道如果圆直径大于 就掉不下去。然后我们考虑掉不下去怎么求距离。 看到梯形我们考虑用相似三角。 首先两个相似求出 ：然后由于它是等腰，我们可以继续求。 （注意这个球掉到上面的地方与墙面碰到的两个点组成的直线不是直径）（我当时就搞错了...