扎红颜

分类

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

/ 注册

全部文章（共50篇）

牛8 A：Ares, Toilet Ares

题面：厕所战神（真实故事改编），有n道题，m道没换的题，k次去厕所的机会，a道写了不会被怀疑的题，'k'题有l行代码，给出每次去厕所抄代码的行数和错误的可能性，求ac的问题数。解析：题目中有较多无关数据，其中真正有用的是a和概率。k题能ac,即每次去厕所抄的代码都正确。除法不能直接取模，用费马小定理...

2021-08-13

0 507

牛8 E:Rise of Shadows

题面：给定一个数，判断既是闰年又是质数。解析：闰年必是偶数，所以不可能同时间满足条件。代码： using namespace std; long long t,n; int main(){ cin>>t; while(t--){ cin>>n;...

2021-08-13

0 299

牛八 K:Yet Another Problem About Pi

题面：已知网格中的长和宽，一个人可以走π km,求最多经过多少区域。解析：因为π 是无限不循环小数，网格的长宽是有限的，所以问题可以相当为人只走交叉点，因为只需要轻微的扰动就可以经过点周围的四片区域。而相邻的点的距离只有三种，长，宽，对角线，增加的区域则是2，2，3。即求3x+2y的最大值，在ax+...

2021-08-12

0 383

牛6 I：Intervals on the Ring

题面：已知1到n的环，给定m个区间，要求构造若干个区间，它们的交集是原区间的并集。解析：根据集合里面的概念，区间补的交等于区间并的补；原区间并的补就是未覆盖区域，相当于m个未覆盖区间的并，所以只要构造区间是未覆盖区域的补即可。代码： #include<bits/stdc++.h> us...

2021-08-12

0 278

牛6 F：Hamburger Steak

题面：给定n块牛排，m个锅，每块牛排最多煎两次，同一时间不能同时煎一块，求用最少时间内，符合条件的煎法。解析：先考虑最少时间，最好的情况是总时间被重复利用。但要满足条件， (除法向上取整）。因为若小于最大的煎一块牛排时间，就会出现同一时间牛排出现在两个锅内。然后，就是模拟每块牛排煎的过程，每口锅的时...

2021-08-12

0 463

牛4 C：LCS

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

2021-08-06

0 412

牛4 J:Average

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

2021-08-05

0 402

牛4 I:Inverse Pair

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

2021-08-05

0 352

牛4F：Just a joke

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

2021-07-31

0 390

杭电1：Xor sum

题面：给定一个长度为n的序列，求一个异或不小于k的最小子序列，输出最小的左端点和其右端点。解析：暴力方法是将序列的每一个点当作左端点，找到最小的子序列。复杂度o(n^2),显然是不行的。我们知道a xor b= c;a xor b xor c= 0;若用sun[i]表示前i个数的异或值，则sum[i...

2021-07-31

0 362