2024/03/24 周一
合根植物
题目链接
【参考代码】
#include <iostream>
using namespace std;const int N = 1e6+1;
int a[N];int find(int index)
{if(a[index] == index)return index;return a[index] = find(a[index]);
}int main()
{// 请在此输入您的代码int m, n;cin>>m>>n;int capacity = m*n;for(int i=1; i<=capacity; i++){a[i] = i;}int operation;cin>>operation;for(int i=0; i<operation; i++){int x1, x2, boss1, boss2;cin>>x1>>x2;boss1 = find(x1);boss2 = find(x2);if(boss1 != boss2)a[boss1] = boss2;}int result = 0;for(int i=1; i<=capacity; i++){if(a[i] == i)result++;}cout << result << endl;return 0;
}二进制王国【3.23算法赛补题】
题目链接
【参考代码】
20%样例
#include <bits/stdc++.h>
using namespace std;int main()
{// 20%通过map<string, int> mp;int n;cin>>n;for(int i=0;i<n;i++){string s = "";int cnt = 0;cin>>s;for(int j=0;j<s.size();j++){cnt += s[j];}mp[s] = cnt;}for(map<string, int>::iterator it = mp.begin(); it != mp.end(); it++){cout << (*it).first ;}return 0;
}100%样例
我靠这么简单!
#include <bits/stdc++.h>
using namespace std;const int N = 2e5;
string s[N];bool compare(string a, string b)
{return a + b < b + a;
}int main()
{//我靠这么简单!int n;cin>>n;for(int i=0;i<n;i++){cin>>s[i];}sort(s, s+n, compare);for(int i=0;i<n;i++){cout << s[i];}
}2024/03/27 周三
修改数组
题目链接
【参考代码】
hash做法
#include <bits/stdc++.h>
using namespace std;const int N = 1e6;int main()
{// hash做法int n;int hash[N];cin>>n;for(int i=0;i<n;i++){int x;cin>>x;while(hash[x]) //重复数字{hash[x]++;x += hash[x]-1;}hash[x]++;cout << x << ' ';}return 0;
}使用并查集的做法，说实话真的做的时候思路比较难联系到并查集
并查集思路：
1.初始化并查集
2.对于每一个元素
*如果不属于并查集,那么输出该元素,找祖先元素其实就是初始化的自己,同时指向祖先节点x+1即最大
未使用的数字
*如果属于并查集,直接在集合中找到祖先节点,即当前数字应该替换的最大元素,直接输出就是答案
3.技巧
3.1 并查集维护当前最大未使用的元素,对于重复元素查找祖先元素即可快速实现降重
4.时间复杂度O(N+M)
【参考代码】
/*
1.初始化并查集
2.对于每一个元素
*如果不属于并查集,那么输出该元素,找祖先元素其实就是初始化的自己,同时指向祖先节点x+1即最大
未使用的数字
*如果属于并查集,直接在集合中找到祖先节点,即当前数字应该替换的最大元素,直接输出就是答案
3.技巧
3.1 并查集维护当前最大未使用的元素,对于重复元素查找祖先元素即可快速实现降重
4.时间复杂度O(N+M)
*/
#include<bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int fa[N]; //并查集存储当前 “节点族” 最大还有哪个节点未用上
int n;int find(int x)
{if(fa[x] != x) fa[x] = find(fa[x]); //向上查找祖先节点，同时进行 “路经压缩“return fa[x]; //返回最大的可以用的节点
}int main()
{cin >> n;//1.初始化并查集for(int i = 0; i<N; i++) //注意此时，并查集初始化取决于数组中元素A的大小Nfa[i] = i;//2.对于每个节点，加入并查集，更新最大未使用的元素int x;for(int i = 0; i<n; i++){scanf("%d", &x);x = find(x); //找到当前最大未使用的元素printf("%d ", x);fa[x] = x + 1; //当前节点已经用过了 -> 往后偏移 -//如果是最新的，那么会直接输出当前元素，反之，输出之前记录的可以使用的最大元素}return 0;
}2024/03/28 周四
更小的数
题目链接
【参考代码】
40%样例通过，原因超时。
#include <bits/stdc++.h>
using namespace std;int main()
{// 40%通过，超时了int ans = 0;string s;cin>>s;for(int i=0;i<s.size();i++){for(int j=i+1; j<s.size(); j++){string temporary = s;reverse(temporary.begin()+i, temporary.begin()+j+1);//为什么要加1，因为右区间不包含if(temporary < s)ans++;}}cout << ans << endl;return 0;
}100%通过，罗勇军老师博客代码结果有误
#include <bits/stdc++.h>
using namespace std;对于每个子串，比较它的首尾字符s[i]和s[j]，得到状态转移方程。（1）若s[i] > s[j]，说明反转后的子串肯定小于原子串，符合要求，赋值dp[i][j] = 1。（2）若s[i] < s[j]，说明反转后的子串肯定大于原子串，赋值dp[i][j] = 0。（3）若s[i] = s[j]，需要继续比较s[i+1]和s[j-1]，有dp[i][j] = dp[i+1][j-1]。int f[5001][5001];int main()
{int ans = 0;string s;cin>>s;for(int len=2; len<=s.size(); len++){for(int l=0; l+len-1<s.size(); l++){int r = l+len-1;if(s[l] < s[r])f[l][r] = 0; if(s[l] > s[r])f[l][r] = 1;if(s[l] == s[r]) f[l][r] = f[l+1][r-1]; if(f[l][r] == 1)ans++;}}cout << ans << endl;
}
