A - Takahashi san 2
直接判断字符串是否以san结尾即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
int n=s.size();
if(s[n-1]=='n'&&s[n-2]=='a'&&s[n-3]=='s') cout<<"Yes";
else cout<<"No";
return 0;
}
B - Unvarnished Report
用特殊符号将两个字符串补到相同长度，然后逐位判断即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
string s,t;
int main(){
cin>>s>>t;
int n=max(s.size(),t.size());
s.resize(n,'*'),t.resize(n,'*');
if(s==t) cout<<"0\n";
else{
for(int i=0;i<n;i++){
if(s[i]!=t[i]){
cout<<i+1<<"\n";
break;
}
}
}
return 0;
}
C - Separated Lunch
\(2^N\)枚举哪些人分配到A组即可，剩下人分到B组。
点击查看代码
#include<bits/stdc++.h>
#define N 30
#define int long long
using namespace std;
int n,a[N],ans=LLONG_MAX;
signed main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=(1<<n)-1;i>=0;i--){
int cnta=0,cntb=0;
for(int j=0;j<n;j++){
if(i&(1<<j)) cnta+=a[j];
else cntb+=a[j];
}
ans=min(ans,max(cnta,cntb));
}
cout<<ans;
return 0;
}
D - Laser Marking
先\(n!\)暴力枚举打印顺序，然后再\(2^n\)枚举每条线段起始端点。然后就以\(O(2^n\times n!)\)的优秀（大嘘）时间复杂度通过了
嘛，反正是暴搜题，能过就行(^^;
此题也有\(O(n^2\times 2^n)\)的做法，见https://atcoder.jp/contests/abc374/editorial/11105，如果有空会回来补这种做法的。
点击查看代码
#include<bits/stdc++.h>
#define N 10
#define int long long
using namespace std;
int n,s,t,sx[N],sy[N],tx[N],ty[N],tmp[N];
double ans=1e18;
double dist(int sx,int sy,int tx,int ty){
int x=sx-tx,y=sy-ty;
return sqrt(x*x+y*y);
}
double solve(){
int x=0,y=0;
double ans=0;
for(int ti=0;ti<n;ti++){
int i=tmp[ti];
ans+=dist(x,y,sx[i],sy[i])/(1.0*s);
ans+=dist(sx[i],sy[i],tx[i],ty[i])/(1.0*t);
x=tx[i],y=ty[i];
}
return ans;
}
signed main(){
cin>>n>>s>>t;
for(int i=0;i<n;i++){
cin>>sx[i]>>sy[i]>>tx[i]>>ty[i];
}
for(int i=0;i<n;i++) tmp[i]=i;
do{
for(int i=(1<<n)-1;i>=0;i--){
for(int j=0;j<n;j++){
if((1<<j)&i){
swap(tx[j],sx[j]);
swap(ty[j],sy[j]);
}
}
ans=min(ans,solve());
for(int j=0;j<n;j++){
if((1<<j)&i){
swap(tx[j],sx[j]);
swap(ty[j],sy[j]);
}
}
}
}while(next_permutation(tmp,tmp+n));
cout<<fixed<<setprecision(10)<<ans<<"\n";
return 0;
}
E - Sensor Optimization Dilemma 2
看到需要最大化最小值，于是考虑二分答案\(ans\)，判断使得每个工序的生产能力都达到\(ans\)以上所需要付出的最小钱数是否在\(X\)以内。
难点在于计算当前工序达到\(ans\)的生产能力所需要的最小钱数，如果和背包一样，用\(f[i][j]\)表示正在考虑第\(i\)台机器，达到\(j\)的生产能力所需要的最少钱数，处理每个工序时间复杂度将是\(O(V)\)，其中\(V\)与\(A\times X=10^9\)同阶，表示答案的值域；即使交换键值，处理每个工序的时间复杂度也会达到\(O(X)\)，总时间复杂度\(O(nX\log V)\)，无法通过。
我们可以直接枚举\(S\)机器的个数，有一个结论，假设\(S\)是成本较高的那台机器，那么只需要枚举\(S\)的台数从\(0\)到\(\frac{D}{A}-1\)，其中\(D=\text{lcm}(A,B)\)。理解起来不难，先把\(ans\)中整的\(D\)全用成本较低的机器达成，对于剩余的零头，再枚举用多少台成本较高的机器。这一步的时间复杂度和\(A\)、\(B\)是同阶的。
代码为了方便直接设\(D=A\times B\)，也没判断哪个机器成本更低，用\(2\)次循环把\(S,T\)都枚举了一遍（只是因为懒而已）。不影响复杂度：\(O(nA\log V)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 110
using namespace std;
int n,x,a[N],b[N],p[N],q[N];
bool check(int w){
int ans=0;
for(int i=1;i<=n;i++){
int money=LLONG_MAX;//j是S的个数，k是T的个数
for(int j=0;j<=b[i]&&j*a[i]<=w;j++){
int k=(w-j*a[i]+b[i]-1)/b[i];
money=min(money,j*p[i]+k*q[i]);
}
for(int k=0;k<=a[i]&&k*b[i]<=w;k++){
int j=(w-k*b[i]+a[i]-1)/a[i];
money=min(money,j*p[i]+k*q[i]);
}
ans+=money;
if(ans>x) return 0;
}
return 1;
}
signed main(){
cin>>n>>x;
for(int i=1;i<=n;i++) cin>>a[i]>>p[i]>>b[i]>>q[i];
int l=0,r=1e9;
while(l<r){
int mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l;
return 0;
}