目錄

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。