首页 > 其他分享 >28号个人赛

28号个人赛

时间：2023-07-28 20:33:40浏览次数：39  
标签：idx int 28 cin ++ 个人赛 mp cre

个人赛链接: https://www.luogu.com.cn/contest/120853#description
今天只补了七道, 太难了呜呜呜...


A.Geodetic

解题思路

根据题意多源最短路肯定要用floyd算法, 而题目要求找到最短路中所有可能的中间点, 所有我们直接遍历所有点, 找到点i满足g[a][i] + g[i][b] == g[a][b], 则点i就是从a到b最短路的中间点; 这个题我一开始想的很复杂, 想要在floyd上做修改, 但是理解中间点这个需求之后就清晰多了;

神秘代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 5e6 + 10, mod = 1e9 + 7;
int n, m, k,idx;
int g[50][50];
void floyd() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) g[i][j] = 0;
			else g[i][j] = 1e9;
		}
	}
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		g[a][b] = g[b][a] = 1;
	}
	cin >> k;
	floyd();
	while (k--) {
		int a, b;
		cin >> a >> b;
		for (int i = 1; i <= n; i++) {
			if (g[a][i] + g[i][b] == g[a][b]) cout << i << ' ';
		}
		cout << endl;
	}
	return 0;
}



B.Wormholes G

解题思路

题意说是要倒退时间, 并且对走的这条路没有任何要求, 只要能回到起点就行; 所以放在图上其实就是找负环; 直接用spfa算法判断负环即可;

神秘代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, m, k, idx;
int d[N], cnt[N];
int h[N], ne[N], e[N], w[N];
bool st[N];
vector<int> v;
void add(int a, int b, int c) {
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int spfa() {
	memset(st, false, sizeof st);
	memset(cnt, 0, sizeof cnt);
	queue <int >q;
	for (int i = 1; i <= n; i++) {
		q.push(i);
		st[i] = true;
	}
	while (q.size()) {
		int t = q.front();
		q.pop();
		st[t] = false;
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			if (d[j] > d[t] + w[i]) {
				d[j] = d[t] + w[i];
				cnt[j] = cnt[t] + 1;
				if (cnt[j] > n - 1) return 0;
				if (!st[j]) {
					q.push(j);
					st[j] = true;
				}
			}
		}
	}
	return 1;
}
signed main() {
	int t;
	cin >> t;
	while (t--) {
		memset(h, -1, sizeof h);
		idx = 0;
		cin >> n >> m >> k;
		for (int i = 1; i <= m; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			add(a, b, c), add(b, a, c);
		}
		for (int i = 1; i <= k; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			add(a, b, -c);
		}
		if (!spfa()) printf("YES\n");
		else printf("NO\n");
	}

	return 0;
}



C.智能推荐

解题思路

根据题意, 必须解决前面的题才能解锁后面的题, 还是一个比较明显的拓扑序列问题; 用数组w[i]表示完成第i题的天数;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 5e6 + 10, mod = 1e9 + 7;
int n, m, k, t, idx;
int d[N], w[N];
int h[N], ne[N], e[N];
bool st[N];
queue<int> q;
map<int, PII> mp;
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void check() {
	while (q.size()) {
		int t = q.front();
		if (t == m) {
			cout << w[t];
			return;
		}
		q.pop();
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			d[j]--;
			if (d[j] == 0) {
				q.push(j);
				w[j] = w[t] + 1;
			}
		}
	}
	cout << -1;
}
signed main() {
	cin >> n >> m >> k;
	memset(h, -1, sizeof h);
	for (int i = 1; i <= k; i++) {
		int a;
		cin >> a;
		w[a] = 0;
		q.push(a);
	}
	cin >> t;
	for (int i = 1; i <= t; i++) {
		int a, b;
		cin >> a >> b;
		d[a] = b;
		for (int j = 1; j <= b; j++) {
			int c;
			cin >> c;
			add(c, a);
		}
	}
	check();
	return 0;
}



