算法练习专栏——牛客练习——“现代汽车中国前瞻软件赛杯”牛客周赛Round43

A:小红平分糖果

题目描述

小红拿到了n个糖果，她准备和小紫平分这些糖果，也就是说她们拿到的糖果数量必须相同。请你计算她们各自分到多少糖果。

输入描述:

1 2	`一个正整数n。 1≤n≤100`

输出描述:

1 2	`如果无法平分，请输出-1。否则输出两个正整数x,y，用空格隔开，代表小红和小紫拿到的糖果。`

示例1

输入

复制

输出

复制

-1

说明

1	`无论小红分到几颗糖果，小紫的糖果数量都无法和小红的相同。`

示例2

输入

复制

输出

复制

3 3

代码

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    if (n % 2 == 0) {
        cout << n / 2 << " " << n / 2;
    }
    else cout << "-1";
}

B:小红的完全平方数

链接

题目描述

小红有一个正整数 x，她可以进行任意次操作，每次将 x 加上 2，或者将 x 减去 2。

她现在想知道，如果将 x 变为完全平方数，最少需要多少次操作呢，请你帮帮她吧。

输入描述:

1	`输入包含一行一个正整数x，表示小红的数字 x (1≤x≤1012)。`

输出描述:

1	`输出包含一行，表示最少的操作次数。`

示例1

输入

复制

输出

复制

说明

1 2	`可以进行两次 "+2" 操作，变为 9，是完全平方数。也可以进行两次 "-2" 操作，变为 1，也是完全平方数。`

思路

首先,使用二分找到第一个大于等于x的完全平方数k,然后我们是可以知道最终的答案应该是分布在以k为中心**(包括它本身)**的5个完全平方数里面.

我们只需要依次寻找差值最小的即可.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL ans = 1e12;
int main()
{
    long long x;
    cin >> x;
    
    LL l = 1, r = 1e6;
    while (l < r) {
        LL mid = l + r >> 1;
        if (mid * mid >= x) r = mid;
        else l = mid + 1;
    }
    
    --r;
    --r;
    
    if ((r % 2) == (x % 2)) {
        ans = min(ans, abs(x - r * r) / 2);
    }
    ++r;
    if ((r % 2) == (x % 2)) {
        ans = min(ans, abs(x - r * r) / 2);
    }
    ++r;
    if ((r % 2) == (x % 2)) {
        ans = min(ans, abs(x - r * r) / 2);
    }
    ++r;
    if ((r % 2) == (x % 2)) {
        ans = min(ans, abs(x - r * r) / 2);
    }
    ++r;
    if ((r % 2) == (x % 2)) {
        ans = min(ans, abs(x - r * r) / 2);
    }
    cout << ans;
    return 0;
}

C:小苯的字符串变化

链接

题目描述

小苯有一个长度为 n 的字符串 s，每次操作他可以选择一个位置的字母将其的大小写反转，也就是说如果字符是小写，则操作后会变成大写，如果字符是大写则反之。

他现在希望将 s 变为：“前面若干字符是大写，后面的字符全是小写”的样子，例如：”AABBccdd”。

（但全大写和全小写均不合法）

请问他最少需要进行几次操作呢，请你帮帮他吧。

输入描述:

1	`输入包含一行一个字符串 s (2≤∣s∣≤105)，表示题中所述的字符串，保证只包含小写和大写字母。`

输出描述:

1	`输出包含一行一个整数，表示最少的操作次数。`

示例1

输入

复制

aaBB

输出

复制

说明

1	`可以将字符串变为："AABb"，操作了 3 次。`

示例2

输入

复制

AAAA

输出

复制

说明

1	`变为："AAAa"，操作 1 次。`

思路

这道题目可以这样思考,就是我们先枚举A,a的分开位置,比如说AaAAAa这个字符串可以以1~len - 1这些位置为界分别转换为Aaaaaa, AAaaaa, AAAaaa,AAAAaa,AAAAAa,分别计算转换为该类字符串所需变化数量即可,这里用两个前缀和即可简单计算.

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
char s[N];
int s0[N], s1[N];
int ans = 1e9;

int main()
{
    scanf("%s", s);
    int len;
    for (len = 0; s[len]; len++) {
    if (s[len] >= 'A' && s[len] <= 'Z') s[len] = 'A';
        else s[len] = 'a';
    }
    if (s[0] == 'A') s1[0]++;
    else s0[0]++;
    for (int j = 1; j < len; j++) {
        if (s[j] == 'A') s1[j] = s1[j - 1] + 1, s0[j] = s0[j - 1];
        else s0[j] = s0[j - 1] + 1, s1[j] = s1[j - 1];
    }
    
    for (int j = 0; j < len - 1; j++) {
        ans = min(ans, s0[j] + s1[len - 1] - s1[j]);
    } 
    
    cout << ans;
//     for (int j = 0; j < len; j++) cout << s0[j] << " " << s1[j] << '\n';
    return 0;
}

