# 114KSPGC test2 題解
###### tags: `題解`
<!-- 註：題號未定 -->
## pA The Tower
**Idea:** Gana31415
**Prepration:** Gana31415
:::spoiler **Tags**
`dp`
:::
<a> </a>
這是一個遞迴問題。假設你爬到了第11層，你的前一步有可能是從第10層上升1層、或是從第8層上升3層、或是從第1層上升10層，假設$a_n$表示爬到第$n$層的方法數，那麼以上例子可以寫成
\begin{aligned}
a_{11}=a_{10}+a_8+a_1
\end{aligned}
延伸到第$n$層就是
\begin{aligned}
a_n=a_{n-1}+a_{n-3}+a_{n-10}
\end{aligned}
再來用dp就能夠解了
::: spoiler 官解 (Gana31415)
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[105] = {0};
void Dp(){
dp[1] = 1, dp[3] = 1 , dp[10] = 1;
for(int i = 2 ; i <= 100 ; i++){
int a = i-1 , b = i-3 , c = i-10;
b = max(0 , b) , c = max(0 , c);
dp[i] += dp[a] + dp[b] + dp[c];
}
}
int main(){
ll n;
cin >> n;
Dp();
cout << dp[n] <<"\n";
return 0;
}
```
:::
::: spoiler 另解 (niter)
不同方向的dp
```cpp=
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int main(){
long long a[200] = {0};
a[0] = 1;
loop(i,0,101){
a[i+1] += a[i];
a[i+3] += a[i];
a[i+10] += a[i];
}
int n;
cin >> n;
cout << a[n] << "\n";
}
```
:::
## pB Bomb!!
**Idea:** Gana31415
**Prepration:** Gana31415
:::spoiler **Tags**
`dp`
:::
<a> </a>
利用dp可以解答，最簡單的方式是用二維$dp[i][j]$來記錄在第$i$個位置時還要傳$j$次才爆炸。當你接到炸彈時的前一刻有可能是由你的右邊或是左邊傳過來的，因此有轉移式：
\begin{aligned}
dp[i][j]=dp[i-1][j+1]+dp[i+1][j+1]
\end{aligned}
注意一下編號就能過了。當然可以做空間壓縮，會更漂亮。
::: spoiler 官解 (Gana31415)
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[105][105] = {0};
int main(){
int n,m;
cin >> n >> m;
dp[0][m] = 1;
for(int j = m ; j > 0 ; j--)
for(int i = 0 ; i < n ; i++){
int a = i-1, b = i+1;
if(a == -1) a = n-1;
if(b == n) b = 0;
dp[i][j-1] = dp[a][j] + dp[b][j];
}
cout << dp[0][0] << '\n';
return 0;
}
```
:::
::: spoiler 另解 (niter)
```cpp=
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector<long long> a(n, 0);
a[0] = 1;
loop(i,0,m){
vector<long long> b(n, 0);
loop(j,0,n){
b[(j+1+n) % n] += a[j];
b[(j-1+n) % n] += a[j];
}
a = b;
}
cout << a[0] << "\n";
}
```
:::
## pC Sum it all
**Idea:** niter
**Prepration:** niter
:::spoiler **Tags**
`greedy, sorting`
:::
<a> </a>
基本上，在不證明這個性質的情況就AC這題是比較好的做題過程。
因為通常賽中不會有時間慢慢想證明方法，大部分都是「覺得好像對就寫下去了」。
當然在寫之前要先試幾組看會不會有反例啦。
以下是完整解法：
因為先把$a$陣列排序不影響最終的YES/NO，所以為了方便，我們先把$a$陣列由大到小排序。($b$不動)
你可以想成是我們把原本的問題改寫成了與它等價的問題。
接下來，我們要證明：再把$b$陣列由小到大排序後，能使$\sum\limits_{i=1}^n (a_i)^{b_i}$的值達到最小值。
在$a$陣列由大到小排序之後($b$陣列還沒排序)，假設有一組$(i, j)$，使得$\left\{\begin{aligned}{a_i\geq a_j\geq 1} \\{b_i\geq b_j\geq 1}\end{aligned}\right.$，
可以證明$b_i,b_j$交換後，$\sum\limits_{i=1}^n (a_i)^{b_i}$的值會變得更小(或是至少不變)。
> 證明過程：
>
> 因為$\left\{\begin{aligned}{a_i\geq a_j\geq 1} \\{b_i\geq b_j\geq 1}\end{aligned}\right.$，
>
> $\Rightarrow\left\{\begin{array}{l}{(a_i)^{b_j}\geq (a_j)^{b_j}\geq 1} \\{(a_i)^{b_i-b_j}-1\geq (a_j)^{b_i-b_j}-1\geq 0}\end{array}\right.$，
>
> $\Rightarrow\Large(\normalsize(a_i)^{b_j}\Large)(\normalsize(a_i)^{b_i-b_j}-1\Large) \large \geq \Large(\normalsize(a_j)^{b_j}\Large)(\normalsize(a_j)^{b_i-b_j}-1\Large)$，
>
> $\Rightarrow(a_i)^{b_i}-(a_i)^{b_j}\geq (a_j)^{b_i}-(a_j)^{b_j}$，
>
> 所以$(a_i)^{b_i}+(a_j)^{b_j}\geq (a_j)^{b_i}+(a_i)^{b_j}$，故得證。
如果我們不做無意義的交換($b_i=b_j$)，那麼我們必定能在有限次內，
使這些交換最後讓$b$陣列由小到大排序完成，
而此時透過反證法可以得知$\sum\limits_{i=1}^n (a_i)^{b_i}$ 的值不可能再變小了，
所以這時只要在檢查它是否有小於$x$，就可以輸出答案了！
實作細節就是不要溢位，乘到超過${10}^9$要記得break。
可以不使用快速冪來實作，因為$1$的幾次方都是$1$，可以特判，而$2$最多乘到$30$次方就會超過${10}^9$了，
$3$就更小了，所以用for迴圈算次方就只是差一個常數的時間而已。
::: spoiler 官解 (niter)
```cpp=
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i = a; i < b;i++)
using namespace std;
int main(){
int n;
long long x;
cin >> n >> x;
long long a[n + 5], b[n + 5];
loop(i,0,n) cin >> a[i];
loop(i,0,n) cin >> b[i];
sort(a, a + n, less<int>());
sort(b, b + n, greater<int>());
long long ret = 0, tmp;
bool ans = true;
loop(i,0,n){
if(a[i] == 1){
ret++;
}
else{
tmp = 1;
loop(j,0,b[i]){
tmp *= a[i];
if(tmp > x){
ans = false;
break;
}
}
ret += tmp;
}
if(ret > x){
ans = false;
break;
}
}
if(!ans){
cout <<"NO\n";
}
else{
cout << "YES\n";
loop(i,0,n) cout << a[i] << " "; cout << '\n';
loop(i,0,n) cout << b[i] << " "; cout << '\n';
}
return 0;
}
```
:::
## pD Take some numbers!
**Idea:** niter
**Prepration:** niter
:::spoiler **Tags**
`dp`
:::
<a> </a>
經過觀察可以發現這題其實不是數學題，而是湊不湊的到的無限背包問題。
我們定義$dp_i$代表數字$i$湊不湊得到，湊得到就是$1$，否則就是$0$，那麼可以得知以下結論：
如果$dp_i=1$，那麼$dp_{i+a_j}=1(1\leq j\leq n)$，而且$dp_0=1$。
所以我們只要使用for迴圈，由小到大跑過所有的$i$，對每個$i$再跑過所有的$j$即可。
複雜度$O(nC)$，$C=10^6$為詢問範圍。
::: spoiler 官解(niter)
```cpp=
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int _1e6_ = (int)(1e6);
int main(){
int n, q;
cin >> n >> q;
int a[n+5];
loop(i,0,n){
cin >> a[i];
}
bool can[_1e6_ + 100] = {0};
can[0] = 1;
loop(i,0,_1e6_+1){
if(!can[i])
continue;
loop(j,0,n){
if(i + a[j] <= _1e6_){
can[i + a[j]] = true;
}
}
}
int qry;
loop(i,0,q){
cin >> qry;
cout << can[qry] << ' ';
} cout << '\n';
return 0;
}
```
:::
## pE KSRPGC
**Idea:** niter
**Prepration:** 2006lennon
:::spoiler **Tags**
`data structures(STL)`
:::
<a> </a>
由於一個技能可以使用多次，所以每個$(a,b)$都只需要被算一次，那麼可以使用set不能有重複元素的特性來維護(無法插入已經存在的元素)，特別注意如果他沒有移動的話，他並不需要發動技能，也就是$(0,0)$的情況不應被列入技能中
::: spoiler 官解 (2006lennon)
```cpp=
#include <bits/stdc++.h>
typedef long long ll;
#define pii pair <ll,ll>
#define f first
#define s second
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll s,t;
cin>>s>>t;
set <pii> st;
ll n=t-s+1;
vector <ll> x(n),y(n);
for(ll i=0;i<n;i++){
cin>>x[i]>>y[i];
}
for(int i=1;i<n;i++){
st.insert({x[i]-x[i-1],y[i]-y[i-1]});
}
st.erase({0,0});
cout<<st.size()<<"\n";
return 0;
}
```
:::
## pF Listen to the class
**Idea:** sean9575
**Prepration:** sean9575
:::spoiler **Tags**
`data structures`
:::
<a> </a>
待補
::: spoiler 官解 (sean9575)
```
```
:::
## pG Shopping Street and a Tour Guide
**Idea:** sean9575
**Prepration:** niter
:::spoiler **Tags**
`constructive algorithms, 梗題`
:::
<a> </a>
鄭勝宇原本說要拿這題來考線段樹的，後來被發現這題其實超水，所以就被我拿來平衡難度了。
在他的原題中，線段(把行程想成是線段)是沒有權重的，而且是個裸題。
作法：
取一個左邊界是$k$的線段(這樣它就贏所有在它左邊的店了)，再取一個右邊界是$k$的線段(使它贏過所有在它右邊的店)，
就能使編號$k$的店，達到來客數最多，而且沒有其他店跟他一樣多。
也有可能一個線段同時滿足這兩個條件，就是$[k, k]$，這時只要取這個線段就可以了。
::: spoiler 官解 (niter)
`segment_l[k]`, `segment_r[k]`來分別代表有幾個線段左、右邊界是k。
```cpp=
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<(b);i++)
using namespace std;
const int maxN = (int)(1e6) + 5;
struct route{
int l = 0, r = 0, x = 0;
};
route arr_route[maxN];
int segment_l[maxN], segment_r[maxN];
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int n, q;
cin >> n >> q;
int qry, a, k;
loop(i,0,q){
cin >> qry;
if(qry == 1){
cin >> a;
cin >> arr_route[a].l;
cin >> arr_route[a].r;
cin >> arr_route[a].x;
segment_l[arr_route[a].l]++;
segment_r[arr_route[a].r]++;
}
else if(qry == 2){
cin >> k;
segment_l[arr_route[k].l]--;
segment_r[arr_route[k].r]--;
arr_route[k] = {0, 0, 0};
}
else{ // qry == 3
cin >> k;
if(segment_l[k] > 0 && segment_r[k] > 0){
cout << "1 ";
}
else{
cout << "0 ";
}
}
}
cout << '\n';
}
```
:::
## pH Hotel
**Idea:** 2006lennon
**Prepration:** 2006lennon
:::spoiler **Tags**
`sorting, greedy, data structures, implementation`
:::
<a> </a>
對於區間$[l,r]$來說，對左界$l$排序，如果在左界$l$相同的情況下，優先讓區間較小的選擇編號最小的房間
但如果是$[1,3],[1,3],[2,2]$的情況，第一人選1，第二人選2，第三個選不了了，但其實有方法可以將所有人都入住
我們可以維護一個最小值$now$，表示最小可填入的房間，如果有$r$小於$now$，那麼將無法再繼續入住，也就沒有符合的答案了
因此我們可以使用priority_queue來維護$r$的最小值，如果最小的$r$小於$now$，說明已沒有可入住的房間，反之我們可以刪除這個$r$，並將$now$+1
::: spoiler 官解 (2006lennon)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define f first
#define s second
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
int n,m,now=-1;
cin>>n>>m;
bool ans=true;
vector <pii> v(n);
for(int i=0;i<n;i++) cin>>v[i].f>>v[i].s;
sort(v.begin(),v.end());
v.push_back({m+5,m+5});
priority_queue <int,vector<int>,greater<int> > q;
for(int i=0;i<=n;i++){
while(!q.empty() && now<v[i].f){
if(q.top()<now){
ans=false;
break;
}
if(!ans) break;
q.pop();
now++;
}
q.push(v[i].s);
now=v[i].f;
}
if(ans) cout<<"Yes\n";
else cout<<"No\n";
return 0;
}
```
:::
## pI NPC amount reporting
**Idea:** sean9575
**Prepration:** sean9575
:::spoiler **Tags**
`data structures`
:::
<a> </a>
待補
::: spoiler 官解 (sean9575)
```
```
:::
## pJ Nearest Pair in Array
**Idea:** niter
**Prepration:** niter
:::spoiler **Tags**
`Sorting and Searching, data structures`
:::
<a> </a>
原本的式子：$c_{i, j}=|a_i-a_j|-|i-j|$
因為$c_{i, j} = c_{j, i}$，所以我們可以不失一般性假設$i<j$
這樣我們就可以把其中一個絕對值展開了。
$\Rightarrow c_{i, j}=|a_i-a_j|-(j-i)$
$\Rightarrow c_{i, j}=|a_i-a_j|+i-j$
這樣還不夠，我們可以透過判case來把另外一個絕對值展開。
$\Rightarrow c_{i, j}=\left\{\begin{array}{l}{(a_i+i)-(a_j+j)}\quad\quad\quad{(a_i\geq a_j)} \\{(a_j-j)-(a_i-i)}\quad\quad\quad{(a_i\leq a_j)}\end{array}\right.$
在$a_i\geq a_j$的case中，我們可以用BIT紀錄每個$a_i$的值所對應的最小的$(a_i+i)$，如果有另一個$a_j$滿足$a_i\geq a_j$，那麼$(a_i+i)-(a_j+j)$就是其中一種可能的答案。
同理，在$a_i\leq a_j$的case中，我們可以用BIT紀錄每個$a_i$的值所對應的最大的$(a_i-i)$，如果有另一個$a_j$滿足$a_i\leq a_j$，那麼$(a_j-j)-(a_i-i)$就是其中一種可能的答案。
搭配離散化(coordinate compression)可以把複雜度壓到$O(n\log n)$。
關於回溯，我們可以在一個狀態中同時記錄它的來源，這樣之後就有辦法得知它是從哪裡來的值。
（code裡面的from_BIT_max、from_BIT_min陣列）
::: spoiler 官解 (niter)
```cpp=
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define ff first
#define ss second
using namespace std;
int n;
const int maxN = ((int)(1e6)) + 5;
long long best_ans = (1LL<<62);
int best_i = -1, best_j = -1;
long long a[maxN];
int rnk[maxN];
// for case: a[j] >= a[i]
long long BIT_max[maxN];
int from_BIT_max[maxN];
void upd_max(int i){
int ind = rnk[i];
long long val = a[i] - i;
for(; ind < maxN; ind += ((ind)&(-ind))){
if(val > BIT_max[ind]){
BIT_max[ind] = val;
from_BIT_max[ind] = i;
}
}
return;
}
void qry_max(int j){
int ind = rnk[j];
long long val = a[j] - j;
for(; ind > 0; ind -= ((ind)&(-ind))){
if(val - BIT_max[ind] < best_ans){
best_ans = val - BIT_max[ind];
best_i = from_BIT_max[ind];
best_j = j;
}
}
}
void solve1(){
loop(i,0,maxN){
BIT_max[i] = -(1LL<<62);
}
upd_max(0);
loop(i,1,n){
qry_max(i);
upd_max(i);
}
}
// for case: a[i] >= a[j]
long long BIT_min[maxN];
int from_BIT_min[maxN];
void upd_min(int i){
int ind = n - rnk[i] + 1;
long long val = a[i] + i;
for(; ind < maxN; ind += ((ind)&(-ind))){
if(val < BIT_min[ind]){
BIT_min[ind] = val;
from_BIT_min[ind] = i;
}
}
return;
}
void qry_min(int j){
int ind = n - rnk[j] + 1;
long long val = a[j] + j;
for(; ind > 0; ind -= ((ind)&(-ind))){
if(BIT_min[ind] - val < best_ans){
best_ans = BIT_min[ind] - val;
best_i = from_BIT_min[ind];
best_j = j;
}
}
}
void solve2(){
loop(i,0,maxN){
BIT_min[i] = (1LL<<62);
}
upd_min(0);
loop(i,1,n){
qry_min(i);
upd_min(i);
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
loop(i,0,n){
cin >> a[i];
}
// 離散化
vector<pair<long long, int>> uni(n);
loop(i,0,n){
uni[i].ff = a[i];
uni[i].ss = i;
}
sort(uni.begin(), uni.end());
int cnt = 1;
rnk[uni[0].ss] = 1;
loop(i,1,n){
if(uni[i].ff != uni[i-1].ff)
cnt++;
rnk[uni[i].ss] = cnt;
}
// start solving problem
solve1();
solve2();
// cerr << best_ans << '\n';
cout << best_i+1 << ' ' << best_j+1 << '\n';
return 0;
}
```
:::
----
## 統計
AC：
pA 11/11
pB 3/9
pC 3/9
pD 3/3
pE 4/8
pF 4/9
pG 1/1
pH 0/4
pI1 1/2
pI2 0/0
pJ 0/2
首殺：
pA `snorlaxorz` 00:02
pB `hahaha1234` 00:59
pC `Aestivate` 00:21
pD `I dont know the name` 00:54
pE `Aestivate` 00:36
pF `hahaha1234` 00:10
pG `Aestivate` 00:31
pH X
pI1 `Aestivate` 00:54
pI2 X
pJ X
Sign in with Wallet
Connect another wallet