ブルーブリッジカップ第11回ソフトウェア類校内模擬試合——C/C++プログラム設計

第一題
考え方:この問題は約数個の数を求めて、データは暴力的ではありませんて、複雑度O(n)O(n)O(n);しかし、約数O(n)O(sqrt{n})O(n)を求めるアルゴリズムは、コード:

#include

using namespace std;

int divisor(int n) {
	int rs = 0;
	for(int i = 1; i * i <= n; i++) {
		if(n % i == 0) {
			++rs;
			if(i * i != n) ++rs;	
		}
	}
	return rs;
}

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	cout << divisor(1200000);
	return 0;
}

第二題
構想:1 GB=1024 MBコード:

#include

using namespace std;

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	cout << 15.125 * 1024;
	return 0;
}

第三題
構想:全部で2019個の結点があれば、1本の結点で、2018個の葉の結点でいいです.コード:

\\ 

第四題
考え方:すべての数を一つ一つチェックすればいいコード:

#include

using namespace std;

inline bool check(int n) {
	while(n) {
		if(n % 10 == 9) return true;
		n /= 10;
	}
	return false;
}

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	int ans = 0;
	for(int i = 1; i <= 2019; i++) {
		if(check(i)) ++ans;
	}
	cout << ans;
	return 0;
}

第五題
考え方:すべての数を一つ一つチェックすればいいです.コード:

#include

using namespace std;

inline bool check(int n) {
	int p, q = -1;
	while(n) {
		p = n % 10;
		n /= 10;
		if(~q && q < p) return false;
		q = p;
	}
	return true;
}

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	int n, ans = 0;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		if(check(i)) ++ans;	
	}
	printf("%d", ans);
	return 0;
}

第六題
構想:それぞれ正着、逆さまにシーケンスを繰り返し、同時に最小、最大値を維持すればよい.コード:

#include

using namespace std;

const int maxn = 1005;
int n, a[maxn];
bool tag[maxn];

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", a + i);
	}
	int mn = a[1];
	for(int i = 2; i < n; i++) {
		tag[i] = true;
		mn = min(mn, a[i - 1]);
		if(mn >= a[i]) tag[i] = false;
	}
	int mx = a[n], ans = 0;
	for(int i = n - 1; i > 1; i--) {
		mx = max(mx, a[i + 1]);
		if(mx <= a[i]) tag[i] = false;
		if(tag[i]) ++ans;
	}
	printf("%d", ans);
	return 0;
}

第七題
考え方:1.母音アルファベットの位置を1、子音アルファベットの位置を0とします.2.c++に内蔵されたunique関数を使用すると、隣接する位置の重複要素を容易に除去することができる.3.unique関数で得られたシーケンスが0 1 0 1である場合にのみ、要求に合致する.コード:

#include

using namespace std;

inline int check(char & c) {
	if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
		return 1;	
	}
	return 0;
}
char s[105];

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	scanf("%s", s);
	vector<int> v;
	int n = strlen(s);
	for(int i = 0; i < n; i++) {
		v.push_back(check(s[i]));	
	}
	int len = unique(v.begin(), v.end()) - v.begin();
	if(len != 4) puts("no"), exit(0);
	for(int i = 0; i < 4; i++) {
		if(v[i] != (i & 1)) puts("no"), exit(0);
	}
	puts("yes");
	return 0;
}

第八題
構想:すべての初期がgである位置をソース点と見なし、その後、マルチソースbfsを行って残りのすべての点の最短経路を求める.最短経路長は、その点がgになるために必要な最小日数である.コード:

#include

using namespace std;

int n, m, k;
int g[1005][1005];
char s[1005];
struct node { int x, y; };
queue<node> que;

inline void check(int a, int b, int & x, int & y) {
	if(g[a][b] > g[x][y] + 1) {
		g[a][b] = g[x][y] + 1;
		que.push(node{a, b});
	}
}

void bfs() {
	while(!que.empty()) {
		node now = que.front();
		que.pop();
		int x = now.x, y = now.y;
		check(x - 1, y, x, y);
		check(x + 1, y, x, y);
		check(x, y - 1, x, y);
		check(x, y + 1, x, y);
	}
}

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) {
		scanf("%s", s);
		for(int j = 1; j <= m; j++) {
			g[i][j] = 1 << 30;
			if(s[j - 1]	== 'g') {
				g[i][j] = 0;
				que.push(node{i, j});	
			}
		}
	}
	scanf("%d", &k);
	bfs();
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++)	{
	//		cerr << g[i][j] << ' ';
			if(g[i][j] <= k) putchar('g');
			else putchar('.');
		}
		putchar('
');
	}
	return 0;
}

