------------恢复内容开始------------
CF思维题心得&总结
created: 10/18/2021
updated: 10/20/2021
1583B Omkar and Heavenly Tree
题意
t组数据，n个点，m条限制，每条限制输入a、b、c，要求建立的树在a和c之间只有一条路径并且b不在这条路径上。
答案输出树的每条边相邻两点。
思路点
通过观察数据范围m < n，得出一定有一个点没有被限制，然后以这个点为中心连一个树就可以，输出每一条边。
赛中想到的
以一个点为中心连边，每次将不同的点塞在b的两侧，达到了第一层，正解在第n层
Solution
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
// 从点和边的数据范围中观察出技巧
int main(){
int T;
scanf("%d", &T);
while(T--){
int n, m;
scanf("%d%d", &n, &m);
map<int, int> mp;
for(int i = 0; i < m; i++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
mp[b] ++;
}
int center = 0;
for(int i = 1; i <= n; i++){
if(!mp.count(i)){
center = i;
break;
}
}
for(int i = 1; i <= n; i++){
if(center == i)
continue;
printf("%d %d\n", i, center);
}
}
return 0;
}
1594C Make Them Equal
题意
\(t\)组数据，输入长度为\(n\)的字符串\(s\)和一个字符\(c\)，可以进行一个操作，对于\(1≤x≤n\),可以将不能整除\(x\)的\(i(1≤i≤n)\),所在的下标字符替换成\(c\)，问最少经过多少次操作可以使\(s\)每个字符都是\(c\)？
思路点
- 由整除出发，
- 对于\(x=n\)而言，\(1≤i≤n-1\)都可以被替换。
- 对于\(x=n-1而言\)，\(i=n\)可以被替换。
- 因此最多需要2次操作就可以将\(s\)替换成想要的字符串。
- 对于做0次操作，遍历数组就行。
- 对于做1次操作，当数组中\(\exists i<n\)，\(i\)及\(i\)的倍数下标位置的字符都是\(c\)的话，只需要一次操作就可以把\(s\)都替换成\(c\)，输出\(i\)的下标。
- 对于做2次操作，就是\(\nexists i<n\)，\(i\)及\(i\)的倍数下标位置的字符都是\(c\)，输出\(n-1\)和\(n\)。
赛中想到的
上述的第一点想到了，但是忽略了做1次操作的做法，也是这道题的核心，由第1点衍生出，\(i\)可以替换不是它倍数的下标位置（其实就是题意)。我太蠢了
Solution
#include<iostream>
#include<cstring>
using namespace std;
int main(){
int T;
scanf("%d", &T);
while(T--){
int n;
char c;
string s;
cin >> n >> c;
cin >> s;
bool flag = true;
for(int i = 0; i < n; i++){
if(s[i] != c){
flag = false;
break;
}
}
if(flag){
printf("0\n");
continue;
}
bool f = false;
for(int i = 1; i <= n; i++){
flag = true;
for(int j = i; j <= n; j += i){
if(s[j - 1] != c){
flag = false;
break;
}
}
if(flag){
f = true;
printf("1\n%d\n", i);
break;
}
}
if(!f){ // 1-n-1不存在能代替所有字符的位置
printf("2\n%d %d\n", n - 1, n);
}
}
return 0;
}
1593D2 Hall of Same
题意
D1的加强版，赛中过了，这里就不再单独将D1列出来。D1题意是输入一个数组 $a(-1e6≤a_i≤1e6) \(，\)n\(个元素\)(4≤n≤40,n为偶数)$求出一个最大的整数 \(k\)，对每个元素减去若干个 \(k\) 之后，\(a\)中所有元素相同。
此题（D2）的题意与D1大致相同，但求一个最大的 \(k\)，使得数组中至少一半的元素能够相同。
思路点
- 两道题答案所包含的元素组成的子数组中，设最小值为 \(v\)，不难发现，其他元素与\(v\)的差值（设为\(d\) )一定都对\(\%k\) 同余。（
应该这么表示吧?） - 由上一点可知，\(k\) 一定是所有 \(d\) 的最大公约数。
- D1可以求出最小元素 \(v\)，再求其他元素相应的 \(d\)，D2需要观察数据范围，采用暴力枚举所有元素为 \(v\)，再筛选出其他满足条件的 \(d≥0\)，存取所有 \(d\) 的约数，找出大于等于 \(\frac{n}{2}\) 的最大的那个。
赛中想到的
所有 \(d\%k\) 同余想到了，还是没深入思考到 \(k\) 一定是所有 \(d\) 的最大公约数。
Solution
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int main(){
int T;
scanf("%d", &T);
while(T--){
int n;
scanf("%d", &n);
int a[45];
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int ans = -1;
for(int i = 1; i <= n; i++){
int v = a[i];
vector<int> nums;
int same = 0;
for(int j = 1; j <= n; j++){
int d = a[j] - v;
if(d == 0) same++;
if(d > 0) nums.push_back(d);
}
if(same >= n / 2){
ans = INT_MAX;
continue;
}
map<int, int> s;
for(int j = 0; j < nums.size(); j++){
int & d = nums[j];
for(int g = 1; g <= d / g; g++){
if(d % g == 0){
s[g]++;
if(d / g != g)
s[d / g]++;
}
}
}
for(auto t: s){
if(t.second >= n / 2 - same){
ans = max(ans, t.first);
}
}
}
if(ans == INT_MAX)
ans = -1;
printf("%d\n", ans);
}
return 0;
}
1593B Make it Divisible by 25
题意
多测，输入数字 \(n(n ≤ 1e18)\)，每次可以对 \(n\) 进行操作，删去一位数字，使 \(n\) 可以整除 \(25\)， 求最少的操作次数 \(ans ≥ 0\)，数据保证一定有解。
思路点
- 一个数可以被 \(25\) 整除，其后个位和十位可以是 \(00、25、50、75\) 这四种情况，根据个位为 \(5\) 或 \(0\)，分类讨论就可以了(
这场ACD1E都做了，B居然没写)
赛中
脑子糊了
Solution
#include<iostream>
#include<cstring>
using namespace std;
int main(){
int T;
scanf("%d", &T);
while(T--){
string s;
cin >> s;
int n = s.size();
// 25 75
int ans1 = 0;
// 50 00
int ans2 = 0;
bool flag = false;
for(int i = s.size() - 1; i >= 0; i--){
if(s[i] != '5')
ans1++;
else{
for(int j = i - 1; j >= 0; j--){
if(s[j] == '2' || s[j] == '7'){
flag = true;
break;
}
else
ans1++;
}
}
if(flag)
break;
}
flag = false;
for(int i = s.size() - 1; i >= 0; i--){
if(s[i] != '0')
ans2++;
else{
for(int j = i - 1; j >= 0; j--){
if(s[j] == '0' || s[j] == '5'){
flag = true;
break;
}
else
ans2++;
}
}
if(flag)
break;
}
printf("%d\n", min(ans1, ans2));
}
return 0;
}
------------恢复内容结束------------