首页 > 其他分享 >雅礼 2023.12.20 习题课记录（讲解版）

雅礼 2023.12.20 习题课记录（讲解版）

时间：2023-12-23 10:00:16浏览次数：29  
标签：20 int 2023.12 ll 雅礼 mp ans using include

雅礼 \(2023.12.20\) 习题课记录（讲解版）

前言

Always CF，Never AT。

又双是 CF 题，只能说“水”，AK 了。

水题（只放代码）

B - Two Vessels（CF1872A)

有分别装有 \(a, b\) 单位水的两个杯子，容量无限大。现在有一个勺子，容量为 \(c\)，每次可以从一个杯子里舀一勺不超过 \(c\) 单位的水（\(c\) 可以不是整数），放入另一个杯子中。请问最少需要多少次操作才能使两个杯子里的水量相同。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 5e4 + 50, kMaxM = 1.8e5 + 18, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

ll a, b, c;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    cin >> a >> b >> c;
    ll ans = 0;
    if (a < b) {
      swap(a, b);
    }
    for (; a > b; ++ ans) {
      a -= c, b += c;
    }
    cout << ans << '\n';
  }
  return 0;
}

高级水题 & 低级正常题

C - The Corridor or There and Back Again（CF1872B)

有若干个房间排成一行，其中有 \(n\) 个房间有陷阱，对于这 \(n\) 个房间，它们有两个属性：\(d_i\) 和 \(s_i\)，分别代表标号和陷阱形成的时间，即若你第 \(t\) 秒第一次到达 \(i\) 号房间，\(t+s_i\) 秒时陷阱就会在此房间形成，此后你无法通过此房间。每秒你可以走到与当前房间标号相邻的房间。你需要从 \(1\) 号房间走到 \(k\) 号房间，并且再从 \(k\) 号房间走回 \(1\) 号房间。求 \(k\) 最大是多少。

我们可以发现，当碰到机关时，你最多可以往后走 \((s_i - 1) \div 2\) 个房间了。所以我们的答案就是 \(\min_{i = 1}^{n} d_i + (s_i - 1) \div 2\)。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 110, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

ll n, d, s;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    cin >> n;
    ll ans = kLInf;
    for (int i = 1; i <= n; ++ i) {
      cin >> d >> s;
      ans = min(ans, d + (s - 1) / 2);
    }
    cout << ans << '\n';
  }
  return 0;
}

D - Non-coprime Split（CF1872C）

给出 \(l,r\)，构造一组 \(a,b\) 使满足以下条件：

  • \(l \le a+b \le r\)
  • \(\gcd(a,b) \neq 1\)

若有多组解，则输出任意一组。

我们可以发现 \(l \sim r\) 区间内，如果一个数 \(n\) 不是质数。设它的最小因数为 \(x\)，那么 \(\gcd(x,\ n - x) = 1\)。所以我们枚举 \(l \sim r\)，如果 \(i\) 不是质数，那么就输出 \(i\) 的最小因数和 \(i - (i\) 的最小因数\()\)。如果 \(l \sim r\) 区间内没有满足条件的 \(i\)，输出 \(-1\)（无解）。时间复杂度 \(O(t·(r - l + 1)·\sqrt{i})\)。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 110, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

ll l, r; 

ll M(ll x) { // 求最小因数
  for (int i = 2; i * i <= x; ++ i) { // 枚举因数
    if (!(x % i)) {
      return i;
    }
  }
  return 0;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    cin >> l >> r;
    bool f = 0;
    for (int i = l; i <= r; ++ i) { // 枚举 l~r 区间
      int r = M(i); // 求最小因数
      if (!r) {
        continue;
      }
      f = 1;
      cout << r << ' ' << i - r << '\n';
      break;
    }
    if (!f) {
      cout << "-1\n"; // 无解
    }
  }
  return 0;
}

G - United We Stand（CF1859A）

一共 \(t\) 组数据，每组数据给定一个长度为 \(n\) 的数组 \(a\)，将其分为两个数组，使得任意第二个数组中的数不可以整除任意第一个数组中的数。

构造题，这种题最简单。

如果 \(a\) 中所有元素相同，无解。否则，我们把 \(a\) 分割成两个数组，\(a_n\) 为第二个数组，然后把 \(a\) 数组从 \(n - 1\) 个元素从后往前遍历，如果当前数与后一个数相同，把它分给第二个数组，否则停止分割。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 110, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

int n, a[kMaxN], ans1[kMaxN], ans2[kMaxN];

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    memset(ans2, 0, sizeof ans2);
    cin >> n;
    int l1 = 0, l2 = 0;
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    if (a[1] == a[n]) {
      cout << "-1\n";
    } else {
      ans2[++ l2] = a[n];
      for (int i = n - 1; i >= 1; -- i) {
        if (a[i] == a[i + 1]) {
          ans2[++ l2] = a[i];
        } else {
          break;
        }
      }
      cout << n - l2 << ' ' << l2 << '\n';
      for (int i = 1; i <= n - l2; ++ i) {
        cout << a[i] << ' ';
      }
      cout << '\n';
      for (int i = 1; i <= l2; ++ i) {
        cout << ans2[i] << ' ';
      }
      cout << '\n';
    }
  }
  return 0;
}

