蓝桥校内训练赛

发表于 |
字数统计: 3.6k | 阅读时长 ≈ 19

蓝桥校内训练赛的总结

1

1
2
double n = 15.125;
printf("%0lf",n*1024);

2

有多少个约数可以用质因数定理，分解出来，比如 n = pow(a,a1)pow(b,a2)…则它总共质因数有(a1+1)(a2+1)个，然而这道题没有这么复杂直接for就行了……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n,t,k,sum=1,nn;
int a[10000];
void pp(int n)
{
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)
			a[k++]=i;
		while(n%i==0) n/=i;
	}
	if(n>1) a[k++]=n;
}
int main()
{
	SIS;
	//¼ÓËÙcin/cout
	n=1200000;
	nn=1200000;
	pp(n);
	for(int i=0;i<k;i++)
	{
		t=0;
		while(nn%a[i]==0){
	 		t++;nn/=a[i];		
		}
		sum=sum*(t+1);
	}
	pf("%d\n",sum);
	return 0;
}

3

包含9直接判断就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int sum=0;
bool pd(int x)
{
	while(x>0){
		int t=x%10;
		x/=10;
		if(t==9)
			return true;
	}
	return false;
}
int main()
{
	SIS;
	//¼ÓËÙcin/cout
	rep(i,1,2019){
		if(pd(i))
			sum++;
	}
	pf("%d\n",sum);
	return 0;
}

4

一看题我以为是道二叉树的题，然后想着二分……结果是个水题

1
printf("2018\n");

5

判断是不是数位递增的，可以先取出最后一个数，让其为最大，然后判断前一个数是不是比这个还大，如果前一个数比它大则不是数位递增，否则（else）就emmm直接将前一个数赋值为最大继续判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int a[10],sum,n;
bool pd(int x)
{
	int mmax=x%10;
	x/=10;
	while(x>0){
		int t=x%10;
		x/=10;
		if(t>mmax)
			return false;
		else
			mmax=t;
	}
	return true;
}
int main()
{
	SIS;
	//?¨®?¨´cin/cout
	cin>>n;
	rep(i,1,n){
		if(pd(i))
			sum++;
	}
	pf("%d\n",sum);
	return 0;
}

6

递增数列，数据太小了，直接暴力就行了，我一开始以为得用st表记录下每次查询结果来，一看数据，还是直接暴力吧……（所以看数据范围很主要）猥琐

题解，直接判断该元素左边有没有比它小大，右边有没有比它大的，如果同时满足，则ok改元素可以，sum++;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//F
#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
const int maxn=1e4+7;
int a[maxn],n;
bool pd(int x)
{
	if(x==1 || x==n)
		return false;
	int kk=a[x];
	int flag1=0,flag2=0;
	dep(i,x-1,1){
		if(a[i]<kk){
			flag1=1;
			break;
		}
	}
	if(flag1)
		rep(i,x+1,n){
			if(a[i]>kk){
				flag2=1;
				break;
			}
		}
	if(flag1 && flag2)
		return true;
	else
		return false;
}
int sum=0;
int main()
{
	SIS;
	//¼ÓËÙcin/c## 标题out
	cin>>n;
	rep(i,1,n){
		cin>>a[i];
	}
	rep(i,1,n){
		if(pd(i))
			sum++;
	}
	pf("%d\n",sum);
	return 0;
}

7

记住规则，辅，元，辅，元，这样判断就行了，直接道最后一个，想法很简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
bool pd(char c)
{
	if(c=='a' || c=='e' || c=='i' || c=='o' || c=='u')
		return true;
	else
		return false;
}
int main()
{
	SIS;
	//¼ÓËÙcin/cout
	string s;
	cin>>s;
	int pos,k,i;
	int flag1=0,flag2=0,flag3=0,flag4=0;
	for(i=0;i<s.size();i++)
	{
		if(!pd(s[i])){
			pos=i;
			flag1=1;
		}else break;
	}
	for(i=pos+1;i<s.size();i++)
	{
		if(pd(s[i])){
			pos=i;
			flag2=1;
		}else break;
	}
	for(i=pos+1;i<s.size();i++)
	{
		if(!(pd(s[i]))){
			pos=i;
			flag3=1;
		}else break;
	}
	for(i=pos+1;i<s.size();i++)
	{
		if(pd(s[i])){
			pos=i;
			flag4=1;
		}else break;
	}
	if(flag1 && flag2 && flag3 && flag4 && pos==s.size()-1)
		pf("yes\n");
	else
		pf("no\n");
	return 0;
}

