分类 OI 下的文章

Codeforces Round #574 (Div. 2)

A. Drinks Choosing 2s/256MB

题意

给定a[i],每次选出一个x,在集合中删去两个和x相等的数,最多做n/2上取整次,问最多划掉多少个。

#include <iostream>
 
const int N = 1001;
 
int cnt[N];
 
int main () {
    register int i, j;
    int n, m, x;
 
    std::cin >> n >> m;
    for (i = 1; i <= n; ++ i) {
        std::cin >> x;
        ++ cnt[x];
    }
 
    int ans = 0;
    for (i = 1; i <= m; ++ i) {
        ans += (cnt[i] % 2);
    }
 
    std::cout << n - ans / 2;
 
    return 0;
}

B. Sport Mafia 2s/256MB

题意

有一个盒子,每次操作可以放入或吃掉盒子里若干个糖果(第一次操作必须放入一个糖果)。给定操作数和盒子里最终剩余的糖果,求吃掉了多少个糖果。

解法

推一元二次方程的求根公式

#include <iostream>
#include <cmath>
 
typedef long long ll;
 
int main () {
    ll n, k, m, d;
 
    std::cin >> n >> k;
    m = (n + k) * 2;
    d = std::round(std::sqrt(9 + 4 * m));
    std::cout << n - (d  - 3) / 2 << "\n";
 
    return false; 
}

C. Basketball Exercise

题意

给2*n个数组,选取若干上下左右不相邻的数,使得和最大,求这个和

解法

简单DP,令fi分别为第i列中,不取,取第一个数,取第二个数三种情况的累加和

#include <iostream>
 
typedef long long ll;
const int N = 1e5+1;
 
ll a[N][3], f[N][3];
 
inline ll max(ll x, ll y) {
    return x > y ? x : y;
}
 
int main () {
    register int i, j;
    ll n;
 
    std::cin >> n;
    for (i = 1; i <= n; ++ i) std::cin >> a[i][0];
    for (i = 1; i <= n; ++ i) std::cin >> a[i][1];
 
    for (i = 1; i <= n; ++ i) {
        f[i][0] = max(f[i - 1][1], f[i - 1][2]) + a[i][0];
        f[i][1] = max(f[i - 1][0], f[i - 1][2]) + a[i][1];
        f[i][2] = max(f[i - 1][0], max(f[i - 1][1], f[i - 1][2]));
    }
 
    std::cout << max(f[n][0], max(f[n][1], f[n][2]));
 
    return 0;
}

D1. Submarine in the Rybinsk Sea (easy edition) &

D2. Submarine in the Rybinsk Sea (hard edition)

素数判定和筛选算法

I 素数判定算法

枚举判定

对于正整数n,枚举2~n-1以判定n是否为指数
时间复杂度为O(n);

bool check(int x) {
    if (x == 1) return false;
    if (x == 2) return true;
    for (int i = 2; i < x; ++ i) {
        if (x % i == 0) return false;
    }
    return true;
}

优化枚举判定

不难发现,正整数的n总是成对出现的。对于n的判定,只要枚举到sqrt n就可以了
时间复杂度为O(sqrtn);

bool check(int x) {
    if (x == 1) return false;
    if (x == 2) return true;
    for (int i = 2; i * i < x; ++ i) {
//  for (int i = 2; i < sqrt(x); ++ i) {  这样写也是正确的
        if (x % i == 0) return false;
    }
    return true;
}

再优化枚举判定[1]

令$$x≥1$$,将≥5的自然数表示如下
$6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5,6(x+1),6(x+1)+1..$
可知

I 素数筛选算法

C++中的那些极值

最近在写SPFA时候发现这个极值的问题,在C++中其实已经有了解决。

数据类型的极值

在limits.h中,我们可以找到如下定义(已简化):

#define CHAR_BIT    8
#define MB_LEN_MAX    2
#define SCHAR_MIN    (-128)
#define SCHAR_MAX    127
#define UCHAR_MAX    255
#define CHAR_MIN    SCHAR_MIN
#define CHAR_MAX    SCHAR_MAX
#define INT_MAX        2147483647
#define INT_MIN        (-INT_MAX-1)
#define UINT_MAX    0xFFFFFFFF
#define SHRT_MAX    32767
#define SHRT_MIN    (-SHRT_MAX-1)
#define USHRT_MAX    0xFFFF
#define LONG_MAX    2147483647L
#define LONG_MIN    (-LONG_MAX-1)
#define ULONG_MAX    0xFFFFFFFFUL
#define SSIZE_MAX    LONG_MAX
#define LONG_LONG_MAX    9223372036854775807LL
#define LONG_LONG_MIN    (-LONG_LONG_MAX-1)
#define ULONG_LONG_MAX    (2ULL * LONG_LONG_MAX + 1)#define _I64_MIN    LONG_LONG_MIN
#define _I64_MAX    LONG_LONG_MAX
#define _UI64_MAX    ULONG_LONG_MAX

