Problem 1. 小 X 的加法難題

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

---

題目描述：
第一節(jié)編程課上，老師要求大家寫一個(gè)程序計(jì)算兩個(gè)正整數(shù)的和。
看到小 X 不屑的眼神后，老師決定給小 X 增加難度。以求 12 和 3 的和為例，老師在 12 + 3 這個(gè)
原始式子里加入一些無(wú)用的空格，再把它交給小 X。
這下小 X 傻眼了，希望你幫幫他。
Input
第一行包含一個(gè)字符串，表示老師給小 X 的式子。
Output
若式子的結(jié)果不超過(guò) 108，則第一行包含一個(gè)整數(shù)，表示式子的結(jié)果；否則第一行包含一個(gè)字符串“Large”。

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

Scoring
? 對(duì)于 30% 的數(shù)據(jù)，式子中不包含無(wú)用的空格，式子的結(jié)果不超過(guò) 108。 ? 對(duì)于 100% 的數(shù)據(jù)，字符串長(zhǎng)度不超過(guò) 100。

思路：
這其實(shí)求是一道大模擬題，我們只需注意下‘+’的位置，
然后分別將‘+’前后的字符串轉(zhuǎn)為數(shù)字出入a,b兩個(gè)變量。
然后，題目可能會(huì)有一百位的字符串輸入，所以我們
需要注意一下‘+’前后組成數(shù)字后的位數(shù)，大于8位就輸出
“Large”了。

#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 的密碼破譯

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

---

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

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

Example
password.in

3 0 0 2

password.out

2

Scoring

? 對(duì)于 30% 的數(shù)據(jù)，n ≤ 103。 ? 對(duì)于 60% 的數(shù)據(jù)，n ≤ 105。 ? 對(duì)于 100% 的數(shù)據(jù)，1 ≤ n ≤ 107，0 ≤ a, b, c ≤ 100。

思路：
根據(jù)題意模擬即可

#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 的液體混合

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

---

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

3 2
1 2
2 3

mixture.out

4

Scoring
? 對(duì)于 30% 的數(shù)據(jù)，n ≤ 10。
? 對(duì)于 100% 的數(shù)據(jù)，1 ≤ n ≤ 1000，a = b，同種反應(yīng)不會(huì)出現(xiàn)多次。

思路：
我們把題目分成多個(gè)集合，或是說(shuō)連通塊。設(shè)有x個(gè),那么它能貢獻(xiàn)的最大價(jià)值為 $2^{n?x}$

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

圖有點(diǎn)特別，不要在意！！
那它的最大貢獻(xiàn)肯定是：$2^{m?1}$ (m表示當(dāng)前這個(gè)連通塊有m個(gè)節(jié)點(diǎn))

根據(jù)題意，那按貪心來(lái)算，我們肯定是每次選這個(gè)塊中度最大的作為根節(jié)點(diǎn)，
然后再將與它相連的點(diǎn)為根節(jié)點(diǎn)，重復(fù)當(dāng)前操作。這個(gè)大家應(yīng)該都理解，
所以最后一定是在這個(gè)連通塊中的每一個(gè)點(diǎn)（除根節(jié)點(diǎn)外）都是可以
直接或間接與根節(jié)點(diǎn)發(fā)生化學(xué)反應(yīng)的。
那它的最大價(jià)值不就是$2^{m?1}$，減一是指根節(jié)點(diǎn)，因?yàn)榈谝淮渭尤氲囊后w
是沒(méi)有一個(gè)與它發(fā)生化學(xué)反應(yīng)的。

接著我們?cè)倩氐揭粋€(gè)大圖中，那最大價(jià)值是不是就是每一個(gè)
連通塊的價(jià)值和，即：Ans=2${}^{m_1?1}$+2${}^{m_2?1}$+2${}^{m_2?1}$…+2${}^{m_x?1}$
那有x個(gè)連通塊，是不是就是減去x個(gè)一，那x個(gè)連通塊的內(nèi)部節(jié)點(diǎn)個(gè)數(shù)，
不就是這個(gè)圖的總結(jié)點(diǎn)個(gè)數(shù)（x的意思看上文），so…最后答案就為 $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;
}