# 建電下學期ㄉ模擬賽題解
## pA 鄉下人與等差數列
`Author: Lemon`
總之這不能算簽到題，
開始測資還爛掉了，
因為有人把自己題目的solution寫爛 ㄏㄏ
### Subtask 1 (30%)
:::spoiler Solution
$1 \leq n, m \leq 1000$
這個測資的解很簡單w
就是硬跑一次
因為我們可以算出來每個數字要加多少
就照著加就好ㄌ
:::spoiler code
```cpp=
#include <iostream>
using namespace std;
const int MAXN = 1005;
long long int a[MAXN];
void solve() {
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
for(int i = 0; i < m; ++i) {
int l, r, d;
cin >> l >> r >> d;
for(int j = l; j <= r; ++j) {
a[j] += 1ll * (j - l + 1) * d;
}
}
for(int i = 1; i <= n; ++i) {
cout << a[i] << " \n"[i == n];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
### Subtask 2 (20%)
:::spoiler Solution
$d = 1$
~~這個Subtask其實是我亂出ㄉ~~
基本上想到Subtask 2不太可能想不到Subtask 3(?
假設今天題目改成我們要對$\forall i \in [l, r]$ㄉ$a_i$加上$d$
我們可以很簡單的想到要維護差分陣列 ~~不要砸BIT、線段樹~~
例如$a = [3, 2, 1, 5, 3]$
要對$[2, 4]$加上$1$
我們會先對$a$做**差分**得到：
$diff = [3, -1, -1, 4, -2]$ (為了方便定義$diff[0] = a[0]$)
則我們只要讓
```cpp=
diff[2] += 1, diff[5] -= 1;
```
最後再做一次**前綴和**
就會得到新的陣列ㄌ
看回原本的題目
我們試著觀察加了一個等差數列的途中改變了什麼?
跟上面同個例子只是帶回原題
$a = [3, 2, 1, 5, 3],\ l = 2,\ r = 4,\ d = 1$
$a' = [3, 3, 3, 8, 3]$
如果我們對他做差分ㄋ(?
$diff' = [3, 0, 0, 5, -5]$
對比原來的$diff = [3, -1, -1, 5, 3]$
我們發現$[2, 4]$間的差增加ㄌ$1$ OAO
而$[5, 5]$間的差減少ㄌ$3$ OAO
原來是因為$[2, 4]$間加的值和前一個加的值差了1
而$[5, 5]$的改變來自於等差數列的**最後一項**!
所以**我們就可以維護$\forall i \in [l, r]$每個$diff[i]$加上$1$**
然後**只要在$diff[r + 1]$減掉等差數列的最後一項$(r - l + 1)$**
~~然後你就輕鬆ㄘTLE~~
對一個區間的$diff$加上1 不就是區間加值ㄇ(?
再做一次**差分** ~~一樣不要線段樹或BIT~~
最後在計算答案時先計算$a$的差分
就做完ㄌ
Code放在下一個Subtask
因為基本上一樣w
:::
### Subtask 3 (50%)
:::spoiler Solution
其實只要把上面所以提到$1$的地方改成$d$
就完全okㄌ
:::spoiler code
```cpp=
#include <iostream>
using namespace std;
const int MAXN = 1e5 + 5;
long long int a[MAXN];
long long int diffdiff[MAXN];
long long int diff[MAXN];
void solve() {
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
for(int i = 0; i < m; ++i) {
long long int l, r, d;
cin >> l >> r >> d;
diffdiff[l] += d;
diffdiff[r + 1] -= d;
diff[r + 1] -= d * (r - l + 1);
}
long long int prediffdiff = 0;
long long int prediff = 0;
for(int i = 1; i <= n; ++i) {
prediffdiff += diffdiff[i];
diff[i] += prediffdiff;
prediff += diff[i];
cout << a[i] + prediff << " \n"[i == n];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
## pB 窩根本不會數學
`Author: Lemon`
窩根本不會數學QAQ
### Subtask 1 (5%)
:::spoiler Solution
$k \leq 200$
解決$ax + by + cz = k$
基本上很難不過(?
就照順序直接窮舉就好ㄌ
主要要注意邊界測資(有0的情況)
:::spoiler code
```cpp=
#include <iostream>
using namespace std;
void solve() {
int a, b, c, k;
cin >> a >> b >> c >> k;
for(int x = 1; a * x <= k; ++x) {
for(int y = 1; b * y <= k; ++y) {
for(int z = 1; c * z <= k; ++z) {
if(1ll * a * x + b * y + c * z == k) {
cout << "POSSIBLE\n";
cout << x << ' ' << y << ' ' << z << '\n';
return;
}
if(!c) break;
}
if(!b) break;
}
if(!a) break;
}
cout << "IMPOSSIBLE\n";
return;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
### Subtask 2 (15%)
:::spoiler Solution
當我們已經窮舉了$x, y$
而要解決$ax + by + cz = k$
我們可以嘗試使$cz = k - ax - by = u$
如果 $u > 0$ 且 $c|u$ 的時候便有唯一的正整數解 $\frac{u}{c}$
我們只需要處理前面的窮舉順序便能令字典序最小ㄌouo
~~話說我測資好像有點太水~~
:::spoiler code
```cpp=
#include <iostream>
using namespace std;
void solve() {
int a, b, c, k;
cin >> a >> b >> c >> k;
for(int x = 1; a * x <= k; ++x) {
for(int y = 1; a * x + b * y <= k; ++y) {
int val = k - (a * x + b * y);
if(c) { // c != 0
if(!(val % c)) { //整除
cout << "POSSIBLE\n" << x << ' ' << y << ' ' << val / c << '\n';
return;
}
} else if(!val){ // c == 0 && val == 0
cout << "POSSIBLE\n" << x << ' ' << y << ' ' << 1 << '\n';
return;
}
if(!b) break;
}
if(!a) break;
}
cout << "IMPOSSIBLE\n";
return;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
### Subtask 3 (10%)
:::spoiler Solution
既然已經知道$a = b$
我們可以化簡式子得到$a(x + y) + cz = k$
又因為要字典序最小$x = 1$(不然顯然可以用$y$取代)
所以使$cz = k - a(x + y) = u$
就變成和上一題一樣的情況了
:::spoiler code
```cpp=
#include <iostream>
using namespace std;
void solve() {
int a, b, c, k;
cin >> a >> b >> c >> k;
// x = 1
for(int y = 1; a * (y + 1) <= k; ++y) {
int val = k - a * (y + 1);
if(c) {
if(!(val % c)) {
cout << "POSSIBLE\n1" << ' ' << y << ' ' << val / c << '\n';
return;
}
} else if(!val) {
cout << "POSSIBLE\n" << 1 << ' ' << y << ' ' << 1 << '\n';
return;
}
if(!a) break;
}
cout << "IMPOSSIBLE\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
### Subtask 4 (70%)
:::spoiler Solution
這題的難度頗高
我們一樣考慮窮舉$x$
可以得到並使$by + cz = k - ax = u$
$by + cz = u$
hmmm 似曾相似
沒錯就是貝祖定理
**一定存在$y, z$ 使 $by + cz = kgcd(b, c)$其中都是整數**
透過擴展歐幾里得算法可以解出其中一組解$(y_0, z_0)$
我們可以嘗試透過這組解$(y_0, z_0)$找到的一種字典序最小的正整數解$(x, y)$便是答案ㄌ
啊我就不解釋ㄌ
因為窩根本不會數學。
~~可以參考[危機百科](https://zh.wikipedia.org/zh-tw/%E8%B2%9D%E7%A5%96%E7%AD%89%E5%BC%8F)~~
~~[這個才是Rickroll](https://www.youtube.com/watch?v=dQw4w9WgXcQ)~~
如果窮舉完$x$仍不存在正整數解
那麼就輸出"IMPOSSIBLE"ㄅ
一樣要處理邊際測資ㄛㄛㄛ
:::spoiler code
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int ll;
ll exgcd(ll a, ll b, ll& x, ll& y) {
if(a < b) return exgcd(b, a, y, x);
if(!b) {
x = 1;
y = 0;
return a;
}
ll ret = exgcd(b, a%b, x, y);
ll temp = x;
x = y;
y = temp - a / b * y;
return ret;
}
void solve() {
const int INF = 1e9 + 7;
int a, b, c;
long long int k;
cin >> a >> b >> c >> k;
if(!a) a = INF;
ll y0, z0;
ll unit = exgcd(b, c, y0, z0);
if(!unit) {
if(k % a) cout << "IMPOSSIBLE\n";
else cout << "POSSIBLE\n" << k / a << ' ' << 1 << ' ' << 1 << '\n';
return;
}
b /= unit;
c /= unit;
ll mn = INF;
for(int x = 1; a * x <= k; ++x) {
int val = k - a * x;
if(val % unit) continue;
val /= unit;
ll dy = val * y0, dz = val * z0;
if(dz > 0) {
ll d = (dz - 1) / b;
dy += c * d;
dz -= b * d;
}
if(dy > 0) {
ll d = (dy - 1) / c;
dy -= c * d;
dz += b * d;
}
if(dy > 0 && dz > 0) {
cout << "POSSIBLE\n";
cout << x << ' ' << dy << ' ' << dz << '\n';
return;
}
}
cout << "IMPOSSIBLE\n";
return;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
### 酷酷DP解
:::spoiler Solution
這是吳亞倫ㄉ扣哈哈
所以可以直接去問他(?
:::spoiler code
```cpp=
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define AI(x) begin(x),end(x)
#define ll long long int
#define endl '\n'
#ifdef DEBUG
#define debug(args...) LKJ("[ "+string(#args)+" ]", args)
template<class I> void LKJ(I&&x){ cerr << x << '\n'; }
template<class I, class...T> void LKJ(I&&x, T&&...t){ cerr << x << ", ", LKJ(t...); }
template<class I> void OI(I a, I b){ while(a < b) cerr << *a << " \n"[next(a) == b], ++a; }
#else
#define debug(...) 0
#define OI(...) 0
#endif
#define _ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
signed main() {_
int val[5];
int k;
for (int i = 1; i <=3 ; i++) cin >> val[i];
cin >> k;
k-=val[1];
k-=val[2];
k-=val[3];
if(k<0) {
cout << "IMPOSSIBLE\n";
return 0;
}
// debug(k);
bool dp[5][(int)1e6+5] = {0};
vector<vector<vector<int>>> source(5,vector<vector<int>>((int)1e6+5,vector<int>(3)));
dp[0][0] = 1;
source[0][0] = {1,1,1};
for (int i = 1; i <= 3; ++i) {
for (int j = 0; j <= k; ++j) {
if (j>=val[i] && dp[i][j-val[i]] && !dp[i-1][j]) {
dp[i][j] = 1;
source[i][j] = source[i][j-val[i]];
source[i][j][i-1]++;
// debug(i,j);
}
else if (j>=val[i] && dp[i][j-val[i]] && dp[i-1][j]){
dp[i][j] = 1;
auto tem = source[i][j-val[i]];
tem[i-1]++;
source[i][j] = min(tem, source[i-1][j]);
}
else if (dp[i-1][j]) {
dp[i][j] = 1;
source[i][j] = source[i-1][j];
}
}
}
if (!dp[3][k]){
cout << "IMPOSSIBLE\n";
return 0;
}
else {
cout << "POSSIBLE\n";
for (int i = 0; i<3; ++i) {
cout << source[3][k][i] << " ";
}
cout << endl;
}
return 0;
}
```
:::
###### tags: `CompetitiveProgramming`
Sign in with Wallet
Connect another wallet