前言
争取两天补一场
a
b
c
abc
abc 加油
传送门 :
C.Jumping Takahashi
题目类型 :
背包问题的可达性统计 , 可以使用
b
i
t
s
e
t
bitset
bitset提高效率
状态表示 :
f
[
i
]
[
j
]
f[i][j]
f[i][j]第
i
i
i次能否到达
j
j
j
状态计算 :
f
[
i
]
[
j
+
(
a
i
∣
b
i
)
]
=
f
[
i
?
1
]
[
j
]
f[i][j+(a_i|b_i)] = f[i-1][j]
f[i][j+(ai?∣bi?)]=f[i?1][j]
MyCode
const int N = 1e4+10;
int f[110][N];
void solve()
{
int n,x;cin>>n>>x;
f[0][0]= 1;
for(int i=1;i<=n;i++){
int a,b;cin>>a>>b;
for(int j = 0 ;j<= N - a ; j ++){
if(f[i-1][j]){
f[i][j+a] = f[i-1][j];
f[i][j+b] = f[i-1][j];
}
}
}
if(f[n][x])
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
D.Strange Balls
题目类型 : 模拟,思维
相当于祖玛游戏,
我们可以使用
v
e
c
t
o
r
<
p
i
i
>
vector<pii>
vector<pii>进行当前顶端的表示和计数,具体看代码
MyCode
void solve()
{
int n;cin>>n;
vector<pii> v;
int len =0;
for(int i=1;i<=n;i++){
int x;cin>>x;
len++;
if(v.size() == 0 ){
v.pb({x,1});
}else{
if(v[v.size()-1].x == x && v[v.size()-1].y == x-1)
len-=x,v.pop_back();
else{
if(v[v.size()-1].x == x)
v[v.size()-1].y ++;
else
v.pb({x,1});
}
}
cout<<len<<endl;
}
}
|