2023牛客寒假基础集训营1

2023牛客寒假算法基础集训营1

比赛链接

A World Final? World Cup! (I)

A

• 模拟

1. 题意

A和B两方点球，A队先点，总共10球。给出点球的结果，如：0101011010.

现在需要判断在踢完第几球时结束，并输出第几次，如果10球无法分出胜负就输出-1.

2. 解题思路

直接一球球的去判断即可，当另一方无法挽回胜负的时候，也就是剩下的球数全进也无法追平比分，那么就能分出胜负了.

3. 代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main()  
{   
    int t; cin >> t; while (t -- )
    {
        string s;
        cin >> s;
        int c1 = 0, c2 = 0;
        int res = -1;
        for (int i = 0; i < s.size(); i ++ )
        {
            if (i % 2 == 0 && s[i] == '1') c1 ++ ;
            if (i % 2 == 1 && s[i] == '1') c2 ++ ;

            //当res==-1，也就是还无法分出胜负.
            //c1-c2为A队大于B队的分， (10-i)/2为B队剩下的轮数
            if ((c1 - c2 > (10 - i) / 2 || c2 - c1 > (9 - i) / 2) && res == -1) res = i + 1;
        }
        cout << res << endl;
    }

    return 0;
}

L 本题主要考察了运气

L

• 数学, 运气(?)

1. 题意

5个团，每个团4个人，求猜中某个人的最佳策略的期望次数

2. 解题思路

1. 如题意，可以1到100猜(❌)
2. 每个团和每个人没区别，最佳策略就是依次猜，算出期望次数是5.05，带入给的公式就是32

3. 代码

#include <bits/stdc++.h>
using namespace std;

int main()  
{
    cout << 32;

    return 0;
}

C 现在是，学术时间 (I)

C

• 诈骗，思维，贪心

1. 题意

H为一个教授发表的所有论文，有至少H篇论文引用量大于等于H。现在每个教授有一篇文章，也给出了这篇文章的引用量

重新分配这些文章，要求出重新分配后所有教授的H值的最大

2. 解题思路

实际上不重新分配就是最大值，所有引用量非0的文章都带来了1的H指数，最优解就是非0文章的数量

3. 代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        int n;
        cin >> n;
        int sum = 0;
        for (int i = 0; i < n; i ++ )
        {
            int x;
            cin >> x;
            if (x != 0) sum ++ ;
        }
        cout << sum << endl;
    }
}

D 现在是，学术时间 (II)

D

• 分类讨论

1. 题意

给定两个矩形，需要求出 交集面积/并集面积的最大值.

一个矩形确定了位置，另一个矩形只给了一个点

2. 解题思路

分类讨论就可以，没什么好说的

3. 代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m;

double area(double x1, double y1, double x2, double y2)
{
    double area = (x2 * y2) - (x1 * y1);
    return area;
}

void solve()    
{
    double n, m, x, y;
    cin >> n >> m >> x >> y;

    double res = 0;
    if (x <= n && y <= m) 
    {
        double s1 = x * y, s2 = x * (m - y), s3 = y * (n - x), s4 = (n - x) * (m - y); 
        res = max(res, s1);
        res = max(res, s2);
        res = max(res, s3);
        res = max(res, s4);

        res = res / (n * m);
    }
    else if (x > n && y > m)
    {
        res = (n * m) / (x * y);
    }
    else if (x > n && y <= m)
    {
        double s1 = n * (m - y), s2 = n * y;
        s1 = s1 / ((x - n) * (m - y) + n * m);
        s2 = s2 / ((x - n) * y + n * m);

        res = max(res, s1);
        res = max(res, s2);
    }
    else
    {
        double s1 = (n - x) * m, s2 = x * m;
        s1 = s1 / ((n - x) * (y - m) + n * m);
        s2 = s2 / (x * (y - m) + n * m);
        
        res = max(res, s1);
        res = max(res, s2);
    }

    printf("%.9f\n", res);
}

int main()  
{
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    
    int t; cin >> t; while (t -- )
    solve();

    return 0;
}

K 本题主要考察了dp

K

• 贪心

1. 题意

需要写出一个仅有0和1组成的长度为n的字符串，要求恰好有m个字符是1

而在字符串的长度为3的子区间内，如果1的个数多于0的个数，那么这就是一个坏区间

