服了，跟 $\text{DP}$ 杠上了，C 和 E 都在想 $\text{DP}$
C 和 D 又交了两发罚时

每题难度：
A:11
B:28
C:226
D:694
E:1504
F:2026
G:2608

A. Takahashi san 2

题意

给你一个字符串，判断这个字符串是否以 san 结尾，是输出 Yes，否则输出 No

思路

使用 string 中的 .substr() 函数，若 s.substr(s.length()-3,3)=="san" 输出 Yes，否则输出 No

注：s.substr(i,len)，表示从字符串 $s$ 的第 $i$ 为开始的 $len$ 个字符组成的字符串（子串）

C++ 代码

#include<bits/stdc++.h>
using namespace std;
string s;
int main(){cin>>s;if(s.substr(s.length()-3)=="san"){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}return 0;
}

B. Unvarnished Report

题意

输出两个字符串 $S$ 和 $T$ 第一个不同的位置

思路

将两个字符串用特殊符号补全，使它们长度相等即可判断

C++ 代码

#include<bits/stdc++.h>
#define sz(v) (int)v.size()
using namespace std;
string s,t;
int main(){cin>>s>>t;while(sz(s)<sz(t)){s+="?";}while(sz(t)<sz(s)){t+="!";}s=" "+s,t=" "+t;for(int i=1;i<=sz(s);i++){if(s[i]!=t[i]){cout<<i<<endl;return 0;}}cout<<0<<endl;return 0;
}

C. Separated Lunch

题意

共 $n$ 个数，将它们分成两组，设这两组的和分别为 $a$ 和 $b$，求 $\max (a,b)$ 的最小值

思路

一开始以为是动态规划，结果直接 $\text{CE}$

暴力枚举每一个选分到第一组还是第二组，用二进制数表示，最多 $2^{20}$ 次循环，时间足够

错误 C++ 代码 ：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=105;
const int maxm=1e8+5
int v[maxn];
int sum;
bool dp[maxn][maxm];
signed main(){int n;cin>>n;for(int i=0;i<n;i++){cin>>v[i];sum+=v[i];}dp[0][0]=1;for(int i=0;i<n;i++){for(int j=0;j<=sum;j++){dp[i+1][j+v[i]]=dp[i+1][j+v[i]]||dp[i][j];dp[i+1][j]=dp[i+1][j]||dp[i][j];}}int ans=sum;for(int i=0;i<=sum;i++){if(dp[n][i]){ans=min(ans,max(i,sum-i));}}cout<<ans<<endl;return 0;
}

正确 C++ 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=25;
int n;
int k[maxn];
signed main(){cin>>n;for(int i=0;i<n;i++){cin>>k[i];}int mn=inf;for(int i=1;i<(1<<n);i++){int mask=i;int cnt=0;int a=0,b=0;while(cnt<n){if(mask&1) a+=k[cnt];else b+=k[cnt];mask>>=1;cnt++;}mn=min(mn,max(a,b));}cout<<mn<<endl;return 0;
}

D. Laser Marking

题意

一个机器，要画出平面上的 $n$ 条线段，每条线段从 $(A_i,B_i)$ 到 $(C_i,D_i)$

画线时每秒移动 $T$ 个单位，不画线时每秒移动 $S$ 个单位

一开始机器在位置 $(0,0)$，你可以从 $(A_i,B_i)$ 到 $(C_i,D_i)$ 画一条线段，也可以从 $(C_i,D_i)$ 到 $(A_i,B_i)$ 画一条线段，一条线段不能中断

忽略抬笔和落笔的时间，问至少需要多少秒才能画完所有线段，误差需要在 $10^{-6}$ 以内

思路

因为 $N\le 6$，所以使用 next_permutation() 函数来枚举画线顺序，

在每个排列中，要使用二进制数枚举画线起点和终点

结果取最小值即可

注：两点间距离公式为 $\text{dist}((A_i,B_i),(C_i,D_i))=\sqrt{(C_i-A_i{)}^2+(D_i-B_i{)}^2}$

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long double ld;
int n;
int s,t;
int a[10],b[10],c[10],d[10];
int pmt[10];
ld res=3e18;
int sqr(int a){return a*a;
}
signed main(){cin>>n>>s>>t;for(int i=1;i<=n;i++){pmt[i]=i;cin>>a[i]>>b[i]>>c[i]>>d[i];}do{for(int i=0;i<(1<<n);i++){ld ans=0;int x=0,y=0;for(int j=1;j<=n;j++){int cur=pmt[j];if(i&(1<<(j-1))){ans+=sqrt(sqr(c[cur]-x)+sqr(d[cur]-y))/s;x=a[cur],y=b[cur];}else{ans+=sqrt(sqr(a[cur]-x)+sqr(b[cur]-y))/s;x=c[cur],y=d[cur];}ans+=sqrt(sqr(a[cur]-c[cur])+sqr(b[cur]-d[cur]))/t;}res=min(ans,res);}}while(next_permutation(pmt+1,pmt+1+n));cout<<fixed<<setprecision(20)<<res<<endl;return 0;
}

E. Sensor Optimization Dilemma 2

AT又在E放二分答案！！！

题意

制造某个产品有 $N$ 个步骤，第 $i$ 个步骤有两个机器可以完成：

• 机器 $1$：每台 $P_i$ 元，每天可以生产 $A_i$ 个产品
• 机器 $2$：每台 $Q_i$ 元，每天可以生产 $B_i$ 个产品

你共有 $x$ 元钱来购买机器，不一定要全用完。

求出这个值的 最大值 ： min ⁡ i = 1 N { 第  i 天生产的产品数 } \min_{i=1}^N \{第\ i\ 天生产的产品数\} mini=1N​{第 i 天生产的产品数}

思路

二分答案：

二分查找这个 $\min$ 值，所以每个步骤就至少得每天生产这么多个产品，求出总钱数判断是否 $\le x$

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=105;
int n,x;
int a[maxn],b[maxn],p[maxn],q[maxn];
bool check(int cur){int sum=0;for(int i=0;i<n;i++){int cost=3e18;for(int j=0;j<100;j++){int rest=max(cur-j*b[i],0ll); //若用j台机器2，还需生产多少个产品int k=(rest+a[i]-1)/a[i]; //还需要多少台机器1cost=min(cost,j*q[i]+k*p[i]); //取第i个步骤的金额最小值}sum+=cost; //计算总价钱if(sum>x){return false;}}return true;
}
signed main(){cin>>n>>x;for(int i=0;i<n;i++){cin>>a[i]>>p[i]>>b[i]>>q[i];if(p[i]*b[i]>q[i]*a[i]){swap(a[i],b[i]);swap(p[i],q[i]);}}int l=0,r=2e9;while(l<r){int mid=(l+r)/2;if(check(mid)){l=mid+1;}else{r=mid;}}cout<<l-1<<endl;return 0;
}