# TFCIS2024暑訓正式賽題解
## 廢話
**這些題目大多是我突然想到的東東，所以有些地方會有破綻之類的XD**
**但基本上都是些演算法。**
**然後這次是打算把題目名稱取難一點，也算是一種梗了(?**
**假如tobiichi3227突然開發出了hack的話，我大概會一個一個看你們的code順便增強我的測資吧XD**
## 預期難度
**pA < pB < pC < pD < pE < pF**
## 題解
:::success
**可以先看 hints 想一想 再看解答**
:::
### pA 破台 首殺：ezy_plate
:::spoiler **hint 1**
**看清楚題目**
:::
:::spoiler **hint 2**
**題目說什麼就是什麼**
:::
:::spoiler **pA題解**
**"TFcis" 是有包含""的**
**但是要在C++裡創建字串還要加反斜線\\**
**諧咖題XD**
**程式碼**
```cpp=
#include <iostream>
using namespace std;
int main() {
string s; getline(cin, s);
if(s == "\"TFcis\"") cout << "TFcis yes yes\n";
else cout << "Ha Ha the contest is too ez\n";
}
```
:::
### pB Treap 首殺：我
:::spoiler **hint 1**
**多看題目**
:::
:::spoiler **hint 2**
**Treap的性質是什麼?**
:::
:::spoiler **hint 3**
**Treap為什麼要被發明出來**
:::
:::spoiler **pB題解**
**一題梗題**
**就算沒學過Treap，只要仔細看一下題目就會發現 : Treap其實就是一個BST(二分樹)，而上面就有說了->二分樹可能會退化成鍊狀結構**
**所以Treap只是發明出來降低這個概率，但實際上最糟還是會發生**
**答案就是所有節點加起來-1**
**程式碼**
```cpp=
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
int ans = 0;
while(n--) {
int k; cin >> k; ans+=k;
int j; while(k--) cin >> j;
}
cout << ans-1 << '\n';
}
```
**BTW**
**這個也蠻好笑的XD**
**多執行幾次範例測資就會發現mxdp會浮動**
**原因是因為我pri是隨機的哈哈**
:::
### pC 最佳線段選擇 首殺：我
:::spoiler **hint 1**
**先轉化題目性質**
:::
:::spoiler **hint 2**
**要怎麼取線段呢?**
:::
:::spoiler **hint 3**
**這題是Greedy!**
:::
:::spoiler **pC題解**
**題目寫得很長，但其實就是一題Greedy**
**證明 :**
**假設選擇了 $Line_i$ 再選擇了 $Line_j$**
**其 $Line_i = A_i \cdot x + B_i$ $Line_j = A_j \cdot x + B_j$**
**那麼 $A_j \cdot (A_i \cdot x + B_i) + B_j > A_i \cdot (A_j \cdot x + B_j) + B_i$**
**稍微整理一下 :**
$A_j \cdot (A_i \cdot x + B_i) + B_j > A_i \cdot (A_j \cdot x + B_j) + B_i$
$\to A_j \cdot A_i \cdot x + A_j \cdot B_i + B_j > A_i \cdot A_j \cdot x + A_i \cdot B_j + B_i$
$\to A_j \cdot B_i + B_j > A_i \cdot B_j + B_i$
**只要把 $x$ 消掉後就可以快樂sort了**
**程式碼**
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n;
while(cin >> n) {
vector<pair<ll, ll> > l(n);
for(auto &d : l) cin >> d.first;
for(auto &d : l) cin >> d.second;
/*
Ll = al(x) + bl, Lr = ar(x) + br
select l before r is best :
ar(alx + bl) + br > al(arx + br) + bl
=> aralx + arbl + br > aralx + albr + bl
=> arbl + br > albr + bl
*/
sort(l.begin(), l.end(), [&](auto Ll, auto Lr) {
auto &[al, bl] = Ll;
auto &[ar, br] = Lr;
return ar*bl + br > al*br + bl;
});
ll x = 0;
for(auto &[a, b] : l) {
x = a*x + b;
}
cout << x << '\n';
}
}
```
**BTW**
**這題我修了兩次(~~官解寫錯兩次~~**
:::
### pD 喪屍圍城 首殺：charhao
:::spoiler **pD題解**
**[搬運題 - abc363_e](https://atcoder.jp/contests/abc363/tasks/abc363_e)**
:::
### pE 排列組合-走格子 首殺：我
:::spoiler **hint 1**
**分析一下複雜度**
:::
:::spoiler **hint 2**
**要讓你的C變得有效率**
:::
:::spoiler **pE 題解**
[**TOJ 071**](https://toj.tfcis.org/oj/pro/71/)
**這題是一題噁心數學題**
**是Lucas**
**相信大家都沒聽過XD**
**詳細作法OI WIKI上有**
**39分解 :**
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int mod = 27751;
ll fpw(ll a, ll b) {
if(b==0) return 1LL;
ll re = fpw(a, b>>1);
if(b&1) return re*re%mod*a%mod;
return re*re%mod;
}
ll C(ll n, ll m) {
ll re = 1;
for(ll i = n; i >= n-m+1; i--) {
re *= i%mod;
re %= mod;
}
for(ll i = 1; i <= m; i++) {
re *= fpw(i, mod-2);
re %= mod;
}
return re;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int n; cin >> n;
ll x = 0, y = 0;
ll re = 1;
for(int i = 0; i < n; i++) {
ll a, b; cin >> a >> b;
re *= C(a-x + b-y, a-x)%mod;
re %= mod;
x = a, y = b;
}
cout << re << '\n';
}
```
**滿分解 :**
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 27751;
ll fra[mod], infra[mod];
ll fpw(ll a, ll b) {
if(b==0) return 1LL;
ll re = fpw(a, b>>1);
if(b&1) return re*re%mod*a%mod;
return re*re%mod;
}
ll C(ll n, ll m) {
if(n < m) return 0;
return fra[n]%mod*infra[m]%mod*infra[n-m]%mod;
}
ll lucas(ll n, ll m) {
if(m==0) return 1;
return C(n%mod, m%mod)%mod * lucas(n/mod, m/mod)%mod;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
fra[0] = 1, infra[0] = 1;
for(ll i = 1; i < mod; i++) fra[i] = fra[i-1]*i%mod, infra[i] = fpw(fra[i], mod-2);
int n; cin >> n;
ll x = 0, y = 0;
ll ans = 1;
for(int i = 0; i < n; i++) {
ll xx, yy; cin >> xx >> yy;
ans *= lucas(xx-x+yy-y, xx-x)%mod, ans %= mod;
x = xx, y = yy;
}
cout << ans << '\n';
}
```
:::
### pF 樹套樹 首殺：我
:::spoiler **hint 1**
**先分析複雜度**
:::
:::spoiler **hint 2**
**這題根本不用樹套樹**
:::
:::spoiler **hint 3**
**看看pB的題目名稱**
:::
:::spoiler **pF 題解**
**只要有學過Treap的都做得出來**
**tw87說BIT上二分搜也可以**
**得出結論 : 模板題**
**BIT上二分搜 (by tw87 orz) :**
```cpp=
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
struct BIT{
vector< int > tree;
int n;
BIT(int N){ n = N, tree.resize(N + 2); }
void modify(int id, int val){ for(; id <= n; id += id&-id) tree[id] += val; }
int query(int id){
int re = 0;
for(; id; id-=id&-id) re += tree[id];
return re;
}
int query(int l, int r){ return query(r) - query(l - 1); }
int kth(int k){
int ans = 0;
for(int i = __lg(n); i >= 0; --i){
if((ans | (1 << i)) > n) continue;
if(k - tree[ans | (1 << i)] > 0){
ans |= (1 << i);
k -= tree[ans];
}
}
return ans + 1;
}
};
int main(){
int n, q; cin >> n >> q;
vector< array<int, 3> > ask(q);
vector< int > num{-1, 8, 7};
for(auto &[t, a, b] : ask){
cin >> t;
if(t == 1) cin >> a >> b, num.push_back(b);
else cin >> a;
}
sort(all(num)); num.resize(unique(all(num)) - num.begin());
auto get = [&](int t)->int {
return lower_bound(all(num), t) - num.begin();
};
BIT bit(num.size());
vector< int > v(n + 1);
for(int i = 1; i <= n; ++i){
v[i] = (i & 1) ? 8 : 7;
bit.modify(get(v[i]), 1);
}
for(auto &[t, a, b] : ask){
if(t == 1){
bit.modify(get(v[a]), -1);
bit.modify(get(b), 1);
v[a] = b;
}
else cout << num[bit.kth(a)] << "\n";
}
}
```
**Treap (by blameazu) :**
```cpp=
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(time(NULL));
struct Treap {
int pri, sz, val;
Treap *l, *r;
Treap(int x) : val(x), pri(rng()), sz(1) {
l = r = nullptr;
}
void pull() {
sz = 1;
if(l) sz += l->sz;
if(r) sz += r->sz;
}
static int getsz(Treap* v) {
return v ? v->sz : 0;
}
static Treap* merge(Treap *a, Treap *b) {
if(!a || !b) return a ? a : b;
if(a->pri > b->pri) return a->r = merge(a->r, b), a->pull(), a;
else return b->l = merge(a, b->l), b->pull(), b;
}
static pair<Treap*, Treap*> splitsz(Treap *v, int k) {
if(!v) return {nullptr, nullptr};
v->pull();
if(getsz(v->l) < k) {
auto p = splitsz(v->r, k - getsz(v->l) - 1);
return v->r = p.first, v->pull(), make_pair(v, p.second);
} else {
auto p = splitsz(v->l, k);
return v->l = p.second, v->pull(), make_pair(p.first, v);
}
}
static pair<Treap*, Treap*> splitval(Treap *v, int k) {
if(!v) return {nullptr, nullptr};
v->pull();
if(v->val <= k) {
auto p = splitval(v->r, k);
return v->r = p.first, v->pull(), make_pair(v, p.second);
} else {
auto p = splitval(v->l, k);
return v->l = p.second, v->pull(), make_pair(p.first, v);
}
}
static void insert(Treap*& root, Treap* node) {
auto p = splitval(root, node->val);
root = merge(merge(p.first, node), p.second);
root->pull();
return;
}
static void erase(Treap*& root, int k) {
auto p = splitval(root, k-1);
auto q = splitsz(p.second, 1);
delete q.first;
root = merge(p.first, q.second);
root->pull();
return;
}
static int kth(Treap*& v, int k) {
auto p = splitsz(v, k-1);
auto q = splitsz(p.second, 1);
if (!q.first) return -1;
int ans = q.first->val;
v = merge(p.first, merge(q.first, q.second));
return ans;
}
};
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n; cin >> n;
vector<int> v(n+1, 0);
Treap* root = nullptr;
for(int i = 1; i <= n; i++) {v[i] = (i&1 ? 8 : 7); Treap::insert(root, new Treap(v[i]));}
int q; cin >> q;
while(q--) {
int c; cin >> c;
if(c == 1) {
int x, y; cin >> x >> y;
Treap::erase(root, v[x]);
Treap::insert(root, new Treap(y));
v[x] = y;
} else {
int k; cin >> k;
cout << Treap::kth(root, k) << '\n';
}
}
}
```
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
