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. 拼图
暂时不会~