Daliy Algorithm (GPLT)– day 94

Nothing to fear

种一棵树最好的时间是十年前，其次是现在！

那些你早出晚归付出的刻苦努力，你不想训练，当你觉的太累了但还是要咬牙坚持的时候，那就是在追逐梦想，不要在意终点有什么，要享受路途的过程，或许你不能成就梦想，但一定会有更伟大的事情随之而来。 mamba out~

2020.7.6 - 7.7

人一我十，人十我百，追逐青春的梦想，怀着自信的心，永不言弃！

GPLT - L2-020 功夫传人

坑

• 只统计得道者得功夫值！读题要仔细
• 祖师爷也可能是得道者
• printf("%.f",ans) 会自动进行四舍五入，而题目要求只输出整数部分，故只能利用强制类型转换。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>

using namespace std;
const int N = 100005;
int n;
double z , r;
vector<int> a[N];
double tot;
int dedao[N];
void dfs(int now,double val)
{
    if(dedao[now]){
        tot += val * dedao[now];
    }
    for(int i = 0;i < a[now].size(); i++)
    {
        dfs(a[now][i] ,val - val * r * 0.01);
    }
}
int main()
{
    cin >> n >> z >> r;
    int k = 0;
    for(int i = 0;i < n ;i ++)
    {
        cin >> k;
        if(k == 0){
            scanf("%d",&dedao[i]);
        }else{
            int x = 0;
            for(int j = 0;j < k;j ++)
            {
                scanf("%d", &x);
                a[i].push_back(x);
            }
        }
    }   
    dfs(0 , z);
    printf("%d\n",(int)tot);
    return 0;   
}

GPLT - L2-021 点赞狂魔

分析：

利用set记录不同得标签出现得次数，标签得平均出现次数为总数量 / 不同标签得数目。然后按照题目规则进行排序即可。

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

const int N = 505;

struct node{
    string name;
    int cnt;
    int k;
}a[N];

bool cmp(node a ,node b)
{
    if(a.cnt == b.cnt)
    {
        return (a.k * 1.0 / a.cnt) < (b.k * 1.0 / b.cnt);
    }else return a.cnt > b.cnt;
}
int main()
{
    int n;
    cin >> n;
    set<int> s;
    for(int i = 0;i < n ;i ++)
    {
        cin >> a[i].name;
        cin >> a[i].k;
        for(int j = 0;j < a[i].k; j++)
        {
            int x = 0;
            scanf("%d" ,&x);
            s.insert(x);
        }
        a[i].cnt = s.size();
        s.clear();
    }
    sort(a , a + n , cmp);
    for(int i = 0;i < 3;i ++)
    {
        if(a[i].k!=0)
        {
            if(i == 0)
                cout << a[i].name;
            else cout << " " << a[i].name;
        }else{
            if(i == 0)
                cout << "-";
            else cout << " -"; 
        }
    }
    return 0;
}

GPLT - L2-022 重排链表

没认真读题还以为要排序呢。。。，注意链表去重，老玩家了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1000005;
struct node{
    int add , val , next;
}a[N] , Link[N] ,ans[N];
int head , n , len = 0;
bool cmp(node a,node b)
{
    return a.val < b.val;
}
int main()
{
    cin >> head >> n;
    int x , y , z;
    for(int i = 0;i < n;i ++)
    {
        scanf("%d %d %d",&x , & y, &z);
        a[x] = {x , y , z};
    }
    for(int i = head ;i != -1 ;i = a[i].next)
    {
        Link[len++] = a[i];
    }
    int i = 0 , j = len - 1 ,id = 0;
    while(i < j)
    {
        ans[id++] = Link[j--];
        ans[id++] = Link[i++];
        if(i == j){
            ans[id++] = Link[i];
            break;
        }
    }
    for(int i = 0;i < len ;i ++)
    {
        if(i == len - 1)
        {
            printf("%05d %d -1\n",ans[i].add , ans[i].val);
        }else{
            printf("%05d %d %05d\n",ans[i].add , ans[i].val ,ans[i+1].add);
        }
    }
    return 0;
}

GPLT - L2-023 图着色问题

