2023牛客寒假算法基础集训营2

news/2024/11/8 22:46:53/

目录

  • C Tokitsukaze and a+b=n (hard)
  • E Tokitsukaze and Function
  • F Tokitsukaze and Gold Coins (easy)
  • H Tokitsukaze and K-Sequence
  • L Tokitsukaze and Three Integers

C Tokitsukaze and a+b=n (hard)

思路：

  • 差分 + 算贡献
  • 每个位置被几条线段覆盖，直接返回c[i] * c[n - i] - o(i == j)的情况即可，其中所有的位置的相同的线段可以利用该题的medium难度的结论预处理出，res - s即为最终答案。

代码如下：

// Time:	2023-01-19 21:19:40
// Problem: Tokitsukaze and a+b=n (hard)
// Contest: NowCoder
// URL: 	https://ac.nowcoder.com/acm/contest/46810/C
// Memory Limit: 	524288 MB
// Time Limit: 		4000 ms#include <algorithm>
#include <iostream>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <string>
#include <bitset>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>#define fast ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)#define mkpr make_pair
#define endl '\n'
#define x first
#define y second
#define y1 Y1
// #define int long longusing namespace std;typedef long long LL;
typedef pair<int, int> PII;const int mod = 998244353;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;const int N = 4e5 + 10, M = 2e5 + 10;LL gcd(LL a,LL b){return b ? gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}int T = 1, cases = 1;
int n, m, times;int s;
int diff[N];void solve()
{scanf("%d%d", &n, &m);for (int i = 1; i <= m; i ++ ){int l, r;scanf("%d%d", &l, &r);diff[l] += 1;diff[r + 1] -= 1;s = ((LL)s + max(min(r, n - l) - max(l, n - r) + 1, 0)) % mod;}for (int i = 1; i <= n; i ++ )diff[i] += diff[i - 1];int res = 0;for (int i = 1; i <= n; i ++ )res = ((LL)res + (LL)diff[i] * diff[n - i]) % mod;printf("%d\n", ((LL)res - s + mod) % mod);return;
}signed main()
{//fast;//cin >> T;// scanf("%d", &T);while(T -- )solve();return 0;
}

E Tokitsukaze and Function

思路：

  • 基本不等式（对勾函数） + 二分

代码如下：

// Time:	2023-01-20 12:19:38
// Problem: Tokitsukaze and Function
// Contest: NowCoder
// URL: 	https://ac.nowcoder.com/acm/contest/46810/E
// Memory Limit: 	524288 MB
// Time Limit: 		4000 ms#include <algorithm>
#include <iostream>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <string>
#include <bitset>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>#define fast ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)#define mkpr make_pair
#define endl '\n'
#define x first
#define y second
#define y1 Y1
// #define int long longusing namespace std;typedef long long LL;
typedef pair<int, int> PII;const int mod = 998244353;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;const int N = 2e5 + 10, M = N * 2;LL gcd(LL a,LL b){return b ? gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}int T = 1, cases = 1;
// int n, m, times;
LL n;LL f(LL x)
{if (x == 0) return 5e18;return n / x + x - 1;
}void solve()
{LL l1, r1;scanf("%lld%lld%lld", &n, &l1, &r1);LL t = (LL)sqrt(n);while (t * t < n) t ++ ;if (t < r1 && f(t) > f(t + 1)){cout << t + 1 << endl;return;}t = min(t, r1);LL l = l1, r = t;while (l < r){LL mid = l + r >> 1;if (f(mid) == f(t)) r = mid;else l = mid + 1;}cout << l << endl;return;
}signed main()
{//fast;//cin >> T;scanf("%d", &T);while(T -- )solve();return 0;
}

F Tokitsukaze and Gold Coins (easy)

思路：

  • 两次dfs

代码如下：

