首页 > 其他分享 >《如 何 速 通 一 套 题》8.0

《如 何 速 通 一 套 题》8.0

时间：2024-10-02 16:33:32浏览次数：9  
标签：8.0 arr fa int ++ mp 100010

邮寄

开场秒 B。

A 稍微退了一会儿，推出一个解法（后面发现假掉了）......

然后 CD，D 感觉是一个 SA。结果 SA 写错了，算法假掉了......

A 智乃的差分

分类讨论。

\(x > 0\)

最大值 \(= x\)，最小值 \(= 0\)

此时可以直接找一个不是 \(x\)，不是 \(0\) 的数来（严格次小值），然后其他的数从大往小排序。

其他情况

直接从大往小排序。

\(x < 0\)

std::sort(arr + 1, arr + n + 1);

\(x = 0\)

这是最复杂的情况。

先把所有的数的出现次数统计出来，然后按照出现次数 从多至少 排序。

如果数组的头部是 \(0\)，还得把这些 \(0\) 扔到后面。

排序部分参考：

//mp[x] 代表 x 的出现次数
bool cmp(int a, int b) {
  return (mp[a] == mp[b]? a > b : mp[a] > mp[b]);
}

...

sort(arr + 1, arr + n + 1, cmp);
if(arr[1] == 0) {
  rotate(arr + 1, arr + mp[0] + 1, arr + n + 1);
}

Code:

#include <bits/stdc++.h>
using namespace std;

int t, n, x, arr[200020], brr[200020];
map<int, int> mp;

bool check() {
  for(int i = 1; i <= n; i++) {
    if(arr[i] - arr[i - 1] == x) {
      return 0;
    }
  }
  return 1;
}

bool cmp(int a, int b) {
  return (mp[a] == mp[b]? a > b : mp[a] > mp[b]);
}

int main() {
  freopen("difference.in", "r", stdin);
  freopen("difference.out", "w", stdout);
  for(cin >> t; t--; ) {
    cin >> n >> x;
    for(int i = 1; i <= n; i++) {
      cin >> arr[i];
    }
    sort(arr + 1, arr + n + 1);
    if(check()) {
      cout << "yes" << '\n';
      for(int i = 1; i <= n; i++) {
        cout << arr[i] << " \n"[i == n];
      }
      goto nxt;
    }
    sort(arr + 1, arr + n + 1, greater<int>());
    if(arr[1] == x && arr[n] == 0) {
      for(int i = 2; i <= n; i++) {
        if(arr[i] != arr[1] && arr[i] != arr[n]) {
          swap(arr[1], arr[i]);
          break;
        }
      }
    }
    if(check()) {
      cout << "yes" << '\n';
      for(int i = 1; i <= n; i++) {
        cout << arr[i] << " \n"[i == n];
      }
      goto nxt;
    }
    for(int i = 1; i <= n; i++) {
      mp[arr[i]]++;
    }
    sort(arr + 1, arr + n + 1, cmp);
    if(arr[1] == 0) {
      rotate(arr + 1, arr + mp[0] + 1, arr + n + 1);
    }
    if(n & 1) {
      for(int i = 1, j = 1; i <= n; i++, j += 2) {
        if(j > n) {
          j -= n;
        }
        brr[j] = arr[i];
      }
    }else {
      for(int i = 1, j = 1; j <= n; i++, j += 2) {
        brr[j] = arr[i];
      }
      for(int i = n / 2 + 1, j = 2; j <= n; i++, j += 2) {
        brr[j] = arr[i];
      }
    }
    copy(brr + 1, brr + n + 1, arr + 1);
    if(check()) {
      cout << "yes" << '\n';
      for(int i = 1; i <= n; i++) {
        cout << arr[i] << " \n"[i == n];
      }
      goto nxt;
    }
    cout << "no" << '\n';
    nxt:;
    mp.clear();
  }
  return 0;
}
/*
4
10 0
9 9 9 9 9 3 3 3 3 3
10 0
9 9 9 9 9 9 3 3 3 3
10 0
0 0 0 0 0 0 0 0 0 0
403 -3
5 1 10 1 9 6 7 3 7 2 1 3 4 2 5 10 1 3 4 9 5 3 5 9 2 1 2 7 2 1 4 1 7 3 5 10 8 9 10 3 4 8 8 2 8 6 8 2 4 2 5 5 5 10 4 10 7 1 2 7 2 4 9 10 5 2 7 2 4 4 5 8 5 1 2 1 5 6 4 3 6 4 7 2 4 8 1 10 2 9 2 9 2 4 8 10 5 10 7 7 7 7 9 10 4 1 10 10 9 5 3 2 10 9 5 4 9 3 10 3 1 6 8 6 6 5 4 5 9 8 7 6 7 6 2 7 3 8 2 10 8 4 3 8 8 4 9 8 1 3 4 3 10 6 10 7 7 9 4 1 1 2 7 5 2 10 8 8 5 2 2 8 2 5 7 5 5 4 10 7 10 8 6 5 4 1 10 2 3 6 10 10 8 9 4 1 6 7 8 3 10 8 1 6 7 8 7 1 6 5 4 3 10 3 7 8 6 5 9 9 10 2 2 9 9 5 9 7 4 3 3 7 10 5 2 6 6 8 1 5 1 7 9 2 2 8 3 5 4 2 2 2 7 3 3 10 2 10 4 5 4 6 5 3 5 1 7 9 8 1 4 3 4 7 9 6 3 9 10 1 10 4 6 2 1 8 2 2 8 6 1 7 3 4 10 7 5 6 6 6 5 6 3 10 2 6 8 9 7 7 1 7 5 4 5 6 4 9 3 7 1 1 1 5 5 7 5 5 8 9 4 7 3 4 4 9 4 10 10 9 10 9 10 2 2 4 3 10 4 8 4 3 5 9 5 4 10 10 9 4 3 8 8 4 5 7 8 6 8 7 10 10 9 7 4 8 1 6 7 7 5 4 4 8 10 9 3 3 4 7 6 4 2 2 8 10 3 1 5 7 8 10 4
*/

