上海月賽11月丙組解題報告

--------------cadifobp0802

創(chuàng)新互聯(lián)成立于2013年，先為武都等服務(wù)建站，武都等地企業(yè)，進行企業(yè)商務(wù)咨詢服務(wù)。為武都企業(yè)網(wǎng)站制作PC+手機+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。T1奇偶數(shù)的判定 題目描述

給定一個整數(shù) n，若 n 是一個偶數(shù)，輸出 even，若 n 是一個奇數(shù)，輸出 odd。

輸入格式

單個整數(shù)：表示 n。

輸出格式

單個字符串：表示 n 的奇偶性

數(shù)據(jù)范圍

?1,000,000≤n≤1,000,000

樣例數(shù)據(jù) 輸入:

0

輸出:

even

輸入:

-1

輸出:

odd

我的想法

簡單的奇偶數(shù)判斷，過

#includeusing namespace std;

int n;

int main(){scanf("%d", &n);
	if (n % 2 == 0)
		printf("even\n");
	else
		printf("odd\n");
	return 0;
}

搭積木 題目描述

小愛用積木搭起一座金字塔。為了結(jié)構(gòu)穩(wěn)定，金字塔的每一層要比上一層多一塊積木。規(guī)則如下：

第 1 層需要放 1 塊積木
第 2 層需要放 2 塊積木
第 3 層需要放 3 塊積木
第 i 層需要放 i 塊積木
給定積木的數(shù)量 n，請問最高可以搭出多少層的金字塔？

輸入格式

單個整數(shù)表示 n

輸出格式

單個整數(shù)表示金字塔的最高高度。

數(shù)據(jù)范圍

對于 50% 的數(shù)據(jù)，1≤n≤1,000
對于 100% 的數(shù)據(jù)，1≤n≤1,000,000,000

樣例數(shù)據(jù) 輸入:

12

輸出:

4

說明:

4層金字塔需要1+2+3+4=10塊積木，而5層金字塔需要1+2+3+4+5=15塊積木，在12塊積木的情況下，最多搭4層金字塔

我的想法

用高斯公式循環(huán)求和（或者直接累加），大于所給積木就輸出。
代碼如下：

#includeusing namespace std;

int n;

int main(){scanf("%d", &n);
	for (int i = 1; i<= n; ++i) {if (i * (i + 1) / 2 >n) {	printf("%d\n", i - 1);
			break;
		}
	}
	return 0;
}

最長平臺 題目描述

給定一個整數(shù)數(shù)列 a₁,a₂,…,a_n
?，請找出最長平臺，并輸出最長平臺的數(shù)量（數(shù)字相等但位置不同的平臺算作不同的平臺）。
所謂平臺，就是指數(shù)列中一段連續(xù)的、完全相等的數(shù)字，單個數(shù)字可以成為一個平臺。

輸入格式

第一行：單個整數(shù) n
第二行：n 個整數(shù) a₁,a₂,…,a_n

輸出格式

兩個整數(shù)：表示最長平臺的長度與最長平臺的數(shù)量

數(shù)據(jù)范圍

對于 50% 的數(shù)據(jù)，n≤1000
對于 100% 的數(shù)據(jù)，n≤500,000
1≤a_i≤1,000,000

樣例數(shù)據(jù) 輸入:

7
2 2 2 1 3 3 3

輸出:

3 2

說明:
最長平臺為2 2 2或3 3 3

輸入:

5
3 1 4 1 5

輸出:

1 5

說明:
每個數(shù)字單獨成一個平臺

我的想法

從頭開始找，每一段平臺到頭了就比較是否比之前的大平臺大。如果大于的話，重新開始統(tǒng)計，如果等于的話，統(tǒng)計+1，否則不統(tǒng)計。
代碼如下：

#includeusing namespace std;
#define MAXN 500010

int n, a[MAXN], s, ans = 0, cnt = 0;

int main(){scanf("%d", &n);
	for (int i = 1; i<= n; ++i)
		scanf("%d", &a[i]);
	int t = a[1];
	s = 1;
	a[n + 1] = a[n] - 1;//為了最后一次判斷特地增加一個最少的
	for (int i = 2; i<= n + 1; ++i) {if (a[i] != t) {	if (s >ans) {		ans = s;
				cnt = 1;
			}
			else if (s == ans)
				cnt++;
			t = a[i];
			s = 1;
		}
		else
			s++;
	}
	printf("%d %d\n", ans, cnt);
	return 0;
}

積木染色 題目描述

