2021 RoboCom 世界机器人开发者大赛-本科组（初赛）
7-1 懂的都懂 (20 分)
题目描述：
原图由n个数字构成，其他图片与原图相似的条件是图片中的每一个数字都可以由原图中任意位置不重合的四个数字求平均数得到，给你k个图片，问这个图片和原图相似吗
思路：
暴力算出原图能产生的所有的平均数，用map存一下，然后判断即可
当然，可以不求平均数，直接存数字和，不除4，这样就不会被卡
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define MAX 100000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int n, k, num;
int sum, x;
map<int, int>mp;
int tr[MAX];
void work(){
cin>>n>>k;
for(int i = 1; i <= n; ++i){
cin>>tr[i];
}
for(int a = 1; a <= n; ++a){
for(int b = a + 1; b <= n; ++b){
for(int c = b + 1; c <= n; ++c){
for(int d = c + 1; d <= n; ++d){
mp[tr[a] + tr[b] + tr[c] + tr[d]] = 1;
}
}
}
}
while (k--) {
cin>>num;
bool p = 0;
while (num--) {
cin>>x;
if(mp[x * 4] == 0)p = 1;
}
if(p)cout<<"No\n";
else cout<<"Yes\n";
}
}
int main(){
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
7-2 芬兰木棋 (25 分)
题目描述：
平面坐标系，有若干木棍，你可以选择任意一个方向选择击倒任意数量的木棍，得到分数的规则如下
- 击倒一根木棍，则获得木棍上的分数
- 击倒2根或以上的木棍，则只得到击倒的木棍的数量（例如击倒5根得5分
问能得到的最大价值是多少，获得价值最大的情况下需要的操作数量最少为多少
思路：
价值为1的点无论是连着打还是分开打，得到的价值都是1，但价值不是1的点必须挨个打，才能得到最大价值
所以得到最大价值的情况下，让所有连着的1都一起打，这样就能得到最小操作数量
这里有两个思路，一个是存斜率，一个是存pair
先说存斜率，比赛的时候我就存的斜率，（但是写假了），主要的思路是通过map来将斜率映射成整数cnt，开个套pair的vector数组，将相同的斜率的点的(横坐标x和价值z)作为一个pair放进对应的cnt对应的vector里面，分别处理四个象限和四条坐标轴，计算的时候就先排个序，因为pair排序的时候先按第一关键字(即横坐标)来排序，就可以得到处理好的所有的点，然后再判断相连的1的数量，给ans减掉即可
存pair的方法是根据一个斜率会对应一个(a,b)，gcd(a, b) = 1，用一个map<pari, int>将所有的(a,b)对映射成整数来存，同样也要用vector< pair >存横坐标x与价值z，再剩下的和第一次的一样
//存斜率
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define MAX 200000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
#define double long double
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int n;
struct ran{
double x, y;
ll z;
}tr[MAX];
ll ans;
int tot;
int cnt;
map<double, int>mp;
vector<pair<double, int>>v[MAX];
void cal(){
for(int i = 1; i <= cnt; ++i)sort(v[i].begin(), v[i].end());
for(int i = 1; i <= cnt; ++i){
for(int j = 1; j < v[i].size(); ++j){
if(v[i][j].second == 1 && v[i][j - 1].second == 1){
--tot;
}
}
v[i].clear();
}
mp.clear();
cnt = 0;
}
void work(){
cin>>n;tot = n;
for(int i = 1; i <= n; ++i){
cin>>tr[i].x>>tr[i].y>>tr[i].z;
ans += tr[i].z;
}
for(int i = 1; i <= n; ++i){
if(tr[i].x < 0 && tr[i].y < 0){
double k = tr[i].y / tr[i].x;
if(mp[k] == 0)mp[k] = ++cnt;
v[mp[k]].push_back(m_p(tr[i].x, tr[i].z));
}
}
cal();
for(int i = 1; i <= n; ++i){
if(tr[i].x > 0 && tr[i].y < 0){
double k = tr[i].y / tr[i].x;
if(mp[k] == 0)mp[k] = ++cnt;
v[mp[k]].push_back(m_p(tr[i].x, tr[i].z));
}
}
cal();
for(int i = 1; i <= n; ++i){
if(tr[i].x < 0 && tr[i].y > 0){
double k = tr[i].y / tr[i].x;
if(mp[k] == 0)mp[k] = ++cnt;
v[mp[k]].push_back(m_p(tr[i].x, tr[i].z));
}
}
cal();
for(int i = 1; i <= n; ++i){
if(tr[i].x > 0 && tr[i].y > 0){
double k = tr[i].y / tr[i].x;
if(mp[k] == 0)mp[k] = ++cnt;
v[mp[k]].push_back(m_p(tr[i].x, tr[i].z));
}
}
cal();
vector<pair<double, int> >ar;
for(int i = 1; i <= n; ++i){
if(tr[i].x == 0 && tr[i].y > 0){
ar.push_back(m_p(tr[i].y, tr[i].z));
}
}
sort(ar.begin(), ar.end());
for(int i = 1; i < ar.size(); ++i){
if(ar[i].second == 1 && ar[i - 1].second == 1)--tot;
}
ar.clear();
for(int i = 1; i <= n; ++i){
if(tr[i].x == 0 && tr[i].y < 0){
ar.push_back(m_p(tr[i].y, tr[i].z));
}
}
sort(ar.begin(), ar.end());
for(int i = 1; i < ar.size(); ++i){
if(ar[i].second == 1 && ar[i - 1].second == 1)--tot;
}
ar.clear();
for(int i = 1; i <= n; ++i){
if(tr[i].y == 0 && tr[i].x < 0){
ar.push_back(m_p(tr[i].x, tr[i].z));
}
}
sort(ar.begin(), ar.end());
for(int i = 1; i < ar.size(); ++i){
if(ar[i].second == 1 && ar[i - 1].second == 1)--tot;
}
ar.clear();
for(int i = 1; i <= n; ++i){
if(tr[i].y == 0 && tr[i].x > 0){
ar.push_back(m_p(tr[i].x, tr[i].z));
}
}
sort(ar.begin(), ar.end());
for(int i = 1; i < ar.size(); ++i){
if(ar[i].second == 1 && ar[i - 1].second == 1)--tot;
}
cout<<ans<<' '<<tot;
}
int main(){
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define MAX 200000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int n;
struct ran{
int x, y, z;
}tr[MAX];
ll ans;
int tot;
int cnt;
int gcd(int a, int b){
if(b) return gcd(b, a % b);
else return a;
}
map<pii, int>mp;
vector<pii>ar[MAX];
void work(){
cin>>n;tot = n;
for(int i = 1; i <= n; ++i){
cin>>tr[i].x>>tr[i].y>>tr[i].z;
ans += tr[i].z;
if(tr[i].x == 0 || tr[i].y == 0)continue;
int gg = gcd(abs(tr[i].x), abs(tr[i].y));
if(mp[m_p(tr[i].x / gg, tr[i].y / gg)] == 0)mp[m_p(tr[i].x / gg, tr[i].y / gg)] = ++cnt;
ar[mp[m_p(tr[i].x / gg, tr[i].y / gg)]].push_back(m_p(tr[i].x, tr[i].z));
}
for(int i = 1; i <= cnt; ++i)sort(ar[i].begin(), ar[i].end());
for(int i = 1; i <= cnt; ++i){
for(int j = 1; j < ar[i].size(); ++j){
if(ar[i][j].second == 1 && ar[i][j - 1].second == 1)--tot;
}
}
vector<pair<int, int> >ar;
for(int i = 1; i <= n; ++i){
if(tr[i].x == 0 && tr[i].y > 0){
ar.push_back(m_p(tr[i].y, tr[i].z));
}
}
sort(ar.begin(), ar.end());
for(int i = 1; i < ar.size(); ++i){
if(ar[i].second == 1 && ar[i - 1].second == 1)--tot;
}
ar.clear();
for(int i = 1; i <= n; ++i){
if(tr[i].x == 0 && tr[i].y < 0){
ar.push_back(m_p(tr[i].y, tr[i].z));
}
}
sort(ar.begin(), ar.end());
for(int i = 1; i < ar.size(); ++i){
if(ar[i].second == 1 && ar[i - 1].second == 1)--tot;
}
ar.clear();
for(int i = 1; i <= n; ++i){
if(tr[i].y == 0 && tr[i].x < 0){
ar.push_back(m_p(tr[i].x, tr[i].z));
}
}
sort(ar.begin(), ar.end());
for(int i = 1; i < ar.size(); ++i){
if(ar[i].second == 1 && ar[i - 1].second == 1)--tot;
}
ar.clear();
for(int i = 1; i <= n; ++i){
if(tr[i].y == 0 && tr[i].x > 0){
ar.push_back(m_p(tr[i].x, tr[i].z));
}
}
sort(ar.begin(), ar.end());
for(int i = 1; i < ar.size(); ++i){
if(ar[i].second == 1 && ar[i - 1].second == 1)--tot;
}
cout<<ans<<' '<<tot;
}
int main(){
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
7-3 打怪升级 (25 分)
题目描述：
问空降到哪个点使得这个点到最远的点的距离最小，并输出到特地点的路径，如果路径不唯一，则输出获得价值最大的那个点
思路：
这个题讲的真的是晦涩难懂，狗屁不是
跑个Floyed得到任意两个点最短距离，然后找出符合题意的下降点后再跑一遍迪杰斯特拉，维护最小花费与最大价值即可
我这里存路径的方法用的是pre数组存节点的父节点，注意⚠️：千万不要用vector存路径，因为如果一个点v之前更新过了，此时来个u可以继续更新v，此时更改路径会导致v后面的点的路径得不到更新，就会出问题
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 1000000 + 50
int n, m;
int dp[1005][1005];
int s;
int x, y;
int sp[MAX], val[MAX];
int num;
int tager[MAX];
int tot;
int head[MAX];
struct ran{
int to, nex, val, jiazhi;
}tr[MAX];
inline void built(int u, int v, int c, int d){
tr[++tot].to = v;
tr[tot].jiazhi = d;
tr[tot].val = c;
tr[tot].nex = head[u];
head[u] = tot;
}
priority_queue<pii, vector<pii>, greater<pii> >q;
int dis[MAX];
bool vis[MAX];
int vv[MAX];
int pre[MAX];
void dijkstra(){
mem(dis, inf);
dis[s] = 0;
q.push(m_p(0, s));
while (!q.empty()) {
int u = q.top().second;q.pop();
if(vis[u])continue;
vis[u] = 1;
for(int i = head[u]; i; i = tr[i].nex){
int v = tr[i].to;
if(dis[v] > dis[u] + tr[i].val){
vv[v] = vv[u] + tr[i].jiazhi;
pre[v] = u;
dis[v] = dis[u] + tr[i].val;
q.push(m_p(dis[v], v));
}
else if(dis[v] == dis[u] + tr[i].val){
if(vv[v] < vv[u] + tr[i].jiazhi){
vv[v] = vv[u] + tr[i].jiazhi;
pre[v] = u;
}
}
}
}
for(int i = 1; i <= num; ++i){
int x = tager[i];
stack<int>st;
while (x != s) {
st.push(x);
x = pre[x];
}
st.push(s);
while (!st.empty()) {
cout<<st.top();st.pop();
if(st.size())cout<<"->";
else cout<<endl;
}
cout<<dis[tager[i]]<<' '<<vv[tager[i]];
cout<<endl;
}
}
void work(){
cin>>n>>m;
for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)dp[i][j] = i == j ? 0 : inf;
for(int i = 1; i <= m; ++i){
cin>>x>>y>>sp[i]>>val[i];
built(x, y, sp[i], val[i]);built(y, x, sp[i], val[i]);
dp[x][y] = dp[y][x] = sp[i];
}
for(int k = 1; k <= n; ++k){
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
cin>>num;
for(int i = 1; i <= num; ++i)cin>>tager[i];
vector<pii>v;
for(int u = 1; u <= n; ++u){
int maxn = -1;
for(int v = 1; v <= n; ++v){
maxn = max(maxn, dp[u][v]);
}
v.push_back(m_p(maxn, u));
}
sort(v.begin(), v.end());
s = v[0].second;
cout<<s<<endl;
dijkstra();
}
int main(){
io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
7-4 疫情防控 (30 分)
题目描述：
N个点，M条双向边，D次询问，每次询问都会在上次的基础上删除一个节点，当然，一个节点被删除以后，他的所有边也会被删除，每次询问都会在删除点后，提出Qi个问题，问a能不能到b
思路：
离线处理询问
先使用并查集将永远不会被删掉的点根据边去emerge，然后倒着并查集，每次询问都先将要删的点根据他的边去emerge，然后对于Qi次询问时，只需要判断a与b的father是不是一个即可
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define MAX 400000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int n, m, d;
int fa[MAX];
int x, y, a, b;
int tot;
int head[MAX];
struct ran{
int to, nex;
}tr[MAX];
inline void add(int u, int v){
tr[++tot].to = v;
tr[tot].nex = head[u];
head[u] = tot;
}
vector<pii>v[MAX];
vector<int>id;
inline int getfa(int x){
return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
inline void emerge(int x, int y){
fa[getfa(x)] = getfa(y);
}
bool vis[MAX];
vector<int>ans;
void work(){
io;
cin>>n>>m>>d;
for(int i = 1; i <= n; ++i)fa[i] = i;
for(int i = 1; i <= m; ++i){
cin>>x>>y;
add(x, y);add(y, x);
}
for(int i = 1; i <= d; ++i){
cin>>a>>b;
vis[a] = 1;
id.push_back(a);
for(int j = 1; j <= b; ++j){
cin>>x>>y;
v[i].push_back(m_p(x, y));
}
}
for(int u = 1; u <= n; ++u){
if(vis[u])continue;
for(int i = head[u]; i; i = tr[i].nex){
int v = tr[i].to;
if(vis[v])continue;
emerge(u, v);
}
}
for(int i = d; i >= 1; --i){
int u = id[i - 1];
vis[u] = 0;
int num = 0;
for(int j = 0; j < v[i].size(); ++j){
if(getfa(v[i][j].first) != getfa(v[i][j].second))++num;
}
ans.push_back(num);
for(int j = head[u]; j; j = tr[j].nex){
int v = tr[j].to;
if(vis[v])continue;
emerge(u, v);
}
}
for(int i = (int)ans.size() - 1; i > 0; --i)cout<<ans[i]<<endl;
cout<<ans[0];
}
int main(){
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
