首页 > 其他 > 详细

CSP2020-S 题解

时间:2020-11-08 22:35:51      阅读:35      评论:0      收藏:0      [点我收藏+]

写在前面

挂了。
noip 还是要打的。
先来补题了,补游记看心情。

A

出题人(1582/10/4 ~ 1582/10/15)

先考虑

B

给定的要求,实际上是对动物编号二进制中某一位 01 情况的限制。
若某条件满足,则 存在 一种动物的二进制该位为 1。
一种原来不存在的动物 不能 加入动物园的条件是该动物满足了 原来不满足 的一条要求,即其某二进制位上为 1。

可以通过位运算简单得到多少位上可以为 1,设有 \(k‘\) 位,答案即为 \(2^{k‘} - n\)

注意特判答案为 \(2^{64}\) 的情况。\(2^{64}-1\) 可以通过 ull 溢出得到。

//知识点:瞎搞
/*
By:Luckyblock
*/
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#define ULL unsigned long long
const int N = 1e6 + 10;
//==================================================
int n, m, c, k, num, noneed[N];
ULL havea, havec, ans;
//==================================================
int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == ‘-‘) f = -1;
  for (; isdigit(ch); ch = getchar()) w = 10 * w + ch - ‘0‘;
  return f * w;
}
//==================================================
int main() {
  n = read(), m = read(), c = read(), k = read();
  for (int i = 1; i <= n; ++ i) {
    ULL a;
    std::cin >> a;
    havea |= a;
  }
  for (int i = 1; i <= m; ++ i) {
    int p = read(), q = read();
    if (! ((1ull << (1ull * p)) & havea)) { //所有q 不相同 
      num += ! noneed[p];
      noneed[p] = true; //第 p 位上为 1 是不合法的,会加入新饲料 
    }
  }
  if ((k - num) == 64) {
    if (! n) {
      printf("18446744073709551616\n");
      return 0;
    } else {
      ans = 0 - n; 
    }
  } else {
    ans = (1ull << (1ull * k -num)) - 1ull * n; 
  }
  std::cout << ans;
  return 0;
}

暴力

#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cstring>
#define LL long long
#define ULL unsigned long long
const int N = 2e6 + 10;
//==================================================
int n, m, c, k, ans, a[N];
int p[N], q[N];
bool visa[N], visc[N];
//==================================================
int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == ‘-‘) f = -1;
  for (; isdigit(ch); ch = getchar()) w = 10 * w + ch - ‘0‘;
  return f * w;
}
//==================================================
int main() {
  n = read(), m = read(), c = read(), k = read();
  for (int i = 1; i <= n; ++ i) {
    a[i] = read();
    visa[a[i]] = true;
  }
  for (int i = 1; i <= m; ++ i) {
    p[i] = read(), q[i] = read();
    for (int j = 1; j <= n; ++ j) {
      if ((a[j] >> p[i]) & 1) {
        visc[q[i]] = true;
        break;
      }
    }
  }
  
  for (int i = 0, lim = (1 << k) - 1; i <= lim; ++ i) {
    if (visa[i]) continue ;
    int flag = 1;
    for (int j = 1; j <= m; ++ j) {
      if ((i >> p[j]) & (! visc[q[j]])) {
        flag = 0;
        break;
      }
    }
    ans += flag;
  }
  printf("%d\n", ans);
  return 0;
}

C

D

CSP2020-S 题解

原文:https://www.cnblogs.com/luckyblock/p/13945486.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!