Problem 1. 小 X 的加法难题

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

---

题目描述：
第一节编程课上，老师要求大家写一个程序计算两个正整数的和。
看到小 X 不屑的眼神后，老师决定给小 X 增加难度。以求 12 和 3 的和为例，老师在 12 + 3 这个
原始式子里加入一些无用的空格，再把它交给小 X。
这下小 X 傻眼了，希望你帮帮他。
Input
第一行包含一个字符串，表示老师给小 X 的式子。
Output
若式子的结果不超过 108，则第一行包含一个整数，表示式子的结果；否则第一行包含一个字符串“Large”。

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

Scoring
? 对于 30% 的数据，式子中不包含无用的空格，式子的结果不超过 108。 ? 对于 100% 的数据，字符串长度不超过 100。

思路：
这其实求是一道大模拟题，我们只需注意下‘+’的位置，
然后分别将‘+’前后的字符串转为数字出入a,b两个变量。
然后，题目可能会有一百位的字符串输入，所以我们
需要注意一下‘+’前后组成数字后的位数，大于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 设了密码，
密码提示是四个整数，且输错后密码和提示就会重新生成。正当小 X 一筹莫展的时候，他打开小 Y 的抽屉，发现里面有一张小纸条，上面写着：“给出提示n, a, b, c，令 di = (a$i^2$ + bi + c) $mod$ 11111111(1 ≤ i ≤ n)，将序列 d 去除重复的数后从小到大排序得到序列 e，设序列 e 有 m 个数，则密码为 (${\sum }_{i=1}^{m}i{e}_i$) $mod$ 11111111。”
小 X 十分激动，想立刻完成密码破译，希望你帮帮他。

Input
第一行包含四个整数 n, a, b, c。
Output
第一行包含一个整数，表示密码。

Example
password.in

3 0 0 2

password.out

2

Scoring

? 对于 30% 的数据，n ≤ 103。 ? 对于 60% 的数据，n ≤ 105。 ? 对于 100% 的数据，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 的液体混合

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

---

题目描述：
虽然小 X 不喜欢化学原理，但他特别喜欢把一大堆液体倒在一起。
现在小 X 有 n 种液体，其中 m 对会发生反应。现在他想把这 n 种液体按某种顺序倒入一个容器
内，让他获得最刺激的体验，也就是使危险系数尽量大。
我们可以这样计算危险系数，一开始容器内没有任何液体，危险系数为 1。每次液体倒入容器时，
若容器内已有一种或多种液体会与这种液体发生反应，则危险系数会乘 2，否则危险系数不变。
最大危险系数小 X 不会算，希望你帮帮他。
Input
第一行包含两个整数 n, m。
接下来 m 行，每行包含两个整数 a, b，表示液体 a 和液体 b 会发生反应。
Output
第一行包含一个整数，表示最大危险系数。
Example
mixture.in

3 2
1 2
2 3

mixture.out

4

Scoring
? 对于 30% 的数据，n ≤ 10。
? 对于 100% 的数据，1 ≤ n ≤ 1000，a = b，同种反应不会出现多次。

思路：
我们把题目分成多个集合，或是说连通块。设有x个,那么它能贡献的最大价值为 $2^{n?x}$

解释一下，我们先来看对于某一个连通块，如下图：

图有点特别，不要在意！！
那它的最大贡献肯定是：$2^{m?1}$ (m表示当前这个连通块有m个节点)

根据题意，那按贪心来算，我们肯定是每次选这个块中度最大的作为根节点，
然后再将与它相连的点为根节点，重复当前操作。这个大家应该都理解，
所以最后一定是在这个连通块中的每一个点（除根节点外）都是可以
直接或间接与根节点发生化学反应的。
那它的最大价值不就是$2^{m?1}$，减一是指根节点，因为第一次加入的液体
是没有一个与它发生化学反应的。

接着我们再回到一个大图中，那最大价值是不是就是每一个
连通块的价值和，即：Ans=2${}^{m_1?1}$+2${}^{m_2?1}$+2${}^{m_2?1}$…+2${}^{m_x?1}$
那有x个连通块，是不是就是减去x个一，那x个连通块的内部节点个数，
不就是这个图的总结点个数（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;
}