2021 RoboCom 世界机器人开发者大赛-本科组（初赛）
7-4 疫情防控 (30 分)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=5e4+10,M = 2e5+10;
int n,m,k;
int p[N],cnt;
PII f[M*10],id[N];
vector<int> e[N];
int num[N];
int find(int x)
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m>>k;
for(int i = 0; i < m;i ++)
{
int a,b;
scanf("%d %d",&a,&b);
e[a].push_back(b),e[b].push_back(a);
}
cnt=0;
set<int>S;
for(int i =0 ; i < k;i ++)
{
scanf("%d %d",&id[i].x,&id[i].y);
S.insert(id[i].x);
for(int j = 0; j < id[i].y ; j ++)
{
cnt++;
scanf("%d%d",&f[cnt].x,&f[cnt].y);
}
}
for(int i = 1;i <= n;i ++) p[i]=i;
for(int i = 1;i <= n;i ++)
{
for(int j=0; j <(int)e[i].size();j ++)
{
int a = i,b = e[i][j];
if(S.count(a)||S.count(b)) continue;
int pa=find(a),pb=find(b);
if(pa!=pb) p[pa]=pb;
}
}
//特殊处理最后一段
for(int i = cnt - id[k-1].y + 1;i <= cnt;i ++)
{
int pa = find(f[i].x),pb=find(f[i].y);
if(pa!=pb) num[k-1]++;
}
cnt -= id[k-1].y;
for(int i = k-2;i>=0;i --)
{
int u=id[i+1].x;
S.erase(u);
for(int j=0;j <(int) e[u].size(); j ++)
{
int a = u,b=e[u][j];
if(S.count(a)||S.count(b)) continue;
int pa=find(a),pb=find(b);
if(pa!=pb) p[pa]=pb;
}
for(int j = cnt - id[i].y + 1; j <= cnt; j ++)
{
int a = f[j].x, b = f[j].y;
int pa = find(a),pb=find(b);
if(pa != pb) num[i]++;
}
cnt -= id[i].y;
}
for(int i = 0; i < k; i ++) cout<<num[i]<<endl;
return(0);
}
2021 RoboCom 世界机器人开发者大赛-本科组（决赛）
T1
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N = 1e3+10;
int n,m;
PII q[N];
int get_dist(PII &a,PII &b){
return abs(a.x - b.x) + abs(a.y - b.y);
}
int main()
{
cin >> n >> m;
q[0]={0,0};
for(int i = 1;i <= n; i ++)
{
int t; cin>>t;
q[i] = q[i-1];
if(i & 1) q[i].y = t;
else q[i].x = t;
//cout<<q[i].x<<" "<<q[i].y<<endl;
}
q[n+1] = q[0];
vector<PII>ans;
ans.push_back({0,0});
set<PII>st;
st.insert({0,0});
int len = 0;
for(int i = 0; i <= n; i ++)
{
int d = get_dist(q[i] ,q[i+1]);
if(d + len >= m)
{
if(i % 2 == 0)
{
int p = q[i + 1].y > q[i].y ? 1 : -1;
PII last = q[i];
while(len + d >= m){
PII u = {last.x, last.y + p * (m - len)};
if (st.count(u) == 0) {
ans.push_back(u);
st.insert(u);
}
d -= (m - len);
last = u;
len = 0;
}
len = d;
}
else
{
int p = q[i+1].x > q[i].x ? 1 : -1;
PII last = q[i];
while(len + d >= m){
PII u = {last.x + p * (m - len), last.y };
if (st.count(u) == 0) {
ans.push_back(u);
st.insert(u);
}
d -= (m - len);
last = u;
len = 0;
}
len = d;
}
}
else len += d;
}
for(auto u:ans)
cout<<u.x<<" "<<u.y<<endl;
return(0);
}
T2
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e3+10;
int n;
int a[N];
int low[N],g[N];
bool st[N];
int ans;
vector<int>res_r;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
//i = n + 1就是全是L 的情况
for (int i = 1; i <= n + 1; i++) {
//找到第一个r
int len = 0;
for (int j = i; j <= n; j++) {
if (len == 0) low[++len] = a[j], g[j] = len;
else {
if (a[j] > low[len]) low[++len] = a[j], g[j] = len;
else if(a[j] > low[1]){
int x = lower_bound(low + 1, low + len + 1, a[j]) - low;
low[x] = a[j];
g[j] = x;
}
}
}
vector<int> vec;
int cnt = len, len1 = 0;
for (int j = n; j >= 1; j--) {
if (g[j] == cnt && cnt) vec.push_back(j), cnt--;
g[j] = 0;
}
sort(vec.begin(), vec.end());
//为了vector后面比较用
for (int j = 0; j < vec.size(); j++) st[vec[j]] = 1;
LL x = low[1];
if (len == 0) x = 1e18;
for (int j = n; j >= 1; j--) {
if (st[j]) {st[j] = 0;continue;}
if (len1 == 0 && a[j] < x)low[++len1] = a[j];
else if(a[j] < x){
if (a[j] > low[len1]) low[++len1] = a[j];
else {
int x = lower_bound(low + 1, low + len1 + 1, a[j]) - low;
low[x] = a[j];
}
}
}
if (ans < len + len1 ) {
ans = len + len1;
res_r = vec;
} else if (ans == len + len1) {
if(res_r.size() == 0) continue;
if(vec.size() == 0) res_r = vec;
else if (vec > res_r)
{
res_r = vec;
}
}
}
cout << ans << endl;
for (int i = 0; i < res_r.size(); i++) st[res_r[i]] = 1;
for (int i = 1; i <= n; i++) {
if (st[i]) cout << "R";
else cout << "L";
}
return(0);
}
T3
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e3+10;
int n;
int a[N];
int low[N],g[N];
bool st[N];
int ans;
vector<int>res_r;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
//i = n + 1就是全是L 的情况
for (int i = 1; i <= n + 1; i++) {
//找到第一个r
int len = 0;
for (int j = i; j <= n; j++) {
if (len == 0) low[++len] = a[j], g[j] = len;
else {
if (a[j] > low[len]) low[++len] = a[j], g[j] = len;
else if(a[j] > low[1]){
int x = lower_bound(low + 1, low + len + 1, a[j]) - low;
low[x] = a[j];
g[j] = x;
}
}
}
vector<int> vec;
int cnt = len, len1 = 0;
for (int j = n; j >= 1; j--) {
if (g[j] == cnt && cnt) vec.push_back(j), cnt--;
g[j] = 0;
}
sort(vec.begin(), vec.end());
//为了vector后面比较用
for (int j = 0; j < vec.size(); j++) st[vec[j]] = 1;
LL x = low[1];
if (len == 0) x = 1e18;
for (int j = n; j >= 1; j--) {
if (st[j]) {st[j] = 0;continue;}
if (len1 == 0 && a[j] < x)low[++len1] = a[j];
else if(a[j] < x){
if (a[j] > low[len1]) low[++len1] = a[j];
else {
int x = lower_bound(low + 1, low + len1 + 1, a[j]) - low;
low[x] = a[j];
}
}
}
if (ans < len + len1 ) {
ans = len + len1;
res_r = vec;
} else if (ans == len + len1) {
if(res_r.size() == 0) continue;
if(vec.size() == 0) res_r = vec;
else if (vec > res_r)
{
res_r = vec;
}
}
}
cout << ans << endl;
for (int i = 0; i < res_r.size(); i++) st[res_r[i]] = 1;
for (int i = 1; i <= n; i++) {
if (st[i]) cout << "R";
else cout << "L";
}
return(0);
}
T4
时间复杂度$o(n(n+mlogm))$ 勉强卡过。
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N = 510,M = 2e5+10,INF = 0x3f3f3f3f;
int n,m,S,T;
//mlogm
int h[N],ne[M],e[M],w[M],idx;
int d[N];
bool rm[M],st[N];
unordered_map<int,int>hs;
void add(int a,int b,int c)
{
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++;
}
int dijkstra(int start,int ed)
{
priority_queue<PII,vector<PII>,greater<>> heap;
memset(d,INF,sizeof d);
memset(st,0,sizeof st);
heap.push({0,start});
d[start] = 0;
while(!heap.empty())
{
auto t = heap.top();
heap.pop();
int u = t.y;
if(u == ed) break;
if(st[u]) continue;
else st[u] = 1;
for(int i = h[u];~i;i = ne[i])
{
int j = e[i];
if(rm[i] || rm[i ^ 1]) continue;
if(d[j] > d[u] + w[i])
{
d[j] = d[u] +w[i];
heap.push({d[j],j});
}
}
}
return d[ed];
}
int main()
{
cin >> n >> m >> S >> T;
memset(h,-1,sizeof h);
for(int i = 1;i <= m; i ++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
if(a == S) hs[b] = idx - 1;
else if(b == S) hs[a] = idx - 1;
add(b,a,c);
}
int ans_1 = INF;
int ans_2 = dijkstra(S,T);
for(int i = 1;i <= n; i ++)
{
if(hs.count(i))
{
rm[hs[i]] = 1;
int dist = dijkstra(i,S);
//cout<<i<<" "<<dist<<endl;
ans_1 = min(ans_1,dist + w[hs[i]]);
rm[hs[i]] = 0;
}
}
if(ans_1 >= INF/2) cout<<"-1";
else cout<<ans_1;
if(ans_2 >= INF/2) cout<<" -1\n";
else cout<<" "<<ans_2<<"\n";
if(ans_1 < ans_2) cout<<"Win!";
else cout<<"Lose!";
return(0);
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+10,inf = 0x3f3f3f3f;
int n,m;
int a[N],b[N];
int dp[N][N][4];
int f[N][N][4];
int main()
{
for(int i = 1; ; i ++)
{
cin>>a[++n];
if(a[n] == -1) break;
}
for(int i = 1; ; i ++)
{
cin >> b[++m];
if(b[m] == -1) break;
}
memset(dp,inf,sizeof dp);
for(int i = 0 ; i < 4; i ++) dp[0][0][i] = 0;
--n,--m;
cout<<n<<endl;
cout<<m<<endl;
for(int i = 1;i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
if(a[i] == b[j])
{
for(int k = 0 ; k < 4 ; k ++)
{
if(dp[i-1][j-1][k] < dp[i][j][2])
{
dp[i][j][2] = dp[i-1][j-1][k];
}
}
}
else
{
//删除
if(a[i + 1] == b[j] && i + 1 <= n)
{
for(int k = 0 ; k <4; k ++)
{
if(dp[i-1][j-1][k] + 1 < dp[i][j][0] )
{
dp[i][j][0] = dp[i-1][j-1][k] + 1;
}
}
}
//改变
for(int k = 1;k < 4; k ++)
{
if(dp[i - 1][j - 1][k] + 1 < dp[i][j][1])
{
dp[i][j][1] = dp[i - 1][j - 1][k] + 1;
}
}
//插入
//前面插入
for(int k = 1;k < 4; k ++)
{
if(dp[i - 1][j - 1][k] + 1 < dp[i][j][2])
{
dp[i][j][2] = dp[i-1][j-1][k] + 1;
}
}
}
}
int ans = 1e9;
for(int i = 0 ; i < 4; i++) ans = min(ans,dp[n][m][i]);
cout<<ans<<endl;
// cout<<dp[n][m]<<endl;
return(0);
}
2022 RoBoCom 本科 国赛
T3
先求最短路，然后按topo序,dp下去求val
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N = 1e5 + 10,M = 2e5+10;
int n,m,k,p,S,T;
int w[N],h[N],e[M],ne[M],idx;
int dist[N];
int q[N],din[N];
int dp[N];
vector<int>v[N];
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a], h[a] = idx++;
}
void bfs()
{
int hh = 0,tt = -1;
memset(dist,-1,sizeof dist);
q[++ tt] = {S};
dist[S] = 0;
while(hh <= tt)
{
auto u = q[hh++];
for(int i = h[u]; ~i ; i = ne[i])
{
int j = e[i];
if(dist[j] != -1)
{
if(dist[j] == dist[u] + 1)
{
v[u].push_back(j);
++ din[j];
}
continue;
}
dist[j] = dist[u] + 1;
v[u].push_back(j);
++ din[j];
q[++ tt] = {j};
}
}
}
void topsort()
{
int hh = 0,tt = -1;
q[++ tt] = S;
dp[S] = ((p == 1)?w[S] : 0);
while(hh <= tt)
{
int t = q[hh ++];
for(auto x : v[t])
{
int y = (dist[x] % k + 1 == p) ? w[x] : 0;
dp[x] = max(dp[x],dp[t] + y);
if(--din[x] == 0) q[++tt] = x;
}
}
cout<<dp[T]<<"\n";
}
int main()
{
memset(h,-1,sizeof h);
cin >> n >> m >> k >> p;
for(int i =1; i <=n ; i ++) scanf("%d",&w[i]);
for(int i = 1; i <= m ;i ++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
cin >> S >> T;
bfs();
topsort();
return(0);
}
T5
队里大佬写的 题解 https://www.cnblogs.com/syf2020/p/16572737.html
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 2e3+10,M = 2 * N;
int n;
int w[N];
int h[N],e[M],ne[M],idx;
int d[N][N];
bitset<N>T[N];
PII q[N];
vector<PII>vec[N];
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void bfs(int start)
{
d[start][start] = 0;
int hh = 0,tt = -1;
q[++ tt]={0,start};
while(hh <= tt)
{
auto t = q[hh++];
int u = t.y;
for(int i = h[u];~i; i = ne[i])
{
int j = e[i];
if(d[start][j] > d[start][u] + 1)
{
d[start][j] = d[start][u] + 1;
q[++ tt] ={d[start][j],j};
}
}
}
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d",&n);
for(int i = 1; i < n; i ++)
{
int a,b; scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
for(int i = 1; i <= n; i ++)
{
scanf("%d",w+i);
T[w[i]].set(i,1);
}
memset(d,0x3f,sizeof d);
for(int i = 1 ;i <= n; i ++) bfs(i);
for(int i = 1; i <= n; i ++)
{
for(int j = i+1;j <= n;j ++)
{
vec[d[i][j]].push_back({i,j});
}
}
LL res = 0;
for(int i = 1; i <= n; i ++)
{
bitset<N>B[N];
for(int j = 0; j < vec[i].size(); j ++)
{
auto u = vec[i][j];
int a = u.x,b = u.y;
B[a].set(b,1);
B[b].set(a,1);
}
for(int j = 0 ; j < vec[i].size(); j ++)
{
auto u = vec[i][j];
int a = u.x,b = u.y;
if(w[a] == w[b]) continue;
res += (B[a] & B[b] & (~T[w[a]] & ~T[w[b]])).count();
}
}
cout<<res/3<<endl;
return(0);
}