现在要求出坏区间总数最少的字符串中有几个坏区间

2. 解题思路

(或许贪心真的靠猜？)

写一写试试，就会发现类似10010010001111这样的区间是最优的

我分为3部分：

1. 在可以保证剩下的位置放够m个1的前提下，放入100
2. 如果还可以放10，那就放入一个10
3. 将剩下的1放入

3. 代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    //cnt00代表可以填入的100的个数，也就是可以填入的00的个数，cnt0为可能还可以填入一个0
    int cnt00 = (n - m) / 2, cnt0 = (n - m) % 2;
    string s;
    for (int i = 0; i < cnt00; i ++ ) s += "100";
    if (cnt0) s += "0";
    for (int i = 0; i < (n - cnt00 * 3 - cnt0); i ++ ) s += "1";

    //直接枚举，来找到坏区间个数
    int res = 0;
    for (int i = 0; i < s.size() - 2; i ++ )
    {
        int cnt = 0;
        if (s[i] == '1') cnt ++ ;   
        if (s[i + 1] == '1') cnt ++ ;
        if (s[i + 2] == '1') cnt ++ ;
        if (cnt > 1) res ++ ; 
    }
    cout << res << endl;

    return 0;
}

M 本题主要考察了找规律

M

• DP

1. 题意

波奇买了m份章鱼仙贝，来分给n为朋友。

当前剩下的仙贝数为x，给一个朋友y个仙贝，那么这个朋友队小波奇的好感度增加 y/x

每个人最多送一次，需要求出总好感度最大的情况

2. 解题思路

就是DP……知道但做的时候不会写，写的还是太少了，之后其实看看还挺清晰的

f [ i ] [ j ]表示给到了第 i 个朋友，给出了 j 份仙贝, 因为到最后把所有仙贝给出才最大，所以答案是f [n] [m]

状态转移方程： f [i] [j] = max(f [i] [j], f [i - 1] [j - k] + k / (m - (j - k))), 也就是给了第 i 个朋友 k 个仙贝

3. 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 510;

double f[N][N];

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k] + (double)k / (m - (j - k)));

    printf("%.8f\n", f[n][m]);

    return 0;
}

G 鸡格线

G

• 数据结构，性质

1. 题意

有一个长度为n的数组a，支持以下两种操作：

1. 对区间[l, r] 中的左右数字执行 x = round(10 * sqrt(x)), round为四舍五入
2. 输出当前数组所有数字的和

2. 解题思路

模拟什么的肯定过不去，写的时候并没有什么思路，想把操作记录下来，之后再去变值，可是中途会输出所有数字的和，就有点无从下手了（太菜了）

首先有三个临界值0，99，100。也就是每个数在经过几次十几次变化后就会达到临界值的值而不再变化，这样 k 的值就可以转变为一个11以内的数（多次尝试发现11正好能通过）

知道这一点后问题就成为了如何知道谁没有更新，可以用set来存储，然后用lower_bound()来找[l,r]区间内没有到达临界值的数，注意要在set中插入n+1,不然会出现问题

3. 代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;

set<int> st;//存储的是下标
ll a[N];

int f(int x)
{
    return round(sqrt(x) * 10);
}

int main()
{
    ll n, m;
    cin >> n >> m;

    ll sum = 0;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        sum += a[i];
        //如果还没有到达临界值，就进入set集合
        if (f(a[i]) != a[i]) st.insert(i);        
    } 

    //防止越界访问!!!
    st.insert(n + 1);

    while (m -- )
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int l, r, k;
            cin >> l >> r >> k;
            //从l开始找
            int pos = l;
            while (1)
            {
                //找到大于等于当前的在集合中的下标
                int now = *st.lower_bound(pos);
                //超出了r，就跳出循环
                if (now > r) break;
                //更新k次，实际更新次数很小，所以取min(k,11)
                for (int i = 1; i <= min(k, 11); i ++ )
                {
                    sum -= a[now];
                    a[now] = f(a[now]);
                    sum += a[now];
                }             
                //如果到达临界值，就移除set集合      
                if (f(a[now]) == a[now]) st.erase(now);
                //后移一位
                pos = now + 1;
            }
        }
        else cout << sum << endl;
    }

    return 0;
}

F 鸡玩炸蛋人

F

• 思维，图论，并查集

1. 题意