8

一道很水的bfs题，我以为类似连通块结果不是，反正都是水……
思路：每个月草地会更新一次，周围上下左右都张草，每次记录下（存下来）有草的地方即可，（剪枝小技巧，每次张草后改地方下次不用再张了，因为其四周已经是草了，可以节省算法复杂度），然后这些个有草的地方四周都bfs一下就行了（也就是张个草）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
const int maxn=1010;
int a[maxn][maxn],vis[maxn][maxn];
int n,m,k;
int dd[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct node{
	int xx;
	int yy;
};
void bfs(int x,int y)
{
	if(a[x][y]==2 && !vis[x][y]){
		for(int i=0;i<4;i++)
		{
			int dx=x+dd[i][0];
			int dy=y+dd[i][1];
			if(dx>=1 && dx<=n &&dy>=1 && dy<=m)
			{
				a[dx][dy]=2;
			}
		}
	}
	vis[x][y]=1;
}
int main()
{
	SIS;
	//¼ÓËÙcin/cout
	cin>>n>>m;
	string s;
	rep(i,1,n){
		cin>>s;
		rep(j,1,m){
			if(s[j-1]=='g')
				a[i][j]=2;
			else
				a[i][j]=1;		
		}
	}
	cin>>k;
	while(k--){
		vector<node> v;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(a[i][j]==2 && !vis[i][j]){
					node temp;temp.xx=i;temp.yy=j;
					v.push_back(temp);					
				}
			}
		}
		for(int i=0;i<v.size();i++)
		{
			bfs(v[i].xx,v[i].yy);
		}	
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]==2)
				pf("g");
			else
				pf(".");
		}
		pf("\n");
	}
	return 0;
}

9

当时提交太快，好像细节忘处理了……还好只是训练赛 ，骄兵必败啊
思路：每次回溯到上一次，注意它能回溯的前提是每一项小于前两项的差的绝对值，所以可以根据这个条件一直回溯下去，直到i的值大于它两绝对值，之前好像做过类似的……

不过dfs可能会炸，所以可以根据这个打个表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n;
const int maxn=1007;
const int mod=10000;
int a[maxn][maxn];
int dfs(int x,int y)
{
	if(a[x][y]!=0) return a[x][y];
	a[x][y]=1;
	for(int i=1;i<abs(x-y);i++)
		a[x][y]+=dfs(y,i);
	return a[x][y]%mod;
}
int sum;
int main()
{
	SIS;
	//¼ÓËÙcin/cout
	cin>>n;
	rep(i,1,n){
		sum+=dfs(n,i);
		sum%=mod;
	}
	cout<<sum<<endl;
	return 0;
}

打表代码
打表是一种很有效的办法，处理数量不大的序列，之前貌似在东大camp碰到一个猥琐打表题……，忘补了，（所以切记，补题，补题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n;
const int maxn=1007;
const int mod=10000;
int a[maxn][maxn];
int dfs(int x,int y)
{
	if(a[x][y]!=0) return a[x][y];
	a[x][y]=1;
	for(int i=1;i<abs(x-y);i++)
		a[x][y]=(a[x][y]+dfs(y,i))%mod;
	return a[x][y]%mod;
}
int sum;
int main()
{
	SIS;
	//加速cin/cout
	cout<<"a[1001]=";
	cout<<"{0,";
	for(n=1;n<=1000;n++)
	{
		sum=0;
		rep(i,1,n){
			sum=(sum+dfs(n,i))%mod;
			sum%=mod;
		}
		if(n%30==0)
			cout<<endl;
		cout<<sum<<",";		
	}
	cout<<"}";
	return 0;
}

