首页 > 代码库 > Codeforces Round #268 (Div. 2)

Codeforces Round #268 (Div. 2)

2024-08-08 14:42:32   219人阅读

A和B估算了一下复杂度都可以乱搞 所以就随意了

A代码：

#include <cstdio>#include <cstring>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 1000;int a[maxn];int main(){    //freopen("in.txt", "r", stdin);    int n;    scanf("%d", &n);    int b, c;    int tmp;    scanf("%d", &b);    for(int i = 0; i < b; i++)    {        scanf("%d", &tmp);        a[tmp] = 1;    }    scanf("%d", &c);    for(int i = 0; i < c; i++)    {        scanf("%d", &tmp);        a[tmp] = 1;    }    bool flag = true;    for(int i = 1; i <= n && flag; i++)    {        if(a[i] == 0)            flag = false;    }    if(flag)        printf("I become the guy.\n");    else        printf("Oh, my keyboard!\n");    return 0;}

 

B代码：

#include <cstdio>#include <cstring>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 10000;int a[maxn];int rec[maxn];int main(){    //freopen("in.txt", "r", stdin);    int p, q, l, r;    int loc = 0;    int maxnum = 0;    scanf("%d%d%d%d", &p, &q, &l, &r);    for(int i = 0; i < p; i++)    {        int x, y;        scanf("%d%d", &x, &y);        maxnum = max(maxnum, y);        for(int j = x; j <= y; j++)        {            a[j] = 1;        }    }    for(int i = 0; i < q; i++)    {        int x, y;        scanf("%d%d", &x, &y);        for(int j = x; j <= y; j++)        {            rec[loc++] = j;        }    }    int ans = 0;    for(int i = l; i <= r; i++)    {        bool flag = false;        for(int j = 0; j < loc; j++)        {            if(rec[j]+i > maxnum)                break;            if(a[rec[j]+i] == 1)            {                flag = true;                break;            }        }        if(flag)            ans++;    }    printf("%d\n", ans);    return 0;}

 

C是构造

灵光一闪就...

小于等于3是没戏的

4的话是全部相乘

5的话是（4+5）* 3 - 2 - 1

考虑到2*3*4就正好是24 再想到乘法的幺元(单位元)是0 0可以强行去掉所有多余的数 所以只要构造出一个24和一个0就可以解决问题了

于是可以退出大于等于6的做法

注意它要输出的有n-1条等式

不要忘记最后让24 + 0 = 24

代码：

#include <cstdio>#include <cstring>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 10000;int a[maxn];int rec[maxn];int main(){    //freopen("in.txt", "r", stdin);    int n;    scanf("%d", &n);    if(n <= 3)        printf("NO\n");    else if(4 == n)    {        printf("YES\n");        printf("1 * 2 = 2\n");        printf("2 * 3 = 6\n");        printf("6 * 4 = 24\n");    }    else if(n == 5)    {        printf("YES\n");        printf("4 + 5 = 9\n");        printf("3 * 9 = 27\n");        printf("27 - 2 = 25\n");        printf("25 - 1 = 24\n");    }    else if(n >= 6)    {        printf("YES\n");        printf("6 - 1 = 5\n");        printf("5 - 5 = 0\n");        for(int i = 7; i <= n; i++)            printf("0 * %d = 0\n", i);        printf("2 * 3 = 6\n");        printf("6 * 4 = 24\n");        printf("0 + 24 = 24\n");    }    return 0;}

 

 

D题一开始以为是一个简单贪心 少考虑了一种两边都能匹配的情况

应该有其他的办法 不过我是选择dfs

然后就是太久没有用STL了 都没什么使用它的意识了

感觉这种要给各个数据项打标记的题目使用map是比较好的

它可以由数值直接映射到数值 一步到位

传统方法的话如果数值大到超过几百万 要建立映射是一件很麻烦而且吃力不讨好的事情

再有就是关于如何存两个集合的和值的问题 如果分别存在两个变量A和B也可以 需要手动推一条公式

不过我还是习惯把它存在一个小数组里 这样根据它所在的集合能直接灵活取数

代码：

#include <cstdio>#include <cstring>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 1100100;int ans[maxn];int a[maxn], b[maxn];int n;int sum[2];map<int, int> check;bool dfs(int a, int k){    if(!check.count(sum[k] - a))        return false;    if(check[sum[k] - a] == -1)    {        check[a] = check[sum[k] - a] = k;        return true;    }    else    {        if(dfs(sum[k^1] - (sum[k] - a), k))        {            check[a] = check[sum[k] - a] = k;            return true;        }        else            return false;    }}int main(){    //freopen("in.txt", "r", stdin);    bool flag = true;    scanf("%d%d%d", &n, &sum[0], &sum[1]);    memset(ans, -1, 4*n);    for(int i = 0; i < n; i++)    {        scanf("%d", &a[i]);        check[a[i]] = -1;    }    for(int i = 0; i < n && flag; i++)    {        if(check[a[i]] != -1)            continue;        if(!dfs(a[i], 0)           && !dfs(a[i], 1))            flag = false;    }    if(!flag)        printf("NO\n");    else    {        printf("YES\n");        for(int i = 0; i < n; i++)        {            printf("%d%c", check[a[i]], " \n"[i == n-1]);        }    }    return 0;}

 

Codeforces Round #268 (Div. 2)


联系
我们