在使用时,只需要包含<limits.h>或者<climits>。

文件名长度的极值MAX_PATH

在Windows下,文件名的长度是有限制的。
注意,这里的文件名长度是指包含目录到文件名的全路径字符长度
就譬如"C:Program FilesMicrosoft Office"这样的一个完整路径长度不能超过260。
这一点在Microsoft官网可以找到解释
https://docs.microsoft.com/zh-cn/windows/win32/fileio/naming-a-file#maximum-path-length-limitation
a.png

并查集

1

并查集就是解决若干元素所属的集合关系的一类问题
简单来说并查集一般有以下几个操作:将两个元素所在的集合合并;查找某个元素所在的集合(根节点)

2

初始化

一般的,在初始情况下,每个元素自成一个集合,这个集合的根节点就是元素本身。
并查集-1.png
用数组fa[]来记录该并查集的话,初始化应该是这样的:

void init(int x) {  //并查集元素个数
    for (int i = 1; i <= x; ++ i) fa[i] = i;
}

查找根节点

简单的,不断顺着数组fa[]“逆流而上”查找,直到fa[x] = x时就找到根节点了,可以用递归或者循环实现。

int get(int x) {  // 获取x的根节点
    if (fa[x] = x) return x;  //找到根节点后返回答案
    return get(fa[x]);
}

注意,并查集有可能遇到这样的糟糕情况:
并查集-4.png
当我们试图查找节点5的根节点时,我们需要遍历整个并查集才能找到节点1。在百万或以上的数据规模中,这种无意义的时间消耗是致命的,所以我们需要路径压缩,将上图的情况优化成这样:
并查集-5.png
这样从节点5就可以一次性找到节点1了。
代码优化后实现如下

int get(int x) {  // 获取x的根节点
    if (fa[x] = x) return x;  //找到根节点后返回答案
    return fa[x] = get(fa[x]); //在查找过程中将所有经过的点一并连接到根节点上
}

合并

将两个并查集合并,只要统一它们的父亲节点即可。当两个并查集拥有同一个根节点的时候,意味着它们是一个并查集。
并查集-2.png
举例,如图,合并并查集{1,2,3}和并查集{4,5}只需要将{1,2,3}的根节点置为4或将{4,5}的根节点置为1
像这样:
并查集-3.png
代码实现如下

void merge(int x, int y) { //将元素x和元素y所在的集合合并
    fa[get(x)] = get(y);
    //fa[get(y)] = get(x);  这也是一个可行的方案
}

3 例题

洛谷P3367为例

题目描述

如题,现在有一个并查集,你需要完成合并和查询操作。

输入输出格式

输入格式:

第一行包含两个整数N、M,表示共有N个元素和M个操作。
接下来M行,每行包含三个整数Zi、Xi、Yi
当Zi=1时,将Xi与Yi所在的集合合并
当Zi=2时,输出Xi与Yi是否在同一集合内,是的话输出Y;否则话输出N

输出格式:

如上,对于每一个Zi=2的操作,都有一行输出,每行包含一个大写字母,为Y或者N

输入输出样例

输入样例#1:

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出样例#1:

N
Y
N
Y

说明

时空限制:1000ms,128M
数据规模:
对于30%的数据,N<=10,M<=20;
对于70%的数据,N<=100,M<=1000;
对于100%的数据,N<=10000,M<=200000。

AC代码

#include <iostream>

int fa[10003];

void init(int x) {
    for (int i = 1; i <= x; ++ i) fa[i] = i;
}
int get(int x) {
    if (fa[x] == x) return x;
    return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
    fa[get(x)] = get(y);
}

int main () {
    std::ios::sync_with_stdio(false);
    register int i, j;
    int n, m, z, x, y;
    
    std::cin >> n >> m;
    init(n);
    for (i = 1; i <= m; ++ i) {
        std::cin >> z >> x >> y;
        if (z == 1) merge(x, y);
        if (z == 2) {
            if (get(x) == get(y)) std::cout << "Y\n";
            else std::cout << "N\n";
        }
    }
    
    return 0;
}