// Time:	2023-01-19 20:47:36
// Problem: Tokitsukaze and Gold Coins (easy)
// Contest: NowCoder
// URL: 	https://ac.nowcoder.com/acm/contest/46810/F
// Memory Limit: 	524288 MB
// Time Limit: 		6000 ms#include <algorithm>
#include <iostream>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <string>
#include <bitset>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>#define fast ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)#define mkpr make_pair
#define endl '\n'
#define x first
#define y second
#define y1 Y1
// #define int long longusing namespace std;typedef long long LL;
typedef pair<int, int> PII;const int mod = 998244353;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;const int N = 5e5 + 10, M = N * 2;LL gcd(LL a,LL b){return b ? gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}int T = 1, cases = 1;
int n, m, times;int g[N][4];
bool m1[N][4], m2[N][4];int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};void dfs(int x, int y, int f)
{if (f == 0) m1[x][y] = true;else m2[x][y] = true;for (int i = 0; i < 4; i ++ ){if (f == 0 && (i == 0 || i == 3) || f && (i == 1 || i == 2)) continue;int a = x + dx[i], b = y + dy[i];if (a < 1 || a > n || b < 0 || b > 3 || g[a][b]) continue;if (f == 0 && m1[a][b]) continue;if (f == 1 && m2[a][b]) continue;dfs(a, b, f);}
}void solve()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= 3; j ++ )g[i][j] = m1[i][j] = m2[i][j] = 0;while (m -- ){int x, y;scanf("%d%d", &x, &y);g[x][y] ^= 1;}dfs(1, 1, 0);dfs(n, 3, 1);int res = 0;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= 3; j ++ ){if (i == 1 && j == 1) continue;if (m1[i][j] && m2[i][j])res ++ ;}cout << res << endl;return;
}signed main()
{//fast;//cin >> T;scanf("%d", &T);while(T -- )solve();return 0;
}

H Tokitsukaze and K-Sequence

思路：

  • 单独算贡献

注： 也可用两个数组算小于大于k的贡献

代码如下：

// Time:	2023-01-19 19:27:41
// Problem: Tokitsukaze and K-Sequence
// Contest: NowCoder
// URL: 	https://ac.nowcoder.com/acm/contest/46810/H
// Memory Limit: 	524288 MB
// Time Limit: 		4000 ms#include <algorithm>
#include <iostream>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <string>
#include <bitset>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>#define fast ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)#define mkpr make_pair
#define endl '\n'
#define x first
#define y second
#define y1 Y1
// #define int long longusing namespace std;typedef long long LL;
typedef pair<int, int> PII;const int mod = 998244353;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;const int N = 1e5 + 10, M = N * 2;LL gcd(LL a,LL b){return b ? gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}int T = 1, cases = 1;
int n, m, times;void solve()
{cin >> n;map<int, int> mp, cnt;for (int i = 1; i <= n; i ++ ){int x;cin >> x;mp[x] ++ ;}// 极限只有100项for (auto it : mp)cnt[it.y] ++;int res[N] = {0};// 看似两重循环，其实时间复杂度最多才1e7for (int i = 1; i <= n; i ++ ){for (auto it : cnt)if (it.x <= i) res[i] += it.x * it.y;else res[i] += (i - 1) * it.y;}for (int i = 1; i <= n; i ++ )cout << res[i] << endl;return;
}signed main()
{fast;cin >> T;//scanf("%d", &T);while(T -- )solve();return 0;
}

L Tokitsukaze and Three Integers

思路：

  • 预处理

代码如下：

// Time:	2023-01-19 19:22:51
// Problem: Tokitsukaze and Three Integers
// Contest: NowCoder
// URL: 	https://ac.nowcoder.com/acm/contest/46810/L
// Memory Limit: 	524288 MB
// Time Limit: 		4000 ms#include <algorithm>
#include <iostream>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <string>
#include <bitset>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>#define fast ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)#define mkpr make_pair
#define endl '\n'
#define x first
#define y second
#define y1 Y1
// #define int long longusing namespace std;typedef long long LL;
typedef pair<int, int> PII;const int mod = 998244353;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;const int N = 5010, M = N * 2;LL gcd(LL a,LL b){return b ? gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}int T = 1, cases = 1;
int n, m, times;LL a[N];
LL c[N];
LL d[N][N];void solve()
{int p;scanf("%d %d", &n, &p);for (int i = 1; i <= n; i ++ )scanf("%lld", &a[i]), a[i] %= p;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ ){if (i == j) continue;int mult = a[i] * a[j] % p;c[mult] ++ ;d[i][mult] += 2;}for (int x = 0; x <= p - 1; x ++ ){LL res = 0;for (int k = 1; k <= n; k ++ ){int t = (x - a[k] + p) % p;res += c[t] - d[k][t];}cout << res << ' ';}cout << endl;return;
}signed main()
{// fast;//cin >> T;//scanf("%d", &T);while(T -- )solve();return 0;
}

