# 111上學期算法班第二次模擬賽題解
### 最終排名
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
Sign in with Wallet
Connect another wallet