“思特奇杯”编程之星初赛——十一届蓝桥杯大赛省赛第二场C/C++大学B组

门牌制作

题面代码结果 既约分数

题面代码结果 蛇形填数

题面暴力枚举法代码结果 跑步锻炼

题面代码结果 七段码

题面暴力枚举法代码DFS求联通块代码结果 成绩统计

题面代码 回文日期

题面代码 子串分值和

题面代码 平面划分

题面代码 字串排序

题面代码

#include
using namespace std;
int main()
{
	int ans=0;
	for(int i=1;i<=2020;i++)
	{
		int j=i;
		while(j!=0)
		{
			if(j%10==2)
			ans++;
			j=j/10;
		}
	}
	cout< 
结果 
624
 
既约分数 
题面 
 
代码 
#include
#include 
using namespace std;
int main()
{
	int ans=0;
	for(int i=1;i<=2020;i++)
	{
		for(int j=1;j<=2020;j++)
		{
			if(__gcd(i,j)==1)
		    ans++;
	    }
    } 
    cout< 
结果 
2481215
 
蛇形填数 
题面 
 
暴力枚举法 
在模拟整个过程中，发现了一些规律，假设在同一斜线上的数为一组数，则一行一列的数在第一斜线，二行二列的数在第三斜线，三行三列的数在第五斜线，由此可以推出20行20列的数在第三十九斜线。而我们又可以观察出n行n列的数都在斜线的正中间，因此我们可以很快的算出1+2+3+……+38+39=780.
 这一列有39个数，而正中间的数则为761
 
代码 
#include
using namespace std;
int a[50][50];
int main(){
	 
	int id=0;//要填的数 
	for(int i=1;i<=40;i++){
		for(int j=0;j 
结果 
761
 
跑步锻炼 
题面 
 
代码 
#include 
using namespace std;
int M[13] = {0, 31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main() {
  int y = 2000, m = 1, d = 1, w = 6, ans = 2;
  while (y != 2020 || m != 10 || d != 1) {
    if (y % 400 == 0 || (y % 4 == 0 && y % 100)) {
      M[2] = 29;
    } else {
      M[2] = 28;
    }
    d++;
    w = (w + 1) % 7;
    if (d > M[m]) {
      d = 1;
      m++;
      if (m > 12) {
        m = 1;
        y++;
      }
    }
    if (d == 1 || w == 1) {
      ans++;
    }
    ans++;
  }
  cout << ans << endl;
  return 0;
}
 
结果 
8879
 
七段码 
题面 
 
暴力枚举法 
我是在经过罗列出所有的可能情况，最终发现：在一个二极管发光的情况有7种情况，两个二极管发光的情况有10种(ab,af,bc,bg,cg,cd,de,eg,ef,fg)，三个二极管发光的情况有16种（abf,abc,abg,afg,afe,bcd,bcg,bgf,bge,cgd,cgf,cge,cde,deg,def,efg），四个二极管发光的情况有20种（abcd,abcg,abcf,abge,abgf,abfe,afeg,bcde,bcdg,bcgf,bcge,bged,bgef,cdef,cdeg,cdgf,cgfa,cgfe,defg,defa），五个二极管发光的情况有19种，在七个里面任选5个是21种情况，排除（agced,afgbd）两种，剩下19种，六个二极管发光的情况有7种（一个发光），七个二极管发光的情况有1种。
 因此，加起来可知结果为80种。
 
代码 
#include
#include
using namespace std;
int fa[10];
bool vis[10];
// a -> 0    b -> 1   c -> 2
// d -> 3    e -> 4   f -> 5   g -> 6 
int ans;
int get(int cur){
	if(cur == fa[cur]) return cur;
	return get(fa[cur]);
}

void merge(int cx,int cy){
	int xx = get(cx);
	int yy = get(cy);
	
	fa[xx] = yy;
}
int main(){
	
	for(int st = 1;st < (1<<7);st ++){
		
		memset(vis,false,sizeof(vis));
		
		for(int i = 0;i <= 6;i ++) fa[i] = i;
		
		
		for(int i = 0;i <= 6;i ++){ //这里的从 0 开始计数也很巧，因为第一次是1左移0位 
			if(st & (1< 
DFS求联通块代码 
#include 
using namespace std;
const int N = 10;
char a[N][N];
int n, m, vis[N][N];

void dfs(int r, int c, int f) {
  if (r < 0 || r >= m || c < 0 || c >= n) {
    return;
  }
  if (vis[r][c] > 0 || a[r][c] != '1') {
    return;
  }
  vis[r][c] = f;
  for (int i = -1; i <= 1; i++){
    for (int j = -1; j <= 1; j++){
      if (i != 0 || j != 0){
        dfs(r + i, c + j, f);
      }
    }
  }
}

int main() {
  int sum = 0;
  freopen("in.txt", "r", stdin);
  while (~scanf("%d%d", &m, &n)) {
    for (int i = 0; i < m; i++){
      scanf("%s", a[i]);
    }
    memset(vis, 0, sizeof(vis));
    int cnt = 0;
    for (int i = 0; i < m; i++){
      for (int j = 0; j < n; j++){
        if (vis[i][j] == 0 && a[i][j] == '1'){
          dfs(i, j, ++cnt);
        }
      }
    }
    if (cnt == 1){
      sum += 1;
    }
  }
  printf("%dn", sum);
  return 0;
}


 
结果 
80
 
成绩统计 
题面 
 
代码 
#include
using namespace std;
int main()
{
	int n,x;
	int i=0,j=0; 
	cin>>n;
	int f=n;
	while(f!=0)
	{
	    cin>>x;
	    if(x>=60)
	    {
	    	i++;
		}
		if(x>=85)
		{
			j++;
		}
		f--;
	}
	double hege=i*1.0/n*1.0;
	double youxiu=j*1.0/n*1.0;
	int ans1=int(hege*1000+5)/10;
	int ans2=int(youxiu*1000+5)/10;
	cout< 
回文日期 
题面 
 
代码 
#include 
#include 
#include 
#include 
#include 
using namespace std;

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

bool hf(int n){
	int yy = n / 10000;
	int mm = n % 10000 / 100;
	int dd = n % 100;
	if(mm > 12) return false;
	if((yy%4==0 && yy%100!=0) || yy%400==0){
		day[2] = 29;
	}else{
		day[2] = 28;
	}
	if(dd > day[mm]) return false;
	return true;
}

bool rev(int n){
	stringstream ss;
	ss << n;
	string s = ss.str();
	string t = s;
	reverse(s.begin(), s.end());
	if(t == s) return true;
	return false;
}

int main(){
	int n;
	scanf("%d", &n);
	bool flag = 1;
	for(int i=n+1; i<1e8; i++){
		if(hf(i)){
			if(rev(i) && flag){
				printf("%dn", i);
				flag = 0;
			}
			if(rev(i)){
				stringstream ss2;
				ss2 << i;
				string s = ss2.str();
				if(s[0]==s[2] && s[0]==s[5] && s[0]==s[7]){
					if(s[1]==s[3] && s[1]==s[4] && s[1]==s[6]){
						printf("%d", i);
						break;
					}
				}
			}
		}
	}
	
	return 0;
}

 
子串分值和 
题面 
 
代码 
#include 
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
char s[N];
ll vis[40];
int main() {
  scanf("%s", s + 1);
  int n = strlen(s + 1);
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    ans += (i - vis[s[i] - 'a']) * (n - i + 1);
    vis[s[i] - 'a'] = i;
  }
  cout << ans << endl;
  return 0;
}

 
平面划分 
题面 
 
代码 
#include
#include
 
字串排序 
题面 
 
代码 
#include 
#include 
#include 

using namespace std;

const int N = 135, M = 10010;

int f[N][30][N];
//chcnt[i][j]记录第i个位置取字母j+'a'的逆序对最大值 
int chcnt[N][30];
//mlen[i]记录每个位置的最大值 
int mlen[N];

void dp()
{
	for (int i = 2; i < N; ++i)
	{
		int m = 0;
		for (int j = 1; j <= 'z' - 'a'; ++j)
		{
			for (int k = 1; k < i; ++k)
			{
				if (k > 1) f[i][j][k] = f[i - 1][j][k - 1] + i - k;
				else f[i][j][k] = chcnt[i - 1][j - 1] + i - 1;
				chcnt[i][j] = max(chcnt[i][j], f[i][j][k]);
			}
			m = max(m, chcnt[i][j]);
		}
		mlen[i] = m;
	}

}

int main()
{
	dp();

	int score = 0;
	cin >> score;
	//找出最短长度值
	int beg = 0;
	for (int i = 1; i < N; ++i)
		if (mlen[i] >= score)
		{
			beg = i;
			break;
		}

	int curr = 0;	//用于记录逆序值
	int same = 1;	//记录后缀中有多少个相同字母
	char last = 'z' + 1;//记录上一个字母是什么 
	for (int i = beg; i > 0; --i)
	{
		//从a开始枚举
		int j = 0;
		for (; j <= last - 'a'; ++j)
		{
			if (j == last - 'a') curr -= same;
			if (curr + chcnt[i][j] >= score)
			{
				curr += i - 1;
				break;
			}
		}
		if (j == last - 'a') same++;
		else
		{
			last = j + 'a';
			same = 1;
		}
		cout << last;
	}
	cout << endl;

	return 0;
}