扎红颜

牛客4

未归档(20) 杭电1(6) 杭电10(1) 杭电3(3) 杭电5(3) 杭电7(2) 牛客10(1) 牛客2(5) 牛客6(2) 牛客8(4)

/ 注册

全部文章 / 牛客4 （共4篇）

牛4 C：LCS

题面：已知三个串的LCS和总长n,构造这三个串。解析：临界条件是出现了三个串的公共部分，设公共部分为mi,则(a-mi)+(b-mi)+(c-mi)+mi>=n在条件以内，就一定可以构造三个串的公共部分。细节见代码： #include<bits/stdc++.h> using na...

2021-08-06

0 361

牛4 J:Average

题面：已知a[],b[],矩阵w[i][j]=a[i]+b[j],求矩阵的最大平均数，并且长不小于x，宽不小于y。解析：易得average=两者互不干扰，分别求二者的最大值即可。穷举会T，这道题可以用二分。二分check函数写法：我们要找的是有没有一段不小于x的区间，使这段区间的平均数尽可能的...

2021-08-05

0 346

牛4 I:Inverse Pair

题面：已知有1到n的排列，每个数可以加1或是加0，求逆序数最小是多少。解析：一个排序的逆序数已经是固定的，逆序数减少就说明一个数字x的后面出现了x-1,x不变，x-1再加1。记录逆序数减少的个数，可以从后往前推，用h[]存数字是否出现,加以判断即可。求逆序数用树状数组。代码： #include<...

2021-08-05

0 306

牛4F：Just a joke

题面：给你一个n个点，m条边的无向图。可以进行两种操作删1条边删k个点,k-1条边。两人轮流操作，不能操作的失败。解析：题目难的是看懂题意。看懂后则很容易发现每次操作减少奇数个，判断n+m的奇偶性即可。实在看不懂还可以猜呀代码 #include<bits/stdc++.h> u...

2021-07-31

0 327