PAT叫我做人

题目只说了图是合法得，没说图是一定联通得，所以要遍历每一个未被访问得结点，不然数据点3是过不去得 惨遭毒手

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <cstring>
using namespace std;

const int N = 250005;
const int M = 505;
struct edge{
    int next;
    int to;
}e[N];
int head[M],tot;
int  n, m, k;
int color[M];
bool vis[M];
void add(int a,int b)
{
    e[tot].to = b;
    e[tot].next = head[a];
    head[a] = tot++;
}
set<int> s;
void checkColor(int now, bool &flag)
{
    vis[now] = true;
    s.insert(color[now]);
    for(int i = head[now] ; i ; i = e[i].next)
    {
        int next = e[i].to;
        if(color[now] == color[next]){
            flag = true;
            return;
        }
        if(!vis[next] && !flag)
        {
            checkColor(next , flag);
        }
    }
}
int main()
{
    cin >> n >> m >> k;
    int x , y;
    for(int i = 0;i < m;i ++)
    {
        scanf("%d %d",&x , &y);
        add(x , y);add(y , x);
    }
    int q;
    cin >> q;
    for(int i = 0;i < q;i ++)
    {
        for(int j = 1;j <= n;j ++){
            scanf("%d",&color[j]);
        }
        memset(vis , 0 , sizeof vis);
        bool flag = false;
        s.clear();
        for(int i = 1;i <= n ;i ++)
        {
            if(!vis[i] && !flag)
            {
                checkColor(i, flag);
            }
        }
        if(!flag && s.size() == k)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

GPLT - L2-024 部落

并查集模板题

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>


using namespace std;

const int N = 10005;
int f[N] , cnt[N];
bool vis[N];
int find(int k)
{
    if(k == f[k])return k;
    else return f[k] = find(f[k]);
}
int Unoin(int a,int b)
{
    int x = find(a) , y = find(b);
    f[x] = y;
}
int main()
{
    for(int i = 1;i <= N;i ++)f[i] = i;
    int n , q;
    cin >> n;
    for(int i = 0;i < n;i ++)
    {
        int k = 0;cin >> k;
        for(int j = 0;j < k;j ++)
        {
            cin >> cnt[j];
            vis[cnt[j]] = 1;
        }
        for(int j = 1;j < k;j ++)
        Unoin(cnt[j-1],cnt[j]);
    }
    int people = 0 , ans = 0;
    for(int i = 1;i <= N;i ++)
    {
        if(vis[i] == 1){
            if(i == f[i])ans++;
            people++;
        }
    }
    cout << people << " " << ans << endl;
    cin >> q;
    int a , b;
    for(int i = 0;i < q;i ++)
    {
        cin >> a >> b;
        int x = find(a) , y = find(b);
        if(x != y)printf("N\n");
        else printf("Y\n");
    }
    return 0;
}

GPLT - L2-025 分而治之

简单dfs判断连通分量即可，话说 说好的m不超过10000呢

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <cstring>
using namespace std;

const int N = 100005;
struct edge{
    int to;
    int next;
}e[N];
int head[N] , tot;
int n , m;
bool vis[N];

void add(int a , int b)
{
    e[tot].to = b;
    e[tot].next = head[a];
    head[a] = tot++;
}

bool dfs(int x)
{
    for(int i = head[x] ; i ; i = e[i].next)
    {
        int next = e[i].to;
        if(vis[next] == false)return false;
    }
    return true;
}
int main()
{
    cin >> n >> m;
    int x , y;
    for(int i = 0;i < m;i ++)
    {
        cin >> x >> y;
        if(x == y)continue;
        add(x , y) ,add(y , x);
    }
    int k , np;
    cin >> k;
    for(int time = 0;time < k;time ++)
    {
        cin >> np;
        memset(vis , 0 , sizeof vis);
        for(int i = 0;i < np;i ++)
        {
            cin >> x;
            vis[x] = 1;
        }
        bool flag = true;
        for(int i = 1;i <= n;i ++)
        {
            if(!vis[i])
            {
                if(!dfs(i))
                {
                    flag = false;
                    break;
                }
            }
        }
        if(flag)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}