B 牛牛的旅行

sb 离线处理板子题。

对于点权最大值和边权和分开处理。

点权最大值

这里的思想是经典的最小瓶颈路。

我们从小往大考虑每一个点：

temp.bmp

然后，对于这个点，我们看所有与这个点有边的 已经考虑 的点。

组合数学计算这个点的贡献。

边权和

弱智题，一遍 DFS 稍微处理一下就可以了。

#include <bits/stdc++.h>
#define int ll
using namespace std;
using ll = long long;

const int kMod = int(1e9) + 7;

int n, val[1000010], fa[1000010], sz[1000010], u, v, id[1000010], is[1000010], ans, sb[1000010];
vector<int> to[1000010];

bool cmp(int x, int y) {
  return val[x] < val[y];
}

int findfa(int x) {
  return fa[x] == x? x : (fa[x] = findfa(fa[x]));
}

void unionn(int x, int y) {
  x = findfa(x), y = findfa(y);
  if(x == y) {
    return ;
  }
  if(sz[x] < sz[y]) {
    swap(x, y);
  }
  sz[x] += sz[y], fa[y] = x;
}

void DFS(int x = 1, int pa = 0) {
  sb[x] = 1;
  for(auto i : to[x]) {
    if(i != pa) {
      DFS(i, x);
      sb[x] += sb[i];
    }
  }
  ans = (ans - 2 * sb[x] * (n - sb[x]) % kMod + kMod) % kMod;
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  freopen("tour.in", "r", stdin);
  freopen("tour.out", "w", stdout);
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> val[i], fa[i] = id[i] = i, sz[i] = 1;
  }
  for(int i = 1; i < n; i++) {
    cin >> u >> v;
    to[u].push_back(v);
    to[v].push_back(u);
  }
  stable_sort(id + 1, id + n + 1, cmp);
  for(int i = 1; i <= n; i++) {
    int tot = 1;
    is[id[i]] = 1;
    for(auto j : to[id[i]]) {
      if(is[j]) {
        tot += sz[findfa(j)];
      }
    }
    for(auto j : to[id[i]]) {
      if(is[j]) {
        ans = (ans + val[id[i]] * sz[findfa(j)] % kMod * (tot - sz[findfa(j)])) % kMod;
      }
    }
    ans = (ans + val[id[i]] * (tot - 1)) % kMod;
    for(auto j : to[id[i]]) {
      if(is[j]) {
        unionn(id[i], j);
      }
    }
  }
  DFS();
  cout << ans << '\n';
  return 0;
}

