您的位置: 首页  >  IT文章  >  【2019.7.15】

【2019.7.15】

分类: IT文章 • 2022-07-30 13:43:51

1.足球联赛 （soccer.pas/c/cpp）

hin水

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<stack>
 7 #include<algorithm>
 8 using namespace std;
 9 #define ll long long
10 #define rg register
11 #define Max(x,y) (x)>(y)?(x):(y)
12 #define Min(x,y) (x)>(y)?(y):(x)
13 const int N=100+5,M=200000+5,inf=0x3f3f3f3f,P=19650827;
14 int n,w[N],mx=0,cnt=0,ans[N];
15 char a[N][N];
16 template <class t>void rd(t &x){
17     x=0;int w=0;char ch=0;
18     while(!isdigit(ch)) w|=ch=='-',ch=getchar();
19     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
20     x=w?-x:x;
21 }
22 
23 
24 int main(){
25     freopen("soccer.in","r",stdin);
26     freopen("soccer.out","w",stdout);
27     rd(n);
28     for(int i=1;i<=n;++i) scanf("%s",a[i]+1);
29     for(int i=1;i<=n;++i)
30     for(int j=1;j<=n;++j)
31     if(i!=j){
32         if(a[i][j]=='W') w[i]+=3;
33         else if(a[i][j]=='L') w[j]+=3;
34         else if(a[i][j]=='D') ++w[i],++w[j];
35     }
36     for(int i=1;i<=n;++i){
37         if(w[i]>mx) mx=w[i],cnt=0;
38         if(w[i]==mx) ans[++cnt]=i;
39     }
40     for(int i=1;i<=cnt;++i) printf("%d ",ans[i]);
41     return 0;
42 }
43
soccer

2.最短路径 （paths.pas/c/cpp）动态规划

我打暴力居然忘了最优性剪枝！！！！在考场上骚想记忆化搜索QAQ 最后的解不仅和当前状态有关 还和后面的状态有关 不能只关注当前 这样就成贪心了

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
#define ll long long
#define rg register
#define lson o<<1
#define rson o<<1|1
#define Max(x,y) (x)>(y)?(x):(y)
#define Min(x,y) (x)>(y)?(y):(x)
const int N=1000+5,M=200000+5,inf=0x3f3f3f3f,P=19650827;
int n,b1,b2,x[N],y[N],vis[N];
double a[N][N],ans=inf;
template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

void dfs2(int nw,double dis,int pre,int fl,int cnt){
    if(nw<b2&&!fl) return;
    if(dis>=ans) return;
    dis+=a[pre][nw];
    if(nw==b2) fl=1;
    if(!nw&&fl&&cnt==n) {ans=Min(ans,dis);return;}
    for(int i=nw-1;i>=0;--i)
    if(!vis[i]) vis[i]=1,dfs2(i,dis,nw,fl,cnt+1),vis[i]=0;
}
void dfs(int nw,double dis,int pre,int fl,int cnt){
    if(nw>b1&&!fl) return;
    if(dis>=ans) return;
    dis+=a[pre][nw];
    if(nw==b1) fl=1;
    if(nw==n-1&&fl) {dfs2(nw,dis,nw,0,cnt);return;}
    for(int i=nw+1;i<n;++i)
    if(!vis[i]) vis[i]=1,dfs(i,dis,nw,fl,cnt+1),vis[i]=0;
}

int main(){
    freopen("paths2.in","r",stdin);
//    freopen("paths.out","w",stdout);
    rd(n),rd(b1),rd(b2);
    for(int i=0;i<n;++i) rd(x[i]),rd(y[i]);
    for(int i=0;i<n;++i)
    for(int j=0;j<n;++j)
    if(!a[i][j]) a[i][j]=a[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    dfs(0,0.0,0,0,0);
    printf("%.2f",ans);
    return 0;
}
20昏 暴力

和周游加拿大那个很像 从0->n-1 再从n-1->0 因为是无向图 从n-1->0可以当成另外一个人走另一条不相交的路线

for(int i=0;i<n;++i)
    for(int j=0;j<n;++j)
    if(i!=j||!i){
        int k=max(i,j)+1;
        if(k==n){
            if(i==n-1) f[n-1][n-1]=Min(f[n-1][n-1],f[i][j]+a[j][n-1]);
            if(j==n-1) f[n-1][n-1]=Min(f[n-1][n-1],f[i][j]+a[i][n-1]);
        }
        else{
            if(k!=b1) f[i][k]=Min(f[i][k],f[i][j]+a[j][k]);//n-1->0这条路线不能走b1
            if(k!=b2) f[k][j]=Min(f[k][j],f[i][j]+a[i][k]);//0->n-1这条路线不能走b2
        }
    }

好吧这是看了标程之后写的 这都是一类模型！！

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register
#define lson o<<1
#define rson o<<1|1
#define Max(x,y) (x)>(y)?(x):(y)
#define Min(x,y) (x)>(y)?(y):(x)
const int N=1000+5,M=200000+5,inf=0x3f3f3f3f,P=19650827;
int n,b1,b2,x[N],y[N],vis[N],xxx;
double a[N][N],f[N][N];
template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

int main(){
    //freopen("paths.in","r",stdin);
    rd(n),rd(b1),rd(b2);
    for(int i=0;i<n;++i) rd(x[i]),rd(y[i]);
    for(int i=0;i<n;++i)
    for(int j=0;j<n;++j){
        if(!a[i][j]) a[i][j]=a[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
        f[i][j]=99999999;
    }
    f[0][0]=0;
    for(int i=0;i<n;++i)
    for(int j=0;j<n;++j)
    if(i!=j||!i){
        int k=max(i,j)+1;
        if(k==n){
            if(i==n-1) f[n-1][n-1]=Min(f[n-1][n-1],f[i][j]+a[j][n-1]);
            if(j==n-1) f[n-1][n-1]=Min(f[n-1][n-1],f[i][j]+a[i][n-1]);
        }
        else{
            if(k!=b1) f[i][k]=Min(f[i][k],f[i][j]+a[j][k]);
            if(k!=b2) f[k][j]=Min(f[k][j],f[i][j]+a[i][k]);
        }
    }
    printf("%.2f",f[n-1][n-1]);
    return 0;
}
paths

3.阿 Q 的停车场 （park.pas/c/cpp）线段树

我瓜想了好久...我真的不可以【2019.7.15】

后面心力交瘁 连暴力都搞不来了 代码都没交

summary

相关推荐