# 第三次社內賽題解
---
### A. 電研社的工作
----
每天選一個人放假組合數=每天可以放假的人數相乘
----
subtask 1
所有人每天都可以放假，所以答案$=k^n$
$O(n\times k)$
----
full score
剪一剪就可以算出每天可以放假的人數
$O(n\times k)$
----
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#define lc 2*v
#define rc 2*v+1
#define f first
#define s second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
using namespace std;
typedef pair<long long,long long> pll;
typedef pair<int,int> pii;
typedef long long ll;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, const vector<A> &p){
for(const auto &a:p)
os << a << " ";
os << "\n";
return os;
}
int cnt[10010];
const ll mod=1e9+7;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin>>n>>k;
rep(i,0,k){
int t;
cin>>t;
set<int> st;
rep(j,0,t){
string a;
cin>>a;
int res=0;
for(auto c:a){
res=(res+(c-'0'))%n;
}
if(st.count(res)==0) cnt[res]++;
st.insert(res);
}
}
ll ans=1;
rep(i,0,n){
ans=ans*(k-cnt[i])%mod;
}
cout<<ans<<NL;
}
```
---
### B. 排序子字串查詢
----
subtask 1
暴力做
$O(q\times |s|\log |s|)$
----
full score
開一個26大小的陣列存每個字母的數量(類似counting sort)就可以做到跟暴力排序一樣的效果。
修改時把原本的字母數量減1，新加的加1
查詢則從陣列l~r看是否=k，但頭尾可以>=k
$O(q)$
----
code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int cnt[30];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin>>s;
for(auto a:s) cnt[a-'a']++;
int q;
cin>>q;
while(q--){
int t;
cin>>t;
if(t==1){
int x;
char c;
cin>>x>>c;
cnt[s[x]-'a']--;
s[x]=c;
cnt[s[x]-'a']++;
}
else{
int l, r, k;
cin>>l>>r>>k;
int flag=1;
for(int i=l;i<=r;++i){
if(cnt[i]<k){
flag=0;
break;
}
if(i>l && i<r && cnt[i]!=k){
flag=0;
break;
}
}
if(!flag) cout<<"No\n";
else cout<<"Yes\n";
}
}
}
```
---
### C. 最小陣列差
----
subtask 1
$O(n^2)$暴力
----
full score
方法一：對兩陣列排序後雙指針，一個指針在B一一遞進，另一個在A維護最大<=B指針的數字。$O(n)$
方法二:排序B陣列，迴圈跑A陣列，每次二分搜B最接近目前A的數字。$O(n\log n)$
----
二分搜code
```cpp=
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin>>n>>m;
vector<ll> a(n), b(m);
for(int i=0;i<n;++i) cin>>a[i];
for(int i=0;i<m;++i) cin>>b[i];
sort(b.begin(), b.end());
ll mn=1e15;
for(int i=0;i<n;++i){
auto tmp=lower_bound(b.begin(), b.end(), a[i]);
if(tmp==b.begin()) mn=min(mn, *tmp-a[i]);
else if(tmp==b.end()) mn=min(mn, a[i]-*(tmp-1));
else mn=min(mn, min(*tmp-a[i], a[i]-*(tmp-1)));
}
cout << mn << "\n";
}
```
---
### D. 群島高鐵系統
----
subtask 1
裸dijkstra
$O(n\log v)$
----
subtask 2
m=n-1為一棵樹，可以用某種樹dp
$O(n)$
----
full score
一樣做dijkstra，只要在priority_queue多存走過的城市數量，每次走一條邊就可以算權重了。
$O(n\log v)$
----
正確性?
每過3站加k的條件代表走越少邊越好，所以跟bfs吻合
----
code
```cpp=
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
using namespace std;
struct dt{
ll tot, cnt, v;
};
struct cmp{
bool operator()(dt &d1, dt &d2){
return d1.tot>d2.tot;
}
};
int is[200010], done[200010];
vector<int> adj[200010];
ll dis[200010];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, c, k;
cin>>n>>m>>c>>k;
for(int i=1;i<=n;++i) cin>>is[i];
for(int i=0;i<m;++i){
int a, b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
priority_queue<dt, vector<dt>, cmp> pq;
fill(dis, dis+n+1, 1e14);
pq.push({dis[1]=0, 1, 1});
while(!pq.empty()){
auto g=pq.top();
pq.pop();
if(done[g.v]) continue;
done[g.v]=1;
for(auto a:adj[g.v]){
ll cur=g.tot;
if((g.cnt+1)%3==0) cur+=c;
if(is[a]!=is[g.v]) cur+=k;
if(cur<dis[a]){
dis[a]=cur;
pq.push({cur, g.cnt+1, a});
}
}
}
cout<<dis[n]<<"\n";
}
```
---
### E. 背包問題改
----
subtask 1
$O(2^n)$枚舉所有取法
----
subtask 2
$dp[i][j][w]=$考慮到前$i$個物品，總價值=j，且取了w個物品的方法數
轉移：$dp[i][j][w]=dp[i-1][j][w]+dp[i-1][j-v_i][w-1]$
答案：$dp[n][k][n-2]$
另解：https://codeforces.com/group/50laGF4JJZ/contest/438519/submission/202365802
$O(n^2\times k)$
----
full score
答案 = 總價值為k的方法數 - (取n個價值為k的方法數 + 取n-1個價值為k的方法數)
*總價值為k的方法數*：用一般的背包
*取n個價值為k的方法數*：看總和是否=k
*取n-1個價值為k的方法數*：枚舉少取哪一個數$O(n)$
$O(n\times k)$
----
code
```cpp=
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll mod=1e9+7;
ll val[210], dp[100010];
int main(){
int n, k;
cin>>n>>k;
int tot=0;
for(int i=1;i<=n;++i) cin>>val[i], tot+=val[i];
dp[0]=1;
for(int i=1;i<=n;++i){
for(int j=k;j>=val[i];--j){
dp[j]+=dp[j-val[i]];
dp[j]%=mod;
}
}
ll minus=0;
if(tot==k) minus++;
for(int i=1;i<=n;++i) if(tot-val[i]==k) minus++;
cout<<dp[k]-minus<<"\n";
}
```
---
### F. 最遠距離
----
subtask 1
$O(n\times q)$暴力
----
spoiler subtask 2
set維護目前在的人，加入時二分搜他左右的人，更新答案
$O(q\log n)$
----
full score
線段樹應用
每個節點存此區間最右，最左的人，以及這區間最大的距離
```cpp
struct nd{
int ll=-1, rr=-1, mx=-1;
void pull(nd L, nd R){ //pull為合併兩子樹
if(R.rr==-1) rr=L.rr;
else rr=R.rr;
if(L.ll==-1) ll=R.ll;
else ll=L.ll;
mx=max(L.mx, R.mx);
if(R.ll!=-1 && L.rr!=-1) mx=max(mx, R.ll-L.rr);
}
}
```
----
code
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct nd{
int ll=-1, rr=-1, mx=-1;
void pull(nd L, nd R){
if(R.rr==-1) rr=L.rr;
else rr=R.rr;
if(L.ll==-1) ll=R.ll;
else ll=L.ll;
mx=max(L.mx, R.mx);
if(R.ll!=-1 && L.rr!=-1) mx=max(mx, R.ll-L.rr);
}
};
nd tree[800010];
void upd(int v, int l, int r, int pos, int x){
if(l==r){
if(x==1) tree[v]={l, l, -1};
else tree[v]={-1, -1, -1};
return;
}
int mid=(l+r)>>1;
if(pos<=mid) upd(2*v, l, mid, pos, x);
else upd(2*v+1, mid+1, r, pos, x);
tree[v].pull(tree[2*v], tree[2*v+1]);
// cout<<l<<" "<<r<<" "<<tree[v].ll<<" "<<tree[v].rr<<" "<<tree[v].mx<<"\n";
}
nd get(int v, int l, int r, int ql, int qr){
if(l==ql && r==qr) return tree[v];
int mid=(l+r>>1);
if(qr<=mid) return get(2*v, l, mid, ql, qr);
else if(ql>mid) return get(2*v+1, mid+1, r, ql, qr);
nd resl=get(2*v, l, mid, ql, mid), resr=get(2*v+1, mid+1, r, mid+1, qr), ret;
ret.pull(resl, resr);
return ret;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin>>n>>q;
while(q--){
int t;
cin>>t;
if(t==3){
int l, r;
cin>>l>>r;
cout<<get(1, 1, n, l, r).mx<<"\n";
}
else{
int x;
cin>>x;
upd(1, 1, n, x, t);
}
}
}
```
{"metaMigratedAt":"2023-06-18T01:54:08.947Z","metaMigratedFrom":"YAML","title":"第三次社內賽題解","breaks":true,"slideOptions":"{\"transition\":\"slide\"}","contributors":"[{\"id\":\"9afea478-d7aa-4c3e-a3c7-5db22422f956\",\"add\":7643,\"del\":395}]"}