牛客周赛 Round 65 - 个人题解

超市

https://ac.nowcoder.com/acm/contest/92972/A

分享一下个人的题解，赛时做出了A-F，G题得了240。赛后过了G题。

A

直接用set存所有合法的结果

2024.10.28 14:25 更新：
之前写的麻烦了，直接取较小的一直取即可。

#include <iostream>
using namespace std;

int main() {
  int n,a,b;
  cin>>n>>a>>b;
  cout<<n/min(a,b)<<'\n';
  
  return 0;
}

B

每读入一个字符直接检查2*2的字符

#include <iostream>
using namespace std;

bool g[1005][1005];

int main() {
  int n,m,ans = 0;
  cin>>n>>m;
  char ch;
  for (int i=1; i<=n; i++)
    for (int j=1; j<=m; j++)
      cin>>ch, g[i][j] = ch == '*', ans += g[i][j] && g[i-1][j] && g[i][j-1] && g[i-1][j-1];
  cout<<ans<<'\n';
  
  return 0;
}

C

贪心选取，只能最小和最大交换，否则更亏

#include <iostream>
#include <algorithm>
using namespace std;

int a[1005];

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n;
    cin>>n;
    for (int i=1; i<=n; i++)
      cin>>a[i];
    sort(a+1, a+1+n);
    long long ans1 = 0, ans2 = 0;
    for (int i=1; i<=n; i++)
      i%2 ? (ans2 += a[i]) : (ans1 += a[i]);
    ans1 -= a[n], ans1 += a[1];
    ans2 += a[n], ans2 -= a[1];
    if (ans1 > ans2)
      cout<<"kou"<<'\n';
    else if (ans1 < ans2)
      cout<<"yukari"<<'\n';
    else
      cout<<"draw"<<'\n';
  }
  
  return 0;
}

D

k只有10，直接计算所有可能的2^k种组合可以治疗的疾病
这里用了状态压缩的思想，例如用j遍历0 - (2^k-1)，j的哪一个二进制位为1，就表示哪个药物被选取
对于每个n，判断每个组合能否治疗该病人，选出用药数最小的组合
(O(1024*n)的复杂度居然不会超时)

2024.10.28 11:32 更新：
改了一下变量命名。

#include <iostream>
using namespace std;

int a[10005], b[15], c[1024];

int main() {
  int n,m,k;
  cin>>n>>m;
  string s;
  for (int i=1; i<=n; i++)
    cin>>s, a[i] = stoi(s, 0, 2);
  cin>>k;
  for (int i=0; i<k; i++)
    cin>>s, b[i] = stoi(s, 0, 2);
  for (int j=1; j<(1<<k); j++)
    for (int i=0; i<k; i++)
      if (j>>i&1)
        c[j] |= b[i];
  for (int i=1; i<=n; i++) {
    int mi = k+1;
    for (int j=0; j<(1<<k); j++)
      if ((c[j]&a[i]) == a[i])
        mi = min(mi, __builtin_popcount(j));
    if (mi == k+1)
      cout<<-1<<'\n';
    else
      cout<<mi<<'\n';
  }
  
  return 0;
}

E

贪心
最大：
如果b[i-1]-x < -50，反正b[i]已经不是寒潮了，直接将b[i]设为50，为后续的寒潮做准备
否则将b[i]设为b[i-1]-x，以便在保证当前是一个寒潮的情况下，为后续的寒潮留有尽量多的空间
最小：
将b[i]刚好设为b[i-1]-x+1，在保证当前不是寒潮的情况下让温度尽量低，当然最低只能为-50

#include <iostream>
#include <cstring>
using namespace std;

int a[105], b[105];

int main() {
  int n,x;
  cin>>n>>x;
  for (int i=1; i<=n; i++)
    cin>>a[i];
  int ans1 = 0, ans2 = 0;
  memcpy(b, a, sizeof b);
  for (int i=1; i<=n; i++)
    if (b[i] == -999)
      b[i] = i == 1 ? 50 : (b[i-1]-x >= -50 ? b[i-1]-x : 50);
  for (int i=2; i<=n; i++)
    if (b[i-1] - b[i] >= x)
      ans1++;
  memcpy(b, a, sizeof b);
  for (int i=1; i<=n; i++)
    if (b[i] == -999)
      b[i] = i == 1 ? b[2] : max(b[i-1]-x+1, -50);
  for (int i=2; i<=n; i++)
    if (b[i-1] - b[i] >= x)
      ans2++;
  cout<<ans1<<' '<<ans2<<'\n';
  
  return 0;
}

