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;
}
标签:AtCoder,Beginner,int,302,dis,long,maxn,include,define
From: https://www.cnblogs.com/righting/p/17429546.html