博客更新记录
2024-07-01
更新文章:关于linux(Ubuntu),调整了一些文章的优先级
2024-06-29
更新文章:关于Ubuntu->关于linux(Ubuntu)
2024-04-07
更新文章:18thZJCPC,19thZJCPC
2024-04-06
上传文章:17thZJCPC,18thZJCPC
2024-03-31
上传文章:2024年度第五届全国大学生算法设计与编程挑战赛(春季赛)更新文章:XCPC模板
2024-03-26
上传文章:2022SHCPC,2023JSCPC;更新文章:hexo-github个人网站开发;添加文章置顶功能
2024-03-16
上传文章:13thSDCPC,整除分块
2024-03-11
更新文章:XCPC模板
2024-03-04
上传文章:【LGR-174-Div-2】T2、T3
2024-02-26
更新文章trick
2024-02-15
上传文章:ICPC2023-HangZhou R 签到+铜牌题,更新文章:2023ICPC杭州站打铁游记,hexo+github个人网站开发
2024-02-13
上传文章:01字典 ...
XCPC模板
DSU12345678910111213141516171819202122232425262728#define N 200005struct DSU { int n; vector<int> par, h; explicit DSU(int _n) : n(_n + 1), par(_n + 1), h(_n + 1) { for (int i = 1; i <= _n; ++i)par[i] = i; }; int find(int x) { return par[x] != x ? par[x] = find(par[x]) : par[x]; } void unite(int x, int y) { x = find(x); y = find(y); if (x == y)return; if (h[x] == h[y]) { h[x]++; ...
trick
本文用来记录一些做题时看到的小技巧以及踩过的坑
技巧
bool可以直接作为参数传递:1234567891011bool f(int i,int j,int m,int n,int next){ if(next>=8){ s[i][j]=1; return 1; } if(a[i+m][j+n]==k[next]) if(f(i+m,j+n,m,n,next+1)){ s[i][j]=1; return 1; } return 0;
清除缓冲区printf(“字符串”);后面加fflush(stdout);cout使用endl。
bool类型可以用bitset代替C++ bitset用法_牛客博客
递归可以实现倒序十进制转二进制输出123456 int r; r = num%2; if(num>=2) toBin(num/2); if(r) cout<<1; else cout<<0;}使用递归解决了倒取余数的问题而递 ...
18thZJCPC
A - League of Legends格莱美喜欢玩世界著名的英雄联盟游戏。在最新版本中,有一个特殊的规则供玩家选择玩。根据此规则, 10 玩家将被分为红队和蓝队。每支队伍由 5 名玩家组成,每个玩家都有一个初始生命值。如果一支队伍中的所有 5 玩家均没有正HP值,则该队伍将输掉这场比赛。每回合,队伍可以选择一名球员并减少他的生命值 1。蓝队首先开始。现在格莱美想知道两支球队是否都按照最优策略比赛,哪支球队会赢得比赛。枚举,比大小,平局蓝队赢
C - Cube给你三维空间中的八个点,请检查它们是否可以组成一个立方体。立方体是正六面体,由六个正方形面包围,每个顶点有三个相交点。T≤100组数据。两两枚举点对之间的距离,根据对角线,体对角线,面对角线,棱的长度和数量关系判断。
123456789101112131415161718192021222324252627282930313233343536373839404142#include <bits/stdc++.h>using namespace std;int t,x[8],y[8],z[8];int main() ...
17thZJCPC
题面:
K - Killing the Brute-force 给定标程和暴力在 n = 1, 2, . . . , m 时的运行时间,找到最小 的 n 使得三倍标程时限可以卡掉暴力 。m很小没什么好讲的就一个遍历找到最小的即可
1234567891011void solve(){ int m; cin>>m; vector<int> a(m),b(m); for(int i = 0;i<m;++i) cin>>a[i]; for(int i = 0;i<m;++i) cin>>b[i]; for(int i = 0;i<m;++i) if(a[i]*3<b[i]) return cout<<i + 1<<endl,void(); cout<<-1<<endl;}
A - AD 2020 给一个日期的区间,问有多少个日期含有子串“202”的。2000.01.01 ≤ 日期 ≤ 9999.12.31参考题解给的是直接 ...
2024年度第五届全国大学生算法设计与编程挑战赛(春季赛)
H 密码是多少?注意字符串长度都是7样例1
1asdfghj
110210310410697115100
样例2
1qazxcdf
11209910010211397122
按题意模拟即可
1234567void solve() { string s; cin>>s; string t = s.substr(3) + s.substr(0,3); for(auto c : t) cout<<(int)c;}
A 送个分吧样例
12aba4
1b
对于给定的样例,前 4 简单的套题分别为:a、ab、aba、b,故答案为 b。对于 100%的数据,1≤∣_s_∣≤5000,1≤_k_≤5,保证答案存在。
就是在问你字典序第k小的子串s的范围决定了这道题最多只能是$O(n^2)$的复杂度。可以这样考虑,比如对于样例而言,前几个子串一定是a开头的,可以是a,ab,aba。那么猜想前面几个一定是字符串中出现的字典序最小的那个字符的某个后缀,比如最小的是a,第二小的是ab(第一个a后面长度为2的后缀),第三小的是aba(第一个a后面长度为3的后缀)。且 ...
2023JSCPC
这个也是当年的湖南全国邀请赛
I Elevator 电梯里有 n 个人(你是其中一个),这些人想去 m 个楼层, 每个人只想去一个楼层。到达一个楼层,所有想去这个楼层 的人都会下电梯。问在你想去的楼层最多有多少人下电梯。
vp的时候题目根本没读懂,感觉就是输出 n − (m − 1) , 交了一发就过了……
J Similarity (Easy Version) 给定 n 个串,求两两之间最长公共子串的最大值。多测T不超过15,字符串长度不超过50,个数也不超过50。并保证n的总和不会超过300。直接暴力匹配即可。
12345678910111213141516171819202122232425262728map<string,int>f;void solve(){ int n; cin>>n; per(i,1,n){ string s; cin>>s; map<string,bool>vis; per(j,0,s.length()-1) ...
2022SHCPC
N Nine Is Greater Than Ten按字典序比较字符串
12345678910void solve(){ string a,b; cin>>a>>b; int res = a.compare(b); if(res == 0){ cout<<a<<'='<<b<<endl; }else if(res < 0){ cout<<a<<'<'<<b<<endl; }else cout<<a<<'>'<<b<<endl;}
G Gua!题意:给你四个参数B R D S,表示枪的一发子弹造成的最大伤害,射速为每分钟射击R次,玩家一共造成了D点伤害,用时S秒,问你这个人是不是挂。不是很懂为什么签到题出这么细节的模拟……vp爆wa心态都炸了三个细节,第一个是由于时间是从0开始算的, ...
整除分块
好像只能用来解决一个类似于$\sum^n_{i = 1}\left \lfloor \frac{n}{i} \right \rfloor$这样的整数求和问题,只要是带这个的,那么复杂度最低就能降到根号级别的。可以发现,比如n = 8这个求和的每一项是这样的
i
1
2
3
4
5
6
7
8
8/i
8
4
2
2
1
1
1
1
那么就可以优化,把结果一样的放在一起分块处理。分的块大概有$2\sqrt{n}$个,因为当i小于等于$\sqrt{n}$时,取值一共有$\sqrt{n}$种,大于也是一样的
12345for (int l = 1; l <= n; ++l) { int d = n / l, r = n/d; ans += (r-l+1)*d; l = r;}
l和r表示这个区间内的数x除n都是d,即n/x = d,累加即可,复杂度是根号的。
[CQOI2007] 余数求和给出正整数 $n$ 和 $k$,请计算$G(n, k) = \sum_{i = 1}^n k \bmod i$其中 $k\bmod i$ 表示 $k$ ...
13thSDCPC
vp打到后面打不动了,好在压线银牌。
[SDCPC2023] Matching给定长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$,我们将从该序列中构造出一张无向图 $G$。具体来说,对于所有 $1 \le i < j \le n$,若 $i - j = a_i - a_j$,则 $G$ 中将存在一条连接节点 $i$ 与 $j$ 的无向边,其边权为 $(a_i + a_j)$。求 $G$ 的一个匹配,使得该匹配中所有边的边权之和最大,并输出最大边权之和。请回忆:无向图的匹配,指的是从该无向图中选出一些边,使得任意两条边都没有公共的节点。特别地,不选任何边也是一个匹配。
考了个常见的转化:$i - j = a_i - a_j$改为$i - a_i = j - a_j$然后把权值一样的放在一起就行。可以开一个map<int,vector<int>>来存储,并且注意到后面压进去的一定是a比较大的,所以从后往前遍历如果两两配对就能找到最大的。
123456789101112131415void solve() { int n; ...