CCF 历年题目集

A. 门禁系统

用 map 记录次数

#include <bits/stdc++.h>
using namespace std;
map<int,int> mp;
int main()
{
	int n;
	cin >> n;

	int x;
	for (int i = 0 ; i < n ; i ++ )
	{
		cin >> x;
		mp[x] ++ ;
		cout << mp[x] << ' ';
	}
	return 0;
}

B. Z字形扫描

按照题目模拟，这里可以一直走到出界再换方向，这样代码量会小点

#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int a[N][N];
int main()
{
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; i ++ )
		for (int j = 1 ; j <= n ; j ++ )
			cin >> a[i][j];
	
	int type = 2; // 1 左下, 2 右上
	vector<int> ans;
	int x = 1 , y = 1;
	while(x != n+1 || y != n+1)
	{
		if(1 <= x && x <= n && 1 <= y && y <= n) ans.push_back(a[x][y]);

		if(type == 1) x ++ , y -- ;
		else x -- , y ++ ;

		if(y <= 0) y = 1,type = 2;
		if(x <= 0) x = 1, type = 1;
	}
	for (auto t : ans) cout << t << ' ';
	return 0;
}

C. 集合竞价

用结构体模拟指令，然后按照题目要求做即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5005;
struct node
{
	string str;
	double mon;
	int num;
	bool f = 0; // 1 is cancel
}p[N];

int main()
{
	int n = 0;
	string s;
	while(cin >> s)
	{
		n ++ ;
		p[n].str = s;
		if(s == "buy") cin >> p[n].mon >> p[n].num;
		else if(s == "sell") cin >> p[n].mon >> p[n].num;
		else
		{
			int u;
			cin >> u;
			p[u].f = 1;
		}
	}
	ll res = 0;
	double ans = 0;
	for (int i = 1 ; i <= n ; i ++ )
	{
		if(p[i].f) continue;
		ll num1 = 0,num2 = 0;
		double trade = p[i].mon;
		for (int j = 1 ; j <= n ; j ++ )
		{
		    if(p[j].f) continue;
			else if(p[j].str == "buy" && p[j].mon >= trade) num1 += p[j].num;
			else if(p[j].str == "sell" && p[j].mon <= trade) num2 += p[j].num; 
		}
		num1 = min(num1,num2);
		if(res < num1) res = num1 , ans = trade;
		else if(res == num1) ans = max(ans,trade);
	}
	cout << fixed << setprecision(2) << ans << ' ' << res << endl;
	return 0;
}

D. 最优灌溉

题目描述可以直观地看出，是求最小生成树

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = N * 2 , INF = 0x3f3f3f3f;

int n,m;
int p[N];

struct Edge
{
	int a,b,w;

	bool operator< (const Edge &W) const
	{
		return w < W.w;
	}
}edges[M];

int find(int x)
{
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}

int kruskal()
{
	sort(edges,edges+m);
	for (int i = 1 ; i <= n ; i ++ ) p[i] = i;

	int res = 0,cnt = 0;
	for (int i = 0 ; i < m ; i ++ )
	{
		int a = edges[i].a , b = edges[i].b , w = edges[i].w;

		a = find(a),b = find(b);
		if(a != b)
		{
			p[a] = b;
			res += w;
			cnt ++ ;
		}
	}

	if(cnt < n-1) return INF;
	return res;
}

int main()
{
	cin >> n >> m;
	for(int i = 0 ; i < m ; i ++ )
	{
		int a,b,w;
		cin >> a >> b >> w;
		edges[i] = {a,b,w};
	}
	int t = kruskal();

	cout << t << endl;

	return 0;
}

E. 货物调度

暂时不会~