CCF 历年题目集

A. 数列分段

#include 
using namespace std;
int main()
{
	int n;
	cin >> n;
	
	int x,c;
	int ans = 0 ;
	for (int i = 0 ; i < n ; i ++ ) 
	{
		cin >> x;
		if(c == x) continue;
		else ans ++ , c = x;
	}
	cout << ans << endl;
	return 0;
}

B. 日期计算

注意判断一下闰年，直接求就行

#include 
using namespace std;

int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

int main()
{
	int y,d;
	cin >> y >> d;

	int days = 0;
	if(y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) month[2] ++ ;

	for (int j = 1 ; j <= 12 ; j ++ )
	{
		if(days + month[j] >= d)
		{
			cout << j << endl << d-days << endl;
			break;
		}
		else days += month[j];
	}
}

C. 模板生成系统

这里我是用 map 存储对应的映射关系，然后遍历时遇到 '{' 就把后面的变量替换成 map 存储的值，并过滤掉对应的 '}' 和 ' '

#include 
using namespace std;
map mp;
string s[105];
int main()
{
	int m,n;
	cin >> m >> n;
	cin.ignore();

	for (int i = 0 ; i < m ; i ++ )
	{
		getline(cin,s[i]);
	}
	while(n -- )
	{
		string str1,str2;
		cin >> str1;
		cin.ignore();
		getline(cin,str2);
		str2 = str2.substr(1,str2.size()-2);
		mp[str1] = str2;
	}
	for (int i = 0 ; i < m ; i ++ )
	{
		for (unsigned j = 0 ; j < s[i].size() ; j ++ )
		{
			if(s[i][j] == '{' && s[i][j+1] == '{')
			{
			    int k = j;
			    string keys = "";
				while(s[i][k] == '{' || s[i][k] == ' ') k ++ ;
				while(s[i][k] != ' ') keys +=  s[i][k] , k ++ ;
				cout << mp[keys];
				j = k + 2;
			}
			else cout << s[i][j];
		}
		cout << endl;
	}
	return 0;
}

D. 高速公路

用 tarjan 求出强连通分量的个数，然后对每个强连通分量求2的组合数，结果相加即可得到答案

#include
using namespace std;
typedef long long ll;
const int N = 20010, M = 100010;

int e[M],h[N],ne[M],idx; // 邻接表存图
int stk[N],top; // 栈与栈顶指针
bool in_stk[N]; // 判断当前点是否在栈中
int dfn[N],low[N],times; // dfn 存遍历到该点的时间，low表示当前点所在的强连通分量的最小值
int color[N],scc_cnt; // 确定强连通分量的个数
int din[N],dout[N]; // 入度和出度
int sizes[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 ; i = ne[i])
	{
		int j = e[i];
		if(!dfn[j]) // 当前点未被遍历
		{
			tarjan(j); // 继续遍历该点
			low[u] = min(low[u],low[j]); // 若不在栈中，则一直取到下一个点在栈中，然后不断回溯最小值，这样u取到的就是子树的最小值
		}
		else if(in_stk[j]) low[u] = min(low[u],dfn[j]); // 若下一个点在栈中，则取最小值 
	}
	if(dfn[u] == low[u]) // 构成一个强连通分量
	{
		++ scc_cnt;
		int y;

		// 将同一联通分量的点染成相同颜色
		do {
			y = stk[top -- ];
			in_stk[y] = false;
			color[y] = scc_cnt;
			sizes[scc_cnt] ++ ;
		}while(y != u);
	}
}	

int main()
{
	memset(h,-1,sizeof h);

	int n,m;
	cin >> n >> m;

	int a,b;
	for (int i = 0 ; i < m ; i ++ )
	{
		cin >> a >> b;
		add(a,b);
	}

	// tarjan缩点
	for (int i = 1 ; i <= n ; i ++ )
	{
		if(!din[i]) tarjan(i);
	}
	
	long long ans = 0;

	for (int i = 1 ; i <= scc_cnt ; i ++ )
	{
		ans += (long long)(sizes[i] * (sizes[i]-1)) / 2;
	}

	cout << ans << endl;

	return 0;

}

E.

暂时不会~