C 第 \(K\) 排列

第十四剪枝。

Part 1

我们定义 \(dp_{i, j}\) 表示当前在 \([i \cdots n]\) 的范围内的最大权值。

Part 2

放弃一个即使最大化权值也无法达到 \(x\) 的状态... 这应该很好做的。

Part 3

放弃了这些状态之后，剩下的状态应该不会很多... 直接暴搜，在丢弃掉所有的无用状态后，剩下的状态会极其精确，所以真正的搜索数量其实真的不多，也就 \(O(NK)\) 吧。

#include <bits/stdc++.h>
using namespace std;

const char c[] = {'P', 'O', 'N', 'I'}, c2[] = {'N', 'O', 'I', 'P'};

int n, rc, k, v[256][256], dp[1010][256], cnt;
string s, ans;

void DFS(int x, int lst, int val) {
  if(x > n) {
    if(val < rc) {
      return ;
    }
    cnt++;
    if(cnt == k) {
      cout << ans << '\n';
      exit(0);
    }
    return ;
  }
  if(val + dp[x - 1][lst] < rc) {
    return ;
  }
  for(int i = 0; i < 4; i++) {
    if(s[x] == '?' || s[x] == c[i]) {
      ans += c[i];
      DFS(x + 1, i, val + v[c[lst]][c[i]]);
      ans.pop_back();
    }
  }
}

int main() {
  freopen("permutation.in", "r", stdin);
  freopen("permutation.out", "w", stdout);
  cin >> n >> rc >> k >> s;
  n = s.size();
  s = ' ' + s;
  for(int i = 0; i < 4; i++) {
    for(int j = 0; j < 4; j++) {
      cin >> v[c2[i]][c2[j]];
    }
  }
  for(int j = 0; j < 4; j++) {
    if(s[n] == '?' || s[n] == c[j]) {
      dp[n][j] = 0;
    }else {
      dp[n][j] = -1e8;
    }
  }
  for(int i = n - 1; i >= 1; i--) {
    for(int j = 0; j < 4; j++) {
      if(s[i] == '?' || s[i] == c[j]) {
        for(int k = 0; k < 4; k++) {
          dp[i][j] = max(dp[i][j], dp[i + 1][k] + v[c[j]][c[k]]);
        }
      }else {
        dp[i][j] = -1e8;
      }
      //cout << dp[i][j] << ' ';
    }
    //cout << '\n';
  }
  ans += c[0];
  DFS(2, 0, 0);
  ans.pop_back();
  ans += c[1];
  DFS(2, 1, 0);
  ans.pop_back();
  ans += c[2];
  DFS(2, 2, 0);
  ans.pop_back();
  ans += c[3];
  DFS(2, 3, 0);
  ans.pop_back();
  cout << -1 << '\n';
  return 0;
}
/*
4 3 108
????
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
*/

D 牛牛的border

如果你不会后缀数组（SA）

先放一张图：

SA.bmp

倍增排序的思想是，我们先把一个字符排好序，然后就可以利用双关键字排序（去重离散化），然后就可以完美进行后缀排序了。

实现（用下面的代码，输入 adsadsadsadsads，即可获得上面的输出）：

#include <bits/stdc++.h>
using namespace std;

struct node {
  int a1, a2, id;
}arr[100010];

int n, bc[256], val[256], cnt, sa[100010], rk[100010], ht[100010];
string s;

