2018-03-21 第三周任务

两种排序方式

#include<iostream>
#include<algorithm>
using namespace std;
#define N 100005
#define INF 0x3f3f3f3f
typedef long long ll;
int b[5]={5,4,3,1,2};
int c[5]={0,1,2,3,4};
bool cmp(int x,int y){
   if(b[x]>b[y]){
       return 0;
   }
   return  1;
}
int main()
{
   
   int a[5]={5,4,3,1,2};
   sort(a,a+5);
   for(int i=0;i<5;i++){
       cout<<a[i]<<" ";
   }
   
   
   cout<<endl;
   sort(c,c+5,cmp);
   for(int i=0;i<5;i++){
       cout<<c[i]<<" ";
   }
   
   
   cout<<endl;
   return 0;
}

L2-002. 链表去重
有时候 一直写不出来就重新写一遍吧。

#include<bits/stdc++.h>
using namespace std;
struct Node{
int x;
int next;
}node[100005];
bool vis[100005];
bool v2[100005];
int q1[100005];
int q2[100005];
int main()
{

    int start,n;
    cin>>start>>n;
    memset(vis,0,sizeof(vis));
    memset(v2,0,sizeof(v2));
    for(int i=0;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        node[a].x=b;node[a].next=c;
    }

    int y=start;
    int cn=0;
    int c1,c2;c1=c2=0;
    while(y!=-1){
        if(vis[abs(node[y].x)]==0){
            cn++;
            vis[abs(node[y].x)]=1;
            v2[y]=1;
            q1[c1++]=y;
        }else{
        q2[c2++]=y;
        }
        y=node[y].next;
    }
    printf("%05d %d ",q1[0],node[q1[0]].x);
    for(int i=1;i<c1;i++){
    printf("%05d\n%05d %d ",q1[i],q1[i],node[q1[i]].x);
    }
printf("-1\n");
if(c2>0){

    printf("%05d %d ",q2[0],node[q2[0]].x);
    for(int i=1;i<c2;i++){
    printf("%05d\n%05d %d ",q2[i],q2[i],node[q2[i]].x);
    }
printf("-1\n");
}


    return 0;
}
/*
00000 2
00000 1 00002
00002 1 -1

00000 3
00000 1 00002
00002 2 00003
00003 1 -1
*/

L2-001. 紧急救援

我这道题败在 细节，还是 TM 的这个图是一个 无向图？？！！！

#include<bits/stdc++.h>
using namespace std;
#define N 505
#define INF 0x3f3f3f3f
int n,m,s,d;
int dis[N];
int num[N];
int ma[N][N];
int pre[N];
int sumnum[N];
bool vis[N];
int l[N];
void dij(){

vis[s]=1;
sumnum[s]=num[s];
dis[s]=0;
    int k=s;
    int mi=INF;

for(int i=0;i<n-1;i++){


     mi=INF;
    for(int j=0;j<n;j++){
        if(!vis[j]){
            if(dis[j]<mi){
                mi=dis[j];
                k=j;
            }
        }
    }
     vis[k]=1;
     for(int j=0;j<n;j++){
        if(!vis[j]){
            if(dis[j]>dis[k]+ma[k][j]){
                dis[j]=dis[k]+ma[k][j];
                pre[j]=k;
                sumnum[j]=sumnum[k]+num[j];
                l[j]=l[k];
            }else if (dis[j]==dis[k]+ma[k][j]){

                l[j]=l[j]+l[k];
                if(sumnum[j]<sumnum[k]+num[j]){
               pre[j]=k;
                     sumnum[j]=sumnum[k]+num[j];
                }
            }
        }
    }

}
}
int p[N];
int cn=0;
void print(int x){
if(x==-1)
    return;
    print(pre[x]);
    p[cn++]=x;
}
int main()
{
    memset(dis,0x3f,sizeof(dis));
    memset(ma,0x3f,sizeof(ma));
    memset(pre,-1,sizeof(pre));
    memset(vis,0,sizeof(vis));

    cin>>n>>m>>s>>d;
    for(int i=0;i<n;i++){
        l[i]=1;
    }
    for(int i=0;i<n;i++)ma[i][i]=0;
    for(int i=0;i<n;i++){cin>>num[i];sumnum[i]=num[i];}
    for(int i=0;i<m;i++)
      {
          int a,b,c;
          cin>>a>>b>>c;
          ma[a][b]=min(ma[a][b],c);
          ma[b][a]=ma[a][b];
          if(a==s){
            dis[b]=min(c,dis[b]);
            sumnum[b]=sumnum[s]+sumnum[b];
            pre[b]=s;
          }
          if(b==s){
            dis[a]=min(c,dis[a]);
            sumnum[a]=sumnum[s]+sumnum[a];
            pre[a]=s;
          }
      }

     dij();
     cout<<l[d]<<" ";
     print(d);
     cout<<sumnum[d]<<endl;cout<<p[0];

     for(int i=1;i<cn;i++){cout<<" "<<p[i];}cout<<endl;

    return 0;
}