有 n 塊積木排成一排，小愛需要給每塊積木染色，顏色有 m 種，請問有多少種方法，能使相鄰兩塊積木的顏色均不相同？

輸入格式

輸入兩個正整數(shù)n,m

輸出格式

輸出滿足條件的方案數(shù)模10⁹+7的結(jié)果

數(shù)據(jù)范圍

對于 30% 的數(shù)據(jù)，1≤n,m≤10
對于 60% 的數(shù)據(jù)，1≤n,m≤10⁴
對于 100% 的數(shù)據(jù),1≤n≤10¹⁵,1≤m≤10⁹

樣例數(shù)據(jù) 輸入:

3 2

輸出:

2

說明:
合法的染色方案有：{1,2,1} {2,1,2}

我的想法

這道題看上去難度不大，第一個積木有m種選擇，之后每一種都是m-1次選擇。
但是數(shù)據(jù)量非常大，n大能到10的15次方。我便采取一種硬核的遍歷方式：
如果n<=10⁷,直接循環(huán)；
如果n>10⁷,先循環(huán)到10⁷，然后拿10⁷，開方，最后解決一些零頭。
代碼如下：

#includeusing namespace std;
#define ll long long
#define MODD 1000000007

ll n, m;

int main(){scanf("%lld%lld", &n, &m);
	ll k = m;
	m -= 1;
	n -= 1;
	ll mm = m;
	if (n< 1e7) {for (ll i = 2; i<= n; ++i) {	mm *= m;
			mm %= MODD;
		}
		k *= mm;
		k %= MODD;
	}
	else {for (ll i = 2; i<= 1e7; ++i) {	mm *= m;
			mm %= MODD;
		}
		ll z7 = n / 1e7, lt = n - z7 * 1e7, mmm = mm;
		for (ll i = 2; i<= z7; ++i) {	mmm *= mm;
			mmm %= MODD;
		}
		for (int i = 1; i<= lt; ++i) {	mmm *= m;
			mmm %= MODD;
		}
		k *= mmm;
		k %= MODD;
	}
	printf("%lld\n", k);
	return 0;
}

出棧序列 題目描述

給定一個長度為n的、僅由小寫字母組成的字符串，將其按序依次放入棧中。

請問在所有可能的出棧序列中，字典序最小的出棧序列是多少？

輸入格式

輸入第一行， 一個正整數(shù)n
輸入第二行，一個長度為n的字符串

輸出格式

輸出所有出棧序列中，字典序最小的出棧序列

數(shù)據(jù)范圍

對于30%的數(shù)據(jù)，1≤n≤10
對于60%的數(shù)據(jù)，1≤n≤10³
對于100%的數(shù)據(jù)，1≤n≤10⁵

樣例數(shù)據(jù) 輸入:

3
yes

輸出:

esy

說明:
字符y、e、s依次進棧，所有出棧的可能性有：
{yes}、{yse}、{eys}、{esy}、{sey}
其中 {esy} 的字典序最小

我的想法

這道題我用數(shù)組模擬鏈表來做。首先找到一個字典序最小的，排在前的優(yōu)先。找到后再拿這個字母前一個和后面所有進行比較，優(yōu)先輸出靠前的。
代碼如下：

#includeusing namespace std;
#define MAXN 100010

struct nod{int next, last;
	char c;
};

int n, id;
char op;
nod ca[MAXN];

void dfs(int w, int el) {cout<< ca[w].c;
	ca[ca[w].last].next = ca[w].next;
	ca[ca[w].next].last = ca[w].last;
	if (el == 0)
		return;
	int wl = ca[w].last;
	if (wl< 1)
		wl = ca[w].next;
	int p = ca[wl].next;
	while (p<= n) {if (ca[p].c< ca[wl].c) {	wl = p;
		}
		p = ca[p].next;
	}
	dfs(wl, el - 1);
}

int main(){cin >>n;
	for (int i = 1; i<= n; ++i) {cin >>ca[i].c;
		ca[i].last = i - 1;
		ca[i].next = i + 1;
		if (i == 1) {	op = ca[i].c;
			id = 1;
		}
		if (op >ca[i].c) {	op = ca[i].c;
			id = i;
		}
	}
	dfs(id, n - 1);
	cout<< endl;
	return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：上海月賽11月丙組解題報告-創(chuàng)新互聯(lián)
文章出自：http://sd-ha.com/article4/hidoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供虛擬主機、網(wǎng)站策劃、網(wǎng)站收錄、網(wǎng)站制作、商城網(wǎng)站、網(wǎng)站設(shè)計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)