void lfsort(int x) {
  cout << "Concat the substrings of x and x + " << x << "(may DNE):" << '\n';
  for(int i = 1; i <= n; i++) {
    arr[i] = {rk[i], (i + x <= n? rk[i + x] : 0), i};
    cout << arr[i].a1 * 10 + arr[i].a2 << ' ';
  }
  cout << '\n';
  sort(arr + 1, arr + n + 1, [](node a, node b) {return a.a1 == b.a1? a.a2 < b.a2 : a.a1 < b.a1;});
  int tmp = 0;
  for(int i = 1; i <= n; i++) {
    tmp += arr[i].a1 != arr[i - 1].a1 || arr[i].a2 != arr[i - 1].a2;
    rk[arr[i].id] = tmp;
  }
}

char sufc(int id, int x) {
  return s[id + x - 1];
}

int main() {
  cin >> s;
  n = s.size();
  for(auto i : s) {
    bc[int(i)]++;
  }
  s = ' ' + s;
  for(int i = 'a'; i <= 'z'; i++) {
    if(bc[i]) {
      val[i] = ++cnt;
    }
  }
  for(int i = 1; i <= n; i++) {
    rk[i] = val[int(s[i])];
  }
  cout << '\n';
  cout << "Initiallize:" << '\n';
  for(int i = 1; i <= n; i++) {
    cout << rk[i] << ' ';
  }
  cout << '\n' << '\n';
  for(int i = 1; ; i <<= 1) {
    lfsort(i);
    cout << "The order of s[x ... x + " << (i << 1) << "]:" << '\n';
    for(int i = 1; i <= n; i++) {
      cout << rk[i] << ' ';
    }
    cout << '\n' << '\n';
    if(i > n) {
      break;
    }
  }
  for(int i = 1; i <= n; i++) {
    sa[rk[i]] = i;
  }
  for(int i = 1; i <= n; i++) {
    ht[rk[i]] = max(ht[rk[i - 1]] - 1, 0);
    for(; sufc(i, ht[rk[i]] + 1) == sufc(sa[rk[i] - 1], ht[rk[i]] + 1); ht[rk[i]]++) {
    }
  }
  cout << "                              Rank =        ";
  int cnt = 45;
  for(int i = 1; i <= n; i++) {
    cnt += 2;
    cnt += rk[i] >= 10;
    cnt += rk[i] >= 100;
    cnt += rk[i] >= 1000;
    cnt += rk[i] >= 10000;
    cnt += rk[i] >= 100000;
    cout << rk[i] << ' ';
  }
  cout << '\n';
  for(; cnt--; ) {
    cout << '-';
  }
  cout << '\n';
  for(int i = 1; i <= n; i++) {
    //cout << "height[i] = " << ht[i] << ',' << "sa[i] = " << sa[i] << ' ';
    cout << "height[" << i << "]";
    if(i < 10) {
      cout << ' ';
    }
    if(i < 100) {
      cout << ' ';
    }
    if(i < 1000) {
      cout << ' ';
    }
    if(i < 10000) {
      cout << ' ';
    }
    if(i < 100000) {
      cout << ' ';
    }
    cout << " = " << ht[i];
    if(ht[i] < 10) {
      cout << ' ';
    }
    if(ht[i] < 100) {
      cout << ' ';
    }
    if(ht[i] < 1000) {
      cout << ' ';
    }
    if(ht[i] < 10000) {
      cout << ' ';
    }
    if(ht[i] < 100000) {
      cout << ' ';
    }
    cout << ",sa[" << i << "]";
    if(i < 10) {
      cout << ' ';
    }
    if(i < 100) {
      cout << ' ';
    }
    if(i < 1000) {
      cout << ' ';
    }
    if(i < 10000) {
      cout << ' ';
    }
    if(i < 100000) {
      cout << ' ';
    }
    cout << " = " << sa[i];
    if(sa[i] < 10) {
      cout << ' ';
    }
    if(sa[i] < 100) {
      cout << ' ';
    }
    if(sa[i] < 1000) {
      cout << ' ';
    }
    if(sa[i] < 10000) {
      cout << ' ';
    }
    if(sa[i] < 100000) {
      cout << ' ';
    }
    cout << ' ';
    cout << s.substr(sa[i]) << '\n';
  }
  return 0;
}

我们可以迅速知道一件事：我们要统计每一个后缀在另一个后缀中的出现次数。

