Problem 1. 小 X 的(de)加法難題

Input file: sum.in
Output file: sum.out
Time limit: 1 second
Memory limit: 256 MB

---

題目描述：
第一節編程課上(shàng)，老師要(yào / yāo)求大(dà)家寫一個(gè)程序計算兩個(gè)正整數的(de)和(hé / huò)。
看到(dào)小 X 不(bù)屑的(de)眼神後，老師決定給小 X 增加難度。以(yǐ)求 12 和(hé / huò) 3 的(de)和(hé / huò)爲(wéi / wèi)例，老師在(zài) 12 + 3 這(zhè)個(gè)
原始式子(zǐ)裏加入一些無用的(de)空格，再把它交給小 X。
這(zhè)下小 X 傻眼了(le／liǎo)，希望你幫幫他(tā)。
Input
第一行包含一個(gè)字符串，表示老師給小 X 的(de)式子(zǐ)。
Output
若式子(zǐ)的(de)結果不(bù)超過 108，則第一行包含一個(gè)整數，表示式子(zǐ)的(de)結果；否則第一行包含一個(gè)字符串“Large”。

Example
sum.in
1 2 + 3
sum.out
15

Scoring
? 對于(yú) 30% 的(de)數據，式子(zǐ)中不(bù)包含無用的(de)空格，式子(zǐ)的(de)結果不(bù)超過 108。 ? 對于(yú) 100% 的(de)數據，字符串長度不(bù)超過 100。

思路：
這(zhè)其實求是(shì)一道(dào)大(dà)模拟題，我們隻需注意下‘+’的(de)位置，
然後分别将‘+’前後的(de)字符串轉爲(wéi / wèi)數字出(chū)入a,b兩個(gè)變量。
然後，題目可能會有一百位的(de)字符串輸入，所以(yǐ)我們
需要(yào / yāo)注意一下‘+’前後組成數字後的(de)位數，大(dà)于(yú)8位就(jiù)輸出(chū)
“Large”了(le／liǎo)。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#define ll long long
using namespace std;
const ll MAX=1e8;
string s;
ll a, b, i, al, bl;
int main()
{
	freopen("sum.in", "r", stdin);
	freopen("sum.out", "w", stdout);
	getline(cin, s);
	ll len=s.size();
	for(i=0; i<len; i++)
	{
		if(al>8) {printf("Large\n"); return 0;}
		if(s[i] >= '0' && s[i] <= '9') a=a * 10 + (s[i] - '0'), ++al;
		if(s[i] == '+') break;
		//printf("i=%d a=%d\n", i, a);
	}
	for(ll j=i; j<len; j++)
	{
		if(bl>8) {printf("Large\n"); return 0;}
		if(s[j] >= '0' && s[j] <= '9') b=b * 10 + (s[j] - '0'), ++bl;
	}
	//cout<<a<<' '<<b<<endl;
	if(a + b > MAX
	) printf("Large\n");
	else printf("%lld", a + b);
	return 0;
} 

Problem 2. 小 X 的(de)密碼破譯

Input file: password.in
Output file: password.out
Time limit: 1 second
Memory limit: 256 MB

---

題目描述：
這(zhè)天小 Y 有事外出(chū)，小 X 又忘記帶電腦了(le／liǎo)，于(yú)是(shì)想使用小 Y 的(de)電腦。不(bù)幸的(de)是(shì)，小 Y 設了(le／liǎo)密碼，
密碼提示是(shì)四個(gè)整數，且輸錯後密碼和(hé / huò)提示就(jiù)會重新生成。正當小 X 一籌莫展的(de)時(shí)候，他(tā)打開小 Y 的(de)抽屜，發現裏面有一張小紙條，上(shàng)面寫着：“給出(chū)提示n, a, b, c，令 di = (a$i^2$ + bi + c) $mod$ 11111111(1 ≤ i ≤ n)，将序列 d 去除重複的(de)數後從小到(dào)大(dà)排序得到(dào)序列 e，設序列 e 有 m 個(gè)數，則密碼爲(wéi / wèi) (${\sum }_{i=1}^{m}i{e}_i$) $mod$ 11111111。”
小 X 十分激動，想立刻完成密碼破譯，希望你幫幫他(tā)。

Input
第一行包含四個(gè)整數 n, a, b, c。
Output
第一行包含一個(gè)整數，表示密碼。

Example
password.in

3 0 0 2

password.out

2

Scoring

? 對于(yú) 30% 的(de)數據，n ≤ 103。 ? 對于(yú) 60% 的(de)數據，n ≤ 105。 ? 對于(yú) 100% 的(de)數據，1 ≤ n ≤ 107，0 ≤ a, b, c ≤ 100。

思路：
根據題意模拟即可

#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 11111111;
int n, a, b, c, ans;
bool v[MAXN];
int main() {
    freopen("password.in", "r", stdin);
    freopen("password.out", "w", stdout);
    scanf("%d%d%d%d", &n, &a, &b, &c);
    for (int i = 1; i <= n; ++i)
        v[(a * 1ll * i * i + b * 1ll * i + c * 1ll) % MAXN] = true;
    for (int i = 0, m = 0; i < MAXN; ++i)
        if (v[i]) ans = (ans + (++m) * 1ll * i) % MAXN;
    printf("%d", ans);
    return 0;
}

