头像

卷卷死他们

南京锁金村居民大学




在线 


最近来访(146)
用户头像
微风入我怀
用户头像
M._3
用户头像
Wyz0856
用户头像
Royal
用户头像
想想yxc要怎么做
用户头像
好大的QQ
用户头像
ac一道就奖励一次
用户头像
种花家的虎式坦克
用户头像
foolwsk
用户头像
rsy
用户头像
yxc的小迷妹
用户头像
超无敌暴龙战士
用户头像
Yeshouci
用户头像
Shinytale
用户头像
codeep
用户头像
su尔
用户头像
不高兴的兽奶
用户头像
时间与生命的长度
用户头像
Song_S
用户头像
香格里拉

活动打卡代码 AcWing 1597. 社会集群

呃呃,自己用了将近1h在pat上过了,果然pat上数据不会出太大,acwing上tle了
自己的思路

1、只要有相同的爱好就可以合并,设置unordered_set,方便后续查找每个人的相同爱好。
2、依次输入每个人的爱好,加入自己的un_set中,每次加入的时候遍历前面人的un_set,看是否有相同元素,能否合并,这里时间复杂度就是N*K*N=1e9,时间限制1e8,可能tle,查找是O(1)
3、每次合并的时候可以记录合并的次数,最后合并集合的数量就是总人数减去次数。
后面我们要找所有在同一个集合中的人,将人数加到vector中,遍历所有人,从前往后找看看有没有与他在同一个集合中的人,如果有,记录人数总和,再把记录过的人都标记访问过。

#include <iostream>
#include <unordered_set>
#include <vector>
#include<algorithm>

using namespace std;

const int N = 1010;

int p[N], hob[N];
unordered_set<int>s[N];
bool vi[N]; 

int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) p[i] = i;

    int cnt = 0; //合并次数
    for (int i = 1; i <= n; i++)
    {
        int k;
        scanf("%d:", &k);

        //输入第i个人的爱好,并看是否与前i-1个人合并
        for (int j = 0; j < k; j++)
        {
            scanf("%d", &hob[j]);
            s[i].insert(hob[j]);

            //m:前i-1个人
            for (int m = 1; m < i; m++) 
            {
                if (s[m].count(hob[j]))
                {
                    int pa = find(i), pb = find(m);
                    if (pa != pb)
                    {
                        p[pa] = pb;
                        cnt++;
                    }
                }
            }
        }
    }

    cout << n-cnt << endl;

    //看哪些人的在同一个集合中
    vector<int>res;
    for (int i = 1; i <= n; i++)
    {
        if (!vi[i]) 
        {
            int num = 1; //集合中的元素个数
            for (int j = i+1; j <= n; j++)
            {
                int a = find(i), b = find(j);
                if (!vi[j])
                {
                    if (a == b)
                    {
                        num++;
                        vi[j] = true;
                    }
                }

            }
            res.push_back(num);
            vi[i] = true;
        }
    }
    sort(res.begin(), res.end(), greater<int>());
    cout << res[0];
    for (int i = 1; i < res.size(); i++) 
        cout << ' ' << res[i];
    cout << endl;

    return 0;
}

思路

1、将所有的爱好开个二维数组,有该爱好的就链接上去
2、有一个爱好的链接上有许多人,把这些人合并,一个人会有许多爱好,爱好有传递性,合并的时候会一起合并在一起。
3、注意位置下标,这里面cnt下标从1开始的

282a38d85ef6312dbbd666f64d0a3be.jpg

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010;

vector<int> hobby[N]; //二维数组,第一维是爱好,第二维是有该爱好的人
int p[N];
int cnt[N]; //祖宗集合里的人数

