ABC374 C - Separated Lunch
将 $n$ 个数尽量均分，因为最多只有 20 个数据，可以直接暴搜
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
#define int long long
const int N=1e5+7, mod=1e9+7;
int n,s,ans=INT_MAX;
int a[N];
void dfs(int cnt,int sum){
if(cnt==n){
ans=min(ans,max(sum,s-sum));
return;
}
dfs(cnt+1,sum);
dfs(cnt+1,sum+a[cnt+1]);
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s+=a[i];
}
dfs(0,0);
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|
ABC374 E - Sensor Optimization Dilemma 2
易想到二分答案，但是在 $check$ 过程中，对每个进程机器的选择需要考虑
如果直接暴力从 $0$ 到 $mid/a[i]$ 一定会超时
考虑如果需要生产 $ab$ 个单位的物品，那么第一种机器会消耗 $bp$，第二种机器则会消耗 $ap$，但在最优方案中，两种机器不可能同时到达这么多需求，因为这样就可以用性价比高的替代低的了
假如 $ab=10,a=5,p=10,b=2,q=5$，我们会优先选 $a$ 因为他的性价比更高，在剩下大于等于 $ab$ 个需求时，我们只会选 $a$ 来满足需求，在小于 $ab$ 时，才会来找需要几个 $b$
所以 $check$ 只需要找 $max(a[i],b[i])$ 次就够了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;
#define endl "\n"
#define int long long
const int N = 1e5 + 7, mod = 1e9 + 7;
int n, x;
int a[N], b[N], c[N], d[N];
bool check(int f) {
int lst = x;
for (int i = 1; i <= n; i++) {
int cost = INT_MAX;
for (int j = 0; j <= 100; j++) {
int remaining = f - j * a[i];
cost = min(cost, j * b[i] + max(0LL, (int)ceil(1.0 * remaining / c[i])) * d[i]);
}
for (int j = 0; j <= 100; j++) {
int remaining = f - j * c[i];
cost = min(cost, j * d[i] + max(0LL, (int)ceil(1.0 * remaining / a[i])) * b[i]);
}
lst -= cost;
if (lst < 0) return false;
}
return lst >= 0;
}
void solve() {
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
}
int l = 0, r = 1e9, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
|
ABC374 F - Shipping
易想到用 $dp$ 解决
开一个 $dp[i][t]$ 第一维代表已发了 $i$ 件，第二维代表最后一次发快递在什么时刻发的
可以想到发快递的时间一定是 $t_{i}+k x, k \in \mathbb{Z}$
因为每次发快递的时间，就是此快递刚到，或是先堆积不发，等到后面的快递到了一起发，只有这两种状态
中间的等待都是无意义的，所以需要考虑的时间点其实并不多
初始状态即为 $dp[1][t[1]]$ 意为第一件，时间为 $t[1]$，此时总花费值为 $0$
然后从第二个进入 $dp$ 过程
当 $i<=k$ 时，此时都可以一次性发出，计算在 $t[i]$ 时发出总花费值，更新 $dp[i][t[i]]$ 的值
从上一次发 $k$ 件的时间时刻，到上一件的时刻，依次考虑在此时发快递的花费，按照上面的更新过程再来一遍
最后在 $dp[n]$ 里找最小值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e3+7, mod=1e9+7;
int k,n,x;
ll t[N];
map<ll,ll>dp[N];
void solve(){
cin>>n>>k>>x;
for(int i=1;i<=n;i++)cin>>t[i];
dp[1][t[1]]=0;
for(int i=2;i<=n;i++){
if(i<=k){
ll res=0;
for(int j=1;j<=i;j++)res+=t[i]-t[j];
if(!dp[i].count(t[i]))dp[i][t[i]]=res;
else dp[i][t[i]]=min(dp[i][t[i]],res);
}
for(int j=i-k;j<=i-1;j++){
if(j>0){
for(auto [key,val]:dp[j]){
ll tmp=max(key+x,t[i]);
ll res=val;
for(int k=j+1;k<=i;k++)res+=tmp-t[k];
if(!dp[i].count(tmp))dp[i][tmp]=res;
else dp[i][tmp]=min(dp[i][tmp],res);
}
}
}
}
ll ans=1e18;
for(auto [key,val]:dp[n])ans=min(ans,val);
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|
[NOIP2017]奶酪
dfs 查询，以当前空洞为原点，计算其他空洞到这个圆心的距离，如果小于 2*r 就进行 dfs，如果能碰到 h 就可以完成任务
要先找到接地的空洞，对他们都进行 dfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7;
const int MOD = 1e9 + 7;
int n, h, r;
ll x[N], y[N], z[N];
bool vis[N];
bool flag = false;
ll dis(ll x1, ll y1, ll z1, ll x2, ll y2, ll z2) {
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2);
}
void dfs(int pos) {
vis[pos] = true;
if (z[pos] + r >= h) {
flag = true;
return;
}
for (int i = 1; i <= n; ++i) {
if (!vis[i] && dis(x[pos], y[pos], z[pos], x[i], y[i], z[i]) <= 4 * r * r) {
if (flag) return;
dfs(i);
}
}
}
void solve() {
cin >> n >> h >> r;
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; ++i) {
cin >> x[i] >> y[i] >> z[i];
}
flag = false;
for (int i = 1; i <= n; ++i) {
if (z[i] - r <= 0 && !vis[i]) {
dfs(i);
}
}
cout << (flag ? "Yes" : "No") << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
|