目录
A - Thermometer
翻译:
思路:
实现:
B - Ticket Gate Log
翻译:
思路:
实现:
C - Variety Split Easy
翻译:
思路:
实现:
D - Cubes
翻译:
思路:
实现:
A - Thermometer
翻译:
高桥测量了自己的体温,发现它是
。
体温分为以下几种:
- 高于或等于
:"高烧"
- 高于或等于
和低于
:"发烧"
- 低于
:"正常"
高桥的体温属于哪种分类?请根据输出部分以整数形式给出答案。
思路:
先判断>=38.0再判断<37.5,都不对输出发烧。可以写快点。
实现:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;void solve(){double n;cin>>n;if (n>=38){cout<<"1\n";}else if (n<37.5){cout<<"3\n";}else{cout<<"2\n";}
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数,不填默认// cout.precision();solve();return 0;
}
B - Ticket Gate Log
翻译:
高桥汇总了检票口的使用记录。但是,他不小心删除了一些进出站记录。他正试图恢复被删除的记录。
给你一个由 i 和 o 组成的字符串 S。我们想在 S 的任意位置插入 0 个或多个字符,这样得到的字符串就能满足以下条件:
- 它的长度是偶数,每个奇数(第 1、第 3......个)字符都是 i,而每个偶数(第 2、第 4......个)字符都是 o。
求需要插入的最少字符数。在此问题的约束条件下,可以证明通过插入适当数量的字符、 S 就能满足条件。
思路:
字符串 io 是没问题,无需改变的。那么删除这些没问题的后剩下都是要在前后插入的字符了,统计一下剩下字符串长度即可。
实现:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;void solve(){string s;cin>>s;int cnt = 0;for (int i=1;i<s.size();i++){if (s[i]=='o' && s[i-1]=='i') cnt++;}int n = s.size();cout<<n-2*cnt<<"\n";
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数,不填默认// cout.precision();solve();return 0;
}
C - Variety Split Easy
翻译:
给你一个长度为 N 的整数序列:
。
当把 A 在一个位置分割成两个非空(连续)子数组时,求这两个子数组中不同整数的计数之和的最大值。
更具体地说,对于整数 i,求以下两个值的最大和,使得 1≤i≤N-1:
中不同整数的数量,和
中不同整数的数量。
思路:
前后缀分解,倒序遍历设立一个数组suffix,suffix[i]为[ i : n ]中A的不同整数数量。之后正序遍历求出以每个为分割点得到的和,比较下。
实现:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 3e5+10;
int vis[MX];
void solve(){int n;cin>>n;vector<int> a(n+1);for (int i=1;i<=n;++i) cin>>a[i];vector<int> suffix(n+1);memset(vis,0,sizeof(vis));for (int cnt=0,i=n;i>=1;--i){vis[a[i]]++;if (vis[a[i]]==1) cnt++;suffix[i] = cnt;}int maxx = 0;memset(vis,0,sizeof(vis));for (int cnt=0,i=1;i<n;i++){vis[a[i]]++;if (vis[a[i]]==1) cnt++;maxx = max(maxx,cnt+suffix[i+1]);}cout<<maxx<<"\n";
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数,不填默认// cout.precision();solve();return 0;
}
D - Cubes
翻译:
你被给予一个正整数N。决定是否存在一个正整数对(x,y)使得
。如果这个整数对,输出这样一个整数对(x,y)。
思路:
如果y存在,可得y至少都为
。而直接遍历明显不行。
令d=x-y, 由
可得
。那么如果(x,y)存在,则满足
。(注意求幂使用pow返回的是浮点型存在精度问题)。且在d确定的情况下上式单调递增,可用二分判断在d确定下y是否存在。
结论:先遍历d区间
,在内部二分搜索y是否有y满足
。即可。时间复杂度为
。注意在此题中要注意整型越界问题。(纯纯数学题)
实现:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){ll n;cin>>n;for (ll d=1;d*d*d<=n;d++){if (n%d!=0) continue;ll l = 0,r = 900000010;while (l+1!=r){ll mid = (l+r)/2;if (d*d+3*d*mid+3*mid*mid>=n/d){r = mid;}else{l = mid;}}if (d*d+3*d*r+3*r*r==n/d){cout<<r+d<<" "<<r<<"\n";return;}}cout<<-1<<"\n";
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}
E - Path Decomposition of a Tree
翻译:
给你一颗有NK个点的树。点的编号为
,并且第 i 条边
连接点
和
。
确定这棵树是否可以分解成 N 条路径,每条路径的长度为 K。更确切地说,确定是否存在满足以下条件的 N×K 矩阵 P:
是一个由
组成的排列。
- 对于每个i=1,2,...,N和j=1,2,...,K-1它们间有边连接着点
。
思路:
对于一个有NK个节点的树(以1为根节点),要求得到N个互不干扰大小为K的子树。
如果一个子树的大小为k(当前树的根节点也算上)且子节点数量 <= 2。那么这颗子树为可用路径,删除它。
如果子树大小 >k 或 子节点数量 >=3 或 子树大小 <k 且 子节点数量 >=2。那么答案就只能为No。对于上面子树的情况可以画图辅助思考下。
实现:
#include<bits/stdc++.h>
using namespace std;
const int MX = 2e5+10;
int n,k;
vector<vector<int>> tree(MX);
int f = 1;
// 属于当前点的子树大小
int dfs(int now,int fa){int res = 1,cnt = 0;for (int& i:tree[now]){if (i==fa) continue;int tree_size = dfs(i,now);res += tree_size;if (tree_size) cnt++;}if (res>k || cnt>=3 || res<k && cnt>=2){f = 0;}if (res==k && cnt<=2){res = 0;}return res;
}
void solve(){cin>>n>>k;for (int x,y,i=1;i<n*k;i++){cin>>x>>y;tree[x].push_back(y);tree[y].push_back(x);}dfs(1,1);if (f){cout<<"Yes\n";}else{cout<<"No\n";}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}
有建议可以评论,我会积极改进qwq。