F

同E，改一下数据范围即可

#include <iostream>
#include <cstring>
using namespace std;

int a[100005], b[100005];

int main() {
  int n,x;
  cin>>n>>x;
  for (int i=1; i<=n; i++)
    cin>>a[i];
  int ans1 = 0, ans2 = 0;
  memcpy(b, a, sizeof b);
  for (int i=1; i<=n; i++)
    if (b[i] == -999999999)
      b[i] = i == 1 ? 5e8 : (b[i-1]-x >= -5e8 ? b[i-1]-x : 5e8);
  for (int i=2; i<=n; i++)
    if (b[i-1] - b[i] >= x)
      ans1++;
  memcpy(b, a, sizeof b);
  for (int i=1; i<=n; i++)
    if (b[i] == -999999999)
      b[i] = i == 1 ? b[2] : max(b[i-1]-x+1, int(-5e8));
  for (int i=2; i<=n; i++)
    if (b[i-1] - b[i] >= x)
      ans2++;
  cout<<ans1<<' '<<ans2<<'\n';
  
  return 0;
}

G

我的做法是，如果m/n >= 1，我们选出 r = n+m%n 只用来分配，否则直接把所有m用来分配。

分配的方法是，先进行第一轮放置，根据r和n的奇偶性，间隔选出若干位置(奇数位或偶数位)，放置一个乌鸦。

但是需要满足的条件是放置后剩余的r为偶数。

如果n为偶数，放置在奇数位置和偶数位置是一样的，我们无法左右放置后剩余的r值。

如果n为奇数，此时：
如果r为奇数，且n/2为奇数，必须放置在2,4...n-1；
如果r为偶数，且n/2为奇数，必须放置在1,3...n；
如果r为奇数，且n/2为偶数，必须放置在2,4...n-1；
如果r为偶数，且n/2为偶数，必须放置在1,3...n。

如果不能保证放置之后剩余的乌鸦数r为非负偶数，则说明一定不行，输出-1。

然后进行第二轮放置。对于剩余的偶数r只乌鸦，从和第一轮相反的位置间隔放置即可。例如第一轮放置在奇数位置，则此轮放置在偶数位置。

如果还有剩余，再进行第三轮放置。从和第一轮相同的位置间隔放置即可。例如第一轮放置在奇数位置，则此轮仍放置在奇数位置。

因为 n+m%n 一定在 n 和 n*2-1 之间，而我们的三轮放置最多能放 n/2 + n*2 只乌鸦，所以一定能放完。

2024.10.28 0:45 更新：
被 3 1 hacked了，已更新。

2024.10.28 13:06 更新：
略微简化了一下代码。

#include <iostream>
using namespace std;

long long a[100005];

int main() {
  int n;
  long long m;
  cin>>n>>m;
  long long b = m/n-1;
  int r;
  if (b > 0) {
    for (int i=1; i<=n; i++)
      a[i] = b;
    r = n+m%n;
  } else {
    r = m;
  }
  int s = r%2 == 0 && n/2%2 || r%2 && n/2%2 == 0 ? 1 : 2;
  r -= s == 1 && n%2 ? n/2+1 : n/2;
  if (r < 0 || r%2) {
    cout<<-1<<'\n';
    return 0;
  }
  for (int i=s; i<=n; i+=2)
    a[i]++;
  if (r != 0) {
    for (int i=(s==2?1:2); i<=n; i+=2) {
      a[i] += 2, r -= 2;
      if (r == 0)
        break;
    }
  }
  if (r != 0) {
    for (int i=s; i<=n; i+=2) {
      a[i] += 2, r -= 2;
      if (r == 0)
        break;
    }
  }
  for (int i=1; i<=n; i++)
    cout<<a[i]<<' ';
  cout<<'\n';
  
  return 0;
}