你会想到什么，当然是 \(height\) 数组啊！

只要 \(height\) 永远不小于某一个值（\(lcp(sa_i, sa_j) = \min \limits_{k = i + 1}^j height_k\)），这个后缀就会一直出现，否则，它就无法变回去了。

所以我们可以按照 \(height\) 顺序合并后缀，并在合并过程中维护答案。

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct node {
  int a1, a2, id;
}arr[100010];

int n, sa[100010], rk[100010], ht[100010], cur, fa[100010], sz[100010], ans;
vector<int> num[100010];
string s, t;

void lfsort(int x) {
  for(int i = 1; i <= n; i++) {
    arr[i] = {rk[i], (i + x <= n? rk[i + x] : 0), i};
  }
  stable_sort(arr + 1, arr + n + 1, [](node a, node b) {return a.a1 == b.a1? a.a2 < b.a2 : a.a1 < b.a1;});
  int tmp = 0;
  for(int i = 1; i <= n; i++) {
    rk[arr[i].id] = tmp += (arr[i].a1 != arr[i - 1].a1 || arr[i].a2 != arr[i - 1].a2);
  }
}

int sufc(int x, int c) {
  return s[sa[x] + c - 1];
}

void cal() {
  sort(t.begin(), t.end());
  int l = unique(t.begin(), t.end()) - t.begin();
  for(int i = 1; i <= n; i++) {
    rk[i] = lower_bound(t.begin(), t.begin() + l, s[i]) - t.begin() + 1;
  }
  for(int x = 1; ; x <<= 1) {
    lfsort(x);
    if(x > n) {
      break;
    }
  }
  for(int i = 1; i <= n; i++) {
    sa[rk[i]] = i;
  }
  
  for(int i = 1; i <= n; i++) {
    if(rk[i] == 1) {
      continue;
    }
    ht[rk[i]] = max(0ll, ht[rk[i - 1]] - 1);
    for(; sufc(rk[i], ht[rk[i]] + 1) == sufc(rk[i] - 1, ht[rk[i]] + 1); ht[rk[i]]++) {
    }
  }
  for(int i = 1; i <= n; i++) {
    num[ht[i]].push_back(i);
  }
}

int findfa(int x) {
  return fa[x] == x? x : (fa[x] = findfa(fa[x]));
}

void unionn(int x, int y) {
  x = findfa(x), y = findfa(y);
  if(x == y) {
    return ;
  }
  if(sz[x] < sz[y]) {
    swap(x, y);
  }
  cur -= sz[x] * (sz[x] + 1) / 2;
  cur -= sz[y] * (sz[y] + 1) / 2;
  fa[y] = x, sz[x] += sz[y];
  cur += sz[x] * (sz[x] + 1) / 2;
}

signed main() {
  freopen("border.in", "r", stdin);
  freopen("border.out", "w", stdout);
  cin >> n >> s;
  n = s.size(), t = s;
  s = ' ' + s;
  cal();
  iota(fa, fa + n + 1, 0);
  fill(sz, sz + n + 1, 1);
  for(int i = n; i; i--) {
    cur++;
    for(auto j : num[i]) {
      unionn(j, j - 1);
    }
    ans += cur * i;
  }
  //*
  for(int i = 1; i <= n; i++) {
    ans -= i * (n - i + 1);
  }
  //*/
  cout << ans << '\n';
  return 0;
}

标签：8.0,arr,fa,int,++,mp,100010
From： https://www.cnblogs.com/leavenothingafterblog/p/18433698/speedrunv8-0