D.打鼹鼠

解题思路

一道类似于最长上升子序列的dp, 状态表示为d[i], 表示以第i只鼹鼠结尾的方案中打到鼹鼠数量最多的方案; 因为机器人初识位置任意, 所以我们可以把所有d[i]初始化为1; 状态计算时, 因为题目按时间递增输入, 省去了排序的过程; 我们先遍历i表示是以第i只鼹鼠结尾, 然后再遍历j, 表示第1 ~ i-1只鼹鼠, 然后我们看能不能把i插在j的后面, 计算出i和j两只鼹鼠之间的曼哈顿距离和时间差; 只要曼哈顿距离小于等于时间差, 那么就可以把i放在j的后面, 即dp[i] = max(dp[i], dp[j] + 1); 最后从d[1]~d[n]中找出最大值即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10, mod = 1e9 + 7;
int n, m, k, idx, res;
int dp[N], t[N];
PII f[N];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		f[i] = { b,c };
		t[i] = a;
	}
	for (int i = 1; i <= m; i++) dp[i] = 1;
	for (int i = 1; i <= m; i++) {
		int a = f[i].first,  b = f[i].second;
		for (int j = 1; j < i; j++) {
			int c = f[j].first, d = f[j].second;
			int dis = abs(a - c) + abs(b - d);
			if (dis <= abs(t[i] - t[j])) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}
	int maxn = 0;
	for (int i = 1; i <= m; i++) {
		maxn = max(maxn, dp[i]);
	}
	cout << maxn;
	return 0;
}



F.Superbull S

解题思路

如果不看标签有个生成树, 这个题还真的是不好想; 因为本题是n支队伍都会参与, 并且一共要进行n-1场比赛, 那就是n个点和n-1条边, 其中没有重边和自环, 那就是一棵树; 根据队伍编号我们可以知道所有队伍之间比赛的分数, 也就是任意两个点之间的权值; 经过这样"翻译"一下, 就变成了给定所有两个点之间的权值, 然后找一条最大生成树即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e7 + 10, mod = 1e9 + 7;
int n, m, k, idx, res;
int d[N], p[N];
struct str {
	int a, b, c;
}cre[N];
bool cmp(str a, str b) {
	return a.c > b.c;
}
int find(int a) {
	if (p[a] != a) p[a] = find(p[a]);
	return p[a];
}
void check() {
	for (int i = 0; i < idx; i++) {
		int a = cre[i].a, b = cre[i].b, c = cre[i].c;
		if (find(a) != find(b)) {
			p[find(b)] = find(a);
			res += c;
		}
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> d[i];
		p[i] = i;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			int a = d[i], b = d[j];
			int c = (a ^ b);
			cre[idx++] = { i,j,c };
		}
	}
	sort(cre, cre + idx, cmp);
	check();
	cout << res;
	return 0;
}



G.采购特价商品

解题思路

