13年12月CCF计算机软件能力认证

总的来说第0次CCF认证的题目比较水 然而本菜鸡还是很多不会做
最大的收获是 T3 的单调栈

这道题太水了，当时提交后没存代码，这里复制的是闫老师的代码。

#include 
using namespace std;
const int N = 10010;
int n, s[N];

int main(){
    cin >> n;
    while (n--){
        int x;
        cin >> x;
        s[x] ++ ;
    }
    int res = 0;
    for (int i = 1; i < N; i ++ )
        if (s[i] > s[res]) res = i;
    cout << res << endl;
    return 0;
}

很水的模拟题（好像还是早年CSP普及组原题？），用python写的，也可用C++，直接放代码：

s = input()
s1 = s.replace('-', '')
sum = 0
for i in range(9):
    sum += int(s1[i]) * (i + 1)

sum = ('X' if sum % 11 == 10 else str(sum % 11))

if s1[-1] == sum:
    print('Right')
else:
    print(s[:-1], sum, sep='')

这道题目有的说了，菜鸡如我只会写暴力 O ( n 2 ) O(n^2) O(n2)做法，记得这个是单调栈经典题，但是想了很久也没想出来怎么套。一直希望能自己想出来所以迟迟没看题解 发现自己想多了 。
所以为了熟悉知识点，就先去做了洛谷的板子题：题目链接
之后就会做了，嗯。

先放暴力做法代码，思路是枚举每个矩形的高，然后找以此为矩形上底最远能到达的左右边界：

#include 
#include 
#include 
#include 
using namespace std;
const int maxn=1e4+5;

int n,a[maxn];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int ans=-1;
	for(int i=1;i<=n;i++){
		int l=i,r=i;
		while(a[l]>=a[i]&&l>=1) l--;
		while(a[r]>=a[i]&&r<=n) r++;
		ans=max(ans,(r-l-1)*a[i]);
	}
	printf("%dn",ans);
	return 0;
}

学了单调栈以后，就可以在 O ( n ) O(n) O(n)时间预处理好每个矩形的高对应的最远左右边界，具体是先用单调栈在 O ( n ) O(n) O(n)时间求出每个矩形左边第一个比自己矮的矩形的下标。同理求出右边第一个矮于自己的矩形下标。

最后再枚举每个矩形，通过左右边界和当前矩形高度求出面积，取最大值就是答案，也是 O ( n ) O(n) O(n)的。具体代码如下：

#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn=1e5+5;

int n,h[maxn],l[maxn],r[maxn];
stack s;

int main()
{
	scanf("%d",&n);

	for(int i=1;i<=n;i++){
		scanf("%d",&h[i]);
		l[i]=0;
		r[i]=n+1;
	}
	s.push(1);
	for(int i=1;i<=n;i++){
		while(!s.empty() && h[s.top()]>h[i]){
			r[s.top()]=i;
			s.pop();
		}
		s.push(i);
	}
	while(!s.empty()) s.pop();
	s.push(n);
	for(int i=n;i>0;i--){
		while(!s.empty() && h[s.top()]>h[i]){
			l[s.top()]=i;
			s.pop();
		}
		s.push(i);
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans, (ll)(r[i]-l[i]-1)*h[i]);
	}
	printf("%lldn",ans);		
	return 0;
}

这道题数据弱， O ( n 2 ) O(n^2) O(n2)的就可以过，所以这里放一个更强数据的 题目链接

一道组合计数题（也有别的做法如：状态机DP、更简单的递推公式）
这里放个链接，可以看到 大佬们的花式题解

一开始公式推对了，但是没有写对。
具体是取模了但没完全取模导致爆 long long 了，所以以为是公式推错了，想了很久才检查出来。

我的做法：
对于要求3：最高位数字不为0，其实没必要考虑，因为2开头的满足要求的数与0开头的数之间存在一一对应（01和23之间的关系的对等的，对应变换 0 ↔ 2 , 1 ↔ 3 0 leftrightarrow 2, 1 leftrightarrow 3 0↔2,1↔3 仍热满足要求），所以只需要求出满足条件1和条件2的个数，再除以2就行。
具体01一共有 k k k 个（ 2 ≤ k ≤ n − 2 2leq k leq n-2 2≤k≤n−2），剩下 n − k n-k n−k 个23。再分别确定01分界线和23分界线。
所以答案为： C n 2 × 1 × ( n − 3 ) + C n 3 × 2 × ( n − 4 ) + … + C n n − 2 × ( n − 3 ) × 1 C_n^2times 1 times (n-3) + C_n^3times 2 times (n-4)+ldots +C_n^{n-2}times (n-3) times 1 Cn2​×1×(n−3)+Cn3​×2×(n−4)+…+Cnn−2​×(n−3)×1.

代码见下：

#include 
#include 
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

ll exgcd(ll a, ll b, ll& x, ll& y){ 
    if(!b) { x=1, y=0; return a; } 
	ll r=exgcd(b,a%b,y,x);
	y-=(a/b)*x;
    return r;
}

ll inv(ll x){
	ll u,v;
	exgcd(x,mod,u,v);
	return u%mod;
}

int main()
{
	ll n; 
	scanf("%lld",&n);
	ll ans=0,tmp=n;
	for(ll i=2;i<=n-2;i++){
		tmp=((tmp*inv(i)%mod) *(n-i+1))%mod;  // 注意溢出，要取2次模
		ans=(ans+tmp*(i-1)*(n-1-i))%mod;
	}
	ans=ans*inv(2)%mod;
	if(ans<0) ans+=mod;
	printf("%lldn",ans);	
	return 0;
}

BTW 据说第五次CSP 最佳文章 这道题必须用 状态机DP做

DFS或BFS水题，效率最高的方法是分别从起点和终点DFS（或BFS），标记哪些方格可以走到，最后再扫一遍每个格子判断一下即可，复杂度是 O ( n ) O(n) O(n)的。
我写的是 O ( n 2 ) O(n^2) O(n2)的，数据比较小，也能过。
代码：

#include 
#include 
#include 
#include 
using namespace std;
typedef pair P;
const int maxn=55;

int R,C,sx,sy,ans;
char G[maxn][maxn];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
vector
 v;
bool flag,vis[maxn][maxn];

void dfs(int x,int y,bool mode){
	if(x<0||x>=R||y<0||y>=C||G[x][y]=='#'||vis[x][y]) return;
	vis[x][y]=1;
	if(mode) v.push_back(P(x,y));
	if(G[x][y]=='+'||G[x][y]=='S'||G[x][y]=='T'){
		if(G[x][y]=='T') flag=1;
		for(int i=0;i<4;i++){
			int xx=x+dx[i],yy=y+dy[i];
			dfs(xx,yy,mode);
		}
	}
	else if(G[x][y]=='-'){
		dfs(x,y-1,mode);
		dfs(x,y+1,mode);
	}
	else if(G[x][y]=='|'){
		dfs(x-1,y,mode);
		dfs(x+1,y,mode);
	}
	else if(G[x][y]=='.'){
		dfs(x+1,y,mode);
	}
	return;
}


int main()
{
	scanf("%d%d",&R,&C);
	for(int i=0;i
		for(int j=0;j
			scanf(" %c",&G[i][j]);
			if(G[i][j]=='S') sx=i,sy=j;
		}
	}
	dfs(sx,sy,1);
	if(!flag){
		printf("I'm stuck!n");
		exit(0);
	}
	for(auto p:v){
		memset(vis,0,sizeof vis);
		flag=0;
		dfs(p.first,p.second,0);
		if(!flag) ans++;
	}
	printf("%dn",ans);
	return 0;
}