第九題
構想:記憶化dfsで答えを検索し、dp[i][j]dp[i][j]dp[i][j]dp[i][j]はこの時点の末尾がi、j i、jの場合、次の可能性を表す.ローカル実行時にn n nが1000,1000,1000に達するとタイムアウトが発生し、テーブル(テーブルを打つ真香打表コード:

#include

using namespace std;

const int mod = 10000;
const int maxn = 1005;
int n, dp[maxn][maxn], a[10005], ans;

int dfs(int p) {
	int d = abs(a[p - 1] - a[p - 2]);
	if(d == 0 || d == 1) return 1;
	if(dp[a[p - 1]][a[p - 2]]) return dp[a[p - 1]][a[p - 2]];
	int rs = 1;
	for(int i = 1; i < d; ++i) {
		a[p] = i;
		rs = (rs + dfs(p + 1)) % mod;	
	}
	return dp[a[p - 1]][a[p - 2]] = rs;
}

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	scanf("%d", &n);   //        n   1 1000  
	a[1] = n;
	for(int i = n; i >= 1; --i) {
		a[2] = i;
		ans = (dfs(3) + ans) % mod;	
	}
	printf("%d", ans);
	return 0;
}

送信コード:

#include

using namespace std;

int a[1010] = {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() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	int n;
	scanf("%d", &n);
	printf("%d", a[n]);
	return 0;
}

第十題
考え方:1.問題の意味は簡単で、区間の最大値と最大値の位置を求めるたびにいいです.2.例えばn n個の番組を合計してk k個の番組を選択し、初めて求めるときには[0,n−k][0,n−k][0,n−k][0,n−k]区間の最大値とその位置p 0 p_0 p 0(選択後、少なくともk−1 k−1 k−1番組があることを保証するため)、2回目は[p 0+1,n−k+1][p_0+1,n−k+1][p 0+1,n−k+1][p 0+1,n−k+1]区間の最大値とその位置を求める;...k k個を順次求めるだけでよい;3.暴力的であれば複雑度はO(k n)O(kn)O(kn)O(kn)であり、少しは取れるが効率的ではない;区間RMQ問題に遭遇した場合の線分ツリーの効率は非常に高く,O(k l o g n)O(klogn)O(klogn)O(klogn)時間でコードを解くことができる2つの線分ツリーが区間最大値と区間最大値をそれぞれ維持する位置を確立した.

#include

using namespace std;

const int maxn = 100005;
int n, m, _n, dat[maxn << 2], pos[maxn << 2];

void init_() {
	_n = 1;
	while(_n < n) _n <<= 1;
	for(int i = 1; i <= n; i++) {
		pos[i + _n - 1] = i;	
	}
}
inline void update(int k, int a) {
	k += _n - 1;
	dat[k] = a;
	while(k > 1) {
		k = k >> 1; 
		if(dat[k << 1] >= dat[k << 1 | 1]) {
			dat[k] = dat[k << 1];
			pos[k] = pos[k << 1];
		}else {
			dat[k] = dat[k << 1 | 1];
			pos[k] = pos[k << 1 | 1];	
		}
	}
}
typedef pair<int, int> P;
#define fi first 
#define sc second 
inline P query(int a, int b, int k, int l, int r) {   // max value of [a, b]
	if(b < l || a > r) return P(0, 0);
	if(l >= a && r <= b) return P(dat[k], pos[k]);
	P p1 = query(a, b, k << 1, l, (l + r) >> 1);
	P p2 = query(a, b, k << 1 | 1, (l + r) / 2 + 1, r);
	if(p1.fi >= p2.fi) return p1;
	else return p2;
}

int main() {
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	scanf("%d %d", &n, &m);
	init_();
	for(int i = 1; i <= n; i++) {
		int v;
		scanf("%d", &v);
		update(i, v);	
	}
	int s = 1;
	while(m--) {
		P p = query(s, n - m, 1, 1, _n);
		printf("%d ", p.fi);
		s = p.sc + 1;
	}
	return 0;
}