ap_st_13

随便的占位符

C Olya and magical square cf1080d 思维

给你一个大正方形,划分k次将其分割为若干个小正方形(划分指画一个十字),问是否存在任意一种方案使得从左下到右上角有一条路径且路径里的正方形大小是一样的(在分割后的一块内分割不会把相邻的其它几块一起割掉)。如果看不懂可以看原样例。

首先,解决边长2^n的正方形的最大能分割几次,根据观察就能写出递推公式:cnt[i] = cnt[i - 1] * 4 + 1,当然这其实是个q = 4的等比数列求和公式,所以实际上是cnt[i] = (4^n - 1)/3

因为只要找出任意一条路径就行,不妨假设这个路径是贴着最左边的边一直往上到左上,然后一直向右到右上(这样比较好想)。

这样所能想到的只有枚举这条路径上正方形的边长大小,但是n=1e9没法直接枚举……把k = 1e18代入得到i = 31左右,所以当n > 31时可以分割出n = 31的位于右下角的正方形,然后把右下角的正方形随便分割,反正肯定能分割完。

n <= 31时枚举,搞一个最小分割和最大分割,看看k在不在里面。最小的肯定是只把这个路径切出来,最大的是一块把剩下的右下角那块大正方形割到不能再割。这几个式子推一推就好了

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
#include <cstdio>
typedef long long ll;
ll cnt[40];

int work(int dep,ll k) {
if(dep > 31) return dep - 1;
ll last = 0;
for(int i = dep - 1; i >= 0; --i) {
ll lb = 0,ub = cnt[dep] - cnt[i] * ((1LL << (dep - i + 1)) - 1);
lb = (last += (1LL << (dep - i)) - 1);
if(k >= lb && k <= ub) return i;
}
return -1;
}

int main() {
cnt[0] = 0;
for(int i = 1; i <= 31; ++i)
cnt[i] = cnt[i - 1] * 4 + 1;
int t;
scanf("%d",&t);
while(t--) {
ll n,k; scanf("%lld%lld",&n,&k);
ll ans = work(n,k);
if(~ans) printf("YES %lld\n",ans);
else puts("NO");
}
return 0;
}

G Dakar Rally zoj3699 贪心

路上有 n 个加油站 
每个加油站的价格可能不同  
你的油箱容积为 v  
问从起点开车到终点加油至少用多少钱

感觉不太好想。首先如果这段路所需油耗大于油箱容量肯定impossible。然后每到一个加油站前都加满油,然后看看看看如果仅用这箱油能跑到的最远的地方里还有没有后面的加油站比当前的更便宜。只要找到之后的第一个便宜的就仅仅加油加到能开到那里所需要的油然后开到那里,否则说明现在的是最便宜的,所以就加满油,去下一个加油站。

大概这种做法隐藏着单调队列的思想?反正感觉还不是特别会就是了……

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
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
ll len[maxn],price[maxn],cost[maxn];
int main() {
int T; scanf("%d",&T);
while(T--) {
ll n,v; scanf("%lld%lld",&n,&v);
bool skip = 0;
for(int i = 0; i < n; ++i) {
scanf("%lld%lld%lld",&len[i],&cost[i],&price[i]);
if(cost[i] * len[i] > v)
skip = 1;
}
if(skip) {
puts("Impossible");
continue;
}
ll vol = 0,ans = 0;
for(int i = 0,j; i < n; ) {
j = i + 1;
ll tot = cost[i] * len[i];
while(j < n && v >= tot + cost[j] * len[j] && price[j] >= price[i]) {
tot += cost[j] * len[j];
++j;
}
if(j >= n || price[j] < price[i]) {
if(vol >= tot) {
vol -= tot;
} else {
ans += (tot - vol) * price[i];
vol = 0;
}
i = j;
} else {
ans += (v - vol) * price[i];
vol = v - cost[i] * len[i];
++i;
}
}
printf("%lld\n",ans);
}
return 0;
}
//https://blog.csdn.net/acvay/article/details/46798685

I Interesting Dart Game zoj2955 完全背包 鸽巢(抽屉)原理

给你n种分数,每种分数是无限个,
然后怎样尽量少选分数,使得它们的和恰好等于一个数m。
n = 100,m = 1e9,每种分数<=100

感觉就应该是完全背包,但是m太大,所以要通过抽屉原理去缩小,而尽可能少选就成了关键。

首先从大到小对an排序。

首先先看

所以说a(1)~a(n-1)种分数一共所选择的次数k1 + k2 + …… + kn-1一定小于a(n),因为如果>=,一定存在连续的一段的和(al~ar) = an的倍数 (假设搞一个前缀和然后都%an,因为这段序列的长度k1 + k2 + …… + kn-1 > an,那么至少两个数%an后的余数相同,也就是说它们的差 = x * an)。然后因为an比每一个ai都大所以将这一段替换成an次数会更少。

所以先对a(1)~a(n-1)完全背包,然后他们的总分数和<=an*an = 10000,然后在统一选an:枚举分数和看看和m的分数差是否等于an的倍数,就可以选了。

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
std::vector<int> v;
struct st {
int num;
int dep;
};
int f[20000];
int main() {
int T; std::cin>>T;
while(T--) {
int n,m;
std::cin>>m>>n;
v.clear();
v.resize(m);
int ans = 2e9;
for(int i = 0; i < m; ++i) {
int x; scanf("%d",&x);
v[i] = x;
}
std::sort(v.begin(),v.end());
for(int i = 1; i <= 10000; ++i)
f[i] = 2e9;
f[0] = 0;
for(int i = 0; i < m - 1; ++i) {
for(int j = v[i]; j <= 10000; ++j) {
f[j] = std::min(f[j],f[j - v[i]] + 1);
}
}

for(int i = 0; i <= 10000; ++i) {
if(f[i] != 2e9 && (n - i) % v[m - 1] == 0)
ans = std::min(ans,f[i] + (n - i) / v[m - 1]);
}

if(ans < 2e9)
printf("%d\n",ans);
else puts("-1");
}
return 0;
}
//https://blog.csdn.net/u012860063/article/details/44946667
//https://blog.csdn.net/qq_42936517/article/details/88851558