信友队暑假集训第2次测试总结：
本次比赛都出的以前做过的题，但本蒟蒻确只写了320（悲
第一题：排行榜
一道水题，秒A
#include <bits/stdc++.h>
using namespace std;
string ans[105],s[105],t[105];
int vis[105];
int main(){
int n;
cin >> n;
memset(vis,0,sizeof vis);
for(int i = 1;i <= n;i++){
cin >> s[i] >> t[i];
if(t[i]=="SAME"){
ans[i] = s[i];
vis[i]=1;
}
}
for(int i = 1;i <= n;i++){
if(t[i]=="DOWN"){
for(int j = 1;j <= i-1;j++){
if(!vis[j]){
ans[j] = s[i];
vis[j]=1;
break;
}
}
}
}
for(int i = n;i >= 1;i--){
if(t[i]=="UP"){
for(int j = n;j >= i+1;j--){
if(!vis[j]){
vis[j]=1;
ans[j] = s[i];
break;
}
}
}
}
for(int i = 1;i <= n;i++){
cout << ans[i] << "\n";
}
return 0;
}
第二题：小信吃甜筒
一道水题：秒A
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,x,y,z;
int a[100005],b[100005],c[100005],d[200005];
bool cmp(int a,int b){
return a>b;
}
signed main(){
cin >>n>>m>>x>>y>>z;
for(int i = 1;i <=x;i++){
scanf("%lld",&a[i]);
}
for(int i = 1;i <=y;i++){
scanf("%lld",&b[i]);
}
for(int i = 1;i <= z;i++){
scanf("%lld",&c[i]);
}
sort(a+1,a+1+x,cmp);
sort(b+1,b+1+y,cmp);
sort(c+1,c+1+z,cmp);
for(int i=1;i<=n;i++){
d[i]=a[i];
}
for(int i=1;i<=m;i++){
d[i+n]=b[i];
}
sort(d+1,d+1+n+m);
for(int i =1;i<=min(z,n+m);i++){
if(c[i]>=d[i]) d[i]=c[i];
}
int ans=0;
for(int i = 1;i <= n+m;i++){
ans+=d[i];
}
cout<<ans;
return 0;
}
第三题：替换字母
本来是一道贪心水题，但是想错了贪心策略，WA20
#include <bits/stdc++.h>
using namespace std;
int n,m;
string s,ss;
int main(){
cin >>n>> m;
cin >> ss;
int ans = 1e9;
for(char a='a';a<='z';a++){
int j = -1;
int cnt=0;
string s;
s=ss+a;
for(int i = 0 ;i < s.size();i++){
if(i==0 && s[i] == a){
j=i;
}else if(s[i]==a && i - j >1){
j=i;
cnt++;
}else if(i-j > m){
j=i;
cnt++;
}
}
ans=min(ans,cnt);
}
cout << ans;
return 0;
}
第四题：泽泽在巴西
调了很久，考试时都快崩溃了，考完才发现，球门到人的速度是距离×2，忘记了这个×2，不要读题太马虎，虽然改了×2只有70分，但是还要检查，需要更细心。
#include<bits/stdc++.h>
using namespace std;
int xz,yz,n,m;
int zx[305],zy[305];
double g[305][305];
int lx[305],ly[305];
bool check(int x,int y,int z){
double a =sqrt((zx[x]-zx[y])*(zx[x]-zx[y]) +(zy[x]-zy[y])*(zy[x]-zy[y]));
double b =sqrt((zx[x]-lx[z])*(zx[x]-lx[z]) +(zy[x]-ly[z])*(zy[x]-ly[z]));
double c =sqrt((zx[y]-lx[z])*(zx[y]-lx[z]) +(zy[y]-ly[z])*(zy[y]-ly[z]));
if(abs(a-b-c) > 1e-4) return true;
return false;
}
int main(){
cin >> xz >> yz >> n >>m;
for(int i = 1;i <= n;i++){
cin >> zx[i] >> zy[i];
}
for(int i = 1;i <= m;i++){
cin >> lx[i] >> ly[i];
}
memset(g,0x3f,sizeof g);
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
for(int k = 1;k <= m;k++){
if(i==j) continue;
if(check(i,j,k)){
//可以建边
g[i][j]=sqrt((zx[i]-zx[j])*(zx[i]-zx[j])+(zy[i]-zy[j])*(zy[i]-zy[j]));
g[j][i]=sqrt((zx[i]-zx[j])*(zx[i]-zx[j])+(zy[i]-zy[j])*(zy[i]-zy[j]));
}
}
}
}
for(int i=1;i<=n;i++){
g[i][n+1] = sqrt((xz-zx[i])*(xz-zx[i])+(yz-zy[i])*(yz-zy[i]));
}
for(int k =1;k <= n+1;k++){
for(int i = 1;i <= n+1;i++){
if(i == k) continue;
for(int j = 1;j <= n+1;j++){
if(j == i || j == k) continue;
g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
}
}
}
printf("%.0lf",g[1][n+1]);
return 0;
}
第五题：重要的城市
O（n^4),用弗洛伊德，秒A
#include <bits/stdc++.h>
using namespace std;
int n,m;
int u,v,w;
int dis[205][205];
int ans[205],ai;
int ids[205][205];
int vis[205][205];
int main(){
cin >>n >>m;
memset(dis,0x3f,sizeof dis);
memset(ids,0x3f,sizeof ids);
memset(vis,0x3f,sizeof ids);
for(int i = 1;i <= m;i++){
int u,v,w;
cin >> u >> v >> w;
dis[u][v]=w;
ids[u][v]=w;
dis[v][u]=w;
ids[v][u]=w;
vis[v][u]=w;
vis[u][v]=w;
}
for(int k = 1;k <= n;k++){
for(int i = 1;i <= n;i++){
if(k==i)continue;
for(int j = 1;j <= n;j++){
if(j==i||j==k)continue;
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
for(int x = 1 ; x <= n;x++){
for(int i = 1;i <= n;i++){
for(int j =1;j <= n;j++){
ids[i][j]=vis[i][j];
}
}
for(int k = 1;k <= n;k++){
if(k==x)continue;
for(int i = 1;i <= n;i++){
if(i==x)continue;
if(k==i)continue;
for(int j = 1;j <= n;j++){
if(j==x)continue;
if(j==i||j==k)continue;
ids[i][j]=min(ids[i][j],ids[i][k]+ids[k][j]);
}
}
}
int flag=0;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(i==j||i==x||j==x) continue;
if(ids[i][j] > dis[i][j]) flag=1;
}
}
if(flag){
ans[++ai] = x;
}
}
if(ai==0) cout<<"No important cities.";
else for(int i = 1;i <= ai;i++){
cout << ans[i] << " ";
}
return 0;
}
第六题：因为第四题没调出来，不想写，当时而且我很困，不想写，只想看着调