打表ac代码
复杂度o（1）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
using namespace std;
int a[1001]={0,1,2,4,7,14,26,53,106,220,452,946,1967,4128,8638,8144,8068,26,8127,3542,3277,3278,7643,5433,5774,8217,4846,687,3097,6887,
3556,4840,3454,5378,722,2230,767,1447,1839,4776,7618,7831,6222,5236,7802,5696,1835,1102,9537,1605,1227,3034,2159,1613,6811,3941,6794,5960,4903,75,
2158,349,4258,5189,4717,2894,4193,2890,258,2928,6125,2913,1482,8419,7244,1652,3440,2138,9272,4714,3333,3543,8834,6763,9180,1803,4631,6307,9056,3170,
8339,6213,1176,3258,272,4257,1893,8020,3682,9531,6961,4145,3086,3455,9057,1346,5768,6907,247,2450,4732,8653,8229,842,3346,9671,7106,3561,4952,9539,
1791,6208,6083,8838,7474,6854,198,7300,8219,5912,8884,3976,9650,4821,7317,9720,5572,3834,6326,2281,34,8409,28,445,8155,9846,9944,2504,3954,1639,
7243,8502,6926,1609,7449,3769,5695,6683,7531,6275,5827,6184,1982,736,9718,2777,7688,6626,7456,961,5556,7573,6886,4543,3957,2859,4666,9795,305,9052,
5350,9827,5445,6970,2599,7566,2848,2987,5179,1537,2392,6375,9621,7376,3301,1357,6545,7838,9390,4284,2631,1814,2566,7666,1110,5694,7595,5000,1290,4735,
5994,9401,6475,9012,5877,2867,7912,3509,5505,885,7490,5622,4374,8721,5134,8788,5430,3869,9852,5762,75,5964,262,5565,1599,7525,5388,8612,1143,7938,
7580,2953,7901,5629,1456,9852,5216,965,3739,7879,1212,9029,9263,9609,1926,8151,1997,6298,5125,5715,4864,3852,604,7652,313,6248,4077,3875,3816,7046,
9525,3798,6959,9366,2216,4463,6546,6367,614,9477,3176,4098,7162,7535,4696,749,2686,8212,9050,255,1389,287,1086,9414,9897,2293,31,9121,4682,7084,
8951,834,1051,2236,3712,6426,8642,185,785,8162,6015,658,8923,5741,2551,7629,2095,8882,7695,5629,8684,5116,6362,7701,9441,9403,1108,4395,5688,9466,
953,9191,4967,7236,6020,3465,8165,872,4530,3353,7859,1422,1504,6366,126,1246,1530,1777,8970,4590,2195,6920,9086,689,2163,6035,4961,2055,7699,4121,
3971,1824,3707,4405,854,6088,6971,1679,1779,7097,5696,2449,2104,3264,796,8595,6183,26,5597,7295,5926,9039,4550,9601,5959,3244,7451,5641,2343,6587,
3755,4361,3890,446,8187,1979,7000,7094,8658,1647,6090,8332,4407,4570,2340,3057,5029,5424,2736,4844,2771,5782,5912,3745,2504,2782,7247,1393,5403,7175,
9903,1723,7600,7021,4566,9778,5188,46,8542,7915,5043,4983,519,480,8199,1141,73,9316,6248,966,3218,6614,6974,5078,9775,7263,6263,7267,1947,5357,
286,674,3876,1985,4731,1850,512,1493,5310,5443,4183,5963,8642,1389,6320,4264,9565,7348,4378,6192,1300,3393,4794,8323,6063,9651,9368,7899,9053,4933,
5140,5604,9114,9299,7603,2485,884,7313,4139,9883,1405,9843,7419,1483,2031,8610,4150,3313,6257,3790,1688,994,1357,9660,583,5735,1548,7156,9678,8047,
3617,9611,7966,7764,5177,7716,4206,7985,6989,6318,5854,8292,9639,687,370,3252,7104,5813,758,8219,3809,2506,3605,9340,3559,4118,4757,8229,4258,944,
1596,4940,622,5832,1270,6948,1744,1125,7895,9348,7601,7426,1975,9611,3722,4143,4979,7904,3221,3817,5755,1798,6549,3463,3190,201,6894,6209,3488,670,
7643,7020,6164,5583,5036,6309,8644,7961,3465,7795,1486,4535,3111,5252,4049,4253,7515,1517,6148,2438,1296,8826,7924,7761,9126,6951,7110,7549,1170,8533,
793,1633,6451,6261,5887,8694,6447,8993,6398,1289,2925,2362,3935,6744,1358,1743,3937,9942,3696,1601,8295,3086,2595,9554,8566,1465,2109,3474,3950,9216,
8948,2020,3536,943,4934,8377,6171,1243,3525,259,3001,4205,4548,4754,2365,8630,4690,7872,5131,3995,2672,728,6532,9785,9379,5865,4774,6660,3721,4451,
9085,4771,8008,857,9737,5630,4040,3106,5997,4152,8542,3992,3294,5064,2656,5247,635,1521,3026,1502,9396,2171,7188,2425,9758,2640,8648,9454,274,9471,
8972,9301,911,6023,4155,126,7802,2948,5675,6313,69,1374,9925,3685,6901,432,1884,4803,8173,9638,3626,695,4286,3836,8670,8834,1444,5187,6281,2482,
8801,7656,9066,5138,5160,9857,906,5235,7243,5281,5103,5826,5023,3637,5607,1204,5697,3422,1192,8753,6087,2083,3256,8201,9853,1886,3953,4732,7351,6387,
9148,2299,4843,3891,3572,874,9873,1235,7323,8860,3439,113,5132,6521,1234,7427,4062,1342,2480,641,8802,9788,5336,3649,1301,3268,749,1628,9202,2689,
3284,9170,5252,1577,1705,5640,2185,2252,4943,271,5117,8699,2743,8221,2119,3851,701,2740,4247,7037,9764,4445,5848,6135,6166,5328,2584,1131,3005,8817,
2783,7749,6112,5567,9688,2549,7929,8650,60,1896,3998,7345,3352,8990,1143,873,1191,5821,9485,5249,3086,8016,9319,4139,3566,8871,7528,7873,4117,1085,
7064,8222,5947,4447,1326,5206,12,9703,5711,3951,219,6966,3168,2372,9603,9092,1904,1010,2704,2106,7568,3410,296,6825,9781,637,4465,7953,6861,2142,
2035,9743,1921,3051,7424,7112,7676,5245,9531,2284,4498,6423,6977,3106,1367,5696,2003,1291,3025,76,3147,9094,4580,5097,7390,8637,5853,359,3153,4957,
6635,5721,3353,2266,3481,7432,3020,7330,1172,5285,1525,2928,5331,8856,2163,5169,1465,4439,1876,7446,2192,5577,726,6599,352,3645,7733,8331,5447,8017,
5017,7287,6602,7248,6323,4195,9617,2263,4013,450,4073,6131,3569,9019,1858,9827,8118,4972,7422,9666,5760,9213,2817,7952,3948,8683,3645,6402,3264,1919,
9276,2519,190,766,8940,3413,2644,8048,83,9724,7009,3777,9663,2483,5752,4578,8951,5902,2170,9967,894,8556,6049,7254,2746,8962,8317,6848,767,7907,
1028,9458,6881,4978,6717,8210,3835,1064,7434,746,9449};
int main()
{
	int n;
	cin>>n;
	cout<<a[n]<<endl;
	return 0;
}

