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

《如 何 速 通 一 套 题》12.0

时间：2024-10-03 22:01:35浏览次数：9  
标签：arr return cout int 44 12.0 ans

别问我为什么没有 11.0。补完了 1002 的题我就更 11.0。

邮寄

开场秒掉 AC，用了 1h。

然后开始看 B，死磕了 B 2h 之后磕不动了，然后看 D。

D 忽略了一个关键信息，100 -> 0... 挂大分了。

100+40+75+0=200。

A 旋律的总数

可以固定第一个元素为 \(1\)（因为其他的情况会重掉）。

然后答案就是 \(m^{n - 1}\)。

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

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

int t, n, m;

int qpow(int x, int y) {
  int rs = 1;
  for(; y; y >>= 1) {
    if(y & 1) {
      rs = 1ll * rs * x % kMod;
    }
    x = 1ll * x * x % kMod;
  }
  return rs;
}

int main() {
  freopen("sum.in", "r", stdin);
  freopen("sum.out", "w", stdout);
  for(cin >> t; t--; ) {
    cin >> n >> m;
    cout << qpow(m, n - 1) << '\n';
  }
  return 0;
}

B 水果加工

第十四剪枝。

首先，显然的我们有一个加了可行性剪枝的暴搜：

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

int n, arr[44], x, y, cx[44], cy[44], dx[44], dy[44], ux[44], uy[44], ans = 1e11;

void DFS(int c, int a, int b, int cd, int cu) {
  //cout << c << ' ' << a << ' ' << b << '\n';
  if(c > n) {
    //cout << cd << ' ' << cu << '\n';
    ans = min(ans, cd + cu);
    return ;
  }
  for(int i = 0; i <= arr[c]; i++) {
    int na = a + (!!i) * cx[c], nb = b + (!!(arr[c] - i)) * cy[c];
    if(na <= x && nb <= y) {
      DFS(c + 1, na, nb, max({cd, dx[c] * i, dy[c] * (arr[c] - i)}), max({cu, ux[c] * i, uy[c] * (arr[c] - i)}));
    }
  }
}

