Educational Codeforces Round 125 (Rated for Div. 2)

A. Integer Moves

给你 ,从 出发,只能走曼哈顿距离( )为整数的点,问最少几步到达

由于 ,所以可以直接暴力

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
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
queue<PII> q;
q.emplace(0,0);
map<PII,int> m;
m[{0,0}]=0;
while(!q.empty()){
PII t=q.front();q.pop();
for(int i=0;i<=50;i++){
for(int j=0;j<=50;j++){
if(make_pair(i,j)==t)continue;
double res=sqrt((t.first-i)*(t.first-i)+(t.second-j)*(t.second-j));
if(((int)res)==res){
if(m.find({i,j})==m.end()){
q.emplace(i,j);
m[{i,j}]=m[t]+1;
}
}
}
}
}
while(t--){
int x,y;
cin>>x>>y;
cout<<m[{x,y}]<<"\n";
}
}

其实仔细想想,如果从原点出发,无法直接走到 ,那就可以直接走 ,走 ,两次到达

那么答案显然,如果 ,答案就是 ,如果 是整数,答案就是 ,剩下的则是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
int x,y;
cin>>x>>y;
if(x==0&&y==0)cout<<"0\n";
else{
double dis=sqrt(x*x+y*y);
if((int)dis==dis)cout<<1<<"\n";
else cout<<"2\n";
}
}
}

B. XY Sequence

的最大值

贪心即可,只要加上 不大于 就加,否则就减去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
ll n,b,x,y;
cin>>n>>b>>x>>y;
ll res=0,ans=0;
for(int i=1;i<=n;i++){
if(res+x<=b)res+=x;
else res-=y;
ans+=res;
}
cout<<ans<<"\n";
}
}

C. Bracket Sequence Deletion

给你只包含 ‘(’ 和 ‘)’ 的字符串

如果字符串满足以下两个条件的任意一个就叫好的字符串:

  • 该字符串为合法的括号序列

  • 该字符串为回文串

找到 前缀里最短的好的字符串并删去,直至无法找到

求删去了几次

如果开头是 ‘(’

graph TB;
    A(("("))-->B(("(("))
    A(("("))-->C(("()"))

无论下一位是什么都可以

如果开头是 ‘)’

graph TB;
    A((")"))-->B(("))"))
    A((")"))-->C((")("))
    C((")("))-->D((")()"))
    C((")("))-->E((")(("))
    E((")(("))-->F((")(()"))
    E((")(("))-->G((")((("))

可以发现,只要遇到了 ‘)’ 就一定是回文串

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<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
int n,cnt=0;
string s;
cin>>n>>s;
int i=0;
for(i=0;i<s.length()-1;){
if(s[i]=='('){
cnt++;
i+=2;
}
else{
auto j=s.find(')',i+1);
if(j!=string::npos){
cnt++;
i=j+1;
}
else break;
}
}
cout<<cnt<<" "<<s.length()-i<<"\n";
}
}

D. For Gamers. By Gamers

种士兵,每个士兵都有 花费, 单位时间攻击力, 血量

个 boss ,每个 boss 都有 单位时间攻击力, 血量

每轮战斗只打一个 boss ,且有 钱,你只能选一种类型的士兵,战斗中不能让任何一个士兵死亡,问最少花费多少钱可以击败 boss (伤害是连续的),即击败 boss 的速度严格大于 boss 击败一个士兵的速度

按题意写成数学公式就是 为士兵个数

那么我们就把 看成一个整体

为在花费不超过 钱时,最大的 ,则 为选的个数

最后要

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
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define PII pair<ll,ll>
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n,C;
cin>>n>>C;
unordered_map<ll,ll> a;
for(int i=1;i<=n;i++){
ll c,d,h;
cin>>c>>d>>h;
a[c]=max(a[c],d*h);
}
vector<ll> f(C+1,0);
for(auto i:a){
for(ll j=1;i.first*j<=C;j++){
f[i.first*j]=max(f[i.first*j],i.second*j);
}
}
for(int j=1;j<=C;j++){
f[j]=max(f[j],f[j-1]);
}
ll m;
cin>>m;
while(m--){
ll d,h;
cin>>d>>h;
ll pos=lower_bound(f.begin()+1,f.end(),d*h+1)-f.begin();
if(pos==C+1)cout<<"-1\n";
else cout<<pos<<"\n";
}
}

Educational Codeforces Round 125 (Rated for Div. 2)

http://blog.therehello.top/cf1657/

发布于

2022-03-23

更新于

2022-03-23

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...