牛客小白月赛96（待补思路和F）

比赛链接：牛客小白月赛96

赛时感受

       赛时在前面卡的时间有点长，C题没开longlong wa了n发，D题没考虑负数又wa了n发，然后来写E的时候时间就不长了，匆忙写一次交一发。

A

思路

题解

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define ll long long

int n;

int main() {
  string s1, s2;
  cin >> s1 >> s2;
  int len1 = s1.length(), len2 = s2.length();
  if (len1 == 6 || len2 == 6)
    cout << -1 << endl;
  else
    cout << abs(len1 - len2) + 1 << endl;
  
  return 0;
}

B

思路

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define ll long long

int n;

int main() {
  cin >> n;
  string s;
  cin >> s;

  int len = s.length(), count1 = 0, count0 = 0;
  for (int i = 0; i < len; i++) {
    if (s[i] == '0')
      count0++;
    else
      count1++;
  }

  if (count0 == count1) {
    if (len == 2) {
      cout << -1 << endl;
    } else {
      cout << 2 << endl;
    }
  } else if (n != 1 && count1 && count0) {
    cout << 1 << endl;
  } else {
    cout << 0 << endl;
  }

  return 0;
}

C

思路

题解

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define ll long long

ll n;
ll p[N], sum[N];
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
    sum[i] = sum[i - 1] + p[i];
  }

  ll ans = 0;
  for (int j = n; j >= 1; j--) {
    ll l = 0, r = j - 1, mid, res = 0, a3 = sum[n] - sum[j - 1];
    if (a3 > sum[j - 1]) break;
    while (l <= r) {
      mid = (l + r) >> 1;
      ll a2 = sum[j - 1] - sum[mid];
      if (a2 > sum[mid] && a2 > a3) {
        res = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    if (res == 0) break;
    ans += res;
  }

  cout << ans << endl;
  
  return 0;
}

D

思路

       。

题解

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define ll long long

ll odd[N], even[N], count1, count0;
void solve() {
  ll n, a, b, sum0 = 0, sum1 = 0;
  count1 = count0 = 0;
  cin >> n >> a >> b;
  for (int i = 1; i <= n; i++) {
    ll x;
    cin >> x;
    if (x % 2)
      count1++;
    else
      count0++;
  }

  ll num = ((count1 - 1) * count1 / 2 + (count0 - 1) * count0 / 2);
  if (count1 == 0 || count0 == 0) {
    // 都是奇数或者偶数
    if (a < 0) {
      cout << a * num << endl;
    } else {
      cout << a * (n - 1) << endl;
    }
  } else if (a < 0 && b < 0) {
    // 若a和b都小于0，则加上可以为结果做贡献
    cout << a * num + (n * (n - 1) / 2 - num) * b << endl;
  } else if (a > b) {
    // 若
    if (b < 0) {
      cout << (n * (n - 1) / 2 - num) * b << endl;
    } else {
      cout << b * (n - 1) << endl;
    }
  } else {
    if (a < 0) {
      cout << a * num + b << endl;
    } else {
      cout << a * (n - 2) + b << endl;
    }
  }
  return;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  
  return 0;
}

E

思路

题解

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define ll long long

// be数组计算当前节点及其子树的权值和，af数组计算当前节点及其所有祖先节点的权值和，ans计算原树中有多少稳定点
ll n, a[N], fa[N], before_value[N], after_value[N], ans, after_num[N], before_num[N];
bool flag[N];
vector<int>edge[N];
// 计算原树中稳定点的个数和标记原树中是稳定点的节点
void dfs(int x) {
  if (after_value[x] <= a[x] * 2 && a[x] * 2 <= before_value[x])
    after_num[x]++, flag[x] = true;
  ll len = edge[x].size();
  for (int i = 0; i < len; i++) {
    dfs(edge[x][i]);
    after_num[x] += after_num[edge[x][i]];
  }
}

void dfs1(int x) {
  before_num[x] += before_num[fa[x]] + flag[x];
  int len = edge[x].size();
  for (int i = 0; i < len; i++) {
    dfs1(edge[x][i]);
  }
}

int main() {
  cin >> n;
  ll res = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    before_value[i] = after_value[i] = a[i];
  }
    
  for (int i = 1; i <= n; i++) {
    cin >> fa[i];
    edge[fa[i]].push_back(i);
    before_value[i] += before_value[fa[i]];
  }

  for (int i = n; i; i--) {
    after_value[fa[i]] += after_value[i];
  }

  // 枚举删边，计算原树的稳定点个数
  ans = 0;
  dfs(1);
  dfs1(1);
  res = max(res, after_num[1]);
  ll mark = after_num[1];

  for (int i = 2; i <= n; i++) {
    ans = mark - after_num[i] - before_num[fa[i]];
    // 修改当前节点的祖先节点为下标的af数组的权值和，并判断当前节点在删边之后是否是稳定点
    for (int j = fa[i]; j; j = fa[j]) {
      if (after_value[j] - after_value[i] <= a[j] * 2 &&
          a[j] * 2 <= before_value[j]) {
        ans++;
      } else {
        break;
      }
    }
    res = max(res, ans);
  }
  cout << res << endl;
  
  return 0;
}

F

思路

题解