D:小红的子数组排列判断

原题

题目描述

小红拿到了一个数组，她想知道有多少个长度为k的连续子数组是排列？

定义排列为：1到k每个元素都恰好出现了1次。

输入描述:

第一行输入两个正整数n,k，代表小红拿到的数组大小和连续子数组的大小。
第二行输入n个正整数ai，代表数组中的元素。
1≤k≤n≤105
1≤ai≤105

输出描述:

1	`一个整数，代表长度为k的连续子数组是排列的数量。`

示例1

输入

复制

1 2	`5 2 1 2 1 1 2`

输出

复制

说明

1	`有3个长度为2的连续子数组是排列：两个[1,2]和一个[2,1]`

思路

本人这里使用的是类似于滑动窗口的思想,详细的思路请看以下描述:

这里我们需要构建一个长度为k的子序列,我们现在要做的就是从左往右依次维护这个长度为k的数组,保证这个数组一定是由1~k的一种全排序构成的.这样我们每移动一位就需要维护一下这个数组,判断是否符合条件,符合条件ans++.而这里如何维护就是这道题目的一个难点,具体的维护方式请看代码.

代码

#include <iostream>
#include <set>

using namespace std;
const int N = 1e5 + 10;
int st[N];
int a[N], s[N];
int ans;
set<int> p;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n, k;
    bool flag = true;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    // 将不符合条件的放入p中(这里专指大于k的)
    for (int i = 1; i <= k; i++) {
        if (st[a[i]] || a[i] > k) p.insert(a[i]);
        st[a[i]]++;
    }
    if (p.empty()) ans ++;
    
    // 这里的 i 表示的是连续子数组尾部位置
    for (int i = k + 1; i <= n; i++) {
//         cout << ans << '\n';
        // 首先就需要预处理一下,指的是将已经跑出子数组的第一位置的数st[a[i - k]]数量去掉
        st[a[i - k]]--;
        // 然后就是进来的++一下
        st[a[i]]++;
        
        // 下面4行代码的主要思想就是将违规的情况加入p或者前面的数弹出去之后不再违规的数插入进来
        
        
        if (st[a[i - k]] <= 1 && a[i - k] <= k) p.erase(a[i - k]);
        else p.insert(a[i - k]);
        
        if (st[a[i]] <= 1  && a[i] <= k) p.erase(a[i]);
        else p.insert(a[i]);
        
        if (p.empty()) ans ++;
    }
    
    cout << ans;
}

E:小红的平行四边形

链接

题目描述

小红在平面上有n个点，她准备选择其中四个点画一个平行四边形。请你帮小红求出平行四边形的最大面积。

输入描述:

第一行输入一个正整数n，代表点的数量。
接下来的n行，每行输入2个整数xi，代表第i个点的坐标。
4≤n≤1000
−109≤xi,yi≤109
保证不存在两个重合的点。

输出描述:

1 2	`如果不存在平行四边形，请输出-1。否则输出一个浮点数，代表平行四边形的面积。保留一位小数。`

示例1

输入

复制

输出

复制

1.0

说明

1	`选前四个点即可（正方形也是平行四边形）`

思路

持续更新中……

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<LL, LL> PII;
const int N = 1e3 + 10;
int x[N], y[N];
map<PII, set<PII>> Map;
LL res = -1;

LL clk() {
    return chrono::steady_clock::now().time_since_epoch().count();
}
int main()
{
    LL st = clk();
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j) {
                LL x1 = x[i] - x[j], y1 = y[i] - y[j];
                // 存对于横坐标差和纵坐标差为x1,y1的坐标有哪些
                Map[{x1, y1}].insert({x[i], y[i]});
            }
        }
    }
    
    for (auto [p, s] : Map) {
        auto [x1, y1] = p;
        if (clk() - st > 1.9e9) break;
        
        // 下面就是一个一个遍历了,看看距离相同的情况下,坐标是否不重合且平行,但是这里比较极限
        // ,上面用到了一个比较离谱的玩意
        for (auto [x2, y2]:s) {
            for (auto [x3, y3]:s) {
                LL x = x2 - x3, y = y2 - y3;
                if (!x && !y) continue;
                LL w = x1 * y - y1 * x;
                if (w == 0) continue;
                res = max(res, llabs(w));
            }
        }
    }
    if (res == -1) cout << -1;
    else cout << res << ".0";
    
    return 0;
}

算法学习专栏——线段树——线段树的多类操作(有问题!!!debug中.......) 上一篇

杂题——转圈下一篇