相关文章

  • MySQL 8.0修改密码
    MySQL8.0前修改密码在MySQL8.0前，执行：SETPASSWORD=PASSWORD('[新密码]')进行密码修改，在MySQL8.0后，以上的方法使用root用户修改别的用户密码是报错的，因为MySQL8.0后修改了修改密码的方式！mysql>usemysql;mysql>updateusersetpassword=password('新密码')whereuser=......
  • VMware ESXi 8.0U3b macOS Unlocker & OEM BIOS 2.7 Dell HPE 定制版 9 月更新发布
    VMwareESXi8.0U3bmacOSUnlocker&OEMBIOS2.7DellHPE定制版9月更新发布VMwareESXi8.0U3bmacOSUnlocker&OEMBIOS2.7标准版和厂商定制版ESXi8.0U3标准版，Dell(戴尔)、HPE(慧与)、Lenovo(联想)、IEITSYSTEMS(浪潮信息)、Cisco(思科)、Fujitsu(富士通)......
  • VMware ESXi 8.0U3 Dell (戴尔) 定制版更新 OEM BIOS 2.7 支持 Windows Server 2025
    VMwareESXi8.0U3Dell(戴尔)定制版更新OEMBIOS2.7支持WindowsServer2025VMwareESXi8.0U3macOSUnlocker&OEMBIOSDell(戴尔)定制版ESXi8.0U3标准版，Dell(戴尔)、HPE(慧与)、Lenovo(联想)、Inspur(浪潮)、Cisco(思科)、Hitachi(日立)、Fujitsu(富士通......
  • 解读MySQL8.0数据字典重构源码
    本文分享自华为云社区《【华为云MySQL技术专栏】MySQL8数据字典重构源码解读》，作者：GaussDB数据库1.背景介绍在MySQL5.7版本的使用实践过程中，我们很容易遇到DDL崩溃后导致数据不一致的问题，具体场景描述如下：主备高可用架构部署下，备机回放执行DROPTABLE的中途，因触发其它社区......
  • Mysql8.0启动时出现ERROR: Different lower_case_table_names settings for server ('
    分析：出现这个原因数据库启动后，调整lower_case_table_names参数导致的这个问题。mysql8.0之后，lower_case_table_names配置必须在安装好MySQL后，初始化mysql配置时才有效。一旦mysql启动后，再设置是无效的，而且启动报错。lower_case_table_names=1表示mysql是不区分大小写的......
  • k8s离线部署v1.28.0版本（基于docker容器）
    1.环境配置主机名配置磁盘大小操作系统ip地址k8s-master2c4g50gcentos7.6192.168.100.194k8s-node12c4g50gcentos7.6192.168.100.195k8s-node22c4g50gcentos7.6192.168.100.196yum2c4g50gcentos7.6192.168.100.2012.必要环境准备1）关......
  • MySQL 8.0 为 Java 开发者提供了许多强大的新特性
    以下是一些关键点：1.通用表表达式(CTE):CTE允许您定义命名的临时结果集,这些结果集可以在后续的SELECT、INSERT、UPDATE、DELETE或CREATEVIEW语句中被引用。这对于编写复杂查询特别有用。WITHRECURSIVEemployee_hierarchyAS(SELECTid,name,manager_id,1ASlevelF......
  • Docker打包Net8.0镜像
    Docker常用命令Docker是一种用于构建、打包和运行应用程序的容器化工具，以下是一些常用的Docker命令及其说明：1.Docker基础命令dockerversion#查看Docker的版本信息dockerinfo#查看Docker系统信息dockerbuild-t<image_name>.#构建镜像dockerpullnginx......
  • ETL: 学习搭配PENTAHO-SERVER-CE-9.4.0.0-343 + MYSQL8.0.35 部分错误日志
     学习搭配PENTAHO-SERVER-CE-9.4.0.0-343+ MYSQL8.0.35 ,启动PENTAHO 后，日志显示：UsingCATALINA_BASE:"E:\Programs\pentaho-server\tomcat"UsingCATALINA_HOME:"E:\Programs\pentaho-server\tomcat"UsingCATALINA_TMPDIR:"E:\Programs......
  • WaterCloud：一套基于.NET 8.0 + LayUI的快速开发框架，完全开源免费！
    前言今天大姚给大家分享一套基于.NET8.0+LayUI的快速开发框架，项目完全开源、免费（MITLicense）且开箱即用：WaterCloud。可完全实现二次开发让开发更多关注业务逻辑。既能快速提高开发效率，帮助公司节省人力成本，同时又不失灵活性。项目介绍WaterCloud是一套基于ASP.NET8.0MV......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99