easy
code : https://github.com/zouzhitao/competitive-programing/blob/master/kick-start/2019-B-A.cpp
B. Energy Stones
knapstack 变种.
题意
$n$ 块石头,每块石头有 3 个参数, 初始能量 $e$, 每秒能量损失 $l$, 吃完所需要的时间 $s$, 若石头能量损失到0,或者负数,该石头能量为0. 求吃完说有石头所能够得到的最大能量值
link :https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050eda/00000000001198c3
这其实是一个背包问题,但是要推出是背包还是需要一些功夫的。
首先,能量值为0 的石头一定不会吃它,那我们考虑要吃的石头集合的次序,如果两块石头紧邻,那我们一定会先吃能量损失的少的石头。因此可以以这个顺序将所有石头拍个序,然后问题就变成了一个背包问题了。
以上是官方题解
个人小插曲
在解决这个问题的时候,对于test set 1,我首先想到的是可以对每一个石头求解出次序为 $i$ 的时候它的能量值,然后在求解一个最优次序,这个问题等价与在一张 $nXn$ 的矩阵中,找不再同一列同一行的权值和最大的 $n$ 个数。这个问题等价与二分图的最大权值匹配,复杂度 $O(n^3)$
对于 Test set 2,个人并没能够想出。
看了题解之后用了 dp的方法,这种dp还是很经典的。
其中有一个小bug 让我调试了很久, #define MAXN 100+3
(果然是很久没敲代码了)
code : https://github.com/zouzhitao/competitive-programing/blob/master/kick-start/2019-B-B.cpp
C. Diverse Subarray
对于小数据我们可以用暴力做,对每个 $l$ , 计算以$l$ 为左端点的最优的 $r$ 这个可以暴力统计每个 type
的frequency
code
#include<bits/stdc++.h>
using namespace std;
#define ms(x,v) memset(x,(v), sizeof(x))
#define msn(x,v,n) memset(x,(v),sizeof(x[0]) * n)
#define INF 0x3f3f3f3f
typedef long long LL;
const int MAXN = 100 + 3;
int a[MAXN];
int S,n;
int main(int argc, char const *argv[])
{
ios :: sync_with_stdio(0);
cin.tie(0);
std::cout.precision(8);
std::cout.setf( std::ios::fixed, std:: ios::floatfield );
int T;
cin >> T;
for(int t =1; t <= T ; ++t)
{
cin >>n >> S;
for(int i=0 ; i<n ; ++i)
cin >> a[i];
int ans = 0;
for(int l=0 ; l < n; ++l){
unordered_map<int,int> frq;
int cur_ans = 0;
for(int r = l; r <n ; ++r){
auto f = frq[a[r]];
if(frq[a[r]]<S){
cur_ans++;
++frq[a[r]];
}else if(f==S)
{
cur_ans -=S;
++frq[a[r]];
}
if(ans < cur_ans)ans = cur_ans;
}
}
cout << "Case #"<<t << ": " << ans << "n";
}
return 0;
}
对于大数据就不太行了,这里看了题解后明白了
首先,从右统计每个type的频率,那么频率数组是可以继承的.
example
1,1,2,1,3,2,3,2,
设 $S=2$
则仿照官方题解的做法,贡献如下:
+1,+1,+1,-2,+1,+1+1,-2
若此时左端又来了一个 1, 那么将变为
+1,+1,-2,+1,0,+1,+1+1,-2
若我们维护从 $l$ 到 $i$ 的浅醉和,我们会发现,此时[l,n] 全都+1,然后,[ptr[a[l]]+s,n] -(s+1),[ptr[a[l]+s+1,n]+s
ptr 表示当前访问元素的下标。
以上操作可以用线段树处理
code C
版权声明
本作品为作者原创文章,采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
作者: taotao
转载请保留此版权声明,并注明出处
近期评论