欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Codeforces Round #669 Div2 前三题

程序员文章站 2022-06-15 22:41:44
目录A - AhahahahahahahahaB - Big VovaC - Chocolate BunnyA - AhahahahahahahahaB - Big VovaC - Chocolate Bunny...

A - Ahahahahahahahaha

题意:

给你一个01串,最多能删去一半,删完以后要使 a 1 − a 2 + a 3 − a 4 + … = 0 a_1−a_2+a_3−a_4+…=0 a1a2+a3a4+=0,也就是下标为奇数的数之和等于下标为偶数的数之和。

输入:

首行T,接下来T组数据,一行给出n,下一行给出n个数,即01串的主体。

4
2
1 0
2
0 0
4
0 1 1 1
4
1 1 0 0

输出:

输出删减完以后的01串。

1
0
1
0
2
1 1
4
1 1 0 0

思路:

开始想的很复杂。实际上就是讨论0和1的个数。

  1. 0的个数大于等于1,也就是0的个数大于等于一半,所以直接输出所有的0;
  2. 1的个数大于0,基本操作同上,但是此时需要注意,若1的个数为奇数,差值不是为0而是为1,所以是奇数少输出一个1;

B - Big Vova

参考: B. Big Vova(暴力)

题意:

给你一个长度为n的数组a,求一个数组b,可以使得数组c的字典序最大,其中
c i = G C D ( b 1 , … , b i ) c_i=GCD(b_1,…,b_i) ci=GCD(b1,,bi)
输入:

首行输入T,接下来T组数据,每组第一行输入n,第二行输入n个数字,即数组a本体。

7
2
2 5
4
1 8 2 3
3
3 8 9
5
64 25 75 100 50
1
42
6
96 128 88 80 52 7
5
2 4 8 16 17

输出:

按顺序输出数组b,每个元素间以空格间隔。

5 2 
8 2 1 3 
9 3 8 
100 50 25 75 64 
42 
128 96 80 88 52 7 
17 2 4 8 16 

思路:

详见链接。

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#define INF 0x3f3f3f3f
#define pi acos(-1)
#define N 1000005
typedef unsigned long long ll;
using namespace std;

int a[N];
int b[N];
bool vis[N];

int gcd(ll c, ll b)
{
    ll tmp;
    while(b)
    {
        tmp = b;
        b = c % b; c = tmp;
    }
    return c;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        memset(vis, 0, sizeof(vis));
        int n;
        scanf("%d", &n);
        int cnt = 0;
        int maxx = -1, maxi = -1;
        for(int i = 0; i < n; i++)
        {
            scanf("%d", a + i);
            if(a[i] > maxx)
            {
                maxx = a[i];
                maxi = i;
            }
        }
        b[cnt++] = maxx;
        vis[maxi] = 1;
        for(int i = 1; i < n; i++)
        {
            int maxg = -1;
            int maxgi = -1;
            for(int j = 0; j < n; j++)
            {
                if(vis[j])
                    continue;
                if(gcd(maxx, a[j]) > maxg)
                {
                    maxg = gcd(maxx, a[j]);
                    maxgi = j;
                }
            }
            //cout << maxg << ' ' << maxgi << endl;
            b[cnt++] = a[maxgi];
            vis[maxgi] = 1;
            maxx = maxg;
        }
        for(int i = 0; i < n; i++)
            printf("%d ", b[i]);
        printf("\n");
    }
}

C - Chocolate Bunny

题意:

交互题,有一个1到n的置换(即1到n每个数出现且仅出现一次的数组),你可以询问2×n次,每次询问两个下标i和j,系统会告诉你 a i ( m o d a ) j a_i \pmod a_j ai(moda)j的值。你最终要按顺序输出这个置换。

输入:

根据输出的询问,给出 a i ( m o d a ) j a_i \pmod a_j ai(moda)j的值。

3

1

2

1

0

输出:

? i j的格式询问,得到答案后用! a b的格式输出置换。

? 1 2

? 3 2

? 1 3

? 2 1

! 1 3 2

思路:

对任意的 a i a_i ai a j a_j aj,由于置换中没有重复的数字,所以两个数一定有一个比另一个大。所以两个数互换询问后(?$a_i a_j $ ? a j a i a_j a_i ajai),必定能问出其中一个数。如,设n>k,则n%k<k,k%n=k,所以互换询问一定能问出两个数中较小的那个数。互换询问n次,每次问两次,刚好问2×n次。

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
#include <iomanip>
#define INF 0x3f3f3f3f
#define pi acos(-1)
#define N 10010
#define M 110
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    int j = 1;
    for(int i = 2; i <= n; i++)
    {
        printf("? %d %d\n", i, j);
        fflush(stdout);
        int res1;
        scanf("%d", &res1);
        printf("? %d %d\n", j, i);
        fflush(stdout);
        int res2;
        scanf("%d", &res2);
        if(res1 > res2)
        {
            a[i] = res1;
        }
        else
        {
            a[j] = res2;
            j = i;
        }
    }
    printf("!");
    for(int i = 1; i <= n; i++)
    {
        if(!a[i])
            printf(" %d", n);
        else
            printf(" %d", a[i]);
    }
    printf("\n");
    return 0;
}

赛后总结:

  • 没有及时写题解,有点记不清了,就记得A题卡了心态有点崩。还好还是涨分了。以及B题读题一直读不懂,好在C题比较简单,挽回一城。理解能力和思维还是有待提高。
  • 下次一定及时写题解。说实话着急打比赛还不如慢慢来,把每一场都总结好。

多多包涵,努力进步

本文地址:https://blog.csdn.net/qq_49451105/article/details/108561549