CCF 历年题目集

A. 出现次数最多的数

map存储一下

#include 
using namespace std;
map mp;
int main()
{
	int n;
    cin >> n;
    int a;
    for (int i = 0 ; i < n ; i ++ )
    {
        cin >> a;
        mp[a] ++ ;
    } 
    int c = 0 , ans;
    for (auto t : mp)
    {
        if(t.second > c) {
            c = t.second;
            ans = t.first;
        }
    }
    cout << ans << endl;
    return 0;
} 

B. ISBN号码

按照题目要求模拟一下

#include 
using namespace std;
int main()
{
	string s;
	cin >> s;

	int r = 0 , c = 1;
	for (int i = 0 ; i < s.size()-1 ; i ++ )
	{
		if(isdigit(s[i])) {
			r += (s[i] - '0') * c;
			c ++ ;
		}
	}
	r %= 11;

	char k;
	if(r == 10) k = 'X';
	else k = char(r + '0');
	if(s[s.size()-1] == k) puts("Right");
	else cout << s.substr(0,s.size()-1) + k << endl;
	return 0;
}

C. 最大的矩形

这里看到 n 的范围不大，所以直接暴力\(O(n^2)\)做的

#include 
using namespace std;
typedef long long ll;
const int N = 1010;
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 = 0 ; i < n ; i ++ )
	{
		int mh = a[i];
		int ar = 0;

		for (int j = i; j < n ; j ++ )
		{
			if(mh > a[j]) mh = a[j];
			ar = max(ar,mh * (j-i+1));
		}
		ans = max(ans,ar);
	}
	cout << ans << endl;
	return 0;
}

D. 有趣的数

设 01 的个数有 k 个，那么 23 的个数为 n-k 个，题目要求最高位数字不为 0，

所以要在 n-1 个位置中选择 k 个位置放置 01 的方案数为\(C_{n-1}^{k}\)

同时由于所有 0 都必须放到所有 1 的前面，且必须保证每个数字都要出现至少一次，

那么 k 个位置的方案数为 k-1 个，同理 23 的方案数为 n-k-1

所以最终答案为 \(result = C_{n-1}^{k}*(k-1)*(n-k-1) \quad [k=1,2,3\cdots n-2]\)

#include 
using namespace std;
typedef long long ll;
const int N = 1000;
const int mod = 1e9+7;
ll c[N][N];
void init()
{
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (!j) c[i][j] = 1; // 初始化：C[i][0]的方案数为1
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}

int main()
{
	init();

	int n;
	cin >> n;
	
	ll res = 0;
	for (int k = 2 ; k <= n-2 ; k ++ )
	{
		res = res + c[n-1][k] * (k-1) * (n-k-1) % mod;
		res = res % mod;
	}
	cout << res << endl;
	return 0;
}

E. I’m stuck!

从 S 进行一次 dfs ，将可以到达的地方标记出来，然后从 T 倒着进行一次 dfs，

即判断该点附近的点是否可以到达该点，然后按照题目要求输出答案。

#include 
using namespace std;
const int N = 60;

int r,c;
char s[N][N];
int a1,b1,a2,b2;
bool st1[N][N],st2[N][N];
int dx[] = {-1,1,0,0},dy[] = {0,0,-1,1};

bool check(int x,int y,int k)
{
    if(s[x][y] == '+' || s[x][y] == 'S' || s[x][y] == 'T') return true;
    else if((k == 0 || k == 1) && s[x][y] == '|') return true;
    else if(k == 1 && s[x][y] == '.') return true;
    else if((k == 2 || k == 3 ) && s[x][y] == '-') return true;
    return false;
}

void dfs1(int x,int y)
{
    st1[x][y] = true;
    
    // 上下左右
    for (int i = 0 ; i < 4 ; i ++ )
    {
        int a = x + dx[i],b = y + dy[i];
        if(a < 0 || a >= r || b < 0 || b >= c || s[x][y] == '#' || st1[a][b] == true) continue;
        if(check(x,y,i)) {
            dfs1(a,b);
        }
    }
}

void dfs2(int x,int y)
{
    st2[x][y] = true;
    
    // 上下左右
    for (int i = 0 ; i < 4 ; i ++ )
    {
        int a = x + dx[i],b = y + dy[i];
        if(a < 0 || a >= r || b < 0 || b >= c || s[a][b] == '#' || st2[a][b] == true) continue;
        if(check(a,b,i ^ 1)) {
            dfs2(a,b);
        }
    }
}


int main()
{
    cin >> r >> c;
    for (int i = 0 ; i < r ; i ++ )
    {
        for (int j = 0 ; j < c ; j ++ )
        {
            cin >> s[i][j];
            if(s[i][j] == 'S') a1 = i , b1 = j;
            if(s[i][j] == 'T') a2 = i , b2 = j;
        }
    }
    dfs1(a1,b1);
    dfs2(a2,b2);
    
    if(!st1[a2][b2]) puts("I'm stuck!");
    else {
        int res = 0;
        for (int i = 0 ; i < r ; i ++ )
        {
            for (int j = 0 ; j < c ; j ++ )
            {
                if(st1[i][j] && !st2[i][j] && s[i][j] != '#') res ++ ;
            }
        }
        cout << res << endl;
    }
    return 0;
}