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

雅礼信奥 2023.11.22 习题课记录（讲解版）

时间：2023-11-22 18:14:49浏览次数：34  
标签：信奥 22 int text 2023.11 long ans using include

雅礼信奥 \(2023.11.22\) 习题课记录（讲解版）

都是 CF 题，不如 AT。

剧情版后面会更。

A - Yarik and Array（CF1899C）

dp 题，作为学 OI \(3\) 年的萌新 OIer，后面才想到 dp 真是太蒟蒻了，时间复杂度 \(O(tn)\)。

初始 \(f_1 = 1\)，其他为 \(0\)。

状态转移方程：

\(\begin{cases} \text{if} & \text{abs}(a_{i - 1}) \bmod 2 + \text{abs}(a_i) \bmod 2 = 1 & f_i = \max(a_i,\ f_{i - 1} + a_i) \\ \text{if} & \text{abs}(a_{i - 1}) \bmod 2 + \text{abs}(a_i) \bmod 2 \neq 1 & f_i = a_i \end{cases}\)

\(\max(f_1, f_2, \cdots, f_n)\) 即为答案。

罚时 \(1\) 次。

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

using namespace std;

using ll = long long;

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

ll n, a[kMaxN], f[kMaxN], ans = 0;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i];
      f[i] = 0;
    }
    f[1] = a[1];
    ans = f[1];
    for (int i = 2; i <= n; ++ i) {
      if (abs(a[i - 1]) % 2 + abs(a[i]) % 2 == 1) {
        f[i] = max(a[i], f[i - 1] + a[i]);
        ans = max(ans, f[i]);
      } else {
        f[i] = a[i];
        ans = max(ans, f[i]);
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

B - Game with Integers（CF1899A）

一眼题 + 面向样例题，\(n \bmod 3 = 0\) 输出 Second，否则 First，时间复杂度 \(O(t)\)。

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

using namespace std;

using ll = long long;

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

int x;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> x;
    cout << (!(x % 3)? "Second" : "First") << '\n';
  }
  return 0;
}

C - 250 Thousand Tons of TNT（CF1899B）

枚举题。

首先，\(k\) 必定是 \(n\) 的因数，所以我们只需要枚举 \(n\) 的因数即可，时间复杂度不确定，好像是 \(O(tn\sqrt{n})\)。

罚时 \(3\) 次，因为不开 long long 见祖宗。

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

using namespace std;

using ll = long long;

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

ll n, a[kMaxN], b[kMaxN], idx = 0, mini = 1e18, maxa = -1e18, ans = -1e18, sum = 0;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> n;
    idx = 0, ans = -1e18;
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i];
    }
    for (ll i = 1; i * i <= n; ++ i) {
      if (n % i) {
        continue;
      }
      b[++ idx] = n / i;
      mini = 1e18, maxa = -1e18;
      for (ll j = 1; j <= n; ++ j) {
        sum += a[j];
        if (!(j % i)) {
          mini = min(mini, sum);
          maxa = max(maxa, sum);
          sum = 0;
        }
      }
      ans = max(ans, maxa - mini);
    }
    sum = 0;
    for (ll i = 1; i <= idx; ++ i) {
      mini = 1e18, maxa = -1e18;
      for (ll j = 1; j <= n; ++ j) {
        sum += a[j];
        if (!(j % b[i])) {
          mini = min(mini, sum);
          maxa = max(maxa, sum);
          sum = 0;
        }
      }
      ans = max(ans, (b[i] == n? 0 : maxa - mini));
    }
    cout << ans << '\n';
  }
  return 0;
}

D - Yarik and Musical Notes（CF1899D）

