Codeforces Round #625解题报告

记录丢人点滴

虽然真的很丢人 但是看了一下大家代码发现我至少代码还是短(?

A: Contest for Robots

题目链接
题意:两种机器人对于n个问题有会和不会(1和0) 希望第一种的得分比第二种高 要如何安排问题分数分布 要求分数中最大的尽量小
算一下第一种比第二种多的1和0 除一下
可能会除零 要先判掉再除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
int a[105],b[105];
int main(){
int n,c1(0),c2(0); sc(n);
rep(i,0,n) sc(a[i]);
rep(i,0,n){
sc(b[i]);
if(a[i]==b[i]) continue;
else if(a[i]>b[i]) c1++;
else c2++;
}
if(!c1) return pf("-1\n"),0;
int ans=(c2+c1)/c1;
pf("%d\n",ans>0?ans:0);
}

B: Journey Planning

题目链接
题意:希望选择b的总和尽量大且满足选中的bi,bj有i-j==bi-bj
每个b去减去i 找相同的
数组存的话加上n也行 但是map就是香啊
要ll 赛时比较草率qwq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%lld", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
int a[maxn];
map<int,int>ans;
signed main(){
int n,mx(0); sc(n); rep(i,1,n+1){
sc(a[i]); int t=a[i]-i; ans[t]+=a[i];
}
for(auto& x:ans) mx=max(mx,x.second);
pf("%lld\n",mx);
}

C: Remove Adjacent

题目链接
题意:给一个字符串 对于每个字符 如果相邻字符有ascii码刚好比自己少1的 则可以删除 问最多能删多少个
枚举z到a 每次for一遍删 O(26*n^3)

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
#define rep(i,s,e) for(ll i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
int main(){
ios::sync_with_stdio(0);
int n,cnt(0); string s; cin>>n>>s; s+=' ';
dep(k,25,1) rep(i,0,n) if(s[i]==k+'a'){
if(s[i+1]==s[i]-1||(i&&s[i-1]==s[i]-1)) s.erase(i,1),n--,cnt++,i=i?i-2:-1;
} cout<<cnt;
}

D: Navigation System

题目链接
题意:高德地图持续为您规划路线
n个点m条边的有向无权图 给k个点是必须经过的 导航每次路线会选择最短路 如果不是最短路就rebuild重新找最短路 问rebuild的最少和最多次数
无权图 bfs/dij/spfa啥的都行qwq
判是不是最短路用dis就行
mx和mn就差在有多条最短路的时候 这时候记一下就好了

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
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(ll i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
struct node{
int id,dt;
bool operator < (const node a) const{
return dt>a.dt;
}
};
priority_queue<node>q;
int n,m,k,s,t,tot;
int dis[maxn],vis[maxn],head[maxn],cnt[maxn];
int nex[maxn<<1],to[maxn<<1],val[maxn<<1];
void addedge(int u,int v,int w){
nex[++tot]=head[u];
head[u]=tot; to[tot]=v; val[tot]=w;
}
void dij(int s){
rep(i,1,n+1) dis[i]=1e9; dis[s]=0;
q.push({s,0}); while(!q.empty()){
int fr=q.top().id; q.pop();
if(vis[fr]) continue; vis[fr]++;
for(int j=head[fr];j;j=nex[j])
if(dis[to[j]]>val[j]+dis[fr]&&!vis[to[j]]){
dis[to[j]]=val[j]+dis[fr];
q.push({to[j],dis[to[j]]});
}
else if(dis[to[j]]==val[j]+dis[fr])
cnt[to[j]]=1;
}
} // 板子闭着眼一套
int p[maxn];
int main(){
int mn(0),mx(0); sc(n); sc(m); while(m--){
int u,v; sc(u); sc(v); addedge(v,u,1);
} sc(k); rep(i,1,k+1) sc(p[i]);
dij(p[k]); rep(i,1,k+1){
if(i!=k&&dis[p[i]]!=dis[p[i+1]]+1) mn++;
else mx+=cnt[p[i]];
} pf("%d %d\n",mn,mn+mx);
}

E: World of Darkraft: Battle for Azathoth

题目链接
补了加qwq