本题算是个模板题, 只是需要根据坐标把两个店之间的距离求出来, 然后用最短路求出s到t之间的最短路即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, m, k,idx;
double d[N], w[N];
int h[N], ne[N], e[N];
bool st[N];
map<int, PII> mp;
void add(int a, int b, double c) {
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
void check(int u) {
	for (int i = 1; i <= n; i++) d[i] = 1e9;
	priority_queue<PII,vector<PII>,greater<PII>> q;
	q.push({ 0,u });
	d[u] = 0;
	while (q.size()) {
		auto t = q.top();
		q.pop();
		int a = t.second;
		if (st[a]) continue;
		st[a] = true;
		for (int i = h[a]; i != -1; i = ne[i]) {
			int j = e[i];
			if (d[j] > d[a] + w[i]) {
				d[j] = d[a] + w[i];
				q.push({ d[j],j });
			}
		}
	}
}
signed main() {
	cin >> n;
	memset(h, -1, sizeof h);
	int a, b;
	for (int i = 1; i <= n; i++) {
		cin >> a >> b;
		mp[i] = { a,b };
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> a >> b;
		int x = mp[a].first - mp[b].first;
		int y = mp[a].second - mp[b].second;
		double c = x * x + y * y;
		c = sqrt(c);
		add(a, b, c), add(b, a, c);
	}
	cin >> a >> b;
	check(a);
	printf("%.2lf", d[b]);
	return 0;
}



H.逐个击破

解题思路

根据题意我没学需要去删合适的道路, 但是这样似乎难以下手, 因为我们需要在局部操作去追求整体的最大值, 但是这样的做法一般都是贪心, 但是本题很显然没法用贪心, 所有每次操作都得前瞻后顾, 非常的难受; 所以我们不如改变思路, 我们把这道题看出给定m条道路方案, 问该如何修建道路可以让所有敌军隔离开来, 并且花的钱要尽可能多; 因为题目指明有n-1条边, 说明没有重边或者成环这样的复杂情况, 也是就说我们要在隔离敌军的前提下, 把尽可能多的友军连起来; 所有, 又是一个最大生成树的题, 并且本题和kruskal算法的适配性很好; 因为隔离敌军的本质就是把树分成多个连通块, 且每个连通块里面最多只有一个敌军; 所有在kruskal算法中, 如果这条边的两个顶点所在连通块里都已经有敌军了, 那么这条边就不用连接了; 如果两个连通块中至少有一个没有敌军, 那么就可以连接, 如果其中一个里面有敌军, 那么我们为了更快地辨认连通块里是否有敌军, 我们可以把新形成的连通块的祖宗节点就设为该敌军的节点编号; 为此, 我们在输入敌军编号时可以对其编号进行一下标记方便后期辨认; 最后得到这个特殊的最大生成树的权值和, 然后全部的费用减去权值和即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, m, k, idx, res;
int p[N];
map<int, int> mp;
struct str {
	int a, b, c;
}cre[N];
bool cmp(str a, str b) {
	return a.c > b.c;
}
int find(int x) {
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}
void check() {
	for (int i = 1; i < n; i++) {
		int a = cre[i].a, b = cre[i].b, c = cre[i].c;
		int x = find(a),  y = find(b);
		if (mp[x] && mp[y]) continue;
		if (x != y) {
			if (mp[x]) p[y] = x;
			else if (mp[y]) p[x] = y;
			else p[x] = y;
			res += c;
		}
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) p[i] = i;
	for (int i = 1; i <= m; i++) {
		int a;
		cin >> a;
		mp[a]++;
	}
	for (int i = 1; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		cre[i] = { a,b,c };
		idx += c;
	}
	sort(cre + 1, cre + n, cmp);
	check();
	cout << idx-res;
	return 0;
}



I.消息扩散

解题思路

本题是一个强连通分量的模板题, 但是, 我没学...无奈之下只好去恶补了一下; 既然是模板题, 那我就不多说了; 想学的自动跳转吧;

神秘代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, m, idx, times, top, cnt;
int stk[N], id[N], sizes[N], dfn[N], low[N];
int cd[N], rd[N];
int h[N], ne[N], e[N];
bool in_stk[N];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u) {
    dfn[u] = low[u] = ++times;
    stk[++top] = u, in_stk[u] = true;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    if (dfn[u] == low[u]) {
        cnt++;
        int y;
        do {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = cnt;
            sizes[cnt]++;
        } while (y != u);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = h[i]; j != -1; j = ne[j]) {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) {
                cd[a]++, rd[b]++;
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= cnt; i++) {
        if (!rd[i]) res++;
    }
    cout << res;
    return 0;
}

标签：idx,int,28,cin,++,个人赛,mp,cre
From： https://www.cnblogs.com/mostimali/p/17588838.html

