11/24-提高组笔记
Avoid Knight Attack
思路
. set：自带排序以及去重的容器，把输入的点以及它周围 个点都放进 set 中，可以直接使用 pair 来完成。
欧阳宁佑同学的set代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
set<pair<ll, ll>>vis;
ll ans = 0;
ll dx[] = {0, 2, 1, -1, -2, -2, -1, 1, 2};
ll dy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
while(m--)
{
int i, j;
cin >> i >> j;
for(int p = 0; p < 9; p++)
{
if(i + dx[p] >= 1 && i + dx[p] <= n && j + dy[p] >= 1 && j + dy[p] <= n);
else continue;
vis.insert({i + dx[p], j + dy[p]});
}
}
cout << n * n - vis.size() << "\n";
}
利用 map 进行标记一个点是否已经有了，做法大概是 map[{i, j}] = 1，每个标记第一次出现，就统计一下，map + pair 来实现
map的代码
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#define ll long long
#define ull unsigned long long
#define eps 1e-10
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
using namespace std;
const ll mod1=1e9+7;
const ll mod2=998244353;
const int maxn = 2e5 + 10;
const int maxm = 2e5 + 10;
const ll inf=1e18L;
typedef pair<int,int>Pii;
typedef pair<int,ll>Pil;
using namespace std;
long long n, m;
int dx[8] = {1, 1, 2, 2, -1, -1, -2, -2};
int dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
map<Pii,int>mp;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
mp[{x, y}]++;
for(int j = 0; j < 8; j++)
{
int xx = x + dx[j];
int yy = y + dy[j];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= n)
{
mp[{xx, yy}]++;
}
}
}
cout << n * n - mp.size() << '\n';
return 0;
}
不需要使用任何你不会的东西的做法：开一个结构体数组，把所有的点都放进去。 问题就变成了 如何求一个数组内 不一样的东西有多少？
只需要sort一下，判断相邻位置是否相等即可。
沈宇泽同学的代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,a,b;
struct edge{
long long x,y;
};
bool cmp(edge c,edge d){
if(c.x>d.x){
return true;
}else if(c.x<d.x){
return false;
}else{
return c.y>d.y;
}
}
edge g[1800010];
int main(){
cin>>n>>m;
long long cnt=1;
for(long long i=1;i<=m;i++){
cin>>a>>b;
g[cnt].x=a;
g[cnt].y=b;
cnt++;
g[cnt].x=a+2;
g[cnt].y=b+1;
cnt++;
g[cnt].x=a+1;
g[cnt].y=b+2;
cnt++;
g[cnt].x=a-1;
g[cnt].y=b+2;
cnt++;
g[cnt].x=a+2;
g[cnt].y=b-1;
cnt++;
g[cnt].x=a-2;
g[cnt].y=b-1;
cnt++;
g[cnt].x=a-1;
g[cnt].y=b-2;
cnt++;
g[cnt].x=a+1;
g[cnt].y=b-2;
cnt++;
g[cnt].x=a-2;
g[cnt].y=b+1;
cnt++;
}
sort(g+1,g+cnt,cmp);
long long ans=0;
for(long long i=1;i<cnt;i++){
if((g[i].x!=g[i-1].x||g[i].y!=g[i-1].y)&&g[i].x>0&&g[i].y>0&&g[i].x<=n&&g[i].y<=n){
ans++;
}
}
cout<<n*n-ans;
}
营救
李任泽昊同学的代码
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#define ll long long
#define ull unsigned long long
#define eps 1e-10
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
using namespace std;
const ll mod1=1e9+7;
const ll mod2=998244353;
const int maxn = 2e5 + 10;
const int maxm = 1e6 + 10;
const ll inf=1e18L;
typedef pair<int,int>Pii;
typedef pair<int,ll>Pil;
using namespace std;
int n,m,p,father[10005],s,t;
int find(int x){
if(father[x]==x){
return x;
}
else{
return father[x]=find(father[x]);
}
}
int same(int x,int y){
if(find(x)==find(y)){
return 1;
}
return 0;
}
struct edge{
int u,v,cost;
}e[200005];
int cmp(edge e1,edge e2){
return e1.cost<e2.cost;
}
int kruskal(){
sort(e+1,e+1+m,cmp);
int res=0,cnt=0;
for(int i=1;i<=m;i++){
if(same(e[i].u,e[i].v)==0){
cnt++;
father[find(e[i].u)]=find(e[i].v);
}
if(find(s)==find(t)){
return e[i].cost;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>s>>t;
for(int i=1;i<=n;i++){
father[i]=i;
}
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].cost;
}
int ans=kruskal();
cout<<ans;
return 0;
}
P4779 - dij
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#define ll long long
#define ull unsigned long long
#define eps 1e-10
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
using namespace std;
const ll mod1=1e9+7;
const ll mod2=998244353;
const int maxn = 2e5 + 10;
const int maxm = 2e5 + 10;
const ll inf=1e18L;
typedef pair<int,int>P;
typedef pair<int,ll>Pil;
using namespace std;
//priority_queue<int,vector<int>,greater<int>>q;
//pair .first .second
//按照 first 排序 first 存路径长度 second 存点的编号
priority_queue<P,vector<P>,greater<P>>q;
struct edge
{
int to, cost;//这条边能到哪个点，边的长度
};
vector<edge>G[100010];
int dist[100010], n, m, s;
void dij()
{
//1.初始化
for(int i = 1; i <= n; i++)
{
dist[i] = 1e9;
}
//2.把起点放入优先队列
q.push({0, s}); dist[s] = 0;
//3.用优先队列取最小值，进行松弛操作
while(q.empty() == 0)
{
P now = q.top(); q.pop();
int v = now.second;//点的编号
// 走到 v 号点的之前最短路 会存在 dist[v]
// 如果 dist[v] < now.first
// 意味着之前到 v 的最短路，比这一次走到 v 要好
// 不好，这次求出来的长度就没意义，直接 continue
if(dist[v] < now.first) continue;
//接下来就是要做松弛操作了
//从 v 号点出发，看看能到哪些点，能不能使得这些点
//最短路变得更小。要写一个图的遍历（vector）
int siz = (int)G[v].size();
for(int i = 0; i < siz; i++)
{
edge e = G[v][i];
// v 能走到的下一个点 e.to
// v -> e.to 的边长是 e.cost
// 判断之前走到 e.to 的最短路 dist[e.to]
// 是否比 从 v 号点走过去的距离更长
// 从 v 号点走过去 = 走到 v 的最短路 + 这条边
// 从 v 号点走过去 = dist[v] + e.cost
// 如果dist[e.to] 更大，就要进行更新（松弛）
if(dist[e.to] > dist[v] + e.cost)
{
dist[e.to] = dist[v] + e.cost;
q.push({dist[e.to], e.to});
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> s;
while(m--)
{
int a, b, c;
cin >> a >> b >> c;
G[a].push_back({b, c});
}
dij();
for(int i = 1; i <= n; i++) cout << dist[i] << " ";
return 0;
}
P3371 - spfa
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#define ll long long
#define ull unsigned long long
#define eps 1e-10
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
using namespace std;
const ll mod1=1e9+7;
const ll mod2=998244353;
const int maxn = 2e5 + 10;
const int maxm = 2e5 + 10;
const ll inf=1e18L;
typedef pair<int,int>P;
typedef pair<int,ll>Pil;
using namespace std;
struct edge
{
int to, cost;//这条边能到哪个点，边的长度
};
vector<edge>G[100010];
// vis[i] 表示 i 号点是否在队列中
int dist[100010], n, m, s, vis[100010];
queue<int>q;
void spfa()
{
for(int i = 1; i <= n; i++)
{
dist[i] = (1LL << 31) - 1;
}
q.push(s); dist[s] = 0; vis[s] = 1;
while(!q.empty())
{
int now = q.front(); q.pop(); vis[now] = 0;
//松弛
int siz = (int)G[now].size();
for(int i = 0; i < siz; i++)
{
edge e = G[now][i];
if(dist[e.to] > dist[now] + e.cost)
{
dist[e.to] = dist[now] + e.cost;
if(vis[e.to] == 0)
{
q.push(e.to);
vis[e.to] = 1;
}
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> s;
while(m--)
{
int a, b, c;
cin >> a >> b >> c;
G[a].push_back({b, c});
}
spfa();
for(int i = 1; i <= n; i++) cout << dist[i] << " ";
return 0;
}
我们会审查剪贴板内容，并对发布不合适内容的同学进行相应的处理