成为一个合法的一对 \((i, j)\) 必须满足 \(a_i = a_j\) 或 \(a_i = 1\)，\(a_j = 2\) 或 \(a_i = 2\)，\(a_j = 1\)，所以我们建立一个哈希表 \(mp\)（一定要开 map，unoredered_map 被卡了！），如果 \(a_i = 1\)，答案加 \(mp_2\)，如果 \(a_i = 2\)，答案加 \(mp_1\)，然后每次答案加 \(mp_{a_i}\)。时间复杂度 \(O(n)\)。

罚时 \(5\) 次，因为 unoredered_map 啊啊啊啊啊！

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

using namespace std;

using ll = long long;

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

ll n, a[kMaxN], ans = 0; 

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    unordered_map<ll, ll> mp;
    ans = 0;
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i];  
      if (a[i] == 1) {
        ans += mp[2];
      }
      if (a[i] == 2) {
        ans += mp[1];
      }
      ans += mp[a[i]];
      ++ mp[a[i]];
    }
    cout << ans << '\n';
  }
  return 0;
}

E - Treasure Chest（CF1895A）

分类讨论题，只需稍微推一下就可以。

\(\begin{cases} \text{if} & x > y & x \\ \text{if} & x < y \text{ and } y - (k + x) \ge 0 & y \\ \text{if} & x < y \text{ and } y - (k + x) < 0 & x + k + (y - (k + x) \times 2) \end{cases}\)

当初还以为是搜索。

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

using namespace std;

using ll = long long;

const int kMaxN = -1, kInf = (((1 << 30) - 1) << 1) + 1;

int x, y, k;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> x >> y >> k;
    if (x > y) {
      cout << x << '\n';
    } else {
      if (y - (k + x) <= 0) {
        cout << y << '\n';
      } else {
        cout << x + k + (y - (k + x) << 1) << '\n';
      }
    }
  }
  return 0;
}

F - Queue Sort（CF1899E）

首先，我们定义一个 \(ans\) （存最小值）和 \(cnt\)（用来记录答案）。每次把 \(ans\) 赋值为 \(10^{18}\)，\(cnt\) 赋值为 \(0\)。遍历一遍数组，\(cnt\) 记录最小值的下标。如果 \([cnt + 1, n]\) 区间内有 \(a_i < a_{i - 1}\) 的情况，输出 \(-1\)，否则输出 \(cnt - 1\)。

罚时 \(1\) 次。

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

using namespace std;

using ll = long long;

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

ll n, a[kMaxN], ans = 1e18, cnt = 0;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> n;
    ans = 1e18, cnt = 0;
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i];
      if (a[i] < ans) {
        ans = a[i];
        cnt = i;
      }
    }
    for (int i = cnt + 1; i <= n; ++ i) {
      if (a[i] < a[i - 1]) {
        cnt = -1;
      }
    }
    cout << (cnt == -1? -1 : cnt - 1) << '\n';
  }
  return 0;
}

G - Points and Minimum Distance（CF1895B）

当初还以为是最短路，所以放在后面，结果发现 G 好简单。

将输入的数据排好序，然后遍历 \([1, n - 1]\)，每次把距离加 \(\text{abs}(a_i - a_{i + 1}) + \text{abs}(a_{i + n} - a_{i + n + 1})\)，遍历完后输出。然后我们定义两个指针 \(i, j\)，\(i = 1\)，\(j = n \times 2\)，每次 \(i\) 加 \(1\)，\(j\) 减 \(1\)，\(a_i, a_j\) 即是我们要输出的坐标。

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

using namespace std;

using ll = long long;

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

ll n, ans = 0, a[kMaxN];

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    ans = 0;
    cin >> n;
    for (int i = 1; i <= (n << 1); ++ i) {
      cin >> a[i];
    }
    sort(a + 1, a + (n << 1) + 1);
    for (int i = 1; i <= n - 1; ++ i) {
      ans += labs(a[i] - a[i + 1]) + labs(a[i + n] - a[i + n + 1]);
    }
    cout << ans << '\n';
    for (int i = 1, j = (n << 1); i <= j; ++ i, -- j) {
      cout << a[i] << ' ' << a[j] << '\n';
    }
  }
  return 0;
}