相关文章

  • 7.28
    #include<stdio.h>#include<math.h>structprople{intnum;intname[10];}p[10000],pmin;//pmin表示最小值intmain(void){inti,n,sum=0;doublehalf;//half表示平均数的一半scanf("%d",&n);for(i=0;i<n;i++){scanf("%s%d&q......
  • 7.28 EOI
    #include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefdoubledb;constintN=2e5+50;constintM=1e5+50;constintMod=1e9+7;inlineintread(){intx=0,f=1;charch=getchar();while(ch<......
  • 7.28 后记
    T1异或和塞到状态里就不用管路径相交了式子：\[f_{i,j,k\operatorname{xor}G_{i,j},0}=f_{i-1,j,k,0}+f_{i,j-1,k,0}\]\[f_{i,j,k\operatorname{xor}G_{i,j},1}=f_{i-1,j,k,1}+f_{i,j-1,k,1}\]\[f_{i,j,k,1}=f_{i-1,j,k,0}+f_{i,j-1,k,0}\]T2朋友能到达\(k\)的人一定都......
  • 暑假集训D5 2023.7.28 补题
    首先来回顾一下\(dijkstra\)和\(SPFA\)里面\(vis\)数组的作用和区别,以及不用\(vis\)数组的影响.(今天发现之前写堆优化的\(Dijkstra\)都不加\(vis\)数组...)\(Dijkstra\)算法中,每次取出距离源点最近的一个点来更新与他相连的其他点,置\(vis\)数组为\(true\)......
  • 【2023-07-28】渴望亲密关系
    20:00人没有苦闷，没有矛盾，就不会进步。有矛盾才会逼你解决矛盾，解决一次矛盾即往前迈进一步。到晚年矛盾减少，即是生命将要告终的表现。没有矛盾的一片恬静只是一个崇高的理想，真正实现的话并不是一个好现象。                      ......
  • 国标GB28181视频平台LntonGBS（源码版）国标视频平台大并发下SIP消息出现重复SN号的问题解
    随着国家倡导平安城市、智慧城市的建设，安防视频监控作为智慧城市安防建设的重要环节，也越来越受到重视。LntonGBS是基于公安部推出的安防主流协议（国标GB28181协议）的视频接入、处理及分发平台，具有视频直播监控、云端录像、云存储、检索回放、智能告警、语音对讲、平台级联等功能。我......
  • 【2023.07.28】三年计划
    =主线任务今年的主线是考上研究生，并让学校所有人都认识我攒钱买辆车（大概率小米）明年的主线是软考高项，业余时间去考电工和思科支线任务增肥上60kg，让自己身体更好，目前只有53还是太瘦了和妹妹拼完一整个柜子的积木（目前四层已经塞满两层）谈恋爱，找女朋友入校后打算......
  • 2023-07-28 后端接口返回的数据与postman返回的数据不一致 ==》前端不兼容数据库字段
    前言：在传参一致，接口一致的情况下，微信开发者工具调的接口和postman返回的数据的id不一致。具体为：微信开发者工具端调接口拿到的id为22位的数据：1884661033952220199看起来平平无奇对吧，而postman返回的id则为：1884661033952220200是的，接口一样，传参一样，返回的其它数据也一样，唯独这......
  • 开源视频监控管理平台国标GB28181视频EasyCVR电子地图功能展示优化
    视频汇聚平台EasyCVR可拓展性强、视频能力灵活、部署轻快，可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等，以及厂家私有协议与SDK接入，包括海康Ehome、海大宇等设备的SDK等。视频监控综合管理平台EasyCVR可提供的视频能力包括：视频监控直播、云端录像、云存储、录像检索与回......
  • 算法学习笔记(28): 筛法
    筛法线性筛杜教筛放在偏序关系\((\Z,|)\)中卷积……如何快速的求\(S(n)=\sum_{i=1}^nf(i)\)。如果能够找到一个函数\(g\)：\[\begin{aligned}\sum_{i=1}^n(f*g)(i)&=\sum_{i=1}^n\sum_{d|i}f(\fracid)g(d)\\&=\sum_{d=1}^{n}g(d)\sum_{i......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99