Codeforces Round #696 (Div. 2)

昨晚训练赛打到23:00,又打了一场cf,前面两题做的挺顺畅的,第三题可能是太累了犯了个很傻逼的错(C题n小于1000,但是输入是数据量为2n,我只开了1111的数组,结果太累了把RE当成了TLE,一直在优化时间,其实第一发的代码改大数组就能过的),本来应该很快就能搞完三题的,结果就过了两道题,掉大分了。说到底还是不够细心,练得不够多,吃一堑长一智吧!

题目链接

A. Puzzle From the Future(模拟 贪心)

题意:

有两个01序列a b,先将a和b不进位相加得到c(例如010110 + 110101 = 120211),再将c连续相同的数字用一个数字代替(例如1112200 = 120),将其表示成十进制数得到d,故(102>21 , 012<101, 021=21),现在告诉你a,让你求b使得d尽量大。

题目分析:

要d尽量大就要使得c尽量长,即a+b后保证没有连续的长度,其次要使得每位数字尽量大,且位数越高的地方数字要尽可能的高,所有从最高位开始向后遍历a,b的第一位一定为1,然后根据上一位确定当前应该是1还是0(如果当前是1不会使得当前位和上一位数字一样就为1,否则为0),依次确定每一位即可得到b。

代码:

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
string a,b;
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while(t--) {
        b.clear();
        int n;
        cin >> n >> a;
        int past = a[0] - '0' + 1;
        b += '1';
        for(int i = 1; i  <n; i++) {
            if(past == a[i] - '0' + 1) {
                b += '0';
                past = a[i] - '0';
            }
            else {
                b += '1';
                past = a[i] - '0' + 1;
            }
        }
        cout << b << endl;
    }
    return 0;
}

B – Different Divisors

题意:

给你数字d,要你求出最小的整数a,a满足至少4个因子,且任意两个因子的差大于等于d。

题目分析:

首先1是所有数字的因子,肯定要选,然后我们可以找到两个素数,分别为大于等于1+d的最小素数和大于等于1+2d的最小素数,作为a的另外两个因子,然后将这两个素数相乘当做a的最后一个因子,同时这个因子就是a。

代码:

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int primes[maxn], cnt;  // primes[]存储所有素数
bool st[maxn];          // st[x]存储x是否被筛掉 0是素数
void get_primes() {
    for (int i = 2; i <= maxn-10; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= maxn / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
int main(int argc, char const *argv[]) {
    get_primes();
    int t;
    cin >> t;
    while(t--) {
        int d;
        cin >> d;
        int now = 1+d;
        int ans;
        while(st[now]!=0) now++;
        ans = now;
        now += d;
        while(st[now] != 0) now++;
        ans *= now;
        cout << ans << endl;
    }
    return 0;
}

C – Array Destruction

题意:

给你有2n个数字的数组,要你任选一个数字x,执行操作:删去数组中任意两个和为x的数字,再将两个数字中较大的数当做x,重复执行此操作。问你是否存在x使得可以删完所有的数,若可以输出YES和x以及操作过程,否则输出NO。

题目分析:

首先由于x每次变成选取的两个数字中较大的那个,所以我们第一次必须选上数组中最大的数(否则最大的那个数肯定删不掉),我们先把数组排好序,那么x就变成了$a[i] + a[2n](0 \le i \le 2*n-1)$,所以枚举所有的i就可以确定第一个x的数值,剩下的问题就是如何快速验证某个x是否可行,我的做法是直接模拟,用vis记录是否已经选取,再加上一点剪枝过的,还有一种做法是用mutilset,这是一种查找和删除都是nlogn的数据结构,实现起来更加简洁。

代码:

代码1

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int a[2111];
bool vis[2111];
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        n *= 2;
        for (int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + 1 + n);
        int f = 0;
        for (int k = 1; k <= n - 1; k++) {
            queue<PII> q;
            int cnt = 2;
            for (int i = 0; i <= n; i++) vis[i] = 0;
            vis[k] = vis[n] = 1;
            q.push({k, n});
            int now = a[n];
            int i = n;
            while (i >= 1) {
                i--;
                if (vis[i] == 1) continue;
                int flag = 0;
                for (int j = 1; j < i; j++) {
                    if (vis[j] == 1) continue;
                    if (a[j] + a[i] == now) {
                        vis[i] = vis[j] = 1;
                        q.push({j, i});
                        now = a[i];
                        flag = 1;
                        cnt += 2;
                        break;
                    }
                    if (a[j] + a[i] > now) break;
                }
                if (flag == 0) break;
            }
            if (cnt == n) {
                f = 1;
                puts("YES");
                cout << a[q.front().first]+a[q.front().second] << endl;
                while (q.size()) {
                    cout << a[q.front().first] << ' ' << a[q.front().second]<< endl;
                    q.pop();
                }
                break;
            }
        }
        if (f == 0) puts("NO");
    }
    return 0;
}

代码2:

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int a[2111];
bool flag;
int n;
vector<PII> ans;
bool judge(int x) {
    ans.clear();
    multiset<int> s;
    for (int i = 1; i <= n; i++) s.insert(a[i]);
    for (int i = 0; i < n / 2; i++) {
        auto it = --s.end();
        int now = *it;
        s.erase(it);
        it = s.find(x - now);
        if (it == s.end()) return false;
        int other = *it;
        s.erase(it);
        ans.push_back({now, other});
        x = now;
    }
    return true;
}
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        n *= 2;
        for (int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + 1 + n);
        flag = 0;
        for (int k = 1; k <= n - 1; k++) {
            int x = a[k] + a[n];
            if (judge(x)) {
                flag = 1;
                puts("YES");
                printf("%d\n", x);
                for (int i = 0; i < ans.size(); i++)
                    printf("%d %d\n", ans[i].first, ans[i].second);
                break;
            }
        }
        if (flag == 0) puts("NO");
    }
    return 0;
}
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