# NPSC 2023 題目&詳解&sample code
[題本](https://contest.cc.ntu.edu.tw/npsc2023/teamclient/final-sen.pdf)
:::info
因為沒拿到code所以sample code是賽後重寫的
不一定與賽中做法相同
可能有錯
:::
## pA 非確定性義大利麵條醬汁料理
首先要知道
1. 平面上加直線會多 $1+與原有直線交點數量$ 個面
2. 期望值加法和乘常數可以亂亂做 (期望值是線性函數)
然後
一條直線對答案的貢獻可以訂為 $\frac 12(1+與原有直線交點數量期望值)$
交點數量期望值 = 交點出現概率總和
交點出現概率取決於有幾條原有直線經過
$n$條就是$1-\frac{1}{2^n}$
實作部分
每條直線只要考慮index比他小的
並用交點到題目給的向量兩端距離比代表交點位置
這可以用兩端點分別到另一向量兩端圍出的三角形面積比算
再用map存一存就好了
:::spoiler sample code (AC on TIOJ)
```cpp=
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
const ll border = 1e6;
ll qpow(ll a, ll p){
ll r = 1;
while(p){
if (p&1) r=r*a%mod;
a=a*a%mod;
p>>=1;
}
return r;
}
ll rev(ll a){
return qpow(a,mod-2);
}
ll gcd(ll a, ll b){
while(a){
ll c = a;
a = b%a;
b = c;
}
return b;
}
struct pos{
ll x,y;
pos operator+(const pos &o) const{
return {x+o.x,y+o.y};
}
pos operator-(const pos &o) const{
return {x-o.x,y-o.y};
}
pos operator-() const{
return {-x,-y};
}
pos operator*(const ll &i) const{
return {x*i,y*i};
}
ll operator^(const pos &o) const{
return x*o.y-y*o.x;
}
bool out() const{
return abs(x)>border || abs(y)>border;
}
};
struct line{
pos a,b;
void extend(){
pos f1 = b-a;
pos f2 = a-b;
ll l = 0,r=1000000;
while(l<r){
ll m = l+r>>1;
if ((b+f1*m).out() && (a+f2*m).out()) r = m;
else l = m+1;
}
a = a+f2*l;
b = b+f1*l;
}
};
struct frac{
ll a,b;
frac():a(1),b(1){}
frac(ll x, ll y){
if(y<0) x = -x,y = -y;
ll g = gcd(abs(x),y);
a = x/g;
b = y/g;
}
bool operator==(const frac &o) const{
return a==o.a&&b==o.b;
}
bool operator!=(const frac &o) const{
return !(a==o.a&&b==o.b);
}
bool operator<(const frac &o) const{
return a!=o.a?a<o.a:b<o.b;
}
};
int main(){
ios::sync_with_stdio(0);cin.tie(0);
ll n;
cin >> n;
vector<line> a(n);
for(line &o : a) cin >> o.a.x >> o.a.y >> o.b.x >> o.b.y;
vector<ll> rev2(n,1);
ll r2 = rev(2);
for(ll i = 1;i<n;i++) rev2[i] = rev2[i-1]*r2%mod;
for(ll &i : rev2) i = (mod+1-i)%mod;
ll ans = 1;
for(ll i = 0;i<n;i++){
line cur = a[i];
map<frac,ll> mp;
for(ll j = 0;j<i;j++){
line o = a[j];
frac key(abs((o.b-cur.a)^(o.a-cur.a)),abs((o.b-cur.b)^(o.a-cur.b)));
mp[key]++;
}
ll x = 1;
for(auto [k,v] : mp) x = x+rev2[v];
ans = (ans+x%mod*r2)%mod;
}
cout << ans << "\n";
}
```
:::
## pB NPSC總統大選
觀察到
$1>\lfloor\frac12\rfloor$
所以給支持者都自己一個選區
其他給盡量少就好了
可以證明混合的選區必定不能使答案更好
:::spoiler sample code (AC on TIOJ)
```cpp=
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
ll n,k;
cin >> n >> k;
vector<vector<ll>> v(k);
for(auto &o : v) o.push_back(0);
for(ll i=1;i<=n;i++){
ll a;
cin >> a;
v[a-1].push_back(i);
}
for(auto &o : v){
o.push_back(n+1);
ll x = o.size()-2;
ll y = 0;
for(ll i = 1;i<o.size();i++) y += o[i]>o[i-1]+1;
cout << (x>(x+y)/2?"Yes\n":"No\n");
}
}
```
:::
## pC 巴乙己放石頭問題
我不會數學
## pD 蛋餅愛爬山 2
對於一次查詢
一開始一定是選區間最高的點做起點最好
然後分別考慮第一步向左/右
先看向右
若$L_i$表$i$點開始第一步往左後自由亂跑的答案
$d_i$是$i$點可以往左反跳幾次
$x$是剛剛選到的最高點位置
答案是$max_{x\lt i\le qr}(d_i-d_x+L_i)$
這可以用線段樹之類的維護
為什麼可以這樣?
因為往右再往左之後不管怎樣跑都跑不出$(x,qr)$了
所以可以亂跑
一些細節
可跳躍的$(i,j)$最多只有$2n-2$個
因為可以到指定$j$的$i$只有左/右第一個比他高的
這關係可以用單調stack做
:::spoiler sample code (AC on TIOJ)
```cpp=
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct obj{
ll l,r,x;
};
struct segtree0{
ll n;
vector<pair<ll,ll>> a;
segtree0(ll N):n(N),a(N<<2){}
void set(ll i, ll l, ll r, ll p, ll x){
if(l == r) a[i] = {x,l};
else{
ll m = l+r>>1;
if (p<=m) set(i<<1,l,m,p,x);
else set(i<<1|1,m+1,r,p,x);
a[i] = max(a[i<<1],a[i<<1|1]);
}
}
pair<ll,ll> get(ll i, ll l, ll r, ll ql, ll qr){
if(ql<=l&&r<=qr) return a[i];
else{
ll m = l+r>>1;
if (qr<=m) return get(i<<1,l,m,ql,qr);
else if(ql>m) return get(i<<1|1,m+1,r,ql,qr);
else return max(get(i<<1,l,m,ql,qr),get(i<<1|1,m+1,r,ql,qr));
}
}
};
struct segtree{
ll n;
vector<ll> a;
segtree(ll N):n(N),a(N<<2){}
void set(ll i, ll l, ll r, ll p, ll x){
if(l == r) a[i] = x;
else{
ll m = l+r>>1;
if (p<=m) set(i<<1,l,m,p,x);
else set(i<<1|1,m+1,r,p,x);
a[i] = max(a[i<<1],a[i<<1|1]);
}
}
ll get(ll i, ll l, ll r, ll ql, ll qr){
if (ql>qr) return 0ll;
if(ql<=l&&r<=qr) return a[i];
else{
ll m = l+r>>1;
if (qr<=m) return get(i<<1,l,m,ql,qr);
else if(ql>m) return get(i<<1|1,m+1,r,ql,qr);
else return max(get(i<<1,l,m,ql,qr),get(i<<1|1,m+1,r,ql,qr));
}
}
};
int main(){
ios::sync_with_stdio(0);cin.tie(0);
ll n,q;
cin >> n >> q;
vector<ll> h(n);
for(ll &i : h) cin >> i;
vector<pair<ll,ll>> ord(n);
for(ll i = 0;i<n;i++) ord[i] = {h[i],i};
sort(ord.begin(),ord.end());
vector<obj> qs(q);
vector<ll> ans(q,0);
for(obj &o : qs) cin >> o.l >> o.r,o.l--,o.r--;
{
segtree0 t(n);
for(ll i = 0;i<n;i++) t.set(1,0,n-1,i,h[i]);
for(obj &o : qs) o.x = t.get(1,0,n-1,o.l,o.r).second;
}
vector<ll> pL(n,-1),pR(n,-1),scL(n,0),scR(n,0),sc(n,0);
{
vector<ll> v;
for(ll i = 0;i<n;i++){
while(v.size()&&h[v.back()]<h[i]) v.pop_back();
if (v.size()) pL[i] = v.back();
v.push_back(i);
}
}
{
vector<ll> v;
for(ll i = n-1;i>=0;i--){
while(v.size()&&h[v.back()]<h[i]) v.pop_back();
if (v.size()) pR[i] = v.back();
v.push_back(i);
}
}
for(ll i = 0;i<n;i++){
ll j = ord[i].second;
sc[j] = max(scL[j],scR[j]);
if(pL[j]!=-1) scR[pL[j]] = max(scR[pL[j]],sc[j]+1);
if(pR[j]!=-1) scL[pR[j]] = max(scL[pR[j]],sc[j]+1);
}
{
vector<ll> d(n,0);
for(ll i = n-1;i>=0;i--){
ll j = ord[i].second;
if(pL[j]!=-1) d[j] = d[pL[j]]+1;
}
segtree t(n);
for(ll i = 0;i<n;i++) t.set(1,0,n-1,i,d[i]+scL[i]);
for(ll i = 0;i<q;i++) ans[i] = max(ans[i],t.get(1,0,n-1,qs[i].x+1,qs[i].r)-d[qs[i].x]);
}
{
vector<ll> d(n,0);
for(ll i = n-1;i>=0;i--){
ll j = ord[i].second;
if(pR[j]!=-1) d[j] = d[pR[j]]+1;
}
segtree t(n);
for(ll i = 0;i<n;i++) t.set(1,0,n-1,i,d[i]+scR[i]);
for(ll i = 0;i<q;i++) ans[i] = max(ans[i],t.get(1,0,n-1,qs[i].l,qs[i].x-1)-d[qs[i].x]);
}
for(ll i : ans) cout << i << "\n";
}
```
:::
## pE 雞蛋糕
對於一個最短路徑
每一步走完後垂直剛剛的行動方向劃直線一定不會經過走過的點
因為走過的點一定離終點更遠
而這樣的點走最短路徑到目前點只能走直線
但若存在則與垂直的要求矛盾
所以若碰到燙的就翻轉這直線
一定能過
輸出"Yes"
:::spoiler sample code (AC on TIOJ)
```cpp=
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cout << "Yes\n";
}
```
:::
## pF 守護魔摩市
定義結果的特異點為剛到飽滿狀態或在飽滿狀態碰到魔法少女的點
然後對$i\in[1,N]$算"假設i是特異點，那碰到下個魔法少女後的下個特異點位置與之間的貢獻"
然後用倍增存碰到$2^n$個魔法少女後的數據
對每次查詢、$第一個魔法少女+A$ 為第一個特異點
用倍增找到不超出邊界的最後一個特異點
可能還能再碰一個魔法少女
但那樣多處理一下就好了
:::spoiler sample code
```cpp=
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
ll n,m,a,b;
cin >> n >> m >> a >> b;
string s;
cin >> s;
vector<ll> v(n+1,n);
for(ll i = n-1;i>=0;i--){
v[i] = s[i]=='1'?i:v[i+1];
}
ll beg = a*(a+1)/2;
ll ed = a*b+a*(a-1)/2;
vector<vector<ll>> nxt(21,vector<ll>(n+1,n)),got(21,vector<ll>(n+1,0));
for(ll i = 0;i<n;i++){
ll g = s[i]=='1'?v[i+1]:v[i];
if(g==n){
nxt[0][i] = n;
got[0][i] = 0;
}else if (g<=i+b){
nxt[0][i] = g;
got[0][i] = (g-i)*a;
}else if (g<i+a+b){
ll d = g-i-b;
nxt[0][i] = g+d;
got[0][i] = a*b+d*(2*a-d);
}else{
nxt[0][i] = g+a;
got[0][i] = ed+beg;
}
nxt[0][i] = min(n,nxt[0][i]);
}
for(ll j = 1;j<21;j++){
for(ll i = 0;i<n;i++){
ll np = nxt[j-1][i];
nxt[j][i] = nxt[j-1][np];
got[j][i] = got[j-1][i]+got[j-1][np];
}
}
while(m--){
ll l,r;
cin >> l >> r;
l--,r--;
ll g = v[l];
if (g>r){
cout << "0\n";
continue;
}
ll ans = beg+ed;
ll cur = g+a;
for(ll j = 20;j>=0;j--){
if (nxt[j][cur]<=r){
ans += got[j][cur];
cur = nxt[j][cur];
}
}
if (cur<n&&(s[cur]=='1'?v[cur+1]:v[cur])<=r){
ans += got[0][cur];
}
cout << ans << "\n";
}
}
```
:::
## pG 猜餅乾
先query1~N
灰色表示不存在
然後query中位數
用這來限制$Q_1,Q_3$的位置
來一次query $Q_1,Q_3$
再不斷重複下去
:::spoiler sample code
```cpp=
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
ll n;
cin >> n;
cout << "?";
for(ll i = 1;i<=n;i++) cout << " " << i;
cout << endl;
vector<ll> a(n,-1);
string s;
cin >> s;
vector<ll> v;
for(ll i = 0;i<n;i++){
if (s[i]!='C') v.push_back(i+1);
}
vector<vector<ll>> b;
function<void(ll,ll,ll)> dfs;
dfs = [&](ll l, ll r, ll h){
if (l<r){
if (b.size()<=h) b.emplace_back();
ll m = l+r>>1;
b[h].push_back(v[m]);
dfs(l,m-1,h+1);
dfs(m+1,r,h+1);
}
};
dfs(0,v.size()-1,0);
for(auto &o : b){
vector<ll> q = a;
vector<ll> u = q;
vector<ll> d = q;
if (q[0]==-1) d[0] = v.front()-1;
for(ll i = 1;i<n;i++){
if(q[i]==-1) d[i] = d[i-1];
}
if (q[n-1]==-1) u[n-1] = v.back()+1;
for(ll i = n-2;i>=0;i--){
if(q[i]==-1) u[i] = u[i+1];
}
for(ll i = 0;i<n;i++){
if(q[i]==-1){
auto it = upper_bound(o.begin(),o.end(),d[i]);
if (it==o.end()||*it>=u[i]){
q[i] = *upper_bound(v.begin(),v.end(),d[i]);
}else q[i] = *it;
}
}
cout << "?";
for(ll i = 0;i<n;i++) cout << " " << q[i];
cout << endl;
string s;
cin >> s;
for(ll i = 0;i<n;i++){
if (s[i]=='A') a[i] = q[i];
}
}
{
vector<ll> q = a;
vector<ll> u = q;
vector<ll> d = q;
if (q[0]==-1) d[0] = v.front()-1;
for(ll i = 1;i<n;i++){
if(q[i]==-1) d[i] = d[i-1];
}
for(ll i = 0;i<n;i++){
if(q[i]==-1){
q[i] = *upper_bound(v.begin(),v.end(),d[i]);
}
}
cout << "!";
for(ll i = 0;i<n;i++) cout << " " << q[i];
cout << endl;
}
}
```
:::
## pH 巫醫單車
注意到限制有個奇妙的$NK\le4\times 10^6$
所以先算沒魔法時各事件結束時的cost
再$O(NK)$DP某一次事件若用過魔法且當前為$i$台車
:::spoiler sample code (AC on TIOJ)
```cpp=
#include<bits/stdc++.h>
using namespace std;
using ll = int; // long long 被卡常
ll k;
struct obj{
ll x,y,z,c;
bool operator<(const obj &o) const{
return z<o.z;
}
obj op(char o){
if (o=='1'){
if(c==0) return {x,y,z+1,c};
else return {x,y,z,c-1};
}else{
if(c==k) return {x,y,z+1,c};
else return {x,y,z,c+1};
}
}
};
int main(){
ios::sync_with_stdio(0);cin.tie(0);
ll n,b;
cin >> n >> k >> b;
string s;
cin >> s;
vector<obj> v(n+1);
v[0] = {1,b,0,b};
for(ll i = 0;i<n;i++) v[i+1] = v[i].op(s[i]);
vector<vector<obj>> dp(n,vector<obj>(k+1));
for(ll i = 0;i<n;i++)
for(ll j = 0;j<=k;j++)
dp[i][j] = {i+1,j,v[i].z,j};
for(ll i = 1;i<n;i++){
for(ll j = 0;j<=k;j++){
if (s[i-1]=='0'){
if (j>0) dp[i][j] = min(dp[i][j],dp[i-1][j-1].op(s[i-1]));
if (j==k) dp[i][j] = min(dp[i][j],dp[i-1][j].op(s[i-1]));
}else{
if (j<k) dp[i][j] = min(dp[i][j],dp[i-1][j+1].op(s[i-1]));
if (j==0) dp[i][j] = min(dp[i][j],dp[i-1][j].op(s[i-1]));
}
}
}
obj ans = dp[n-1][0].op(s[n-1]);
for(ll j = 0;j<=k;j++) ans = min(ans,dp[n-1][j].op(s[n-1]));
cout << ans.x << " " << ans.y << " " << ans.z << "\n";
}
```
:::
Sign in with Wallet
Connect another wallet