10

这是一个典型的贪心题，每次选m个，则一定是挑前m大的那几个数，但顺序不难打乱了。
这个题hash，vector，结构体数组好像都能过，我感觉还是set好用，代码特短。
思路：用两个vector容器存两个数组，然后一个存原始的数组，一个存排好序的数组（由大到小排序），然后将排好序的前m个元素放到set中，然后从原始数组中开始查找，看这个出现在set中没，如果出现则输出。
总复杂度，排序是nlogn，然后查找是logm，所以后面复杂度为nlogm，总复杂度为nlogn+nlogm，应该不会被tle吧，不是特别暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
vector<int> v,st;
set<int> s;
bool cmp(int a,int b)
{
	return a>b;
}
int n,m;
int main()
{
	SIS;
	//加速cin/cout
	cin>>n>>m;
	rep(i,1,n){
		int t;
		cin>>t;
		v.push_back(t);
		st.push_back(t);
	}
	sort(st.begin(),st.end(),cmp);
	rep(i,0,m-1){
		s.insert(st[i]);
	}
	rep(i,0,n-1){
		if(s.count(v[i])==1)
			pf("%d ",v[i]);
	}
	return 0;
}

*小结：此次校内赛，让我昨晚cf卡c题那个痛苦稍微缓解了一下，也证明了多打游戏手速会更快这个划掉，然后这次第9题稍微卡了一下，说明回溯还是得练习练习，还有好几个题比如9，10好像都可以st表过，可惜我线段树，st表不是太会，还是得练习啊，多打游戏，热爱生活，我tcl…… *

-------------本文结束感谢您这么好看还看我的文章-------------