A - Task Failed Successfully
翻译：
高桥为N天设定了任务目标。
他计划在第i天（1≤i≤N）完成A_i个任务，实际完成了B_i个任务。
求他完成的任务数超过目标任务数的天数。
思路：
遍历天数比较A_i,B_i大小。（模拟）
实现：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){
int n;cin>>n;
int ans = 0;
for (int a,b,i=1;i<=n;i++){
cin>>a>>b;
ans+=a<b;
}
cout<<ans<<endl;
}
int main(){
int t=1;
// cin>>t;
while (t--) solve();
return 0;
}
B - Precondition
翻译：
给定两个字符串 S 和 T，它们由英文字母的大小写字母组成。
判断字符串 S 是否满足以下条件：
- S 中所有不在开头的大写字母，其前一个字符均来自 T。更正式地说，对于所有满足 2≤i≤∣S∣ 的整数 i，若 S 的第 i 个字符为大写字母，则 S 的第 (i−1) 个字符属于 T。
思路：
顺序遍历A的每个字符进行判断。（模拟）
实现：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){
string s,t;
cin>>s>>t;
bool f = 1;
for (int i=1;i<s.size();i++){
if (isupper(s[i]) && t.find(s[i-1])==string::npos){
f = 0;
}
}
if (f) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
int main(){
int t=1;
// cin>>t;
while (t--) solve();
return 0;
}
C - Giant Domino
翻译：
有 N 块编号为 1 到 N 的多米诺骨牌。第 i 块多米诺骨牌的大小为 S_i。
考虑将一些多米诺骨牌从左到右排列成一行，然后推倒它们。当第 i 块多米诺骨牌向右倒下时，如果紧邻第 i 块多米诺骨牌右侧的多米诺骨牌的大小不超过 2S_i，那么该多米诺骨牌也会向右倒下。你决定选择两块或更多多米诺骨牌，并将其从左到右排列成一行。多米诺骨牌的排列必须满足以下条件：
- 最左侧的多米诺骨牌是第1块。
- 最右侧的多米诺骨牌是第N块。
- 当第1块多米诺骨牌向右倒下时，第N块多米诺骨牌最终也会向右倒下。
是否存在满足上述条件的骨牌排列方式？如果存在，需要排列的骨牌的最小数量是多少？
你将得到T个测试案例，请分别解决每个案例的问题。
思路：
按条件，多米诺骨牌倒下时，右边的骨牌大小要尽量大。在确定了起点与终点后，使用二分搜索快速找到当前骨牌能达到的最大骨牌以此类推直到大于等于终点大小或始终到不了。（二分搜索，贪心）
实现：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){
int n;cin>>n;
vector<int> weight(n);
for (int& i:weight) cin>>i;
int end = weight[n-1];
sort(weight.begin()+1,weight.end());
int ans = 2,now = 0;
while (1){
// look for lower_bound 2*weight[now] position -1
int pos = upper_bound(weight.begin()+1,weight.end(),2*weight[now])-weight.begin()-1;
if (pos==now){
cout<<-1<<"\n";
return;
}else if(weight[pos]>=end){
cout<<ans<<"\n";
return;
}
now = pos;
ans++;
}
}
int main(){
int t=1;
cin>>t;
while (t--) solve();
return 0;
}D - Make 2-Regular Graph
翻译：
存在一个简单的无向图 G，包含 N 个顶点和 M 条边。顶点编号为 1, 2, …, N，第 i 条边是连接顶点 A_i 和 B_i 的无向边。
你可以以任意顺序和任意次数重复以下两项操作：
- 向G添加一条无向边
- 从G移除一条无向边
求使G成为一个简单无向图且所有顶点度数均为2所需的最小操作次数。
思路：
最终的G因该变为一个环或两个环。由于N最大为8直接排列所有点之间的相连顺序，也就8！=40320次。得到相连顺序后到的cnt为最终情况下已经存在的边，ans=m-cnt+n-cnt。（暴力，图论）
实现：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// to make a loop
void solve(){
int n,m;cin>>n>>m;
vector<vector<int>> maze(n+1,vector<int>(n+1,0));
for (int a,b,i=1;i<=m;i++){
cin>>a>>b;
maze[a][b] = 1;
maze[b][a] = 1;
}
vector<int> order(n);
for (int i=1;i<=n;i++){
order[i-1] = i;
}
auto check = [&](vector<int> order)->int{
int cnt = 0;
for (int i=0;i<n;i++){
cnt+=maze[order[i]][order[(i+1)%n]];
}
int res = m+n-2*cnt;
// 分为两个环
for (int k=3;k<=5;k++){
if (n-k>=3){
cnt = 0;
for (int i = 0; i < k; ++i){
cnt += maze[order[i]][order[(i+1)%k]];
}
for (int i = k; i < n; ++i){
cnt += maze[order[i]][order[k + (i+1-k)% (n-k)]];
}
res = min(res,m + n - 2 * cnt);
}
}
return res;
};
int ans = INT_MAX;
do {
ans = min(ans,check(order));
}while (next_permutation(order.begin(),order.end()));
cout<<ans<<"\n";
}
int main(){
int t=1;
// cin>>t;
while (t--) solve();
return 0;
}E - LCM Sequence
翻译：
对于正整数 n，定义 A_n 作为 1、2、…、n 的最小公倍数。
给定正整数 L 和 R。序列 (A_L ,A_{L+1} ,…,A_R ) 中包含多少个不同的整数？
思路：
A_n是非严格递增的，只有当n为质数幂时才会A_n>A_{n-1}。那么就是求（L，R】中质数幂的数量，这个可以用二段筛+记录每个值有几种质数构成实现。（数论，二段筛）
实现：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MX = 1e7+10;
vector<ll> is_prime(MX,1),primes;
void init(){
for (ll i=2;i<MX;i++){
if (is_prime[i]){
primes.push_back(i);
for (ll j=i*i;j<MX;j+=i){
is_prime[j] = 0;
}
}
}
}
void solve(){
ll l,r;cin>>l>>r;
ll ans = 1;
vector<ll> nums(r-l+1);
for (ll i=l;i<=r;i++) nums[i-l] = i;
vector<ll> cnts(r-l+1,0);
for (ll& prime:primes){
for (ll i = (l+prime-1)/prime*prime;i<=r;i+=prime){
ll cnt = 0;
while (nums[i-l]%prime==0){
nums[i-l]/=prime;
cnt++;
}
cnts[i-l]+=(cnt>0);
}
}
for (ll i=l;i<=r;i++) cnts[i-l]+=(nums[i-l]>1);
for (ll i=l+1;i<=r;i++) ans+=(cnts[i-l]<=1);
cout<<ans<<endl;
}
int main(){
init();
ll t=1;
// cin>>t;
while (t--) solve();
return 0;
}F - Socks 4
翻译：
在高桥的抽屉中，有 N 种颜色的袜子，第 i 种颜色的袜子有 A_i 只。
一开始，高桥手中已经有一只颜色为 C 的袜子（这只是从抽屉外拿出来的，不在抽屉中）。
然后，他不断重复以下操作，直到满足终止条件：
- 从抽屉中随机抽出一只袜子（每只袜子被抽到的概率相等）。如果现在他手中两只袜子的颜色相同，则操作终止。如果颜色不同，他会选择其中一只袜子放回抽屉中，然后继续抽。他总是选择放回那只袜子的方式，使得未来预期需要的抽取次数最少（即期望值最小）。
操作最终终止前，预期抽了多少次袜子（期望值）。答案对 998244353 取模。
思路：
令dp[i]为袜子i在外的预期抽袜子数，将a从小到大排序，s为袜子总数量-1，可得等式
，注意由费马小定理得到分数取余公式
(动态规划，概率论,逆元)
实现：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
ll qpow(ll a,ll b){
ll res = 1;
while (b){
if (b&1) res = res*a%mod;
a = a*a%mod;
b>>=1;
}
return res;
}
void solve(){
ll n,c,s=0;cin>>n>>c;
vector<ll> a(n+1),pre(n+1,0);
for (ll i=1;i<=n;i++){
cin>>a[i];
s+=a[i];
}
// have one sock outside
ll tmp = ++a[c];
sort(a.begin()+1,a.end());
c = lower_bound(a.begin()+1,a.end(),tmp)-a.begin();
// invs: s的逆元
ll invs = qpow(s,mod-2),sum = 1;
for (int i=1;i<=n;i++) pre[i] = (pre[i-1]+a[i]*invs)%mod;
vector<ll> dp(n+1);
for (int i=n;i>=c;i--){
dp[i] = sum*qpow((1-pre[i-1]+mod)%mod,mod-2)%mod;
sum = (sum+dp[i]*a[i]%mod*invs)%mod;
}
cout<<dp[c]<<endl;
}
int main(){
// 关闭输入输出流同步
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll t=1;
// cin>>t;
while (t--) solve();
return 0;
}之后补题会在此增加题解。
思路标准：思路+算法概要+时空复杂度。