Problem 3. 小 X 的(de)液體混合

Input file: mixture.in
Output file: mixture.out
Time limit: 1 second
Memory limit: 256 MB

---

題目描述：
雖然小 X 不(bù)喜歡化學原理，但他(tā)特别喜歡把一大(dà)堆液體倒在(zài)一起。
現在(zài)小 X 有 n 種液體，其中 m 對會發生反應。現在(zài)他(tā)想把這(zhè) n 種液體按某種順序倒入一個(gè)容器
内，讓他(tā)獲得最刺激的(de)體驗，也(yě)就(jiù)是(shì)使危險系數盡量大(dà)。
我們可以(yǐ)這(zhè)樣計算危險系數，一開始容器内沒有任何液體，危險系數爲(wéi / wèi) 1。每次液體倒入容器時(shí)，
若容器内已有一種或多種液體會與這(zhè)種液體發生反應，則危險系數會乘 2，否則危險系數不(bù)變。
最大(dà)危險系數小 X 不(bù)會算，希望你幫幫他(tā)。
Input
第一行包含兩個(gè)整數 n, m。
接下來(lái) m 行，每行包含兩個(gè)整數 a, b，表示液體 a 和(hé / huò)液體 b 會發生反應。
Output
第一行包含一個(gè)整數，表示最大(dà)危險系數。
Example
mixture.in

3 2
1 2
2 3

mixture.out

4

Scoring
? 對于(yú) 30% 的(de)數據，n ≤ 10。
? 對于(yú) 100% 的(de)數據，1 ≤ n ≤ 1000，a = b，同種反應不(bù)會出(chū)現多次。

思路：
我們把題目分成多個(gè)集合，或是(shì)說(shuō)連通塊。設有x個(gè),那麽它能貢獻的(de)最大(dà)價值爲(wéi / wèi) $2^{n?x}$

解釋一下，我們先來(lái)看對于(yú)某一個(gè)連通塊，如下圖：

圖有點特别，不(bù)要(yào / yāo)在(zài)意！！
那它的(de)最大(dà)貢獻肯定是(shì)：$2^{m?1}$ (m表示當前這(zhè)個(gè)連通塊有m個(gè)節點)

根據題意，那按貪心來(lái)算，我們肯定是(shì)每次選這(zhè)個(gè)塊中度最大(dà)的(de)作爲(wéi / wèi)根節點，
然後再将與它相連的(de)點爲(wéi / wèi)根節點，重複當前操作。這(zhè)個(gè)大(dà)家應該都理解，
所以(yǐ)最後一定是(shì)在(zài)這(zhè)個(gè)連通塊中的(de)每一個(gè)點（除根節點外）都是(shì)可以(yǐ)
直接或間接與根節點發生化學反應的(de)。
那它的(de)最大(dà)價值不(bù)就(jiù)是(shì)$2^{m?1}$，減一是(shì)指根節點，因爲(wéi / wèi)第一次加入的(de)液體
是(shì)沒有一個(gè)與它發生化學反應的(de)。

接着我們再回到(dào)一個(gè)大(dà)圖中，那最大(dà)價值是(shì)不(bù)是(shì)就(jiù)是(shì)每一個(gè)
連通塊的(de)價值和(hé / huò)，即：Ans=2${}^{m_1?1}$+2${}^{m_2?1}$+2${}^{m_2?1}$…+2${}^{m_x?1}$
那有x個(gè)連通塊，是(shì)不(bù)是(shì)就(jiù)是(shì)減去x個(gè)一，那x個(gè)連通塊的(de)内部節點個(gè)數，
不(bù)就(jiù)是(shì)這(zhè)個(gè)圖的(de)總結點個(gè)數（x的(de)意思看上(shàng)文），so…最後答案就(jiù)爲(wéi / wèi) $2^{n?x}$

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e3+10;
int n, m, u, v, fa[N], tot, ans[N];
int find(int x) {return x == fa[x]? x : fa[x] = find(fa[x]);}
void unionn(int u, int v)
{
	int x = find(u), y = find(v);
	fa[x]=y;
}
void gjc()
{
	int x=0, temp;
	for(int i = N; i >= 1 ; i--)
	{
		temp = ans[i] * 2 + x;
		x = temp / 10;
		ans[i] = temp % 10;
	}
}
int main()
{
	freopen("mixture.in", "r", stdin);
	freopen("mixture.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) fa[i] = i; 
	for(int i = 1; i <= m; i++)
		scanf("%d%d", &u, &v), unionn(u, v);
	for(int i = 1; i <= n; i++)
		if(fa[i] == i) tot++;
	//printf("%d\n", tot);
	ans[N] = 1;
	for(int i = 1; i <= n - tot; i++) gjc(); 
	int j = 1;
	while(!ans[j]) j++;
	for(int i = j; i <= N; i++) printf("%d", ans[i]);
	return 0;
}