CCF 历年题目集

A. 最大波动

#include 
using namespace std;
const int N = 1005;
int a[N];
int main()
{
	int n;
	cin >> n;
	for (int i = 0 ; i < n ; i ++ ) cin >> a[i];

	int ans = 0;
	for (int i = 1 ; i < n ; i ++ )
	{
		ans = max(ans,abs(a[i]-a[i-1]));
	}
	cout << ans << endl;
	return 0;
}

B. 火车购票

用 vector 模拟每个车厢的座位，分成能在一排坐下和不能在一排坐下两种情况讨论

#include 
using namespace std;
vector v[20];
int main()
{
	int n;
	cin >> n;

	int c = 0;
	for (int i = 0 ; i < 20 ; i ++ )
		for (int j = 0 ; j < 5 ; j ++ )
			v[i].push_back(++c);

	int x;
	for (int i = 0 ; i < n ; i ++ )
	{
		cin >> x;

		for (int i = 0 ; i < 20 ; i ++ )
		{
			if(v[i].size() >= x)
			{
				while(x -- ) 
				{
					cout << v[i][0] << ' ';
					v[i].erase(v[i].begin());
				}
			cout << endl;
			}
		}
		if(x != -1)
		{
			for (int i = 0 ; i < 20 ; i ++ )
			{
				if(v[i].size()) 
				{
					while(x)
					{
						cout << v[i][0] << ' ';
						v[i].erase(v[i].begin());
						x -- ;
						if(x == 0 || v[i].size() == 0) break;
					}
				}
				if(x == 0) 
				{
					cout << endl;
					break;
				}
			}
		}
	}
	return 0;
}

C. 炉石传说

按照题目模拟就行，注意召唤时和战斗死亡时要更改位置就行

#include 
using namespace std;

struct Master
{
	int health,attack;
}m1[1010],m2[1010];

int h1 = 30,h2 = 30;
int c1 , c2;
vector v1, v2;

int main()
{
	int n;
	cin >> n;

	for (int i = 0 ; i < n ; i ++ )
	{
		string str;
		while(cin >> str)
		{
			if(str == "end") break;
			else if(str == "summon")
			{
				int pos,att,hea;
				cin >> pos >> att >> hea;
				if(i & 1) 
				{
					// 若该位置有随从
					for (int j = 7 ; j >= pos + 1 ; j -- )
					{
						m2[j] = m2[j-1];
					}
					m2[pos] = {hea,att};
				}
				else 
				{
					// 若该位置有随从
					for (int j = 7 ; j >= pos + 1; j -- )
					{
						m1[j] = m1[j-1];
					}
					m1[pos] = {hea,att};
				}
			}
			else if(str == "attack")
			{
				int att,def;
				cin >> att >> def;
				if(i & 1)
				{
					if(def == 0) h1 -= m2[att].attack;
					else
					{
						m2[att].health -= m1[def].attack;
						m1[def].health -= m2[att].attack;

						// 如果死亡
						if(m2[att].health <= 0) 
						{
							for (int i = att ; i <= 7 ; i ++ )
							{
								m2[i] = m2[i+1];
							}
						}
						if(m1[def].health <= 0) 
						{
							for (int i = def ; i <= 7 ; i ++ )
							{
								m1[i] = m1[i+1];
							}
						}
					}
				}
				else
				{
					if(def == 0) h2 -= m1[att].attack;
					else
					{
						m1[att].health -= m2[def].attack;
						m2[def].health -= m1[att].attack;

						// 如果死亡
						if(m1[att].health <= 0) 
						{
							for (int i = att ; i <= 7 ; i ++ )
							{
								m1[i] = m1[i+1];
							}
						}
						if(m2[def].health <= 0) 
						{
							for (int i = def ; i <= 7 ; i ++ )
							{
								m2[i] = m2[i+1];
							}
						}
					}
				}
			}
		}
	}
	if(h2 <= 0) puts("1");
	else if(h1 <= 0) puts("-1");
	else if(h1 && h2) puts("0");

	cout << h1 << endl;
	for (int i = 1 ; i <= 7 ; i ++ )
		if(m1[i].health > 0) v1.push_back(m1[i].health);
	
	cout << v1.size() << ' ';
	for (auto c : v1) cout << c << ' ';
	
	puts("");

	cout << h2 << endl;
	
	for (int i = 1 ; i <= 7 ; i ++ )
		if(m2[i].health > 0) v2.push_back(m2[i].health);
		
	cout << v2.size() << ' ';
		for (auto c : v2) cout << c << ' ';
	
	return 0;
}

D. 交通规划

先用 dijkstra 跑出各个点到 1 的最短距离，然后从其它顶点判断到 1 的距离，如果等于最短距离就加入

#include 
using namespace std;
typedef pair pii;

const int N = 10010,M = 200010;

int n,m;
int h[N],w[M],e[M],ne[M],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c)
{
	e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++ ;
}

void dijkstra()
{
	memset(dist,0x3f,sizeof dist);
	dist[1] = 0;

	priority_queue,greater > heap;
	heap.push({0,1});

	while(heap.size())
	{
		auto t = heap.top();
		heap.pop();

		int ver = t.second, distance = t.first;

		if(st[ver]) continue;
		st[ver] = true;

		for (int i = h[ver] ; ~i ; i = ne[i])
		{
			int j = e[i];
			if(dist[j] > distance + w[i])
			{
				dist[j] = distance + w[i];
				heap.push({dist[j],j});
			}
		}
	}
	return ;
}

int main()
{
	memset(h,-1,sizeof h);
	scanf("%d%d",&n,&m);
	
	int a,b,c;
	while(m -- )
	{
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c); 
	}
	dijkstra();

	int res = 0;
	// 倒着求解
	for (int i = 2 ; i <= n ; i ++ )
	{
		int road = 0x3f3f3f3f;
		for (int j = h[i] ; ~j ; j = ne[j])
		{
			int k = e[j];
			if(dist[i] == dist[k] + w[j])
			{
				road = min(road,w[j]);
			}
		}
		res += road;
	}
	printf("%d\n",res);
	return 0;
}

E. 祭坛

暂时不会~