日常训练补题

7-10 红色警报 - SMU 2024 spring 天梯赛2(补题) (pintia.cn)

题解：这题是一道暴力思维题

我们需要先统计一下最初的点的连通块

然后在一个个删除，每删除一次就跑一个并查集，在统计连通块的个数，然后对比前一次，看看连通块有没有变多即可

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+10,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
int kmp(int a,int k,int p)
{
    int ans=1;
    while (k)
    {
        if(k&1) ans=ans*a%p;
        k>>=1;
        a=a*a;
    }
    return ans;
}
int fa[N];
int find(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
void add(int x,int y)
{
    x=find(x),y=find(y);
    if(x!=y)
    {
        fa[x]=y;
    }
    return;
}
int x[N],y[N];
map<int,int> mp;
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int v,u;
        cin>>v>>u;
        add(v,u);

7-15 特殊堆栈 - SMU 2024 spring 天梯赛2(补题) (pintia.cn)

题解：这道题就是类似于模拟，但是我们需要处理中位数

思维一：用一个栈每次输入输出，记录这个栈里有没有东西，没有东西我们就需要返回错误

然后用对顶堆的思维去维护一下中位数即可   但是这里用优先队列不能用，因为不能删除我们插入的数，所以我们改用

multiset 这个函数相当于没有去重功能的set  然后用迭代器二分跑一下我们要输出元素的位置即可
输出就输出当个堆中间那个即可

思维二：还是这个中位数的问题，我们其实可以不用对顶堆
我们用一个vector然后删除的时候和上面一样二分删除 用迭代器
插入也是二分插入，二分插入让数组有序化然后正常输出中位数即可

void solve()
{
    int n;
    cin>>n;
    vector<int> a;
    stack<int> q;
    vector<int> ::iterator it;
    int r=0;

    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        int x;
        if(s=="Pop")
        {
            if(q.size()!=0) {
                it= lower_bound(a.begin(),a.end(),q.top());
                a.erase(it);
                cout<<q.top()<<endl;
                q.pop();

            }
            else
            {
                cout<<"Invalid"<<endl;
            }

        }
        if(s=="Push")
        {
            cin>>x;
            q.push(x);
            it = lower_bound(a.begin(),a.end(),x);
            a.insert(it,x);
        }
        if(s=="PeekMedian")
        {
            if(!q.empty())
            {
                int y=a.size();
                if(y%2) y++;
                y/=2;
                cout<<a[y-1]<<endl;
            }
            else
            {
                cout<<"Invalid"<<endl;
            }
        }
    }
}
signed main(){
//    std::ios::sync_with_stdio(false);
//    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

 7-11 排座位 - SMU 2024 spring 天梯赛2 (pintia.cn)

题解：这道题少了3分，因为题目看漏了一个条件，就是朋友的朋友也是朋友，我直接判断的朋友的朋友不是朋友，所以少3分

这道题我们可以用并查集维护一下即可，就看看敌人有没有共同的祖先即可满分

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
#define endl '\n'
using namespace std;
const int N=9e3+10,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
int kmp(int a,int k,int p)
{
    int ans=1;
    while (k)
    {
        if(k&1) ans=ans*a%p;
        k>>=1;
        a=a*a;
    }
    return ans;
}

int a[N][N];
vector<int> b[N];
int fa[N];
int find(int x)
{
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}
void add(int x,int y)
{
    x=find(x),y=find(y);
    if(x!=y)
    {
        fa[x]=y;
    }
}

void solve()
{
    int n;
    cin>>n;
    int m;
    cin>>m;
    int k;
    cin>>k;
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        int op;
        cin>>x>>y>>op;
        if(op==-1)
        {
            a[x][y]=-1;
            a[y][x]=-1;
        }
        else
        {
            a[x][y]=1;
            a[y][x]=1;
            add(x,y);
            b[x].push_back(y);
            b[y].push_back(x);
        }
    }
    while (k--)
    {
        int x,y;
        cin>>x>>y;
        if(a[x][y]==0)
        {
            cout<<"OK"<<endl;
        }
        else if(a[x][y]==1)
        {
            cout<<"No problem"<<endl;
        }
        else if(a[x][y]==-1)
        {
            int f=0;
            if(find(x)==find(y)) f=1;
            if(f)
            {
                cout<<"OK but..."<<endl;
            }
            else
            {
                cout<<"No way"<<endl;
            }
        }
    }

}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}