CCF 2014-09


CCF 历年题目集

A. 相邻数对

排序,然后数相邻两个的值差为1的个数

#include 
#include 

using namespace std;

const int N = 10010;

int a[N];

int main()
{
    int n,x;
    cin >> n;
    int ans = 0;
    for (int i = 0 ; i < n ; i ++ ) cin >> a[i];
    sort(a,a+n);
    for (int i = 1 ; i < n ; i ++ )
    {
        if(abs(a[i]-a[i-1]) == 1) ans ++ ;
    }
    cout << ans << endl;
    return 0;
}

B. 画图

数据范围比较小,直接模拟做就行

#include 
using namespace std;
const int N = 110;
bool q[N][N];
int main()
{
	int n;
	cin >> n;

	int a,b,c,d;
	while(n -- )
	{
		cin >> a >> b >> c >> d;
		for (int i = a ; i <= c-1 ; i ++ )
		{
			for (int j = b ; j <= d-1 ; j ++ )
			{
				q[i][j] = true;
			}
		}
	}
	int ans = 0;
	for (int i = 0 ; i <= 100 ; i ++ )
	{
		for (int j = 0 ; j <= 100 ; j ++ )
		{
			if(q[i][j]) ans ++ ;
		}
	}
	cout << ans << endl;
	return 0;
}

C. 字符串匹配

若大小写不敏感直接比较,相反将其全部转换为大写或小写在再进行比较

#include 
using namespace std;
const int N = 100;
string s[N];

string change(string str,int type)
{
	if(!type) transform(str.begin(),str.end(),str.begin(),::tolower);
	return str;
}

int main()
{
	string str,str1;
	cin >> str;

	int type,n;
	cin >> type >> n;
	for (int i = 0 ; i < n ; i ++ )
	{
		cin >> s[i];
		if(change(s[i],type).find(change(str,type)) != string::npos)
		{
			cout << s[i] << endl;
		}
	}

	return 0;
}

D. 最优配餐

一个多源 bfs 的题,只需要将所有初始点加入队列,剩下的与单源 bfs 求最短路相同

#include 
using namespace std;

typedef long long ll;
const int N = 1005;

int n,m,k,d;
char s[N][N];
queue> q;
int dist[N][N];
bool st[N][N];
pair> T[N*N];
int dx[] = {-1,1,0,0},dy[] = {0,0,-1,1};

void bfs()
{
	while(q.size())
	{
		auto t = q.front();
		q.pop();

		for (int i = 0 ; i < 4 ; i ++ )
		{
			int a = t.first + dx[i], b = t.second + dy[i];
			
			if(a < 1 || a > n || b < 1 || b > n || st[a][b]) continue;
			if(s[a][b] == '#') continue;

			if(dist[a][b] > dist[t.first][t.second] + 1) {
				dist[a][b] = dist[t.first][t.second] + 1;
				st[a][b] = true;
				q.push({a,b});
			}
		}
	}
	return ;
}

int main()
{
	ios::sync_with_stdio(false);
	memset(dist,0x3f,sizeof dist);
	cin >> n >> m >> k >> d;

	int x,y,z;
	for (int i = 0 ; i < m ; i ++ )
	{
		cin >> x >> y;
		q.push({x,y});
		st[x][y] = true;
		dist[x][y] = 0;
	}
	for (int i = 0 ; i < k ; i ++ )
	{
		cin >> x >> y >> z;
		T[i] = {x,{y,z}};
	}
	for (int i = 0 ; i < d ; i ++ )
	{
		cin >> x >> y;
		s[x][y] = '#';	
	}

	bfs();

	ll ans = 0;
	for (int i = 0 ; i < k ; i ++ )
	{
		ans = ans + dist[T[i].first][T[i].second.first] * T[i].second.second;
	}
	cout << ans << endl;
	return 0;
}

E. 拼图

暂时不会~

CCF