并查集板子 #include<bits/stdc++.h> using namespace std; int s[10001]; void init_set() { for(int i=1;i<=10001;i++) s[i]=i; } //路径压缩（递归） int find_set(int x) { if(x!=s[x]) s[x]=find_set(s[x]); return s[x]; } void union_set(int x,int y) { x=find_set(x); y=find_set(y); if(x!=y)s[x]=s[y]; } //非递归 int ...

小红的素数合并 标签： 贪心 数学 难度： 适中 思路： 先排序，偶数情况，将最小的和最大的相乘，将倒数第二小和倒数第二大相乘，以此类推，因为偶数最后全需操作为素数。 奇数情况，需舍弃最后一个最大的，然后按偶数处理。 证明：  示例： #include<bits/stdc++.h> using namespace std; #define rep(i,a,n) for(int i=a;i<=n;i++) typedef long long ll; const int N=100010; ll n,a[N]; int main() { cin>>n; rep(i,1...

*** 标签： 数学 难度: 中等 思路： 数学期望，求出方案数，除以总数就是概率，再乘上权值，就是在处理分数取模时要使用逆元。 示例: #include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,a,n) for(int i=a;i<=n;i++) #define MOD 998244353 ll qp(ll a,ll b,ll mod) { ll ans=1; while(b) { if(b&1)ans=ans*a%MOD; a=a*a%MOD; b>&gt...

交换数字 标签: 数学 结论 难度: 适中 思路： 结论题，当a+b为定值时，a和b越接近，即|a-b越小，a*b越大，这题就反其道而行之，使|a-b|最大，两个数乘积就越小。 技巧： 当一个数很大时，用字符串存储转为整型时，可以边乘10，边模。 示例： #include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,a,n) for(int i=a;i<=n;i++) #define MOD 998244353 const int N=200010; int n; char a...

生不逢七 标签： 模拟 数学 难度： 一般 思路： 枚举k-1轮循环，第一次是在上一个后面，因此枚举k-1轮循环，每轮加n即可。 技巧： 当判断一个数是否含有某个数字时，可以用循环求余的方法实现。 示例：  #include<bits/stdc++.h> using namespace std; int T,n,k,a; int main() { cin>>T; while(T--) { cin>>n>>a>>k; for(int i=a+1;i<=a+1+(k-1)*n;i+=n) { int h=i,f=0; while(h...

牛牛取石子 标签： 博弈论 对称棋 难度： 适中 思路： 不难发现，两种策略2+1和1+2，加起来和为3+3，只要先手先出，后手选择相反的策略，最小堆如果是3的倍数，则先手必输。如果不是3的倍数，则先手可以使后手处于3倍数状态即后手必输状态，但这些是基于最小堆一直不变的情况，当在拿石子过程中，最小堆如果变化，即模3为1，且a==b时，后手可以使先手落败，比如4 4时。 示例： #include<bits/stdc++.h> using namespace std; typedef long long ll; ll a,b,T; void xian() { puts("niuniu"...

牛牛排队伍 标签： 双向链表 难度： 适中 思路： 因为按从小到大顺序排队，因此，只需两个数组pre[]和ne[]维护该位置之前和之后排的人即可。 技巧： 竞赛中链表可用数组实现，无需再创建结构体，再分配空间，销毁空间等一系列操作。 示例1： #include <bits/stdc++.h> using namespace std; const int N=1e6+10; int pre[N],ne[N],data[N]; int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n,k,opt,x; ...

小红的循环移位 标签： 字符串 大数 循环 难度： 适中 思路： 考察一个数是否为4的倍数，只需考查该数后两位是否是4的倍数即可（个位数特判），对于循环移位，只需考察移动n-1次即可，只要碰到符合条件就终止，将数存为字符串，栽想象成一个环，然后处理这个环即可。 示例： #include<bits/stdc++.h> using namespace std; string s; int main() { cin>>s; int n=s.length(),i; for(i=-1;i<n-1;i++) { int tmp=0; tmp+=s[(n+i)%n]-'0'; ...

小红的排列构造 标签： 模拟 构造 难度: 一般 思路： 将数组的前n-k位输出，将n-k+2位向后到n位先输出，最后输出n-k+1位，就能保证汉明距离为k了，并且需要特判k==1和k>n，在这两种情况下，无解。 示例: #include<bits/stdc++.h> using namespace std; const int N =100010; int n,k; int a[N],b[N]; int main() { cin>>n>>k; if(k==1||k>n) return cout<<-1,0; for(int i=1;...

Bingbong的奇偶世界 标签： 字符串 动态规划，dp 难度： 较难 思路： 因为前导不为0，还要求为偶数，那只需限制第一个数不为0，末尾的数为偶数。 可以设置一个dp[][3]数组，dp[i][1] 用于记录前i个数，形式为[1-9]xxx 子序列的个数； dp[i][2] 用于记录前i个数，形式为[1-9]xxx[02468]子序列的个数。 处理时，发现一位的时候，第一位和最后一位重合，需特判，不然麻烦。 两位以上时：   首先，继承上一位状态 dp[i][j]=dp[i-1][j]。   其次，当前状态加上上一位状态。   然后，第i位如果是偶数，dp[i][2]就能更新,dp[i]...

Bingbong的蛋仔世界 标签： 结论 难度： 适中 思路： 判断每个蛋仔能否在被淹没之前进入安全板块，只需比较到达时间t和完全淹没时间time即（t <= time）。如果中途被淹没，那这只蛋仔在到达也还是被淹没，也符合结论，因为淹没速度 >= 蛋仔走的速度。 示例： #include<bits/stdc++.h> using namespace std; int n,m,k,x,y; int ans=0; int main() { cin>>n>>m>>k; int time=max(n/2,m/2); while(k--) {...

统一命名规范 标签: 字符串 集合 难度: 适中 思路: 先根据命名规则将单词划分出来，然后再根据命名规则重新命名。 如果只有一个单词，Camel 和 Snake 的写法一致，而 Pascal 首字母大写。 如果但系数量很多， Camel 和 Pascal 根据后面的大写字母划分单词，Snake 则根据后面的下划线划分单词。 #include<bits/stdc++.h> using namespace std; int n; string type; //获取单词 vector<string> GetWords(const string &str) { vec...

预测帕鲁 标签： 数学 难度： 2颗星 思路： 先计算出子代帕鲁的繁育值，将上去整转换为下去整，也可以用ceil()函数上去整。然后从左到右遍历找到繁育值 和子代差值最小的帕鲁即可，需要注意差值相同的情况应该取下标校的帕鲁。 示例： #include <bits/stdc++.h> using namespace std; const int N=510; vector<int>p(N+1); int n,x,y; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>p[i]; cin>&g...

记忆数字 标签： 字符串 难度： 2颗星 思路： 遍历字符串，维护单词长度 len，如果是当前字符是字母就让len++，否则检查一下len是否为0，如果为0则直接输出len % 10并重置len。 技巧： 使用 isalpha() 函数判断字符是不是字母，输入使用getline(cin,str)。 注： 结尾要加一个判断，防止末尾没有不是字母的符号，最后一个单词输出不了。 示例： #include<bits/stdc++.h> using namespace std; int main() { string str; getline(cin, str); int len = 0; ...