L2-020. 功夫传人

dfs 递归

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define INF 0x3f3f3f3f
typedef long long ll;
struct Node{
    bool de=false;
    double fen=0;
    int  bei=0;
    int father=0;
}node[N];
bool vis[N];
double ans=0;
double fen[N]={0};
int n;double z,r;
double dfs(int x){
if(fen[x]!=0){
    return fen[x];
}else{

if(node[x].de){
    fen[x]=node[x].bei*dfs(node[x].father)*((100.0-r)/100.0);
}else{
     fen[x]=((100.0-r)/100.0)*dfs(node[x].father);
}
}
return fen[x];
}
int main()
{

    cin>>n>>z>>r;
    memset(vis,0,sizeof(vis));
    int k;
    for(int i=0;i<n;i++){
        cin>>k;
        int a;
        if(k==0){
            cin>>a;
            node[i].de=true;
            node[i].bei=a;

        }else{
         for(int j=0;j<k;j++){

            cin>>a;
            node[a].father=i;
         }

        }
    }
    fen[0]=z;
    if(n==1){
        fen[0]*=node[0].bei;
    }
    for(int i=0;i<n;i++){
        double x;
        x=dfs(i);
        if(node[i].de)
        ans+=x;
       // cout<<x<<endl;
    }
    ll ans2=(ll)ans;
   printf("%lld",ans2);
    return 0;
}

L2-021. 点赞狂魔

水题

#include<bits/stdc++.h>
using namespace std;
#define N 10000005
#define INF 0x3f3f3f3f
typedef long long ll;
struct Node{
    string name;
    int sum=0;
    int dif=0;
}node[101];

bool cmp(struct Node a,struct Node b){
if(a.dif==b.dif) return a.sum<b.sum;
return a.dif>b.dif;
}
bool vis[N];
int main()
{

    int n;
    int cn;
    int a;
    cin>>n;
    for(int i=0;i<n;i++){

        cin>>node[i].name;
        cin>>cn;
        node[i].sum=cn;
        memset(vis,0,sizeof(vis));
        for(int j=0;j<cn;j++){
                cin>>a;
            if(!vis[a]){
                node[i].dif++;
                vis[a]=1;
            }
        }
       // cout<<node[i].dif<<endl;
    }
     sort(node,node+n,cmp);
//
//    for(int i=0;i<n;i++){
//        cout<<node[i].name<<"  "<<node[i].dif<<" "<<node[i].sum<<endl;
//    }
    cout<<node[0].name;
    for(int i=1;i<3;i++){
        if(n<=i)
            {cout<<" -";}
        else cout<<" "<<node[i].name;
    }
    return 0;
}

L2-023. 图着色问题
水题

#include<bits/stdc++.h>
using namespace std;
#define N 1000
#define INF 0x3f3f3f3f
typedef long long ll;
bool vis[N];
int ma[N][N];
int v,e,k;
int yan[N];
int t;
int a,b;
bool vy[N];
int main()
{

    cin>>v>>e>>k;
    for(int i=0;i<e;i++){
        cin>>a>>b;
        ma[a][b]=1;ma[b][a]=1;
    }
    cin>>t;
    for(int i=0;i<t;i++){
        memset(vy,0,sizeof(vy));
        for(int  ii=0;ii<=v;ii++)yan[ii]=0;
        
        
        int cn=0;
        
        
        for(int j=1;j<=v;j++){
            cin>>yan[j];
            if(!vy[yan[j]]){
                vy[yan[j]]=1;
                cn++;
            }
        }

        int flag=1;
        if(cn!=k)flag=0;
        for(int x=1;x<=v&&flag;x++){
            for(int y=x+1;y<=v&&flag;y++){
                if(ma[x][y]){
                    if(yan[x]==yan[y]){
                        flag=0;
                    }
                }
            }
        }
        if(flag){
            cout<<"Yes"<<endl;
        }else cout<<"No"<<endl;
    }
    return 0;
}