E - Plus Minus Permutation（CF1872D）

数学题。

我们尽量在 \(p_{k_1·x}(1 \le k_1 \le \lfloor \frac{n}{x} \rfloor)\) 放大的数，\(p_{k_2·y}(1 \le k_2 \le \lfloor \frac{n}{y} \rfloor)\) 放小的数。套一些公式即可。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 110, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

ll n, x, y;

ll lcm(ll a, ll b) {
  return a / __gcd(a, b) * b;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    cin >> n >> x >> y;
    ll nx = n / x, ny = n / y;
    nx -= n / lcm(x, y), ny -= n / lcm(x, y);
    ll ans = (2 * n - nx + 1) * nx / 2;
    ans -= (ny + 1) * ny / 2;
    cout << ans << '\n';
  } 
  return 0;
}

正常题

接下来的题才算正常题。

F - Serval and Toxel's Arrays（CF1789C）

给你一个零时刻的长度为 \(n\) 的数组 \(a_i\)。

时刻 \(i\ (1 \le i \le m)\) 的数组是在时刻 \(i-1\) 的基础上把位置 \(p_i\) 的数改成 \(v_i\) 得到的。

现在让你求出 \(\sum_{i=0}^m \sum_{j=i+1}^m f(i,j)\)，其中 \(f(i,j)\) 的值为时刻 \(i\) 和时刻 \(j\) 的数组拼起来后一共有几种数字。

我们知道对答案 \(x\) 造成贡献有两种情况：

  1. \(a_i\) 含有 \(x\)，但 \(a_j\) 不含有 \(x\)。

  2. \(a_i\) 和 \(a_j\) 都含有 \(x\)。

设 \(f_i\) 为 \(i\) 在第 \(f_i\) 中出现过了，可以算出它们贡献分别为 \(s_x(m - s_x + 1)\)， \(\dfrac{(s_x)^2 - s_x}{2}\)。

\(e^{i\pi}\) 年 OI 一场空，不清空数组见祖宗。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 4e5 + 40, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

ll n, m, a[kMaxN], b[kMaxN], c[kMaxN], ans = 0;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    ans = 0;
    cin >> n >> m;
    // 清空数组 清空数组 清空数组
    for (int i = 1; i <= n + m; ++ i) {
      c[i] = 0;
      b[i] = -1;
    }
    // 清空数组 清空数组 清空数组
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i];
      b[a[i]] = 0;
    }
    for (ll i = 1, x, y; i <= m; ++ i) {
      cin >> x >> y;
      if (a[x] != y) {
        c[a[x]] += i - b[a[x]];
        b[a[x]] = -1;
        b[y] = i;
      }
      a[x] = y;
    }
    for (ll i = 1; i <= n + m; ++ i) {
      c[i] += (m - b[i] + 1) * (b[i] != -1);
    }
    for (ll i = 1; i <= n + m; ++ i) {
      ans += c[i] * (m - c[i] + 1) + c[i] * (c[i] - 1) / 2;
    }
    cout << ans << '\n';
  }
  return 0;
}

A - Torn Lucky Ticket（CF1895C）

A 题放压轴，emmmmm……

给出 \(n\) 个长度最多为 \(5\) 的由 \(1\) 到 \(9\) 构成的字符串 \(s\)。求出有多少个 \((i,j)\) 满足 \(s_i + s_j\) 所形成的字符串长度为偶数，并且前半部分的数字之和等于后半部分的数字之和。

我这种做法似乎很稀奇。

我们开一个 map，下标为 pair<long long, long long>，一个存各位数字之和，一个存长度。

每次根据字符串的长度 \(l\) 分类讨论：

  • \(l = 1\)，只能挑选长度为 \(1\) 的。

  • \(l = 2\)，只能挑选长度为 \(2\) 的。

  • \(l = 3\)，既可以挑选长度为 \(3\) 的，又可以挑选长度为 \(1\) 的。

  • \(l = 4\)，既可以挑选长度为 \(4\) 的，又可以挑选长度为 \(2\) 的。

  • \(l = 5\)，可以挑选长度为 \(1, 3, 5\) 的。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

ll n, ans = 0;
string s[kMaxN];
map<pair<ll, ll>, ll> mp;
vector<ll> v;

