专栏首页数据结构与算法Codeforces Round #473 (Div. 2)

Codeforces Round #473 (Div. 2)

这场怎么都是异或啊qwq。。。

A. Mahmoud and Ehab and the even-odd game

直接判断奇偶性

#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long 
using namespace std;
const int MAXN = 2 * 1e6 + 10, INF = 1e9 + 10, B = 63;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
main() { 
#ifdef WIN32
    //freopen("a.in", "r", stdin);
#endif
    int N = read();
    puts(N & 1 ? "Ehab" : "Mahmoud");
}

B. Mahmoud and Ehab and the message

维护出每个graph的最小值,输出即可,我咋还开了个map

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
#define int long long 
using namespace std;
const int MAXN = 2 * 1e6 + 10, INF = 1e9 + 10, B = 63;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, G, M;
string s[MAXN];
int val[MAXN], minval[MAXN];
map<string, int> ID;
main() { 
#ifdef WIN32
    //freopen("a.in", "r", stdin);
#endif
    memset(minval, 0x3f, sizeof(minval));
    N = read(); G = read(); M = read();
    for(int i = 1; i <= N; i++) 
        cin >> s[i];
        //cout << s << endl;
    for(int i = 1; i <= N; i++) 
        val[i] = read();
    for(int i = 1; i <= G; i++) {
        int num = read();
        for(int j = 1; j <= num; j++) {
            int x = read();
            ID[s[x]] = i;
        }
    }
    
    for(int i = 1; i <= N; i++)
        minval[ID[s[i]]] = min(minval[ID[s[i]]], val[i]);
    //for(int i = 1; i <= N; i++) printf("%d ", ID[s[i]]); puts("***");
    //for(int i = 1; i <= N; i++) printf("%d ", minval[ID[s[i]]]); puts("***");
    int ans = 0;
    string x;
    for(int i = 1; i <= M; i++) {
        cin >> x;
        ans += minval[ID[x]];
    }
    printf("%I64d", ans);
}

C. Mahmoud and Ehab and the wrong algorithm

我的构造思路比较奇葩,大概长这样。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
const int MAXN = 2 * 1e6 + 10, INF = 1e9 + 10, B = 63;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

main() { 
#ifdef WIN32
    //freopen("a.in", "r", stdin);
#endif
    int N = read();
    if(N == 2 || N == 3 || N == 4 || N == 5) printf("-1\n");
    else {
        printf("1 2\n");
        printf("1 3\n");
        printf("1 4\n");
        for(int i = 5; i <= N; i++) 
            printf("3 %d\n", i);
    }
    for(int i = 1; i <= N - 1; i++) 
        printf("%d %d\n", i, i + 1);
}

E. Mahmoud and Ehab and the xor-MST

打表后强上oeis

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
#define int long long 
using namespace std;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
map<int, int> ans;
int B(int x) {
    if(ans[x] ) return ans[x];
    if(x & 1) return ans[x] = 2 * B(x / 2) + (x / 2) + 1;
    else return ans[x] = 2 * B(x / 2) + x / 2;
}
main() { 
#ifdef WIN32
    //freopen("a.in", "r", stdin);
#endif
    ans[1] = 1;
    int N = read();
    printf("%I64d", B(N - 1));
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 08:Challenge 1

    总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列,有M次操作,每次操作是以下两种之一: (1)...

    attack
  • CodeChef March Lunchtime 2018 div2

    地址https://www.codechef.com/LTIME58B?order=desc&sortBy=successful_submissions

    attack
  • UOJ#386. 【UNR #3】鸽子固定器(链表)

    如果我们按$s$排序后,我们就可以枚举$max  \ s_i$和$min \ s_i$

    attack
  • UOJ#386. 【UNR #3】鸽子固定器(链表)

    如果我们按$s$排序后,我们就可以枚举$max  \ s_i$和$min \ s_i$

    attack
  • CodeChef March Lunchtime 2018 div2

    地址https://www.codechef.com/LTIME58B?order=desc&sortBy=successful_submissions

    attack
  • 08:Challenge 1

    总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列,有M次操作,每次操作是以下两种之一: (1)...

    attack
  • BZOJ4260: Codechef REBXOR (01Tire树)

    attack
  • 探索C++对象模型

    只说C++对象模型在内存中如何分配这是不现实的,所以这里选择VS 2013作为调试环境具体探讨object在内存中分配情况.目录给出了具体要探讨的所有模型,正...

    racaljk
  • C++和Java中交换两个整数的方法

    在C和C++中交换两个整数有多种方式,我想到的常用方法有以下4种: 1、使用引用传参 2、使用指针传参 3、利用位异或运算符^的特性,并结合引用传参 4...

    ccf19881030
  • P1257 平面上的最接近点对

    题目描述 给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的 输入输出格式 输入格式: 第一行:n;2≤n≤...

    attack

扫码关注云+社区

领取腾讯云代金券