NOIP 2014 模擬賽 普及組

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 i^2 i2 + bi + c) m o d mod mod 11111111(1 ≤ i ≤ n)，將序列 d 去除重復的數后從小到大排序得到序列 e，設序列 e 有 m 個數，則密碼為 ( ∑ i = 1 m i e i \sum_{i=1}^{m} ie_i ∑i=1m?iei?) m o d mod 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^{n-x} 2n?x

解釋一下，我們先來看對于某一個連通塊，如下圖：

圖有點特別，不要在意！！
那它的最大貢獻肯定是： 2 m ? 1 2^{m-1} 2m?1 (m表示當前這個連通塊有m個節點)

根據題意，那按貪心來算，我們肯定是每次選這個塊中度最大的作為根節點，
然后再將與它相連的點為根節點，重復當前操作，這個大家應該都理解，
所以最后一定是在這個連通塊中的每一個點（除根節點外）都是可以
直接或間接與根節點發生化學反應的，
那它的最大價值不就是 2 m ? 1 2^{m-1} 2m?1，減一是指根節點，因為第一次加入的液體
是沒有一個與它發生化學反應的，

接著我們再回到一個大圖中，那最大價值是不是就是每一個
連通塊的價值和，即：Ans=2 m 1 ? 1 ^{m_1-1} m1??1+2 m 2 ? 1 ^{m_2-1} m2??1+2 m 2 ? 1 ^{m_2-1} m2??1…+2 m x ? 1 ^{m_x-1} mx??1
那有x個連通塊，是不是就是減去x個一，那x個連通塊的內部節點個數，
不就是這個圖的總結點個數（x的意思看上文），so…最后答案就為 2 n ? x 2^{n-x} 2n?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;
}