signed main() {
  freopen("fruit.in", "r", stdin);
  freopen("fruit.out", "w", stdout);
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> arr[i];
  }
  cin >> x >> y;
  for(int i = 1; i <= n; i++) {
    cin >> cx[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> cy[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> dx[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> dy[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> ux[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> uy[i];
  }
  DFS(1, 0, 0, 0, 0);
  cout << ans << '\n';
  return 0;
}

聪明的小同学肯定想到了，我们可以加上简单的最优性剪枝啊！

所以有了 Original + CS11：

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

int n, arr[44], x, y, cx[44], cy[44], dx[44], dy[44], ux[44], uy[44], ans = 1e11;

void DFS(int c, int a, int b, int cd, int cu) {
  //cout << c << ' ' << a << ' ' << b << '\n';
  if(cd + cu > ans) {
    return ;
  }
  if(c > n) {
    //cout << cd << ' ' << cu << '\n';
    ans = min(ans, cd + cu);
    return ;
  }
  for(int i = 0; i <= arr[c]; i++) {
    int na = a + (!!i) * cx[c], nb = b + (!!(arr[c] - i)) * cy[c];
    if(na <= x && nb <= y) {
      DFS(c + 1, na, nb, max({cd, dx[c] * i, dy[c] * (arr[c] - i)}), max({cu, ux[c] * i, uy[c] * (arr[c] - i)}));
    }
  }
}

signed main() {
  freopen("fruit.in", "r", stdin);
  freopen("fruit.out", "w", stdout);
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> arr[i];
  }
  cin >> x >> y;
  for(int i = 1; i <= n; i++) {
    cin >> cx[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> cy[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> dx[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> dy[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> ux[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> uy[i];
  }
  DFS(1, 0, 0, 0, 0);
  cout << ans << '\n';
  return 0;
}

然后，更聪明的小伙伴就会发现，这个剪枝力度不够大，还可以再大一点。

于是有了 Original + CS(11 + 21)：

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

int n, arr[44], x, y, cx[44], cy[44], dx[44], dy[44], ux[44], uy[44], ans = 1e11;

void DFS(int c, int a, int b, int cd, int cu) {
  //cout << c << ' ' << a << ' ' << b << '\n';
  if(cd + cu >= ans) {
    return ;
  }
  if(c > n) {
    //cout << cd << ' ' << cu << '\n';
    ans = min(ans, cd + cu);
    return ;
  }
  for(int i = 0; i <= arr[c]; i++) {
    int na = a + (!!i) * cx[c], nb = b + (!!(arr[c] - i)) * cy[c];
    if(na <= x && nb <= y) {
      DFS(c + 1, na, nb, max({cd, dx[c] * i, dy[c] * (arr[c] - i)}), max({cu, ux[c] * i, uy[c] * (arr[c] - i)}));
    }
  }
}

signed main() {
  freopen("fruit.in", "r", stdin);
  freopen("fruit.out", "w", stdout);
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> arr[i];
  }
  cin >> x >> y;
  for(int i = 1; i <= n; i++) {
    cin >> cx[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> cy[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> dx[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> dy[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> ux[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> uy[i];
  }
  DFS(1, 0, 0, 0, 0);
  cout << ans << '\n';
  return 0;
}

这个时候，更加聪明的巨佬就会发现，可以剪掉一定不是当前最优的状态！

于是有了 Original + CS(11, 21, 22)，AC：

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

struct node {
  int c, a, b, cd;
  
  bool operator <(const node &x) const {
    return c == x.c? (a == x.a? (b == x.b? cd < x.cd : b < x.b) : a < x.a) : c < x.c;
  }
};

int n, arr[44], x, y, cx[44], cy[44], dx[44], dy[44], ux[44], uy[44], ans = 1e11;
map<node, int> mpd;

void DFS(int c, int a, int b, int cd, int cu) {
  //cout << c << ' ' << a << ' ' << b << '\n';
  if(cd + cu >= ans) {
    return ;
  }
  if(mpd.find({c, a, b, cd}) != mpd.end() && mpd[{c, a, b, cd}] <= cu) {
    return ;
  }
  mpd[{c, a, b, cd}] = cu;
  if(c > n) {
    //cout << cd << ' ' << cu << '\n';
    ans = min(ans, cd + cu);
    return ;
  }
  for(int i = 0; i <= arr[c]; i++) {
    int na = a + (!!i) * cx[c], nb = b + (!!(arr[c] - i)) * cy[c];
    if(na <= x && nb <= y) {
      DFS(c + 1, na, nb, max({cd, dx[c] * i, dy[c] * (arr[c] - i)}), max({cu, ux[c] * i, uy[c] * (arr[c] - i)}));
    }
  }
}

signed main() {
  freopen("fruit.in", "r", stdin);
  freopen("fruit.out", "w", stdout);
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> arr[i];
  }
  cin >> x >> y;
  for(int i = 1; i <= n; i++) {
    cin >> cx[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> cy[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> dx[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> dy[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> ux[i];
  }
  for(int i = 1; i <= n; i++) {
    cin >> uy[i];
  }
  DFS(1, 0, 0, 0, 0);
  cout << ans << '\n';
  return 0;
}

C 最佳位置

显然对于每一个人除了前缀后缀之外就只会坐在一个区间的中间位置。

所以可以直接两个 set，一个维护有人进来的，一个维护有人出去的，然后根据对应操作直接干就是了。

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

int n, m, x, ans[300030];

int gl(int l, int r) {
  if(l == 1 || r == n) {
    return r - l + 1;
  }
  int mid = (l + r) >> 1;
  return min(mid - l, r - mid) + 1;
}

int pos(int l, int r) {
  if(l == 1) {
    return 1;
  }
  if(r == n) {
    return n;
  }
  return (l + r) >> 1;
}

struct node {
  int len, l, r;
};

struct cmp1 {
  bool operator ()(const node &a, const node &b) const {
    return a.l < b.l;
  }
};

//*
struct cmp2 {
  bool operator ()(const node &a, const node &b) const {
    return a.len == b.len? a.l < b.l : a.len > b.len;
  }
};
//*/

set<node, cmp1> st1;
set<node, cmp2> st2;

void ins(int l, int r) {
  if(l > r) {
    return ;
  }
  int tmp = gl(l, r);
  st1.insert({tmp, l, r});
  st2.insert({tmp, l, r});
}

int main() {
  freopen("location.in", "r", stdin);
  freopen("location.out", "w", stdout);
  cin >> n >> m;
  st1.insert({-1, -1, -1});
  st2.insert({-1, -1, -1});
  st1.insert({-1, n + 2, n + 2});
  st2.insert({-1, n + 2, n + 2});
  st1.insert({n, 1, n});
  st2.insert({n, 1, n});
  for(int i = 1; i <= 2 * m; i++) {
    cin >> x;
    if(!ans[x]) {
      node tmp = *st2.begin();
      st2.erase(st2.begin());
      st1.erase(tmp);
      ans[x] = pos(tmp.l, tmp.r);
      ins(tmp.l, ans[x] - 1);
      ins(ans[x] + 1, tmp.r);
    }else {
      node tmpl = *prev(st1.lower_bound({1, ans[x], ans[x]})), tmpr = *st1.lower_bound({1, ans[x], ans[x]});
      int nl = ans[x], nr = ans[x];
      if(tmpl.r == ans[x] - 1) {
        nl = tmpl.l;
        st1.erase(tmpl);
        st2.erase(tmpl);
      }
      if(tmpr.l == ans[x] + 1) {
        nr = tmpr.r;
        st1.erase(tmpr);
        st2.erase(tmpr);
      }
      ins(nl, nr);
    }
    /*
    for(auto i : st1) {
      cout << i.len << ',' << i.l << ',' << i.r << ' ';
    }
    cout << '\n';
    for(auto i : st2) {
      cout << i.len << ',' << i.l << ',' << i.r << ' ';
    }
    cout << '\n';
    for(int i = 1; i <= m; i++) {
      cout << ans[i] << ' ';
    }
    cout << '\n';
    cout << '\n';
    //*/
  }
  for(int i = 1; i <= m; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}
/*
9 9
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
*/

D 跑步路线

赛时没看到有一个 \(w_i\) 互不相同的条件，死了。

当 \(w_i\) 互不相同，MST 唯一，可以直接求出 MST 然后 MST 上面 LCA 求两点距离。

但是这个题要开 __int128_t qaq

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

struct node {
  int u, v, w;
}arr[200020];

struct eeee {
  int v, w;
};

int n, m, f[200020], k, t, x, y, fa[200020][22], ddp[200020], dep[200020];
__int128_t ans;
vector<eeee> to[200020];

void write(__int128_t x) {
  if(!x) {
    return ;
  }
  write(x / 10);
  cout << char(x % 10 + '0');
}

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

bool unionn(int x, int y) {
  x = findfa(x), y = findfa(y);
  f[y] = x;
  return x != y;
}

void kruskal() {
  for(int i = 1; i <= n; i++) {
    f[i] = i;
  }
  for(int i = 1; i <= m; i++) {
    if(unionn(arr[i].u, arr[i].v)) {
      to[arr[i].u].push_back({arr[i].v, arr[i].w});
      to[arr[i].v].push_back({arr[i].u, arr[i].w});
    }
  }
}

void DFS(int x = 1, int pa = 0) {
  fa[x][0] = pa;
  for(int i = 1; i <= 20; i++) {
    fa[x][i] = fa[fa[x][i - 1]][i - 1];
  }
  for(auto i : to[x]) {
    if(i.v != pa) {
      dep[i.v] = dep[x] + i.w + t;
      ddp[i.v] = ddp[x] + 1;
      DFS(i.v, x);
    }
  }
}

int LCA(int x, int y) {
  if(ddp[x] < ddp[y]) {
    swap(x, y);
  }
  int tmp = ddp[x] - ddp[y];
  for(int i = 20; i >= 0; i--) {
    if((tmp >> i) & 1) {
      x = fa[x][i];
    }
  }
  if(x == y) {
    return x;
  }
  for(int i = 20; i >= 0; i--) {
    if(fa[x][i] != fa[y][i]) {
      x = fa[x][i], y = fa[y][i];
    }
  }
  return fa[x][0];
}

signed main() {
  freopen("run.in", "r", stdin);
  freopen("run.out", "w", stdout);
  cin >> n >> m;
  for(int i = 1; i <= m; i++) {
    cin >> arr[i].u >> arr[i].v >> arr[i].w;
  }
  sort(arr + 1, arr + m + 1, [](node a, node b) {return a.w < b.w;});
  kruskal();
  cin >> k >> t;
  DFS();
  cin >> x;
  for(k--; k; k--) {
    cin >> y;
    int tmp = LCA(x, y);
    ans = ans + dep[x] + dep[y] - 2 * dep[tmp];
    x = y;
  }
  //cout << cs << ' ' << cl << ' ' << pk << '\n';
  if(ans) {
    ans = ans - t;
  }
  write(ans);
  return 0;
}

标签：arr,return,cout,int,44,12.0,ans
From： https://www.cnblogs.com/leavenothingafterblog/p/18446059/speedrunv12

相关文章

  • 驱动更新 IObit Driver Booster PRO v12.0.0.354 绿色版
    驱动更新IObitDriverBoosterPROv12.0.0.354绿色版下载地址:https://pan.quark.cn/s/85f9c35e7944介绍IObitDriverBooster，全球专业级驱动更新软件。检测硬件驱动更新、驱动备份管理、支持离线驱动更新，检测游戏组件、修复设备错误、无声问题、网络问题。提供游戏加速、......
  • Android12.0需求开发篇之Native Binder Demo通信篇章二
    1.需求描述        基于篇章一的基础上，增加NativeBinderDemo通信的回调功能，由于之前信息数据传递是个单向链路，即由client端主动发起，发送到Server服务端，缺失服务端调用客户端的逻辑，而在实际场景中，应用组还需要双向通信。基于此，在之前BspServer服务端的基础上增加回......
  • VS2022 17.12.0 Preview2版本对Copilot的功能增强
    前提条件,使用最新版的17.12.0Preview2,并且有有效的CopilotAI订阅,那么可以体验这些新鲜好用的功能增强了CopilotAI对IEnumerableVisualizer的可编辑表达式功能我们可以通过AI实现一些复杂的条件筛查,并且可以即时验证结果是否符合预期,对于开发和调试提供了极大的便利性......
  • Android 12.0 Launcher3禁用widget微件功能实现
    1.前言在12.0的系统rom定制化开发中，在一些Launcher3的定制化功能中，有些产品禁用appwidget微件功能，要求Launcher去掉加载widget微件功能，接下来具体分析下widget微件的加载流程2.Launcher3禁用widget微件功能实现的核心类packages/apps/Launcher3/src/com/android/launcher3/......
  • Android 12.0 wifi设置静态ip功能实现
    1.前言在12.0的系统rom定制化开发中，在某些功能开发中，在wifi模块中，有产品需要要求设置wifi静态ip功能，而系统中wifi连接后ip是动态的，每次开机后连接wifi的ip就是不固定的，所以产品需要采用固定ip，就需要实现静态ip功能2.wifi设置静态ip功能实现的核心类frameworks\base\wifi\ja......
  • Android 12.0 framework层实现点击空白处自动隐藏输入法功能
    1.前言 在12.0的系统rom产品定制化开发中，在进行一些定制开发中，在某些无源码的app中，如果app中没实现点击空白区域外自动隐藏输入法功能的时候，那么就需要在系统framework层中进行相关功能的开发，接下来看下相关功能的实现2.framework层实现点击空白处自动隐藏输入法功能的核......
  • anaconda安装①tensorflow-cpu 1.12.0py3.6②tensorflow-gpu 2.4.0③pytorch 2.4.1 通
    本机环境：Win10、rtx4060tianaconda常用命令condaenvlist#查看已有环境名称condaenvlistcondaactivateenv_name #激活环境condaactivateenv_namecondadeactivateenv_name#退出环境condadeactivateenv_namecondacreate-nenv_namepython=3.x#创建p......
  • Android 12.0 MTK平台关机充电动画横屏显示修改
    1.前言在12.0的系统rom定制化开发中，在关于MTK平台的产品中，系统默认的充电动画是竖屏显示的，但是在像平板的产品中竖屏动画肯定不符合规范，所以需要在平板TV产品中，充电动画同时也是需要修改为横屏显示的，接下来就来分析下充电动画的相关绘制流程，然后实现功能2.MTK平台关机充电动......
  • Android 12.0 展讯平台关机充电动画横屏显示修改
    1.前言在12.0的系统rom定制化开发中，在关于展讯平台的产品中，系统默认的充电动画是竖屏显示的，但是在像平板的产品中竖屏动画肯定不符合规范，所以需要在平板TV产品中，充电动画同时也是需要修改为横屏显示的，接下来就来分析下充电动画的相关绘制流程，然后实现功能2.展讯平台关机充电......
  • MIUI 12.0.15
    /storage/emulated/0/MIUI/Gallery/cloud/.cache/.localthumbnailFile这个目录莫名其妙就很大95GB，感觉有bug Totaldiskusage:95.7GiBApparentsize:95.6GiBItems:18357 我大概明白了，它会将我拍摄的/DCIM/Camera目录下的压缩了的图，莫名其妙转换为未压缩的图，然后......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99