http://www.ppmy.cn/news/18448.html

相关文章

2023年网络安全比赛--Linux渗透测试中职组（超详细）

2023年网络安全比赛--Linux渗透测试中职组（超详细）

一、竞赛时间 180分钟 共计3小时 二、竞赛阶段 1.通过本地PC中渗透测试平台Kali对靶机场景进行系统服务及版本扫描渗透测试，并将该操作显示结果中Apache服务对应的版本信息字符串作为Flag值提交； 2.通过本地PC中渗透测试平台Kali对靶机场景进行渗透测试，将该场景/var/www/ht…
阅读更多...
Linux常用命令——tar命令

Linux常用命令——tar命令

在线Linux命令查询工具(http://www.lzltool.com/LinuxCommand) tar Linux下的归档使用工具&#xff0c;用来打包和备份。 补充说明 tar命令可以为linux的文件和目录创建档案。利用tar&#xff0c;可以为某一特定文件创建档案&#xff08;备份文件&#xff09;&#xff0c;也…
阅读更多...
基于EasyExcel实现百万级数据导入导出

基于EasyExcel实现百万级数据导入导出

基于EasyExcel实现百万级数据导入导出 在项目开发中往往需要使用到数据的导入和导出&#xff0c;导入就是从Excel中导入到DB中,而导出就是从DB中查询数据然后使用POI写到Excel上。 大数据的导入和导出&#xff0c;相信大家在日常的开发、面试中都会遇到。 很多问题只要这一次…
阅读更多...
免费开题报告|基于SpringBoot+Vue的校内跑腿平台

免费开题报告|基于SpringBoot+Vue的校内跑腿平台

作者主页&#xff1a;编程指南针 作者简介&#xff1a;Java领域优质创作者、CSDN博客专家 、掘金特邀作者、多年架构师设计经验、腾讯课堂常驻讲师 主要内容&#xff1a;Java项目、毕业设计、简历模板、学习资料、面试题库、技术互助 收藏点赞不迷路 关注作者有好处 文末获取源…
阅读更多...
新书预告：人机环境系统智能

新书预告：人机环境系统智能

东方算计&#xff1a;象者&#xff0c;像也西方计算&#xff1a;逻辑 or 实证人工智能是数学物理的产物&#xff0c;而数学是不完备的&#xff0c;物理仍是在探索中&#xff0c;所以人工智能存在着先天不足&#xff0c;有着大量的脆弱和缺点&#xff0c;具体而言&#xff0c;包…
阅读更多...
Linux基本功系列之ping命令实战

Linux基本功系列之ping命令实战

文章目录一. 命令介绍二. 语法格式及常用选项三. 参考案例3.1 测试本机与指定网站服务器之间的网络连通性3.2 指定ping的次数3.3 指定时间间隔和次数3.4 设置TTL为2553.5 极快速的测试使用大包ping四. 使用ping命令常见问题总结前言&#x1f680;&#x1f680;&#x1f680; 想…
阅读更多...
7、矩阵的创建

7、矩阵的创建

目录 一、希尔伯特&#xff08;Hilbert&#xff09;矩阵 二、托普利兹&#xff08;Toeplitz&#xff09;矩阵 三、0&#xff5e;1间均匀分布的随机矩阵 四、标准正态分布随机矩阵 五、魔方矩阵 六、帕斯卡矩阵 七、范德蒙&#xff08;Vandermonde&#xff09;矩阵 MATLA…
阅读更多...
Python小技巧：if __name__ == “__main__“ 的作用

Python小技巧：if __name__ == “__main__“ 的作用

前言 这里是Python小技巧的系列文章。这是第一篇&#xff0c;if __name__ "__main__" 的作用。 在编写Python程序时候&#xff0c;总是习惯性的在文件的末尾添加这么一段代码。 if __name__ "__main__":...至于它的作用是什么&#xff0c;先不管&#x…
阅读更多...
最新文章

Copyright @ 2022~2023