n个结点，m条边，可以控制炸蛋人进行操作：移动和放置炸弹。不能移动到有炸蛋的地方，但可以从有炸蛋的地方出发。

现在给出最终给出每个点的炸蛋数量，需要求出有多少种起点终点方案（保证起点终点至少有一个不同）

2. 解题思路

在连通块内，无论炸蛋如何防止，以任意两点作为起点和终点，都可以做到，

引用大佬的证明：

连边之后，分成了多个连通块。这样可以分成3种情况：

1. 有大于一个连通块有炸蛋，因为连通块之间并不连接，所以无解
2. 只有一个连通块有炸蛋，这样就只能在这一个连通块中移动，才能保证最终可以放置炸蛋
3. 没有连通块有炸蛋，此时可以在任意一个连通块内移动

3. 代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;

int p[N], num[N];
map<int,int> mp;

//维护并查集
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

//合并并查集，并且更新联通块数量
void add(int a, int b)
{
    p[b] = a;
    num[a] += num[b];
}

int main()
{
    int n, m;
    cin >> n >> m;

    //初始化并查集，自己为跟节点。 初始化连通块数量为1。
    for (int i = 1; i <= n; i ++ ) p[i] = i, num[i] = 1;

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        a = find(a), b = find(b);
        if (p[a] != p[b]) 
        {
            add(a, b);
        }
    }

    //存储有炸蛋的连通块
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        cin >> x;
        if (x != 0) mp[find(i)] ++ ;
    }

    //分3种情况
    if (mp.size() > 1) cout << 0 << endl;
    else if (mp.size() == 1)
    {
        int x = mp.begin()->first;
        ll res = 1ll * num[x] * num[x];
        cout << res << endl;
    }
    else
    {
        ll res = 0;
        for (int i = 1; i <= n; i ++ )
        {
            if (find(i) == i)
            {
                res = res + 1ll * num[i] * num[i];
            }
        }
        cout << res << endl;
    }

    return 0;
}

E 鸡算几何

E

• 计算集合，叉乘

1. 题意

二维的平面上有一根 L 型的铁丝，由AB和BC两条线段组成，现在能对这根铁丝进行三种操作：

1. 任意平移即铁丝上每一个点横坐标都变化Δx、纵坐标都变化Δy；
2. 以B点为轴，任意的旋转铁丝
3. 将铁丝拿起，在手里任意调整铁丝后，再放回（不能使铁丝发生形变）

操作完后铁丝为DEF(不保证和ABC三点一 一对应)，现在给出ABC和DEF的坐标。

需要判断：是否可以断言一定使用过至少一次第三次操作

2. 解题思路

• 一大坑点：ABC和DEF不一定对应

当时这个大坑点，我调了很久都调不过来，印象深刻(寄)

其实就是判断有没有进行过翻着就可以了，然后就用到了叉乘，（第一次见）

先根据长度来判断对应的边，然后判断叉乘的正负是否相同即可判断是否发生了翻折。

特判：当AB和BC两条边相等时，就无法判断是否发生了翻折

3. 代码

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-9;

double len(double x1, double y1, double x2, double y2)
{
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

double cmp(double x1, double y1, double x2, double y2, double x3, double y3)
{
    return (x1 - x2) * (y2 - y3) - (y1 - y2) * (x2 - x3);
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        double x1, x2, y1, y2, x3, y3, x4, y4, x5, y5, x6, y6;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
        cin >> x4 >> y4 >> x5 >> y5 >> x6 >> y6;

        double len1 = len(x1, y1, x2, y2), len2 = len(x2, y2, x3, y3);
        //如果AB和BC长度相等，那就无法判断是否发生翻折
        if (fabs(len1 - len2) < eps) 
        {
            cout << "NO" << endl;
            continue;
        }
        int res1 = cmp(x1, y1, x2, y2, x3, y3);

        double len3 = len(x4, y4, x5, y5);
        double res2;
        //根据AB和DE的长度，来判断是否对应，并求出DEF叉乘
        if (fabs(len3 - len1) < eps) res2 = cmp(x4, y4, x5, y5, x6, y6);
        else res2 = cmp(x6, y6, x5, y5, x4, y4);

        //如果叉乘正负性不同，就代表发生偏折
        if (res1 * res2 > 0) cout << "NO" << endl;
        else cout << "YES" << endl;
    }

    return 0;
}