【XCPC笔记】2023 (ICPC) Jiangxi Provincial Contest——ABCIJKL 做题记录

2024-04-06 04:28

本文主要是介绍【XCPC笔记】2023 (ICPC) Jiangxi Provincial Contest——ABCIJKL 做题记录,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

补题

赛后gym练习及补题,gym链接:2023 (ICPC) Jiangxi Provincial Contest – Official Contest
另外,D题我也打算找机会学习写下,C题的博弈论还需要好好理解,感觉都是比较有趣的数学问题

补题顺序如下

  • 补题
  • L [Zhang Fei Threading Needles - Thick with Fine](https://codeforces.com/gym/104385/problem/L)
    • 题面解读
    • 参考代码
  • A [Drill Wood to Make Fire](https://codeforces.com/gym/104385/problem/A)
    • 题面解读
    • 参考代码
  • B [Wonderful Array](https://codeforces.com/gym/104385/problem/B)
    • 题面解读
    • 参考代码
  • I [Tree](https://codeforces.com/gym/104385/problem/I)
    • 题面解读
    • 参考代码
  • J [Function](https://codeforces.com/gym/104385/problem/J)
    • 题面解读
    • 参考代码
  • K [Split](https://codeforces.com/gym/104385/problem/K)
    • 题面解读
    • 参考代码
  • C [Battle](https://codeforces.com/gym/104385/problem/C)
    • 题面解读
    • 参考代码

L Zhang Fei Threading Needles - Thick with Fine

签到题

题面解读

当时在场人数为N,其中夏侯杰被吓死了,其他人被吓跑了,请问张飞吓跑了的人数是多少?

输出N-1即可

参考代码

#include<bits/stdc++.h>
using namespace std;int main()
{ios::sync_with_stdio(0), cin.tie(0);int n; cin >> n;cout << n - 1;return 0;
}

A Drill Wood to Make Fire

签到题

题面解读

钻木取火与钻木的速度与力量有关,当速度与力量的乘积大于某个阈值的时候,能够钻木取火成功。提供阈值、力量、速度,问是否能够取火成功。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n, s, v;int main()
{ios::sync_with_stdio(0), cin.tie(0);int t; cin >> t;while(t--){cin >> n >> s >> v;if(s * v >= n) cout << "1\n";else cout << "0\n";}return 0;
}

B Wonderful Array

数学题

题面解读

给定一个长度为 k 的数组 a ,对于长度为 n 的数组 b
b i = { x , i = 0 b i − 1 + a i − 1 m o d k , 0 < i ≤ n b_{i}=\begin{cases}x,i=0\\ b_{i-1}+a_{i-1}\quad mod \quad k,0 <i\leq n\end{cases} bi={x,i=0bi1+ai1modk,0<in
找出 有多少个 i 使得 :
b i m o d m ≤ b i + 1 m o d m b_{i} \quad mod \quad m\leq b_{i+1}\quad mod \quad m bimodmbi+1modm
此处,由于 a[i] 大于 0,所以 b[i] 在不取模情况下一定是一个单调递增的。所以正向考虑满足题意的部分,直接顺序枚举会是一个 O(n) 的复杂度,题目限制 1s ,这样肯定超时。

那么,我们选择反向考虑,寻找能够使得 b[i] > b[i + 1] (取模后)的位置。由于对 m 取模,那么对于一个递增的数组,这个位置就应该每当数组递增超过 m 就出现一次。在整个b数组过程中,就应该有 b[n]/m 个。那么新的问题就是如何去计算 b[n] ?由于 数组 b 一直在对 k 取模,所以 数组 b 是一个周期性增减的,我们就不用去看整个数组b而是找其中一段。计算 数组b[n] 的办法详见代码。

最终答案的个数是 n - b[n]/m

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int K = 1e6 + 5;ll k, n, m, x;
ll arr[K];int main()
{ios::sync_with_stdio(0), cin.tie(0);cin >> k;for(int i = 0; i < k; ++i) cin >> arr[i];cin >> n >> m >> x;ll b = 0, cnt = 0;x = x % m;for(int i = 0; i < k; ++i) b += arr[i] % m;b = n / k * b + x;for(int i = 0; i < n % k; ++i) b += arr[i] % m;cout << n - b / m;return 0;
}

I Tree

异或

题面解读

一个 n 节点的树,结点连接的边有边权。执行 q 次操作:

  1. 对结点 x 到结点 y 的路径上每条边的边权异或 z
  2. 询问编号为 x 的结点的所有边的边权异或和。

此处,有个小的脑筋急转弯。比如,对于操作1,如果1-2-3这三个点按照这个顺序连接,当让1到3的路径上边权都异或上 w ,那么此时对于结点 2 ,它所连接的两个边的异或和是没有变化的:比如 1与2的边权为 3 ,2 与 3 的边权大小为 5,对结点 1 到结点 2 的路径上每条边的边权异或 2 ,对于结点2的边权异或和 3 ^ 5 ==> 3 ^ 2 ^ 5 ^ 2 == 3 ^ 5,因为对于一个数异或自己为0。

那么,操作1的修改只会对 x 和 y 有效。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, q, v[N];
int main()
{ios::sync_with_stdio(0), cin.tie(0);cin >> n >> q;for(int i = 1; i <= n - 1; ++i){int x, y, w;cin >> x >> y >> w;v[x] ^= w, v[y] ^= w;}while(q--){int op; cin >> op;if(op == 1){int x, y, z;cin >> x >> y >> z;v[x] ^= z, v[y] ^= z;}else{int x; cin >> x;cout << v[x] << '\n';}}return 0;
}

J Function

题面解读

给定多个一元二次函数,询问在某一点处的最小值是多少。

当给出一个一元二次函数的时候,我们就可以去通过这个函数去更新其他点上最小值是多少。而如果我们每给出一个函数,就去更新 1 ~ n 上所有点的话,最坏的时间复杂度就是 O(1e10),无法在1s 内跑完。

根据题目中 b b b 的数据范围肯定小于 1e5 ,那么当
( x − i ) 2 > b \left( x-i\right) ^{2} >b (xi)2>b
此时就不用再去维护这个最小值,因为肯定大于其他函数在这个位置上的最小值。

参考代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;ll arr[N], a, b;
int n, m;
int mxl = int(sqrt(1e5) + 0.5); // 向上取整,大概317void update(int x)
{arr[x] = min(arr[x], b);for(int i = x - 1, j = 1; i >= 1 && j <= mxl; ++j, --i)arr[i] = min(arr[i], j * j + b);for(int i = x + 1, j = 1; i <= n && j <= mxl; ++j, ++i)arr[i] = min(arr[i], j * j + b);
}int main()
{ios::sync_with_stdio(0), cin.tie(0);cin >> n;memset(arr, 0x3f, sizeof arr);for(int i = 1; i <= n; ++i){cin >> b;update(i);}cin >> m;for(int i = 1; i <= m; ++i){int op; cin >> op;if(op){cin >> a; cout << arr[a] << "\n";}else{cin >> a >> b;update(a);}}return 0;
}

K Split

题面解读

题目中给出了一个长度为 n n n 的非增序列。进行 m m m 次操作,分为两种:

操作0,给你一个 1 < x < n 1 <x <n 1<x<n ,使得 a x = a x + 1 + a x − 1 − a x a_{x}=a_{x+1}+a_{x-1}-a_{x} ax=ax+1+ax1ax

操作1,将序列分成 k k k 个小块,其中每个小块的最大值-最小值之和要最小,并且输出每个小块中最大值-最小值之和最小值。

对于操作1,随机挑选一段,结果为: a 1 − a i + a i + 1 − . . . − a j + a j + 1 − a n a_1 - a_i + a_{i+1} -... - a_j + a_{j+1} - a_n a1ai+ai+1...aj+aj+1an, 整理后得: a 1 − a n + a i + 1 − a i + a j + 1 − a j . . . a_1 - a_n + a_{i+1} - a_i + a_{j+1} - a_j ... a1an+ai+1ai+aj+1aj...。可以看出,前两项一定且大于0,后面每两项都是相邻两数之差且小于等于0(后一项-前一项)。因此,为了让最大值减最小值之和最小,我们挑选这个序列中最小的 k − 1 k-1 k1 个差就可以了。

对于操作0,对序列中某段 a x − 1 , a x , a x + 1 a_{x-1},a_x,a_{x+1} ax1,ax,ax+1,转变为 a x − 1 , a x + 1 + a x − 1 − a x , a x + 1 a_{x-1},a_{x+1}+a_{x-1}-a_{x},a_{x+1} ax1,ax+1+ax1ax,ax+1
对于初始情况,这一段的后一项-前一项为: a x − a x − 1 , a x + 1 − a x a_x - a_{x-1},a_{x+1}-a_x axax1,ax+1ax,改变之后为: a x − 1 − a x , a x − a x + 1 a_{x-1}-a{x},a_{x}-a_{x+1} ax1ax,axax+1。可见,这一波操作并没有对整个序列的差分造成什么影响。所以后续代码中也不会对操作0进行任何处理。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
int n, m;
ll a[N], b[N];int main()
{ios::sync_with_stdio(0), cin.tie(0);cin >> n;for(int i = 0; i < n; ++i) cin >> a[i];for(int i = 1; i < n; i++) b[i] = a[i] - a[i - 1]; // 计算上述后项与前项的差sort(b + 1, b + n); // 将差分结果排序for(int i = 1; i < n; i++) b[i] = b[i] + b[i - 1]; // 将排序完的结果计算前缀和,方便后续查询直接使用cin >> m;while(m--){int op, k;cin >> op >> k;if(op == 1) cout << a[0] - a[n - 1] + b[k - 1] << "\n"; // 只要选择前 K-1 项即可}return 0;
}

C Battle

题面解读

博弈论中一个经典的Nim游戏,为了补题,专门去看了一眼什么是公平组合游戏。虽然看了,感觉明白了但没完全明白,感兴趣的可以去看看大佬的博客,本蒟蒻还得再吸收理解几遍。
推荐参考理解的博客:算法学习笔记(51): SG函数 、公平组合游戏

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll p, ans;ll sg(ll x)
{if(x == p) return 2;if(x&1) return 1;return 0;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> p;for (int i = 0; i < n; i++){ll t;cin >> t;if (p & 1){if(t&1) ans ^= 1;else ans ^= 0;}else{ans ^= sg(t % (p + 1));}}if(ans) cout << "GOOD\n";else cout << "BAD\n";return 0;
}

这篇关于【XCPC笔记】2023 (ICPC) Jiangxi Provincial Contest——ABCIJKL 做题记录的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/878989

相关文章

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

Node.js学习记录(二)

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个