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;
}

谈话重点（废话）

STL:
set
upper_bound
lower_lound
dijstral :

裸题
自己下看 floyed : 多点最短
并查集合
自己找题做
理解dfs 一步一步调试

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

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

打比赛 codeforces. 牛客网 .
补题：刷一遍老师讲过的题，遇到的比赛不会的题目

9.acm. 加分

vj. 找题给你们做

多看大牛代码
多分享，多交流

13.一定不要拖题

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,937评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,503评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,712评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,668评论 1赞 276
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,677评论 5赞 366
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,601评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,975评论 3赞 396
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,637评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,881评论 1赞 298
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,621评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,710评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,387评论 4赞 319
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,971评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,947评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,189评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 44,805评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,449评论 2赞 342

2018-03-21 第三周任务

推荐阅读更多精彩内容