---
# System prepended metadata

title: 111上學期算法班第二次模擬賽題解

---

# 111上學期算法班第二次模擬賽題解

### 最終排名
![](https://i.imgur.com/sYPaFZH.png)

1. 01S379
2. 11S242, pn0818x

---

	預計難度：P1<P2<P3<P5<P4
	實際難度：P1=P2=P3=P4=P5 (零AC)

---

## P1 
by binghua
#### 敘述
問你四則運算式的答案是多少

#### 解法 1
by binghua
:::spoiler
這題因為輸入量頗大，光是輸入就會吃tle，因此需要IO優化
很多人看到這題就放棄了，其實這題關鍵點就是"先乘除後加減"
解法就是把一個字串一個一個讀，遇到乘或除就先把他運算好，最後再去做加減
這題需要用到資料結構，下面用的是deque，不會用的就去看看講義吧～～
需要用到兩個deque，一個用來存取數字，一個用來存取運算符號
接著就是去判斷這個字元該丟到哪個deque，最後在進行加總就好了
:::

#### 解答 1
:::spoiler AC code
```cpp=
#include <bits/stdc++.h>
//#define int long long
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin>>s;
    deque<int> a;
    deque<char> b;
    int sum=0;
    int tmp=0;
    for(int i=0;i<s.size();i++){
        if(int(s[i])<42 or int(s[i])>57){
            cout<<"Happy New Year.";
            return 0;
        }
        if(int(s[i])<58 and int(s[i]>47)){
            a.push_back(int(s[i])-48);
        }else{
            if(s[i]=='+' or s[i]=='-')
            b.push_back(s[i]);
            else{
                int tmp=a.back();
                a.pop_back();
                if(s[i]=='*'){
                    i++;
                    tmp*=int(s[i]-48);
                    a.push_back(tmp);
                }
                if(s[i]=='/'){
                    i++;
                    tmp/=int(s[i]-48);
                    a.push_back(tmp);
                }
            }
        }
    }
    sum=a.front();
    a.pop_front();
    while(!b.empty()){
        char q=b.front();
        b.pop_front();
        if(q=='+'){
            int x=a.front();
            a.pop_front();
            sum+=(x);
        }
        if(q=='-'){
            int x=a.front();
            a.pop_front();
            sum-=(x);
        }
    }
    cout<<sum;
}
```
:::

#### 解法 2
by koukirocks
:::spoiler
我們為了方便觀察，這邊假設乘和除一樣，加和減一樣，實作時再分開就好
可以發現前三個數字總共有四種組合

1. a + b + c
2. a + b * c
3. a * b + c
4. a * b * c

對於第一種，我們直接讓 a 和 b 相加
對於第二種，我們必須先讓 b 和 c 相乘
對於第三，四種，我們先讓 a 和 b 相乘
執行完後會剩下兩個數字，接下來再吃進一個數字，重複直到剩兩個數字為止，直接計算剩下的兩個數字就是答案啦！
:::

#### 解答 2
:::spoiler AC code
```cpp=
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define oo 0x3f3f3f3f3f3f3f3f
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pii pair<int,int>
using namespace std;

const int MAX=2e5+10;

int n;
string s;

int main() {
	speed;
	cin>>s;
	ll a=-INF,b=-INF;
	char op1='$',op2='$';
	for (int i=0;i<s.length();i++) {
//		cout<<a<<" "<<op1<<" "<<b<<" "<<op2<<"\n";
		char c=s[i];
		if (i%2==0) {
			if (c-'0'>9 or c-'0'<0) {
				cout<<"Happy New Year.\n";
				return 0;
			}
			if (a==-INF) {
				a=c-'0';
				continue;
			}
			if (b==-INF) {
				b=c-'0';
				continue;
			}
			ll x=c-'0';
			if (i>=4) {
				if (op1=='*') {
					a*=b;
					b=x;
					op1=op2;
					op2='$';
				} else if (op1=='/') {
					a/=b;
					b=x;
					op1=op2;
					op2='$';
				} else if (op2=='*') {
					b*=x;
					op2='$';
				} else if (op2=='/') {
					b/=x;
					op2='$';
				} else if (op1=='+') {
					a+=b;
					b=x;
					op1=op2;
					op2='$';
				} else if (op1=='-') {
					a-=b;
					b=x;
					op1=op2;
					op2='$';
				}
			}
		} else {
			if (c!='+' and c!='-' and c!='*' and c!='/') {
				cout<<"Happy New Year.\n";
				return 0;
			}
			if (op1=='$') {
				op1=c;
				continue;
			}
			if (op2=='$') {
				op2=c;
				continue;
			}
		}
	}
	if (op1=='+') {
		a+=b;
	} else if (op1=='-') {
		a-=b;
	} else if (op1=='*') {
		a*=b;
	} else if (op1=='/') {
		a/=b;
	}
	cout<<a<<"\n";
}

```
:::

---

## P2 & P4
by koukirocks
#### 敘述
問你最多可以選幾組數據形成一個鍊狀，使第 $i$ 項的兩個數值都比第 $i+1$ 項大

#### 簡單版解法
:::spoiler
把一個人想像成一個二維點，兩項數值分別是 x 和 y
A 比 B 厲害就代表 A 在 B 的右上方
所以我們先把所有點根據 x 排序，再找他們 y 的 LIS 長度就是答案啦！
(不懂 LIS 的給我滾回去看講義
:::

#### 測資加強版解法
:::spoiler
差異在我們找 LIS 長度的方式
正常 dp 解要花 $n^2$ 的時間，遇到 $n=2*10^5$ 會直接炸 TLE
這裡介紹一個 $nlogn$ 的二分搜 LIS 解
我們建一個 vector ，把所有 y 掃過一次，若當前 y > vector 最後一項，把 y push_back 進去，不然找到第一個 >= 當前 y 的數字，把它換成當前 y ，最後 vector 的長度就是答案啦！
講師沒查過證明，有興趣可以上網查
:::

#### $n^2$ 解答
:::spoiler P2 AC code
```cpp=
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pii pair<int,int>
using namespace std;

const int MAX=1e3+10;

int n;
pii a[MAX];
int dp[MAX];

int main() {
	speed;
	cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>a[i].first>>a[i].second;
	}
	sort(a+1,a+n+1);
	dp[1]=1;
	for (int i=2;i<=n;i++) {
		dp[i]=1;
		for (int j=1;j<i;j++) {
			if (a[i].second>a[j].second) {
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
	}
	int ans=0;
	for (int i=1;i<=n;i++) ans=max(ans,dp[i]);
	cout<<ans<<"\n";
}

```
:::

#### $nlogn$ 解答
:::spoiler P2 & P4 AC code
```cpp=
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pii pair<int,int>
using namespace std;

const int MAX=2e5+10;

int n;
pii a[MAX];

int main() {
	speed;
	cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>a[i].first>>a[i].second;
	}
	sort(a+1,a+n+1);
	vector<int> ans;
	for (int i=1;i<=n;i++) {
		auto it=lower_bound(ans.begin(),ans.end(),a[i].second);
		if (it==ans.end()) ans.push_back(a[i].second);
		else *it=a[i].second;
	}
	cout<<ans.size()<<"\n";
}

```
:::

---

## P3
by koukirocks
#### 敘述
問你有沒有辦法把一個無向圖的每一個點塗上兩種顏色的其中一種，使每個點的所有相鄰點顏色都和它不一樣
就是二分圖拉

#### 解法
:::spoiler
跑一次 BFS ，在加入 queue 的時候上色，如果已經上過色了就檢查是否矛盾
:::

#### 解答
:::spoiler AC code
```cpp=
#include <bits/stdc++.h>
#define ll long long
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;

const int MAX=2e5+10;

int n;
vector<int> G[MAX];

int main() {
	speed;
	cin>>n;
	for (int i=1;i<=n;i++) {
		int x;
		cin>>x;
		while (x--) {
			int a;
			cin>>a;
			G[i].push_back(a);
			G[a].push_back(i);
		}
	}
	queue<int> BFS;
	int v[MAX];
	memset(v,0,sizeof(v));
	BFS.push(1);
	v[1]=1;
	while (!BFS.empty()) {
		int nd=BFS.front();
		BFS.pop();
		for (int u:G[nd]) {
			if (v[u]==0) {
				v[u]=3-v[nd];
				BFS.push(u);
			} else {
				if (v[u]!=3-v[nd]) {
					cout<<"-1\n";
					return 0;
				}
			}
		}
	}
	int ans=0;
	for (int i=1;i<=n;i++) if (v[i]==1) ans++;
	cout<<ans<<"\n";
	for (int i=1;i<=n;i++) if (v[i]==1) cout<<i<<" ";
	cout<<"\n";
	return 0;
}

```
:::

---

## P5
by koukirocks
#### 敘述
[積木疊疊樂 (MD Judge)](http://mdcpp.mingdao.edu.tw/contest/34/problem/T20)
[原題](https://cses.fi/problemset/task/2413)
沒錯就是抄題
然後全場唯一一個 AC 就是有人上網抄這題的答案 (哭

#### 解法
:::spoiler
我們把塔中的最後兩層分成兩種情況：屬不屬於同一個積木，定義為 $a_n$ 和 $b_n$
可以發現轉移式就是：
$a_n=2a_n+b_n$
$b_n=a_n+4b_n$
什麼？你問我為什麼可以想到這個？~~通靈阿~~
就是多從題目的不同方向思考狀態，跟玩數獨有點像，從各個角度切入，看是不是對的，不對就再換一個想法
:::

#### 解答
:::spoiler AC code
```cpp=
#include <bits/stdc++.h>
#define speed_up ios_base::sync_with_stdio(0); cin.tie(0)
#define ll long long int
using namespace std;
 
const int MAX=1e6+10,P=1e9+7;
int t;
ll dp[MAX][2];
 
int main(){
    speed_up;
	cin>>t;
	dp[1][0]=1;
	dp[1][1]=1;
	for (int i=2;i<=1000000;i++) {
		dp[i][0]=(dp[i-1][0]*4+dp[i-1][1])%P;
		dp[i][1]=(dp[i-1][1]*2+dp[i-1][0])%P;
	}
	while (t--) {
		int n;
		cin>>n;
		cout<<(dp[n][0]+dp[n][1])%P<<"\n";
	}
}
```
:::

如果還有不懂得可以加 Discord 問我喔
Koukirocks#3624