2025.08.01课堂总结

八月正午的阳光~ 八月正午的阳光~ 八月正午的阳光~ 八月正午的阳光~ 八月正午的阳光~ 八月正午的阳光~ 八月正午的阳光~ 这可太唐了(悲)

T638482 小梦的铁索连环

这道题是一个图论题，但是经过严谨证明后，发现一个兵团的船数大于4时必定会有铁链相交。所以使用四重循环枚举即可

#include<bits/stdc++.h>
using namespace std;
int n, m, ans, a[10005];
bool p[500][500];
vector<int> g[500];//使用邻接矩阵
int main(){
	cin >> n >> m;
	for(int i=1; i <= n; i++) cin>>a[i];
	for(int i = 1; i <= m; i++){
		int u, v;
		cin>> u >> v;
		p[u][v] = p[v][u] = 1;//图的存储
		if(u > v) swap(u, v);
		g[u].push_back(v);
	}
	for(int i = 1; i <= n; i++){
		int size = g[i].size();
		for(int j = 0; j < size; j++){
			ans = max(ans, a[i] + a[g[i][j]]);
			for(int k = j + 1; k < size; k++){
				if(!p[g[i][j]][g[i][k]]) continue;
				ans = max(ans, a[i] + a[g[i][j]] + a[g[i][k]]);
				for(int h = k + 1; h < size; h++){//四重循环
					if(!p[g[i][h]][g[i][k]] || !p[g[i][h]][g[i][j]]) continue;
					ans = max(ans, a[i] + a[g[i][j]] + a[g[i][k]] + a[g[i][h]]);
				}
			}
		}
	}
	cout << ans;
	return 0;
} 

T638458 忙碌的老师

这道题我是重新按照题意直接用数组搓出来的，但老师建议使用优先队列写，下面是优先队列的部分语法知识：

priority_queue<type,vector<type>,greater<type> >name;//第一空填类型，第三空排序是按照第一空的数据类型排。greater<type>是从大到小，less<type>是从小到大

注意:

优先队列没有.back()函数，队头函数为.top()!

#include<bits/stdc++.h>
using namespace std;
struct P{
	int a, b;
}a[107891];
bool cmp(P x,P y){//排序规则
	return x.a < y.a;
}
int n, cnt = 1, e[107891], f;
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin>> a[i].a >> a[i].b;	
		e[i] = -1e9;
	}
	sort(a + 1, a + n + 1, cmp);//排序每个老师的下课时间
	for(int i = 1; i <= n; i++){//枚举每个老师的下课时间
		f = 0;
		for(int j = 1; j <= cnt; j++){
			if(e[j] < a[i].a){//还可以接着上课
				f = 1;
				e[j] = a[i].b;
				break;
			}
		}	
		if(f == 0){
			cnt++;//来新老师
			e[cnt] = a[i].b;
		}
	}
	cout << cnt;//输出总人数
	return 0;
} 

好了，今天的总结就写到这里了，感谢您的观看！😊😊😊