int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) p[i] = i;

    //编号1--n人的爱好
    for (int i = 1; i <= n; i++)
    {
        int k;
        scanf("%d:", &k);
        while (k--)
        {
            int x; //爱好
            cin >> x;
            hobby[x].push_back(i); //把这个人插到爱好中
        }
    }

    //合并所有爱好中的人
    for (int i = 1; i <= 1000; i++)
        //将后面的人与第一个人合并到同一个集合中
        for (int j = 1; j < hobby[i].size(); j++)
        {
            int a = hobby[i][0], b = hobby[i][j];
            int pa = find(a), pb = find(b);
            p[pb] = pa; //b的祖宗节点的父节点是a
        }

    //统计合并到同一个集合的个数,cnt从1开始
    for (int i = 1; i <= n; i++) cnt[find(i)]++;
    sort(cnt+1, cnt+1+n, greater<int>()); //降序

    //总共合并集合的数量就是非0集合的数量
    //sum-1是长度
    int sum = 1;
    while (cnt[sum]) sum++;

    cout << sum-1 << endl;
    cout << cnt[1];
    for (int i = 2; i < sum; i++) cout << ' ' << cnt[i];
    cout << endl;


    return 0;
} 



呃呃,自己用了将近1h在pat上过了,果然pat上数据不会出太大,acwing上tle了
自己的思路

1、只要有相同的爱好就可以合并,设置unordered_set,方便后续查找每个人的相同爱好。
2、依次输入每个人的爱好,加入自己的un_set中,每次加入的时候遍历前面人的un_set,看是否有相同元素,能否合并,这里时间复杂度就是N*K*N=1e9,时间限制1e8,可能tle,查找是O(1)
3、每次合并的时候可以记录合并的次数,最后合并集合的数量就是总人数减去次数。
后面我们要找所有在同一个集合中的人,将人数加到vector中,遍历所有人,从前往后找看看有没有与他在同一个集合中的人,如果有,记录人数总和,再把记录过的人都标记访问过。

#include <iostream>
#include <unordered_set>
#include <vector>
#include<algorithm>

using namespace std;

const int N = 1010;

int p[N], hob[N];
unordered_set<int>s[N];
bool vi[N]; 

int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) p[i] = i;

    int cnt = 0; //合并次数
    for (int i = 1; i <= n; i++)
    {
        int k;
        scanf("%d:", &k);

        //输入第i个人的爱好,并看是否与前i-1个人合并
        for (int j = 0; j < k; j++)
        {
            scanf("%d", &hob[j]);
            s[i].insert(hob[j]);

            //m:前i-1个人
            for (int m = 1; m < i; m++) 
            {
                if (s[m].count(hob[j]))
                {
                    int pa = find(i), pb = find(m);
                    if (pa != pb)
                    {
                        p[pa] = pb;
                        cnt++;
                    }
                }
            }
        }
    }

    cout << n-cnt << endl;

    //看哪些人的在同一个集合中
    vector<int>res;
    for (int i = 1; i <= n; i++)
    {
        if (!vi[i]) 
        {
            int num = 1; //集合中的元素个数
            for (int j = i+1; j <= n; j++)
            {
                int a = find(i), b = find(j);
                if (!vi[j])
                {
                    if (a == b)
                    {
                        num++;
                        vi[j] = true;
                    }
                }

            }
            res.push_back(num);
            vi[i] = true;
        }
    }
    sort(res.begin(), res.end(), greater<int>());
    cout << res[0];
    for (int i = 1; i < res.size(); i++) 
        cout << ' ' << res[i];
    cout << endl;

    return 0;
}

思路

1、将所有的爱好开个二维数组,有该爱好的就链接上去
2、有一个爱好的链接上有许多人,把这些人合并,一个人会有许多爱好,爱好有传递性,合并的时候会一起合并在一起。
3、注意位置下标,这里面cnt下标从1开始的

282a38d85ef6312dbbd666f64d0a3be.jpg

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010;

vector<int> hobby[N]; //二维数组,第一维是爱好,第二维是有该爱好的人
int p[N];
int cnt[N]; //祖宗集合里的人数

