上海月賽11月丙組解題報告-創(chuàng)新互聯

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

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

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

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

輸入格式

單個整數：表示 n。

輸出格式

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

數據范圍

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

樣例數據輸入:

輸出:

even

輸入:

-1

輸出:

odd

我的想法

簡單的奇偶數判斷，過

#includeusing namespace std;

int n;

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

搭積木題目描述

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

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

輸入格式

單個整數表示 n

輸出格式

單個整數表示金字塔的最高高度。

數據范圍

對于 50% 的數據，1≤n≤1,000
對于 100% 的數據，1≤n≤1,000,000,000

樣例數據輸入:

輸出:

說明:

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;
}

最長平臺題目描述

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

輸入格式

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

輸出格式

兩個整數：表示最長平臺的長度與最長平臺的數量

數據范圍

對于 50% 的數據，n≤1000
對于 100% 的數據，n≤500,000
1≤a_i≤1,000,000

樣例數據輸入:

7
2 2 2 1 3 3 3

輸出:

3 2

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

輸入:

5
3 1 4 1 5

輸出:

1 5

說明:
每個數字單獨成一個平臺

我的想法

從頭開始找，每一段平臺到頭了就比較是否比之前的大平臺大。如果大于的話，重新開始統(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 種，請問有多少種方法，能使相鄰兩塊積木的顏色均不相同？

輸入格式

輸入兩個正整數n,m

輸出格式

輸出滿足條件的方案數模10⁹+7的結果

數據范圍

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

樣例數據輸入:

3 2

輸出:

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

我的想法

這道題看上去難度不大，第一個積木有m種選擇，之后每一種都是m-1次選擇。
但是數據量非常大，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的、僅由小寫字母組成的字符串，將其按序依次放入棧中。

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

輸入格式

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

輸出格式

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

數據范圍

對于30%的數據，1≤n≤10
對于60%的數據，1≤n≤10³
對于100%的數據，1≤n≤10⁵

樣例數據輸入:

3
yes

輸出:

esy

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

我的想法

這道題我用數組模擬鏈表來做。首先找到一個字典序最小的，排在前的優(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)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

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

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

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

猜你還喜歡下面的內容