【补题系列】2020USST算法竞赛练习场2
题解
题意：第一行输入三个数，分别代表乘客数、Y国间谍数、XY双重间谍数，然后依次每行输入对应的名字，要求找出乘客中不是双重间谍的Y国间谍并输出
很简单，当时没太看懂题QAQ，用vector实现即可
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
string ss[1005];
int main(){
int n,m,k;
while(cin>>n>>m>>k){
vector<string> aa,bb,cc,dd;
string s;
for(int i=0;i<n;i++){
cin>>s;
aa.push_back(s);
}
for(int i=0;i<m;i++){
cin>>s;
for(int j=0;j<n;j++){
if(aa[j]==s){
bb.push_back(s);
break;
}
}
}
for(int i=0;i<k;i++){
cin>>s;
cc.push_back(s);
}
for(int i=0;i<bb.size();i++){
for(int j=0;j<cc.size();j++){
if(bb[i]==cc[j]) break;
else if(j==cc.size()-1){
dd.push_back(bb[i]);
}
}
}
if(dd.size()==0){
cout<<"No enemy spy"<<endl;
continue;
}
for(int i=0;i<dd.size();i++){
if(i!=dd.size()-1)cout<<dd[i]<<" ";
else cout<<dd[i];
}
cout<<endl;
}
return 0;
}
|
题解
题意：给定若干站点，并给出一个表，表明某些距离段内的票价，有若干次询问，要求输出询问中两站点之间的最小票价
算法：floyd
首先预处理出任意两个点间的距离对应的票价，然后用一遍floyd求出每两个点间的最小票价，最后输出即可，（注意英文单词别打错！Orz）
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1ll<<60;
int l[105],c[105],n,m;
ll dis[105][105];
int pos[105];
int main(){
int t;
cin>>t;
for(int o=1;o<=t;o++){
for(int i=1;i<=4;i++) scanf("%d",l+i);
for(int i=1;i<=4;i++) scanf("%d",c+i);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",pos+i);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) dis[i][j]=0;
else dis[i][j]=inf;
}
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
int distance=abs(pos[i]-pos[j]);
ll w=inf;
for(int k=1;k<=4;k++){
if(distance<=l[k]){
w=c[k];
break;
}
}
dis[i][j]=dis[j][i]=min(dis[i][j],w);
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
printf("Case %d:\n",o);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
if(dis[x][y]==inf){
printf("Station %d and station %d are not attainable.\n",x,y);
}else{
printf("The minimum cost between station %d and station %d is %lld.\n",x,y,dis[x][y]);
}
}
}
return 0;
}
|
题解
题意：给定一行格子、若干炮塔、若干敌人，炮塔固定一个坐标，拥有一个范围的攻击力，一次能对该范围内敌人造成攻击力的伤害，敌人在固定坐标内出现并朝着终点走，一次走一格，求最后还剩几个敌人活着
算法：差分+前缀和（倒前缀和）
很简单的前缀和题，由于敌人是朝着终点走，于是可以从终点向起点过两遍前缀和，就能求出每个点的累计伤害，然后把他跟每个敌人的生命值比较即可
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,cor[100005];
ll hp[100005],gg[100005];
int main(){
while(scanf("%d",&n)!=EOF&&n!=0){
memset(gg,0,sizeof(gg));
scanf("%d",&m);
for(int i=1;i<=m;i++){
int l,r,d;
scanf("%d%d%d",&l,&r,&d);
gg[r]+=d;
gg[l-1]-=d;
}
for(int i=n;i>=1;i--){
gg[i]=gg[i]+gg[i+1];
}
for(int i=n;i>=1;i--){
gg[i]=gg[i]+gg[i+1];
}
scanf("%d",&k);
int ans=0;
for(int i=1;i<=k;i++){
scanf("%lld%d",&hp[i],&cor[i]);
if(hp[i]<=gg[cor[i]]) ans++;
}
printf("%d\n",n-ans);
}
return 0;
}
|
题解
这题比赛时AC了，但是感觉是个比较好的贪心题，记录一下
题意：给定若干作业的DDL，以及如果交不了的话对应的惩罚分数，求最小惩罚分数
算法：贪心
让所有作业按照惩罚降序排序，惩罚相同则按DDL升序排序，然后从第一个作业开始遍历，把他放到对应的DDL做，如果这一天已经被占用了，则往前挪即可，如果挪到了第0天都没做成，则ans+对应惩罚分数
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
}a[10005];
bool vis[10005];
inline bool cmp(node x1,node x2){
if(x1.y==x2.y) return x1.x<x2.x;
return x1.y>x2.y;
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
cin>>a[i].x;
}
for(int i=1;i<=n;i++){
cin>>a[i].y;
}
sort(a+1,a+1+n,cmp);
int ans=0;
for(int i=1;i<=n;i++){
int td=a[i].x;
while(td>0&&vis[td]==1) td--;
if(td==0){
ans+=a[i].y;
}else{
vis[td]=1;
}
}
cout<<ans<<endl;
}
return 0;
}
|
题解
也AC了，但是是自己做的不多的数学题，记录一下
题意：给定$n$，求满足$y^2=n+x^2$的最小的正整数$x$
算法：数学
把题目式子变形成$(y-x)(y+x)=n$，令$i=y-x,\frac{n}{i}=y+x$，求得$x=\frac{\frac{n}{i}-i}{2},y=\frac{\frac{n}{i}+i}{2}$，由于要求最小的x，所以i可以从sqrt(n)开始遍历，满足n%i==0&&(n/i+1)%2==0&&(n/i-1)%2==0&&n/i-i!=0的第一个i即得答案
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
bool f=true;
int i=(int)sqrt(n);
for(;i>0;i--){
if(n%i==0&&(n/i+i)%2==0&&(n/i-i)%2==0&&n/i-i!=0){
cout<<(n/i-i)/2<<endl;
f=false;
break;
}
}
if(f) cout<<"-1"<<endl;
}
return 0;
}
|