C - Separated Lunch
题目：
思路：
dfs枚举每个数是否选入a数组中，求和比较
代码：
#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N=25;int a[N];
bool st[N];
int mn=0x3f3f3f3f;
int sum;
int n;
void dfs(int u, int s)
{if(u==n){mn=min(mn,max(sum-s,s));return;}dfs(u+1,s);dfs(u+1,s+a[u]);
}int main()
{cin>>n;for(int i=0; i<n; i++){cin>>a[i];sum+=a[i];}dfs(0,0);cout<<mn<<'\n';return 0;}
欣赏一下jiangly的代码：
#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int N;std::cin >> N;std::vector<int> K(N);for (int i = 0; i < N; i++) {std::cin >> K[i];}int tot = std::accumulate(K.begin(), K.end(), 0);int ans = tot;std::vector<int> sum(1 << N);for (int s = 0; s < (1 << N); s++) {if (s > 0) {int u = __builtin_ctz(s);sum[s] = K[u] + sum[s ^ (1 << u)];}ans = std::min(ans, std::max(sum[s], tot - sum[s]));}std::cout << ans << "\n";return 0;
}
D - Laser Marking
题目：
思路：
dfs一下1~n的全排列，注意每次递归两个端点，取最小值
代码：
#include <bits/stdc++.h>
#define fi first
#define se second;using namespace std;typedef long long LL;
typedef pair<int,int> PII;int main()
{int n;cin>>n;int s, t;cin>>s>>t;vector<int> A(n), B(n), C(n), D(n);for(int i=0; i<n; i++){cin>>A[i]>>B[i]>>C[i]>>D[i];}double ans=1e18;vector<bool> vis(n);auto dfs = [&] (auto &self ,int x,int y, double sum=0.0, int c=0){if(c==n){ans= min(ans,sum);return;}for(int i=0; i<n; i++){if(vis[i]){continue;}double d1=hypot(A[i]-x, B[i]-y);double d2=hypot(C[i]-x, D[i]-y);double d0=hypot(A[i]-C[i], B[i]-D[i]);vis[i]=true;self(self ,C[i], D[i], sum+d1/s +d0/t, c+1);self(self ,A[i], B[i], sum+d2/s +d0/t, c+1);vis[i]=false;}};dfs(dfs,0,0);cout<<fixed<<setprecision(20)<<ans<<'\n';return 0;
}E - Sensor Optimization Dilemma 2
题目：
思路：
截取了两位博主的思路
代码：
#include <bits/stdc++.h>
#define fi first
#define se second;using namespace std;typedef long long LL;
typedef pair<int,int> PII;int main()
{int n,x;cin>>n>>x;vector<int> A(n), B(n), P(n), Q(n);for(int i=0; i<n; i++){cin>>A[i]>>P[i]>>B[i]>>Q[i];if(A[i]*Q[i]<B[i]*P[i]){swap(A[i], B[i]);swap(P[i], Q[i]);}}auto check = [&](int u){LL ans=0;for(int i=0; i<n; i++){LL res=1e18;for(int j=0; j<=100; j++){LL v=j*Q[i];int need =u-j*B[i];if(need > 0){v+=1LL *(need + A[i]-1)/A[i] *P[i];}res=min(res,v);}ans+=res;}return ans <= x;};int l=0, r=1e9;while(l<r){int mid=(l+r+1)/2;if(check(mid)){l=mid;} else {r=mid-1;}}cout<<l<<'\n';return 0;
}