int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) p[i] = i;

    //编号1--n人的爱好
    for (int i = 1; i <= n; i++)
    {
        int k;
        scanf("%d:", &k);
        while (k--)
        {
            int x; //爱好
            cin >> x;
            hobby[x].push_back(i); //把这个人插到爱好中
        }
    }

    //合并所有爱好中的人
    for (int i = 1; i <= 1000; i++)
        //将后面的人与第一个人合并到同一个集合中
        for (int j = 1; j < hobby[i].size(); j++)
        {
            int a = hobby[i][0], b = hobby[i][j];
            int pa = find(a), pb = find(b);
            p[pb] = pa; //b的祖宗节点的父节点是a
        }

    //统计合并到同一个集合的个数,cnt从1开始
    for (int i = 1; i <= n; i++) cnt[find(i)]++;
    sort(cnt+1, cnt+1+n, greater<int>()); //降序

    //总共合并集合的数量就是非0集合的数量
    //sum-1是长度
    int sum = 1;
    while (cnt[sum]) sum++;

    cout << sum-1 << endl;
    cout << cnt[1];
    for (int i = 2; i < sum; i++) cout << ' ' << cnt[i];
    cout << endl;


    return 0;
} 


活动打卡代码 AcWing 1608. 森林里的鸟

思路
每次遍历一个树的时候,都将相邻的两个鸟合并,并记录下鸟的编号

#include <iostream>

using namespace std;

const int N = 10010;

int p[N];
int birds[10]; //一棵树中最多有10只鸟,表鸟的编号
bool vi[N]; //记录这只鸟是否被标记过

int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}

int main()
{
    int n, q;
    cin >> n;

    //不知道鸟的个数,所以全部初始化
    for (int i = 1; i <= N; i++) p[i] = i;

    int cnt = 0; //合并的次数 
    for (int i = 0; i < n; i++)
    {
        int m;
        cin >> m;

        //每棵树上的鸟
        for (int j = 0; j < m; j++) 
        {
            cin >> birds[j]; //每只鸟的编号
            vi[birds[j]] = true;
        }

        //将这棵树上的m只鸟合并,每次合并相邻的2只鸟
        for (int j = 1; j < m; j++)
        {
            int a = birds[j-1], b = birds[j];
            int pa = find(a), pb = find(b);
            if (pa != pb)
            {
                p[pa] = pb;
                cnt++;
            }
        }
    }

    //把所有标记访问过的鸟加起来
    int tot = 0; //鸟的总数
    for (int i = 0; i < N; i++) tot += vi[i];

    printf("%d %d\n", tot-cnt, tot); //树的数量为鸟数量-合并次数,
    //询问
    cin >> q;
    while (q--)
    {
        int a, b;
        cin >> a >> b;
        int pa = find(a), pb = find(b);

        if (pa != pb) puts("No");
        else puts("Yes");
    }



    return 0;
}




思路
每次遍历一个树的时候,都将相邻的两个鸟合并,并记录下鸟的编号

#include <iostream>

using namespace std;

const int N = 10010;

int p[N];
int birds[N]; //一棵树中最多有N只鸟,表鸟的编号,PAT上没说范围
bool vi[N]; //记录这只鸟是否被标记过

int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}

int main()
{
    int n, q;
    cin >> n;

    //不知道鸟的个数,所以全部初始化
    for (int i = 1; i <= N; i++) p[i] = i;

    int cnt = 0; //合并的次数 
    for (int i = 0; i < n; i++)
    {
        int m;
        cin >> m;

        //每棵树上的鸟
        for (int j = 0; j < m; j++) 
        {
            cin >> birds[j]; //每只鸟的编号
            vi[birds[j]] = true;
        }

        //将这棵树上的m只鸟合并,每次合并相邻的2只鸟
        for (int j = 1; j < m; j++)
        {
            int a = birds[j-1], b = birds[j];
            int pa = find(a), pb = find(b);
            if (pa != pb)
            {
                p[pa] = pb;
                cnt++;
            }
        }
    }

    //把所有标记访问过的鸟加起来
    int tot = 0; //鸟的总数
    for (int i = 0; i < N; i++) tot += vi[i];

    printf("%d %d\n", tot-cnt, tot); //树的数量为鸟数量-合并次数,
    //询问
    cin >> q;
    while (q--)
    {
        int a, b;
        cin >> a >> b;
        int pa = find(a), pb = find(b);

        if (pa != pb) puts("No");
        else puts("Yes");
    }



    return 0;
}