Thanks for your looking.

标签：信奥,22,int,text,2023.11,long,ans,using,include
From： https://www.cnblogs.com/bc2qwq/p/yali20231122problemclass.html

相关文章

  • 2023.11.22学习笔记（2）
    跳石头P2678[NOIP2015提高组]跳石头-洛谷|计算机科学教育新生态(luogu.com.cn)佬啊佬啊，我的思路：用数组b去储存它的差分，每一次找到它的最小值，将最小值和它旁边的较小的那个值合并，边界的话就直接合并，总计进行m次合并操作，这个时候再找到它的最小值，就是答案但是如果是枚举......
  • 11.22
    今天画了四个图，收入管理， 支出管理， 库存管理， 生产管理 ......
  • P8907 [USACO22DEC] Making Friends P 题解
    明明看着不难的题目，却意外的卡人。思路考虑两头奶牛可以成为朋友条件是什么。存在一条路径连接这两头奶牛。且除去端点外的路径上的所有点的编号小于两端点的较小值。充分必要性都比较显然。如何维护。我们可以从小到大加入点，维护这些路径。对于每个点维护一个\(\text{se......
  • 11.22总结
    packagetest;publicabstractclassAbstractCommand{publicabstractintexecute(intvalue);publicabstractintundo();}packagetest;publicclassAdder{privateintnum=0;publicintadd(intvalue){num+=value;returnnum;}}packagetest;publi......
  • VS2022下nuget包同步失败，提示： PackageSourceMapping 已启用，未考虑以下源: **
    随着Net8的发布，顺带VS2022升级到17.8后，发现nuget还原恢复多了一些配置： 有问题的时候，会提示未找到映射源，此时编译会报错，如下示例： 严重性代码说明项目文件行禁止显示状态错误NU1100无法解析net7.0-android33.0的“HarfBuzzSharp.NativeAssets.Linux(>=2.8.2.3)”......
  • Windows server 2022下载地址
    【Windowsserver2022】ed2k://|file|zh-cn_windows_server_2022_updated_sep_2023_x64_dvd_892eeda9.iso|5525116928|9ADE79B3BC3923E9DD241206E263D611|/magnet:?xt=urn:btih:eaa74aadaac68f481156bad27f153e7e215b4dba&dn=zh-cn_windows_server_2022_updated_sep_2023_......
  • 2023.11.11西九华二日游
    河南西九华，适宜周末二日游。阜阳出发到阜南县郎湾村渡口，坐轮渡到对岸，然后到固始西九华山。淡季景点人很少，不少住宿、餐饮不开门营业。......
  • P2234 [HNOI2002] 营业额统计
    P2234[HNOI2002]营业额统计题解思路对原数组排序，记录下排序前的位置。对排序后的数组构造链表。从原数组的\(n\)往\(1\)枚举，比较排序生成链表中该元素的前驱或后继与该元素差值的最小值，加入答案。在排序生成的链表中删除该元素。正确性的疑惑一开始很困惑，难道排序......
  • 2023.11.21做题笔记（对局匹配，砝码称重shui，单词接龙）
    今天水了一节英语课，翘了一节C++课，就是感觉摆的一批。 对局匹配P8656[蓝桥杯2017国B]对局匹配-洛谷|计算机科学教育新生态(luogu.com.cn)   对于这道题：大佬解法1：#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;intn,k,a[N],an......
  • VMware Ubuntu 22.x.x ens33消失，不可用
    点击更改设置网段可自行修改，88可以改其他的，使用的时候统一即可，然后启用确定，不会照抄修改主机的VMnet8网关的网段和刚才的设置要相同，后续地址可以随意设置，但是不能和其他配置冲突，参考如下设置即可，dns选择合适的即可不会配置的直接照抄，保存后不要随意修改该配置，否则可能导致......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99