void W(ll i, ll len) {
  if (len == 1) {
    ans += mp[{v[i - 1], 1}];
  } else if (len == 2) {
    ans += mp[{v[i - 1], 2}];
  } else if (len == 3) {
    ans += mp[{v[i - 1], 3}];
    ans += mp[{v[i - 1] - 2 * (s[i].back() - '0'), 1}];
    ans += mp[{v[i - 1] - 2 * (s[i].front() - '0'), 1}];
  } else if (len == 4) {
    ans += mp[{v[i - 1], 4}];
    ans += mp[{v[i - 1] - 2 * (s[i].back() - '0'), 2}];
    ans += mp[{v[i - 1] - 2 * (s[i].front() - '0'), 2}];
  } else {
    ans += mp[{v[i - 1], 5}];
    ans += mp[{v[i - 1] - 2 * (s[i].back() - '0'), 3}];
    ans += mp[{v[i - 1] - 2 * (s[i].front() - '0'), 3}];
    ans += mp[{v[i - 1] - 2 * ((s[i].front() - '0') + (s[i][1] - '0')), 1}];
    ans += mp[{v[i - 1] - 2 * ((s[i].back() - '0') + (s[i][3] - '0')), 1}];
  }
} 

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; ++ i) {
    ll cnt = 0;
    cin >> s[i];
    for (int j = 0; j < s[i].size(); ++ j) {
      cnt += s[i][j] - '0';
    }
    v.push_back(cnt);
    ++ mp[{cnt, s[i].size()}];
  }
  for (int i = 1; i <= n; ++ i) {
    W(i, s[i].size());
  }
  cout << ans << '\n';
  return 0;
}

标签：20,int,2023.12,ll,雅礼,mp,ans,using,include
From： https://www.cnblogs.com/bc2qwq/p/YL20231220xitike.html

相关文章

  • 2023-2024-1 20231320 《计算机基础与程序设计》第十三周学习总结
    2023-2024-120231320《计算机基础与程序设计》第十三周学习总结作业信息这个作业属于哪个课程<班级的链接>（2023-2024-1计算机基础与程序设计)这个作业要求在哪里<作业要求的链接>(2022-2023-1计算机基础与程序设计第十三周作业)这个作业的目标<自学《C语言程序......
  • sol. [省选联考 2021 A/B 卷] 滚榜
    [省选联考2021A/B卷]滚榜算法标签：状压DP，差分，费用提前计算。题目描述给定\(n\)个非负整数\(a_1,a_2,\dots,a_n\)，定义\(d_i\)表示以\(a_i\)为第一关键字降序排序，以\(i\)为第二关键字升序排序后的下标。现有\(n\)个非负整数\(b_1,b_2,\dots,b_n\)，满足\(\s......
  • IDEA最新2023.3.2激活教程，亲测有效！
    IDEA是JetBrains公司的产品，这家公司总部位于捷克共和国的首都布拉格，开发人员以严谨著称的东欧程序员为主。教程更新于12月22日第一步：下载IDEA安装包访问IDEA官网：https://www.jetbrains.com/idea/download/，点击download，下载IDEA2023.2版本的安装包第二步：卸载老版本IDEA(未安......
  • 2023-2024-1 20231309 《计算机基础与程序设计》第十三周学习总结
    2023-2024-120231309《计算机基础与程序设计》第十三周学习总结作业信息这个作业属于哪个课程2023-2024-1-计算机基础与程序设计这个作业要求在哪里2023-2024-1计算机基础与程序设计第十三周作业这个作业的目标自学教材《C语言程序设计》第12章并完成云班课测......
  • 2023.12.22——每日总结
    学习所花时间（包括上课）：9h代码量（行）：0行博客量（篇）：1篇今天，上午学习，下午学习；我了解到的知识点：1.设计模式明日计划：学习......
  • “做开源犹如养护花朵，花开需要时间”｜2023年度总结
    你好，我是Kagol。2023年已经接近尾声，OpenTiny从一颗种子......
  • [Qt5] Error starting process C:\Qt\Qt5.12.0\5.12.0\msvc2015\bin\moc.exe:
    作者：丶布布文章预览：问题解决方式问题把工程代码从电脑A拷贝到电脑B，环境vs2015+QT5.12，出现如下错误：ErrorstartingprocessD:\Qt\Qt5.12.0\5.12.0\msvc2015\bin\moc.exe:系统找不到指定的文件经排查后发现电脑A使用的Qt版本是QT5.12.0，电脑B使用的Qt版本是QT5.12.1，程序在电脑A上......
  • [Halcon] 2023.2月license分享（关注持续更新）
    作者：丶布布友情提示：Halcon18以下版本不再提供HDevelop试用授权License(只有运行License需要配合加密狗)，请大家升级到最新版本！Halcon是一款商业化的视觉程序，它封装了很多方便的强大的图像处理算法，很多视觉项目都有用它，与visionpro一样，都是一款商业化的软件，加密狗相当的贵，不过Halcon......
  • 2023常见自动化测试工具集合
    1、Appium------->AppUI自动化测试官网：http://appium.ioAppium是一个移动端自动化测试开源工具，支持iOS和Android平台，支持Python、Java等语言，即同一套Java或Python脚本可以同时运行在iOS和Android平台，Appium是一个C/S架构，核心是一个Web服务器，它提供了一套REST的......
  • [PA2021] Wystawa
    [PA2021]Wystawa牛逼啊喔趣。题意给定长度为\(n\)的序列\(a,b\)。你需要构造一个序列\(c\)，构造方法为：选择\(k\)个\(i\)，令\(c_i\leftarrowa_i\)。对于其他\(i\)，令\(c_i\leftarrowb_i\)。求序列\(c\)的最大子段和的最小值，并给出一种方案。Sol感觉最小......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99