L2-013. 红色警报

dfs

#include<bits/stdc++.h>
using namespace std;
#define N 505
int n,m;
int ma[N][N];
bool vis[N];
bool city[N];
int dfs(int i){
if(vis[i])
    return 0;
    vis[i]=1;
for(int j=0;j<n;j++){
        if(ma[i][j])
         dfs(j);
}
return 1;
}

int cnfun(){
    memset(vis,0,sizeof(vis));
    int cn=0;
        for(int i=0;i<n;i++){
                if(!city[i])
            cn+=dfs(i);
        }
        return cn;
}

int main()
{


    while(cin>>n>>m){
        memset(ma,0,sizeof(ma));
        memset(vis,0,sizeof(vis));
        memset(city,0,sizeof(city));
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            ma[a][b]=1;ma[b][a]=1;
        }
        int cn=cnfun();
      //   cout<<cn<<" dfg "<<endl;
        int k;
        int t;
        cin>>k;
        int pre=cn;
        for(int i=0;i<k;i++){

            cin>>t;
            for(int i=0;i<n;i++){
                if(ma[i][t]==1){
                    ma[i][t]=0;ma[t][i]=0;
                }
            }
            city[t]=1;
            cn=cnfun();
        //       cout<<cn<<" dfg "<<endl;
            if(cn>pre){
                cout<<"Red Alert: City "<<t<<" is lost!\n";
            }else{
            cout<<"City "<<t<<" is lost.\n";
            }
            pre=cn;
        }
        cn=cnfun();
        // cout<<cn<<" dfg "<<endl;
        if(cn==0){cout<<"Game Over.\n";}

    }
    return 0;
}

L2-015. 互评成绩

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k,m;
double x[10004];
double ma,mi,t;

int main()
{


    while(cin>>n>>k>>m){
        for(int i=0;i<n;i++)
            x[i]=0;
        for(int i=0;i<n;i++){
            ma=0,mi=101;
            for(int j=0;j<k;j++){
                cin>>t;
                x[i]+=t;
                ma=max(ma,t);
                mi=min(mi,t);

            }
            x[i]=(x[i]-ma-mi)/(k-2);
        }
        sort(x,x+n);
        printf("%.3lf",x[n-m]);
        for(int i=n-m+1;i<n;i++){
        printf(" %.3lf",x[i]);
        }
        cout<<endl;
    }
    return 0;
}

L2-014. 列车调度
题解

L2-016. 愿天下有情人都是失散多年的兄妹

最后一个样例 没过 ------------------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 200005
struct Node{


int se=1;
int father=-1;
int mather=-1;
}node[N];
bool dfs(int x,int y,int ce){

if(ce>4){
    return false;
}
else{
        if(x==-1||y==-1)
        return false;
        if(x==y&&x!=-1){
           return true;
        }


        if(dfs(node[x].father,node[y].father,ce+1)||
        dfs(node[x].father,node[y].mather,ce+1)||
        dfs(node[x].mather,node[y].mather,ce+1)||
        dfs(node[x].mather,node[y].father,ce+1)) return true;
        return false;
}
}
bool check(int x,int y){

return dfs(x,y,0);

}
int main()
{
int a,b,d;
char c;
int n;
    while(cin>>n){

            for(int i=0;i<n;i++){
        cin>>a>>c>>b>>d;
        if(c=='F'){
          node[a].se=0;
        }

        node[a].father=b;node[a].mather=d; node[d].se=0;}

        int k;
        cin>>k;
        for(int i=0;i<k;i++){
            cin>>b>>d;
             if(node[b].se==node[d].se){
                cout<<"Never Mind"<<endl;
            }else{
            if(!check(b,d)){
                cout<<"Yes"<<endl;
            }
            else{
                cout<<"No"<<endl;
            }
            }
        }
    }
    return 0;
}

谈话重点（废话）

1. STL:
   set
   upper_bound
   lower_lound

2. dijstral :

   裸题
   自己下看 floyed : 多点最短

3. 并查集合
   自己找题做

4. 理解dfs 一步一步 调试

5.代码 风格。。 命名规范。 尽量写成函数。

6. 杭电11 页 或 codeforces 1，2 A，B 题

7. 打比赛 codeforces. 牛客网 .

8. 补题 ： 刷一遍老师讲过的题， 遇到的比赛 不会的题目

9.acm. 加分

10. vj. 找题给你们做

11. 多看 大牛 代码

12. 多分享，多交流

13.一定不要 拖题