牛客寒假算法基础集训营2

A.处女座的签道题

题目描述

平面上有n个点，问：平面上所有三角形面积第k大的三角形的面积是多少?

输入描述:

第一行T，表示样例的个数。
对于每一组样例，第一行两个整数n和k，
接下来n行，每行两个整数x,y表示点的坐标
$ T \leq 80,3 \leq n \leq 100, -10^9 \leq x,y \leq 10^9 $.
对于每一组样例，保证任意两点不重合，且能构成的三角形的个数不小于k

输出描述:

对于每一组样例，输出第k大三角形的面积，精确到小数点后两位（四舍五入）。

输入

1
4 3
1 1
0 0
0 1
0 -1

输出

0.50

说明

样例中一共能构成3个三角形，面积分别为0.5，0.5，和1，面积第3大的为0.5。

思路：

①高中知识：向量叉积求三角形面积：

$S_{\Delta ABC} = \frac{1}{2} \times |\vec{a} \times \vec{b}| = \frac{1}{2} \cdot |\vec{a}| \cdot |\vec{b}| \cdot sin <\vec{a}, \vec{b}>$。
设 $A(x_1, y_1), B(x_2, y_2), C(x_3, y_3), \vec{AB} = (x_2 - x_1, y_2 - y_1), \vec{AC} = (x_3 - x_1, y_3 - y_1)$，则 $S_{\Delta ABC} = \frac{1}{2} \times |\vec{AB} \times \vec{AC}| = \frac{1}{2} \cdot |(x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1)|$.
②nth_elementC++标准库函数的运用：此题中，如果 $ n = 100 $，那么最多大约能构成 $ 1.6 \times 10^5 $ 个三角形。因要求第k大的三角形面积，若直接调用sort排序（$ O(nlog^n) $）大约是 $ 2.7 \times 10^6 $ 级别。若80组测试数据中n都是100，那么将是 $ 2.1 \times 10^8 $ 级别，显然这就太慢了，自测了牛客评测机，93.3%的通过率。此时就要考虑用快排或者是nth_element函数，其期望时间复杂度都是 $ O(n) $。nth_element $ (first,k^{th} - 1,last) $ 表示的是将第k小的元素放在 $ k^{th} - 1 $这个位置上，注意数组下标是从0开始的，即 $ k^{th} $ 这个位置上的元素是第 $ (k^{th} -first + 1) $ 小的（注意first是第1小的，一般first为0）。
③最后要注意的就是精度问题：因为 $ x, y $ 的值相乘之后大可能会达到 $ 10^{18} $，无法用double存，所以最后需要特判 “ .00” 或者 “ .50”。
备注：float： $ 2^{23} = 8388608 $，一共7位，意味着最多能有7位有效数字，但绝对能保证为6位，即float的精度位6~7位有效数字；
double：$ 2^{52} = 4503596927370496 $，一共16位，即double的精度为15~16位。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 105;
int T, n, k;
struct node{LL x,y;}nod[maxn];
inline LL cross(node p0,node p1,node p2){
    return abs((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
}
vector<LL> vec;
int main(){
    while(~scanf("%d", &T)) {
        while(T--) {
            scanf("%d %d", &n, &k); vec.clear();
            for(int i = 1; i <= n; ++i) scanf("%lld %lld", &nod[i].x, &nod[i].y);
            for(int i = 1; i <= n - 2; ++i)
                for(int j = i + 1; j <= n - 1; ++j)
                    for(int k = j + 1; k <= n; ++k)
                        vec.push_back(cross(nod[i], nod[j], nod[k]));
            nth_element(vec.begin(), vec.begin() + k - 1, vec.end(), greater<LL>()); //求数组中第k大元素，因为数组从下标0开始，所以实际位置是k - 1
            printf("%lld", vec[k - 1] / 2);
            puts(vec[k - 1] & 1 ? ".50" : ".00");
        }
    }
    return 0;
}

B.处女座与cf

题目描述

众所周知，处女座经常通过打cf来调节自己的心情。今天处女座又参加了一场cf的比赛，他知道了所有的提交记录，他想知道自己的得分和排在第几名。你知道处女座的cf账号是cnz。Codeforces规则如下：
1.比赛一共2小时；
2.比赛有5题，A题500分，B题1000分，C题1500分，D题2000分，E题2500分；
3.得分规则如下：
在第0分钟完成某一题可以得到全部的分数，每过一分钟每题的分值会衰减1/250，比如在第3分钟完成A题，能够得到 $500 - 2 * 3 = 494$ 分；
4.如果一道题是的返回结果WA或者TLE被称为错误的提交，CE视为无效的提交，AC，WA和TLE 都视为有效的提交。如果一道题你最后通过了，你会得到这道题衰减之后的分值再减去你错误提交次数 $* 50$，就是每次错误的提交会有50分的罚时。
5.如果你通过了一道题，你的得分不会低于该题分值的30%。比如你在第50分钟通过了A，你有7次错误的提交，你的得分为 $max(500 * 0.3, 500 - 2 * 50$ (得分衰减) - $7 * 50$(错误提交的罚时)) $= 150$ 分。
6.由于hack机制的存在，你每进行一次提交，对于这一题之前的有效提交(AC,WA,TLE)都视为错误的提交。
7.一个人只有提交(AC,WA,TLE,CE)过代码，才被视为参加比赛。
处女座又了解到一些信息：本场比赛没有任何选手hack别人，并且没有任何的提交fst（即只要是某题的最后一次提交通过，就视为通过这道题）。

输入描述:

第一行两个整数n和m，n为报名比赛的人数，m为提交的个数
接下来n行，每行一个字符串，表示报名比赛的人的昵称。（字符串只包含小写字母，且长度小于20）
接下来m行，每行的格式为Time，Submiter，Problem，Verdict。
Time为提交的时间，是1到120中的一个正整数（包含1和120）,保证Time按顺序给出
Submiter为提交者昵称
Problem为题目名称，是’A’,’B’,’C’,’D’,’E’中的一个字母。
Verdict为返回的结果，为”AC”,”WA”,”TLE”,”CE”中的一个。
$ 2 \leq n \leq 500 $
$ 1 \leq m \leq 10000 $

输出描述:

如果处女座参加了比赛,输出两行:
第一行为处女座的得分；第二行格式x/y,其中x为处女座的排名，y为参加比赛的总人数。如果分数相同那么排名并列。如果处女座没有参加比赛，输出”-1”。

输入

3 7
cnz
cuber
moon
3 cnz A AC
5 cuber A AC
6 cnz B CE
10 cuber C AC
20 cnz B AC
30 cuber D TLE
100 cnz E AC

输出

2914
1/2

思路：

细节模拟题，主要有3个坑点。
坑点1：如果一个人AC了D题，后来再次提交的状态为WA或者是CE或者是TLE，之前AC的分数应归0；
坑点2：如果分数相同，则其名次应该是相同的，并且下一个不同的分数依旧按前面有效人数来计数，举个栗子：

分数：  3  2  2  1
排名：  1  2  2  4

从样例来看，分数为1的排名应该是4，而不是3！！！
坑点3：过滤掉没有提交的选手！！！
这道题模拟题大佬们都是放最后才AC的，显然比赛策略应该先过掉简单的，再来考虑复杂的。QWQ

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m, t, vid, pos, cnt, ans, a[5] = {500, 1000, 1500, 2000, 2500}, b[5] = {2, 4, 6, 8, 10}, c[5] = {150, 300, 450, 600, 750};
string name, stat, str; bool flag; char id; map<string, int> mp; map<int, int> my;
struct node{int sum, socre[5], times[5]; bool vis; string man;}nod[505];
bool cmp(node x, node y) {
    return x.sum > y.sum;
}
int main(){
    while(cin >> n >> m) {
        flag = false; vid = 0; mp.clear(); my.clear(); cnt = 1;
        for(int i = 0; i < n; ++i) {
            cin >> str;
            if(str == "cnz") flag = true;
            mp[str] = i;
            memset(nod[i].times, 0, sizeof(nod[i].times));
            memset(nod[i].socre, 0, sizeof(nod[i].socre));
            nod[i].vis = false;
            nod[i].man = str;
        }
        while(m--) {
            cin >> t >> name >> id >> stat;
            if(!nod[mp[name]].vis) nod[mp[name]].vis = true, vid++;
            if(stat == "AC")
                nod[mp[name]].socre[id - 'A'] = max(c[id - 'A'], a[id - 'A'] - b[id - 'A'] * t - 50 * nod[mp[name]].times[id - 'A']);
            else nod[mp[name]].socre[id - 'A'] = 0; //坑点1
            if(stat != "CE") nod[mp[name]].times[id - 'A'] ++;
        }
        if(!flag) cout << -1 << endl;
        else{
            for(int i = 0; i < n; ++i)
                for(int j = 0; j < 5; ++j)
                    nod[i].sum += nod[i].socre[j];
            sort(nod, nod + n, cmp);
            for(int i = 0; i < n; ++i) {
                if(!nod[i].vis) {
                    if(nod[i].man == "cnz") {cout << -1 << endl; break;}
                    else continue; //坑点3
                }
                if(!my[nod[i].sum]) my[nod[i].sum] = cnt; //坑点2
                cnt++;
                if(nod[i].man == "cnz") {
                    cout << nod[i].sum << endl;
                    cout << my[nod[i].sum] << "/" << vid << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

C.处女座的砝码

题目描述

处女座热爱做物理实验，为了实验，处女座必须要精确的知道物品的质量。处女座准备自己设计一套砝码，每一个砝码都是正整数，这套砝码必须能够精确测量出n以内所有正整数的质量，处女座想要知道至少需要多少个砝码。你可以在天平的任意一边放置砝码。

输入描述:

一行，一个正整数 $ n, 1 \leq n \leq 10^{1000} $.

输出描述:

一个整数，表示最少的砝码数。

输入

20

输出

4

说明

你可以选择1，2，6，11
1=1
2=2
3=1+2
4=6-2
5=6-1
6=6
7=6+1
8=6+2
9=6+2+1
10=11-1
11=11
12=11+1
13=11+2
14=11+2+1
15=11+6-2
16=11+6-1
17=11+6
18=11+6+1
19=11+6+2
20=11+6+2+1

思路：

本以为这道题比较难，加上赛中后面G、H两道简单题没写出来，于是就自闭不想了，QWQ，吸取教训，以后做不出来的先放一边，先做其他题目，毕竟有5个小时这么长，还有心态要好。赛后想了一下，发现还是挺简单的，主要是找找规律：（考虑每个砝码的质量）
①1g的砝码肯定是需要的，此时能精确测量的物品质量范围为 $ [1, 1] $。
②假设第二个砝码是 $ x g $，那么和之前的 $ 1 g $ 砝码能精确地测量出的范围最小值是 $ x - 1 $， 最大值是 $ x + 1 $，因为当前2个砝码能测出的范围一定是 $ [1, x + 1] $，也就是说区间是连续的，为了不和之前区间有交叉，则 $ x - 1 = 2 $，即 $ x = 3 $，所以第二个砝码的质量最大只能是 $ 3 g $。如果是 $ 4 g $，显然不能测出2这个正整数。
③继续枚举，由上可知 $ 1 g, 3 g $ 砝码能测出的最大范围是 $ [1, 4] $。现假设第3个砝码的质量为 $ y \; g $，则和之前2个砝码能测出的范围最小值是 $ y - 4 $，最大值是 $ y + 4 $，为了使用更少的砝码数，每加一个砝码后其新增的能测出的范围应该不与之前区间有交叉，则 $ y - 4 = 5 $，即 $ y = 9 $，所以第3个砝码的最大值只能是 $ 9 g $。如果是 $ 10 g $，那么就不能测出5这个正整数。所以由 $ 1 g, 3 g, 9 g $ 的砝码能精确地测量出 $ [1, 13] $ 内的每个正整数……
④按照此策略一直枚举下去，我们就可以发现每个砝码的质量的最大值都是3的幂次倍数，即 $ 1 - k $ 个砝码的质量分别是 $ 3^0, 3^1, 3^2, 3^3, \cdots 3^{k - 1} $，对应能测出的范围最大值分别是 $ 1, 4, 13, \cdots \frac{3^k - 1}{2}$。于是这题的规律就推出来了……最后，虽然题目中的n最大是 $ 10^{1000} $，但由于3的幂指数是爆炸式增长的，所以可以直接循环求和，没有必要取对数这么复杂的操作还容易发生精度误差的问题，java大数简单对拍即可！！！

AC代码：

import java.util.Scanner;
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        BigInteger n = scan.nextBigInteger();
        BigInteger sum = new BigInteger("0");
        BigInteger mul = new BigInteger("1");
        BigInteger k = new BigInteger("3"); 
        int ans = 0;
        while(sum.compareTo(n) == -1){ //sum < n ---> 相等就跳出
            ans++; //砝码个数--->对应其能测出的最大范围
            sum = sum.add(mul);
            mul = mul.multiply(k);
        }
        System.out.println(ans);
    }
}

D.处女座与重修费

题目描述

期末考试结束了，处女座发现很多人挂了大物，只能等着第二年重修，还要交400元的重修费。处女座突然想起有个学长和他讲过，如果学校哪一年缺钱了，那一年的大物试卷就会特别难。现在处女座有了所有人的成绩，处女座想知道如果所有挂科的人都在第二年重修，学校能赚多少重修费？
挂科是指一门课的分数小于60分。

输入描述:

第一行一个整数n，表示考试的人数。
第二行n个整数，表示每个人的成绩。$ 1 \leq n \leq 10000 $。
学生的成绩为 $ 0-100 $（包括0和100）之间的整数。

输出描述:

一行，学校能赚的重修费用。

输入

4
60
56
100
59

输出

800

思路:

签道题！

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,x,ans;
int main() {
    while(cin >> n){
        ans = 0;
        while(n--) {
            cin >> x;
            if(x < 60) ans++;
       }
        cout << ans * 400 << endl;
    }
    return 0;
}

G.处女座与复读机

题目描述

一天，处女座在牛客算法群里发了一句“我好强啊”，引起无数的复读，可是处女座发现复读之后变成了“处女座好强啊”。处女座经过调查发现群里的复读机都是失真的复读机，会固定的产生两个错误。一个错误可以是下面的形式之一：
1.将任意一个小写字母替换成另外一个小写字母；
2.在任意位置添加一个小写字母；
3.删除任意一个字母；
处女座现在在群里发了一句话，他收到了一个回应，他想知道这是不是一个复读机。

输入描述:

两行，第一行是处女座说的话s，第二行是收到的回应t
s和t只由小写字母构成且长度小于100。

输出描述:

如果这可能是一个复读机输出”YES”，否则输出”NO”。

输入

abc
abcde

abcde
abcde

输出

YES

YES

说明

样例1：abc->abcd->abcde
样例2：abcde->abcdd->abcde

备注:

只要能经过两步变换就从s得到t就有可能是复读机。

思路：

第二场比赛的dp，没想到用dfs，直接模拟，然后一直WA，进而自闭，QWQ……以后要像大佬一样多涨点暴搜技能(流下了不做题的眼泪)。这道题一开始的想法是求最长公共子序列的长度，但是WA，赛后有位OI大佬给出一组hack数据：

abxyabcd
ababxycd

可知上面的LCS为6，$ 8 - 6 \leq 2 $，输出是YES，实际上是NO，原因就是LCS没办法考虑位置。题目给的字符串长度最大只有100，最简单的做法就是暴力搜索啦，get！！！

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 105;
int len1, len2;char s1[maxn], s2[maxn]; bool flag;
void dfs(int la, int lb, int cnt) {
    if(cnt > 2 || flag || la > len1 || lb > len2) return;
    if(la == len1 && lb == len2) {flag = true; return;}
    if(s1[la] == s2[lb]) dfs(la + 1, lb + 1, cnt); //跳过
    else {
        dfs(la + 1, lb + 1, cnt + 1); //替换
        dfs(la + 1, lb, cnt + 1); //删除
        dfs(la, lb + 1, cnt + 1); //添加
    }
}
int main(){
    while(cin >> s1 >> s2) {
        len1 = strlen(s1), len2 = strlen(s2);
        flag = false; //不是复读机
        if(abs(len1 - len2) <= 2) dfs(0, 0, 0);
        puts(flag ? "YES" : "NO");
    }
    return 0;
}

H.处女座的测验（一）

题目描述

处女座进行了一场c语言的考试，要求很简单，输出2000个正整数，并且满足以下条件：
1.任意两个数互质；
2.任意两个数 $ x,y $，满足 $ \tau(x * y) > 10 $，其中 $ \tau(n) $ 为n的因子的个数；
举例：6的因子有1，2，3，6，所以 $ \tau(6) > 10 $。

输入描述:

本题没有输入

输出描述:

2000行，每行一个正整数。输出的每个整数都必须在 $ 1 - 4 * 10^8 $ 之间，如果有多组答案，输出任意一组即可。

思路:

任意两个数互质，显然只能是素数，又因为任意两个数要满足其乘积的因子个数大于10，根据约数个数定理 $\tau(n) = \prod_{j = 1}^k (a_j + 1)$ 可知一个数只需由两个素数组合而成，但不是任意的组合，因为题目中还有规定每个整数必须在 $1 - 4 * 10^8$，而且只需输出2000个整数。为了尽可能组成较小且满足条件的数字，就让第1个素数和第4000个素数匹配，第2个素数和第3999个素数匹配……也就是先筛选出4000个素数，然后首尾两两组合并输出，最后一个数肯定是这些数中最大的，检验一下其 $(302446877 = 3 * 10^8)$ 不超过 $4 * 10^8$，即这种组合策略是正确的。QWQ

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 4005;
int cnt = 0, prime[maxn];
bool check(int x) {
    for(int i = 2; i * i <= x; ++i)
        if(x % i == 0) return false;
    return true;
}
int main(){
    for(int i = 2; i < 50000 && cnt < 4000; ++i) //筛选出4000个素数
        if(check(i)) prime[cnt++] = i;
    for(int i = 0; i < 2000; ++i)
        cout << prime[i] * prime[3999 - i] << endl; 
    return 0;
}

I.处女座的测验（二）

题目描述

现在处女座顺利的完成了测验，处女座想要知道知道自己输出的结果是否正确。他希望知道自己有自己输出的数中有多少对是不满足要求的。更具体的，处女座想知道下面程序段的答案。其中 $ \tau(n) $ 为n的因子的个数。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2005;
int n, a[maxn];
int main() {
    while(cin >> n) {
        for(int i = 1; i <= n; ++i) cin >> a[i];
        int ans = 0;
        for(int i = 1; i <= n; ++i) {
            for(int j = i + 1; j <= n; ++j) {
                if(τ(a[i] * a[j]) <= 10) ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

输入描述:

两行。第一行一个整数n.
第二行n个整数，$ a_1, a_2, \cdots, a_n $。
$ 2 \leq n \leq 2000, 1 \leq a_i \leq 3 * 10^8 $。

输出描述:

一行，一个整数ans。

输入

7
34 45 23 12 63 23 90

输出

3

备注:

不保证任意两个整数互质。

思路：

显然此题与约数个数定理有关：$\tau(n) = \prod_{j = 1}^k (a_j + 1)$。做法：先求出每个数的所有素因子，以及素因子的次方数。重要剪枝：只要某个数中素因子种类数超过3，就将其过滤掉，因为其约数至少为 $ 2^4 = 16 $ 个，显然不满足题目条件，跳过。然后根据约数个数定理进行统计：有相同的素因子先累加其个数再计数，否则对每个素因子的个数单独计数。

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2005;
LL n, ans, p1, p2, tot, a[maxn];
vector<pair<LL, LL> > vec[maxn];
int main() {
    while(~scanf("%lld", &n)) {
        for(LL i = 0; i <= n; ++i) vec[i].clear();
        for(LL i = 0; i < n; ++i) {
            scanf("%lld", &a[i]);
            for(LL j = 2; j * j <= a[i]; ++j) {
                if(a[i] % j == 0) {
                    LL cnt = 0;
                    while(a[i] % j == 0) cnt++, a[i] /= j;
                    vec[i].push_back(make_pair(j, cnt));
                }
            }
            if(a[i] > 1LL) vec[i].push_back(make_pair(a[i], 1LL));
        }
        for(LL i = 0; i < n; ++i) {
            if(vec[i].size() > 3LL) continue; // 2^3 == 8 , 2^4 == 16 过滤掉一些数的素因子种类数超过3
            for(LL j = i + 1; j < n; ++j) {
                if(vec[j].size() > 3LL) continue; //同上
                p1 = 0LL, p2 = 0LL, tot = 1LL; 
                while(p1 < vec[i].size() && p2 < vec[j].size()) { //有相同的素因子，则累加其个数，再计数
                    if(vec[i][p1].first > vec[j][p2].first) tot *= (vec[j][p2++].second + 1LL);
                    else if(vec[i][p1].first < vec[j][p2].first) tot *= (vec[i][p1++].second + 1LL);
                    else tot *= (vec[i][p1++].second + vec[j][p2++].second + 1LL);
                }
                while(p1 < vec[i].size()) tot *= (vec[i][p1++].second + 1LL); //剩余部分
                while(p2 < vec[j].size()) tot *= (vec[j][p2++].second + 1LL);
                if(tot <= 10LL) ans++; //如果当前tot不超过10，则满足条件，计数器加1
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

J.处女座的期末复习

题目描述

快要期末考试了，处女座现在有n门课程需要考试，每一门课程需要花 $ a_i $小时进行复习，考试的起始时间为$ b_i $，处女座为了考试可以不吃饭不睡觉，处女座想知道他能否复习完所有的科目（即在每一门考试之前复习完该科目）。每一门课的考试时间都为两小时。

输入描述:

第一行一个整数n；
第二行n个整数 $ a_1,a_2,\cdots,a_n $,表示每门课需要复习的时间；
第三行n个整数 $ b_1,b_2,\cdots,b_n $,表示每门课考试的时间。
$ 1 \leq n \leq 10^5 $
$ 0 \leq a_i \leq 10^9 $
$ 0 \leq b_i \leq 10^9 $

输出描述:

如果处女座能复习完，输出”YES”，否则输出”NO”

输入

3
0 1 1
2 6 4

输出

YES

说明

在0-1小时复习第2门课，
在1-2小时复习第3门课，
在2-4小时考第1门课，
在4-6小时考第3门课，
在6-8小时考第2门课

备注:

考试时不能复习，保证考试时间不会重叠。复习可以拆开，只要复习时间够了即可。

思路：

按考试时间升序排，如果考试的起始时间相同，则按复习时间降序排，每次以当前一门考试科目的最终时间为右边界，同时累加当前已用时间，如果已用时超过右边界，说明当前科目不能复习完，break即可。

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n, rt, now_spend; bool flag;
struct node{
    int need, st;
}nod[maxn];
bool cmp(node a, node b) {
    if(a.st != b.st) return a.st < b.st;
    else return a.need > b.need;
}
int main() {
    while(cin >> n) {
        for(int i = 0; i < n; ++i) cin >> nod[i].need;
        for(int i = 0; i < n; ++i) cin >> nod[i].st;
        sort(nod, nod + n, cmp);
        now_spend = rt = 0; flag = false;
        for(int i = 0; i < n; ++i) {
            rt = nod[i].st + 2;
            now_spend += nod[i].need + 2;
            if(now_spend > rt) {flag = true; break;}
        }
        puts(flag ? "NO" : "YES");
    }
    return 0;
}