活动打卡代码 AcWing 1485. 战争中的城市

思路

1、k个连通块连接成1个连通块要k-1条边,所以这题就是算有几个连通块
2、k次询问,每次都先初始化连通块,遍历所有边,将与这个点无关的边的点连通,就求出了连通块数量。
3、时间复杂度:k次询问,每次都要初始化,遍历边,所以O(K*(N+M))
4、数据大,用scanf

#include <iostream>

using namespace std;

const int N = 1010, M = N*N/2;

int p[N]; //祖宗节点
int n, m, k;

struct Edge
{
    int a, b;
}e[M];

int find(int x) //找祖宗节点
{
    return p[x] == x ? x : p[x] = find(p[x]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) 
        scanf("%d%d", &e[i].a, &e[i].b);

    while (k--)
    {
        int x; 
        scanf("%d", &x);

        //初始化并查集
        for (int i = 1; i <= n; i++) p[i] = i;
        int cnt = n-1; //连通块数量,去掉了x点,所以只有n-1

        //遍历所有边,合并与这个点不关联的点
        for (int i = 0; i < m; i++)
        {
            int a = e[i].a, b = e[i].b;
            if (a != x && b != x) //与这个点无关
            {
                int pa = find(a), pb = find(b);
                if (pa != pb) //若这两个点不连通
                {
                    p[pa] = pb;
                    cnt--; //连通块数量--
                }
            }
        }

        printf("%d\n", cnt-1);
    }


    return 0;
}



思路

1、k个连通块连接成1个连通块要k-1条边,所以这题就是算有几个连通块
2、k次询问,每次都先初始化连通块,遍历所有边,将与这个点无关的边的点连通,就求出了连通块数量。
3、时间复杂度:k次询问,每次都要初始化,遍历边,所以O(K*(N+M))
4、数据大,用scanf

#include <iostream>

using namespace std;

const int N = 1010, M = N*N/2;

int p[N]; //祖宗节点
int n, m, k;

struct Edge
{
    int a, b;
}e[M];

int find(int x) //找祖宗节点
{
    return p[x] == x ? x : p[x] = find(p[x]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) 
        scanf("%d%d", &e[i].a, &e[i].b);

    while (k--)
    {
        int x; 
        scanf("%d", &x);

        //初始化并查集
        for (int i = 1; i <= n; i++) p[i] = i;
        int cnt = n-1; //连通块数量,去掉了x点,所以只有n-1

        //遍历所有边,合并与这个点不关联的点
        for (int i = 0; i < m; i++)
        {
            int a = e[i].a, b = e[i].b;
            if (a != x && b != x) //与这个点无关
            {
                int pa = find(a), pb = find(b);
                if (pa != pb) //若这两个点不连通
                {
                    p[pa] = pb;
                    cnt--; //连通块数量--
                }
            }
        }

        printf("%d\n", cnt-1);
    }


    return 0;
}



要注意的几点

1、当遍历了所以要填的位置,发现都是满的,查找次数就为s+1(PAT中未说明这点)
2、当询问的数不在表中,找到的第一个空闲位置就把他插到表中,记作查找成功

第一点说明;当找到初始位置的时候算第一次查找,后面查找是t+0^2, t+1^2....所以最多s+1

#include <iostream>

using namespace std;

const int N = 100010;

int h[N];
int s, n, m; //s:表长,n:要插入的个数, m:询问个数

bool is_prime(int x)
{
    if (x == 1) return false;
    for (int i = 2; i <= x/i; i++)
        if (x % i == 0) 
            return false;

    return true;
}

int find(int x, int& cnt) //返回插入x的地方,cnt:查询次数
{
    int t = x % s; //第一次查找的地方
    cnt = 1; 

    for (int k = 0; k < s; k++)
    {
        int p = (t + k*k) %s;

        //当查找的地方为空,说明这个元素没有被插到表中,记作成功
        //当查找到的元素就是表中元素,查找成功
        if (!h[p] || h[p] == x) return p; 
        cnt++;
    }

    return -1;
}

