AtCoder Beginner Contest 302（E，F，G）
E（图，set)
这个题意大致为一开始给出\(n\)个点，没有一条边，后面陆续会有\(q\)次操作，以下两种方式
\(1\),输入两个点，代表连接这两个点
\(2\),输入一个点，意在把所有和这个点相连的边都删除
每一次操作后我的都需要知道操作后还有多少个孤立无援的点（没有一个其他的点和它相连）
我也是没想到还可以直接，就像我们平时存边一样，用\(vector\)存，但是我之前后面发现不太好删除，就放弃了，其实也是有办法的（先\(find\)找到那个数的位置，然后删除）
但是我后面发现了一个更好操作的容器\(set\),这个可以直接删除那一个数而不用寻找位置
代码还是很好写的
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=3e5+10;
const int mod=998244353;
int n,q;
set<int>g[maxn];
int ans;
bool vis[maxn];
void add(int u,int v)
{
if(g[u].size()==0)
{
ans--;
}
if(g[v].size()==0)
{
ans--;
}
g[u].insert(v);
g[v].insert(u);
return ;
}
void move(int u)
{
for (auto v:g[u])
{
g[v].erase(u);
if(g[v].size()==0) ans++;
}
if(g[u].size()) ans++;
g[u].clear();
return ;
}
signed main ()
{
cin>>n>>q;
ans=n;
while (q--)
{
int op;
cin>>op;
if(op==1)
{
int u,v;
cin>>u>>v;
add(u,v);
}
else
{
int u;
cin>>u;
move(u);
}
cout<<ans<<"\n";
}
system ("pause");
return 0;
}
F（最短路）
我发现我做题的效率真是好低呀（这个题想了半天，原来理解错了）
这个大意就是给你\(n\)个集合，集合里面的数不大于\(m\),然后我们可以对这些集合进行以下操作
对于两个集合\(X,Y\),只要这两个集合存在交集，那么我们可以把这两个集合合并为一个集合
题目要求把\(1\)和\(m\)放在同一个集合需要的最小操作数
我想了半天没有什么思路，就直接讲一下我看到题解的理解
对于有交集，可以理解为这两个容器里面存在有相同的数字，那么我们看某一个数字，可以把一个数字和另外一个数字连在一起，这样像不像图论的边，然后我们把数字和边都看作一个一个的点，只是边权不一样，只有到达了容器才会有边权（我们最后只要求\(1\)到\(m\)这一段有多少个容器，再减一即可）
为了防止数字和容器重叠，把容器放在点的后面，编号为\(i+m\)
然后就按照最短路的写法，从\(1\)到达\(m\)的最小距离
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=4e5+10;
const int mod=998244353;
int n,m;
int w[maxn];
int dis[maxn];
vector<int>g[maxn];
bool vis[maxn];
struct node
{
int pos,dis;
friend bool operator <(const node x,const node y)
{
return x.dis>y.dis;
}
};
void init()
{
for (int i=1;i<=m;i++)
{
dis[i]=dis[i+m]=inf;
vis[i]=vis[i+m]=false;
}
for (int i=1;i<=n;i++)
{
dis[i+m]=inf;
vis[i+m]=false;
}
return ;
}
int dijkstra()
{
priority_queue<node>q;
init();
dis[1]=0;
q.push({1,dis[1]});
while (!q.empty())
{
int u=q.top().pos;
q.pop();
if(u==m)
{
return dis[u]-1;
}
if(vis[u]) continue;
vis[u]=true;
for (auto v:g[u])
{
if(dis[v]>dis[u]+w[v])
{
dis[v]=dis[u]+w[v];
q.push({v,dis[v]});
}
}
}
return -1;
}
signed main ()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
int k=0;
cin>>k;
w[i+m]=1;
for (int j=1;j<=k;j++)
{
int x;
cin>>x;
g[x].push_back(i+m);
g[i+m].push_back(x);
}
}
cout<<dijkstra()<<"\n";
system ("pause");
return 0;
}
G （环）
这个就是给你一个数组，（数组里面的数组不超过\(4\)),我们可以任意交换两个位置的数字，问要把这个数组变成非递减数组的最小操作
也是没有什么头绪
这个题只有\(4\)个数，那么对于那些需要改变的可能形成的环有一元环（这个不需要改变），二元环（\(<x,y>,<y,x>\)),三元环（\(<x,y>,<y,k>,<k,x>\)),四元环（\(<x,y>,<y,k>,<k,z>,<z,x>\))，这几种
我们发现情况很少，可以考虑暴力
我们发现，如果需要交换位置的话，环越小，花费就相对的越小，所以我们先考虑二元环，一个二元环交换的代价是\(1\),三元环代价是\(2\)，四元环代价是\(3\),依次枚举
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=4e5+10;
const int mod=998244353;
int n,m;
int a[maxn],b[maxn];
int cnt[5][5];
signed main ()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(a+1,a+1+n);
for (int i=1;i<=n;i++)
{
cnt[a[i]][b[i]]++;
}
int ans=0;
for (int i=1;i<=4;i++)
{
for (int j=i+1;j<=4;j++)
{
int now=min(cnt[i][j],cnt[j][i]);
ans=ans+=now;
cnt[i][j]-=now;
cnt[j][i]-=now;
}
}
for (int i=1;i<=4;i++)
{
for (int j=1;j<=4;j++)
{
for (int k=1;k<=4;k++)
{
if(i==j||i==k||j==k) continue;
int now=min(cnt[i][j],min(cnt[j][k],cnt[k][i]));
ans=ans+now*2ll;
cnt[i][j]-=now;
cnt[j][k]-=now;
cnt[k][i]-=now;
}
}
}
for (int i=2;i<=4;i++)
{
ans=ans+cnt[1][i]*3ll;
}
cout<<ans<<"\n";
system ("pause");
return 0;
}