A. Catch the Coin
对每个枚硬币分别判断即可
只要其 y 轴上的距离能够赶上，一定能取到
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
|
#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=1e5+7, mod=1e9+7;
void solve(){
int x,y;
cin>>x>>y;
int mn=-abs(x),mx=abs(x);
if(y-abs(x)+1<mn)cout<<"NO\n";
else cout<<"YES\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
B. Substring and Subsequence
只能 $O(n^2)$ 对每一位判断其后方有多少个相同的即可
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
|
#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=1e5+7, mod=1e9+7;
void solve(){
string s,t;
cin>>s>>t;
int ans=s.size()+t.size();
for(int i=0;i<t.size();i++){
int tmp=0;
for(int j=0;j<s.size() && i+tmp<t.size();j++){
if(s[j]==t[i+tmp])tmp++;
}
ans=min(ans,int(s.size()+t.size())-tmp);
}
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;
}
|
C. Two Movies
某人对两部电影的评价相同时，将这个评价存下，不同时，取评分大的那项，最后将存下的所有评分加给当前小的那项
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
|
#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=1e5+7, mod=1e9+7;
int n,suma,sumb;
deque<int>q;
void solve(){
suma=sumb=0;
q.clear();
cin>>n;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
if(x>y)suma+=x;
else if(y>x)sumb+=y;
else q.push_back(x);
}
for(auto x:q){
if(x>0){
if(suma>sumb)sumb++;
else suma++;
}
else{
if(suma>sumb)suma--;
else sumb--;
}
}
cout<<min(suma,sumb)<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
D. Smithing Skill
首先易想到贪心，因为锻造后，一定立马熔铸，这样一次消耗 $a_i-b_i$ 的代价
当 $a_i-b_i$ 相等时，一定选取 $a$ 小的那个操作，这样可以保证操作次数最多
同时，$a_i-b_i$ 大的物品，其 $a_i$ 应该小于前面的物品，因为如果这个 $a_i$ 更大，一定是选前面的更优
所以物品其实是单调栈，将其按照 $a_i-b_i$ 从小到大来存，同时 $a_i$ 逐渐递增
对于栈中物品，我们优先从后取，因为当材料数量大于第一个的 $a$ 时，我们一定取的是第一个
只有无法取第一个时，我们才会从后面取，每次取时，记录当前买了几件栈中的物品，dp 中存的就是能买几件后面的物品
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
60
61
62
63
64
65
66
|
#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
typedef long long ll;
const int N=1e6+7, mod=1e9+7;
int n,m;
int a[N],b[N];
map<int,int>vis;
int c[N];
ll f[N],g[N];
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++){
int x=a[i]-b[i];
if(vis.find(x)==vis.end())vis[x]=a[i];
else vis[x]=min(vis[x],a[i]);
}
deque<pair<int,int>>s;
for(auto [x,y]:vis){
if(s.empty())s.push_back({x,y});
else{
if(y>=s.back().second)continue;
else s.push_back({x,y});
}
}
int mx=s.front().second,mn=s.back().second,tmp=0;
int ta=s.front().second,tb=s.front().second-s.front().first;
for(int i=mn;i<=mx;i++){
if(i==s.back().second){
tmp=s.back().first;
s.pop_back();
}
f[i]=g[i-tmp]+1;
g[i]=max(g[i-1],f[i]);
}
ll ans=0;
for(int i=1;i<=m;i++){
int x;
cin>>x;
if(x>mx){
int ti=(x-tb)/tmp;
x-=ti*tmp;
ans+=ti;
}
ans+=f[x];
}
cout<<ans*2<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|