int main()
{
    cin >> s >> n >> m;
    while (!is_prime(s)) s++;

    //插入
    for (int i = 0; i < n; i++)
    {
        int x, cnt;
        cin >> x;
        int t = find(x, cnt);
        if (t == -1) //插入失败
            printf("%d cannot be inserted.\n", x);
        else
            h[t] = x;
    }

    //询问
    int sum = 0; //查找总和
    for (int i = 0; i < m; i++)
    {
        int x, cnt ;
        cin >> x;
        int t = find(x, cnt);
        sum += cnt;
    }
    printf("%.1f\n", 1.0*sum/m);

    return 0;
}



要注意的几点

1、当遍历了所以要填的位置,发现都是满的,查找次数就为s+1(PAT中未说明这点)
2、当询问的数不在表中,找到的第一个空闲位置就把他插到表中,记作查找成功

第一点说明;当找到初始位置的时候算第一次查找,后面查找是t+0^2, t+1^2....所以最多s+1

#include <iostream>

using namespace std;

const int N = 100010;

int h[N];
int s, n, m; //s:表长,n:要插入的个数, m:询问个数

bool is_prime(int x)
{
    if (x == 1) return false;
    for (int i = 2; i <= x/i; i++)
        if (x % i == 0) 
            return false;

    return true;
}

int find(int x, int& cnt) //返回插入x的地方,cnt:查询次数
{
    int t = x % s; //第一次查找的地方
    cnt = 1; 

    for (int k = 0; k < s; k++)
    {
        int p = (t + k*k) %s;

        //当查找的地方为空,说明这个元素没有被插到表中,记作成功
        //当查找到的元素就是表中元素,查找成功
        if (!h[p] || h[p] == x) return p; 
        cnt++;
    }

    return -1;
}

int main()
{
    cin >> s >> n >> m;
    while (!is_prime(s)) s++;

    //插入
    for (int i = 0; i < n; i++)
    {
        int x, cnt;
        cin >> x;
        int t = find(x, cnt);
        if (t == -1) //插入失败
            printf("%d cannot be inserted.\n", x);
        else
            h[t] = x;
    }

    //询问
    int sum = 0; //查找总和
    for (int i = 0; i < m; i++)
    {
        int x, cnt ;
        cin >> x;
        int t = find(x, cnt);
        sum += cnt;
    }
    printf("%.1f\n", 1.0*sum/m);

    return 0;
}


活动打卡代码 AcWing 1630. 期终成绩

https://www.acwing.com/solution/content/143343/
1561. PAT 评测(结构体内部构造函数)(unordered_map<string,Student)(扫描指针找排名)

思路:
因为有分别多次输入同一个名字的线上,期中,期末成绩,所以不能直接在结构体内部中初始化,必须要重构(类似java思想),然后在内部也构建一个计算总成绩的函数,再在结构体内部重载小于号,有多个关键字。
要快速知道现在这个名字的所有信息,所以要建立<unordered_map> 将名字与结构体映射起来

重构
重构是隐藏的,在生成这个结构体的时候,若它还没有生成结构体成员,就会默认调用重构函数,所以无需自己调用

struct Node
{
    string name;
    int grade;

