AtCoder Beginner Contest 397（ABCDE）

[A - Thermometer]( “A -

Thermometer “)

翻译：

高桥测量了自己的体温，发现它是 。

体温分为以下几种：

• 高于或等于 ：“高烧”
• 高于或等于 和低于 ：“发烧”
• 低于 ：“正常”

高桥的体温属于哪种分类？请根据输出部分以整数形式给出答案。

思路：

先判断>=38.0再判断<37.5,都不对输出发烧。可以写快点。

实现：

#include 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< 高桥汇总了检票口的使用记录。但是，他不小心删除了一些进出站记录。他正试图恢复被删除的记录。

给你一个由 i 和 o 组成的字符串 S。我们想在 S 的任意位置插入 0 个或多个字符，这样得到的字符串就能满足以下条件：

• 它的长度是偶数，每个奇数（第 1、第 3……个）字符都是 i，而每个偶数（第 2、第 4……个）字符都是 o。

求需要插入的最少字符数。在此问题的约束条件下，可以证明通过插入适当数量的字符、 S 就能满足条件。

思路：

字符串 io 是没问题，无需改变的。那么删除这些没问题的后剩下都是要在前后插入的字符了，统计一下剩下字符串长度即可。

实现：

#include 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 给你一个长度为 N

的整数序列：。

当把 A 在一个位置分割成两个非空（连续）子数组时，求这两个子数组中不同整数的计数之和的最大值。

更具体地说，对于整数 i，求以下两个值的最大和，使得 1≤i≤N-1： 中不同整数的数量，和中不同整数的数量。

思路：

前后缀分解，倒序遍历设立一个数组suffix，suffix[i]为[ i : n ]中A的不同整数数量。之后正序遍历求出以每个为分割点得到的和，比较下。

实现：

#include using namespace std; using ll = long long; const int MX = 3e5+10; int vis[MX]; void solve(){ int n; cin»n; vector a(n+1); for (int i=1;i<=n;++i) cin»a[i]; vector 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。决定是否存在一个正整数对（x，y）使得。如果这个整数对，输出这样一个整数对（x，y）。

思路：

如果y存在,可得y至少都为。而直接遍历明显不行。

令d=x-y， 由可得。那么如果(x,y)存在，则满足。（注意求幂使用pow返回的是浮点型存在精度问题）。且在d确定的情况下上式单调递增，可用二分判断在d确定下y是否存在。

结论：先遍历d区间，在内部二分搜索y是否有y满足。即可。时间复杂度为。注意在此题中要注意整型越界问题。（纯纯数学题）

实现：

#include using namespace std; using ll = long long; void solve(){ ll n;cin»n; for (ll d=1;ddd<=n;d++){ if (n%d!=0) continue; ll l = 0,r = 900000010; while (l+1!=r){ ll mid = (l+r)/2; if (dd+3dmid+3midmid>=n/d){ r = mid; }else{ l = mid; } } if (dd+3dr+3rr==n/d){ cout<

给你一颗有NK个点的树。点的编号为，并且第 i 条边连接点和。

确定这棵树是否可以分解成 N 条路径，每条路径的长度为 K。更确切地说，确定是否存在满足以下条件的 N×K 矩阵 P：

是一个由组成的排列。 * 对于每个i=1,2,…,N和j=1,2,…,K-1它们间有边连接着点。

思路：

对于一个有NK个节点的树（以1为根节点），要求得到N个互不干扰大小为K的子树。

如果一个子树的大小为k（当前树的根节点也算上）且子节点数量 <= 2。那么这颗子树为可用路径，删除它。

如果子树大小 >k 或 子节点数量 >=3 或 子树大小 =2。那么答案就只能为No。对于上面子树的情况可以画图辅助思考下。

实现：

#include using namespace std; const int MX = 2e5+10; int n,k; vector> 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=2){ f = 0; } if (res==k && cnt<=2){ res = 0; } return res; } void solve(){ cin»n»k; for (int x,y,i=1;i>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。