    Node() : grade(0) //grade 初始化为0
    {
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>

using namespace std;

struct Student
{
    string name;
    int p, mid_g, final_g, grade; //grade:总成绩

    //将线上,期中,期末的成绩都初始化为-1, 
    //重构函数,创建一个结构体的时候就默认调用
    Student() : p(-1), mid_g(-1), final_g(-1), grade(0){}

    //计算总成绩
    void calc()
    {
        if (final_g >= mid_g) grade = final_g;
        else grade = round(mid_g*0.4 + final_g*0.6);
    }

    //排序,重载小于号
    bool operator < (const Student& t)
    {
        if (grade != t.grade) //第一关键字:按总成绩降序
            return grade > t.grade;
        else //第二关键字:按名字升序
            return name < t.name;
    }
}student;

int main()
{
    int p, m, n; //线上,期中,期末的人数
    cin >> p >> m >> n;

    unordered_map<string, Student> map; //建立名字与结构体的映射关系,可以直接查找到名字
    string name;
    int x;

    //线上
    for (int i = 0; i < p; i++)
    {
        cin >> name >> x;
        map[name].name = name;
        map[name].p = x;
    }

    //期中
    for (int i = 0; i < m; i++)
    {
        cin >> name >> x;
        map[name].name = name;
        map[name].mid_g = x;
    }

    //期末
    for (int i = 0; i < n; i++)
    {
        cin >> name >> x;
        map[name].name = name;
        map[name].final_g = x;
    }

    //将符合条件的人加到答案中
    vector<Student> res;
    for (auto item : map)
    {
        auto stu = item.second; //stu:结构体
        stu.calc();

        if (stu.p >= 200 && stu.grade >= 60) 
            res.push_back(stu);
    }

    //排序
    sort(res.begin(), res.end());

    //输出
    for (auto c : res)
     {
         cout << c.name << ' ' << c.p << ' '<< c.mid_g;
         cout << ' ' << c.final_g << ' ' << c.grade << endl;
     }


    return 0;
}




https://www.acwing.com/solution/content/143343/
1561. PAT 评测(结构体内部构造函数)(unordered_map<string,Student)(扫描指针找排名)

思路:
因为有分别多次输入同一个名字的线上,期中,期末成绩,所以不能直接在结构体内部中初始化,必须要重构(类似java思想),然后在内部也构建一个计算总成绩的函数,再在结构体内部重载小于号,有多个关键字。
要快速知道现在这个名字的所有信息,所以要建立<unordered_map> 将名字与结构体映射起来

重构
重构是隐藏的,在生成这个结构体的时候,若它还没有生成结构体成员,就会默认调用重构函数,所以无需自己调用

struct Node
{
    string name;
    int grade;

    Node() : grade(0) //grade 初始化为0
    {
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>

using namespace std;

struct Student
{
    string name;
    int p, mid_g, final_g, grade; //grade:总成绩

    //将线上,期中,期末的成绩都初始化为-1, 
    //重构函数,创建一个结构体的时候就默认调用
    Student() : p(-1), mid_g(-1), final_g(-1), grade(0){}

    //计算总成绩
    void calc()
    {
        if (final_g >= mid_g) grade = final_g;
        else grade = round(mid_g*0.4 + final_g*0.6);
    }

    //排序,重载小于号
    bool operator < (const Student& t)
    {
        if (grade != t.grade) //第一关键字:按总成绩降序
            return grade > t.grade;
        else //第二关键字:按名字升序
            return name < t.name;
    }
}student;

int main()
{
    int p, m, n; //线上,期中,期末的人数
    cin >> p >> m >> n;

    unordered_map<string, Student> map; //建立名字与结构体的映射关系,可以直接查找到名字
    string name;
    int x;

    //线上
    for (int i = 0; i < p; i++)
    {
        cin >> name >> x;
        map[name].name = name;
        map[name].p = x;
    }

    //期中
    for (int i = 0; i < m; i++)
    {
        cin >> name >> x;
        map[name].name = name;
        map[name].mid_g = x;
    }

    //期末
    for (int i = 0; i < n; i++)
    {
        cin >> name >> x;
        map[name].name = name;
        map[name].final_g = x;
    }

    //将符合条件的人加到答案中
    vector<Student> res;
    for (auto item : map)
    {
        auto stu = item.second; //stu:结构体
        stu.calc();

        if (stu.p >= 200 && stu.grade >= 60) 
            res.push_back(stu);
    }

    //排序
    sort(res.begin(), res.end());

    //输出
    for (auto c : res)
     {
         cout << c.name << ' ' << c.p << ' '<< c.mid_g;
         cout << ' ' << c.final_g << ' ' << c.grade << endl;
     }


    return 0;
}