---
tags: DDJ_Contest
---
# DDJ Regular Contest Round\#3 Tutorial
## [A. 質數總和](http://203.64.191.163/ShowProblem?problemid=a620)
tags: ```brute force, number theory```
窮舉所有區間，用 $O(\sqrt{N})$ 或以下的複雜度 判斷當下區間是不是質數，是就加上總和
複雜度 $O(T \sqrt{N})$
判斷質數教學: http://web.ntnu.edu.tw/~algo/Prime2.html#2
:::spoiler Solution
```cpp
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
bool isprime(int x){
if(x<=1) return 0;
for(int i=2;i*i<=x;i++) if(x%i==0) return 0;
return 1;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int t;cin>>t;
string n;
while(t--){
int ans=0;
cin>>n;
for(int i=0;i<n.size();i++){
string tmp;
for(int j=i;j<n.size();j++){
tmp+=n[j];
int x=atoi(tmp.c_str());
if(isprime(x)){
ans+=x;
}
}
}
cout<<ans<<endl;
}
return 0;
}
```
:::
## [B. 模除排列](http://203.64.191.163/ShowProblem?problemid=a615)
tags: ```brute force```
爆搜剪枝
直接遞迴窮舉所有組合，
記得每次要先判斷當下要放的數字排在是否能排在前一個數字後面
不能最後窮舉完排列才檢查
由於多筆測資，可能會出現重複的詢問，如果每次都重新計算會TLE
因此算過的詢問要建表記起來，重複就直接查表
然後原題網址XD: https://codeforces.com/gym/103102/problem/I
:::spoiler Solution
```cpp=
#include<bits/stdc++.h>
#define ll long long
#define MXN 20
#define endl '\n'
using namespace std;
int len;
bool v[MXN], used[MXN];
vector<int> arr;
vector<vector<int>> ans[MXN];
void dfs(int x){
if(x==len){
if(arr[len-1]%arr[0]<=2) ans[len].push_back(arr);
return;
}
for(int i=1;i<=len;i++){
if(!v[i] && (arr.empty()||arr.back()%i<=2)){
v[i]=1;
arr.push_back(i);
dfs(x+1);
arr.pop_back();
v[i]=0;
}
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int t,n;cin>>t;
while(t--){
cin>>n;
if(used[n]){
for(auto i:ans[n]){
for(auto j:i) cout<<j<<" ";
cout<<endl;
}
}
else{
used[n]=1;
len=n;
dfs(0);
for(auto i:ans[l]){
for(auto j:i) cout<<j<<" ";
cout<<endl;
}
}
}
return 0;
}
```
:::
## [C. 水庫危機](http://203.64.191.163/ShowProblem?problemid=a612)
tags: <code>dsu, ~~*LCT*~~</code>
~~可以直接砸LCT~~
想想看，如果題目要求反過來把原本每個 $\#$ 變成 $W$ 有沒有比較好做
如果有想到作法的話，那就可以直接從最後面反過來做回去，
把每個操作紀錄起來
接著把原本的圖變成最後的情況，然後反向依序做回來
用一個並查集維護是不是同一個水區
複雜度 $O(NM \alpha(NM))$
並查集教學: https://cp-algorithms.com/data_structures/disjoint_set_union.html
:::spoiler Solution
```cpp=
#include<bits/stdc++.h>
#define MXN 2002
#define MXQ 100005
#define endl '\n'
using namespace std;
int n,m,q;
int ans[MXQ],f[MXN*MXN];
pair<int,int> query[MXQ];
bool v[MXN*MXN];
string land[MXN];
int find(int x){
return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int x,int y){
x = find(x),y =find(y);
if(x==y) return;
f[y]=x;
}
int toord(int x,int y){
return x*n+y;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
iota(f,f+n*m,0);
for(int i=0;i<n;i++) cin>>land[i];
cin>>q;
for(int i=0,a,b;i<q;i++){
cin>>a>>b;
--a,--b;
query[i]=make_pair(a,b);
land[a][b]='#';
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
v[toord(i,j)]=1;
if(!i && !j) continue;
if(land[i][j] == 'W'){
if(i && land[i-1][j]=='W') merge(toord(i,j),toord(i-1,j));
if(j && land[i][j-1]=='W') merge(toord(i,j),toord(i,j-1));
}
}
}
int sum=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(land[i][j]=='W'){
sum+=v[find(toord(i,j))];
v[find(toord(i,j))]=0;
}
}
}
ans[q-1]=sum;
for(int i=q-1;i>0;i--){
int a=query[i].first,b=query[i].second,cnt=0;
land[a][b]='W';
if(a && land[a-1][b]=='W'){
cnt+=find(toord(a-1,b)) != find(toord(a,b))
merge(find(toord(a-1,b)), find(toord(a,b)));
}
if(b && land[a][b-1]=='W'){
cnt+=find(toord(a,b-1)) != find(toord(a,b))
merge(find(toord(a,b-1)), find(toord(a,b)));
}
if(a+1<n && land[a+1][b]=='W'){
cnt+=find(toord(a+1,b)) != find(toord(a,b))
merge(find(toord(a+1,b)), find(toord(a,b)));
}
if(b+1<m && land[a][b+1]=='W'){
cnt+=find(toord(a,b+1)) != find(toord(a,b))
merge(find(toord(a,b+1)), find(toord(a,b)));
}
sum-=cnt-1;
ans[i-1]=sum;
}
for(int i=0;i<q;i++) cout<<ans[i]<<endl;
return 0;
}
```
:::
## [D. 茴芠數回文數](http://203.64.191.163/ShowProblem?problemid=a610)
tags: <code>strings, manacher, palindrome tree</code>
可以用 manacher 求出以每個字元為中心的最長回文長度
接著分奇數偶數兩種case做，
分別再記錄前綴和，可以達到 $O(N)$建表 $O(1)$查表
複雜度 $O(N+Q)$
如果懶得建表，也可以二分搜有幾個長度 $\ge q_i$
複雜度 $O(N+QlgN)$
manacher教學: https://cp-algorithms.com/string/manacher.html
當然也可以直接砸回文樹，把每種狀態看他長度有多長就存起來，再 $O(1)$ 查表，有興趣的再自已去查
:::spoiler Solution
```cpp=
void solve() {
int n;cin>>n;
string str,v="^";cin>>str;
for(const auto& i:str)
v+="#"s+i;
v+="#$"s;
V<int> rad(v.size(),0);
int c=0,r=0;
for(int i=1;i<int(v.size())-1;i++){
int mirror_i = 2*c-i;
if(i<r&&mirror_i>=1&&(i+rad[mirror_i])<r){
rad[i]=rad[mirror_i];
continue;
}
while(v[i-1-rad[i]]==v[i+1+rad[i]])
rad[i]++;
if(i+rad[i]>r)
r=i+rad[i],c=i;
}
V<int> arr(n+1,0);
for(const auto& i:rad)
arr[i]++;
for(int i=n-2;i>0;i-=2)
arr[i]+=arr[i+2];
for(int i=n-3;i>0;i-=2)
arr[i]+=arr[i+2];
int q;cin>>q;
while(q--){
int k;cin>>k;
cout<<arr[k]<<' ';
}
cout<<endl;
}
```
:::
## [E. 填填看](http://203.64.191.163/ShowProblem?problemid=a606)
tags: ```brute force, meet in the middle```
總共有8個變數，如果直接窮舉 $O(N^8)$ 複雜度是爛掉
先把式子簡化：
$\displaystyle \frac{a*b+c*d}{e} +f = g - h$
變成
$a*b+c*d = e * (g-h-f)$
接著可以用中間相遇法，先 $O(N^4)$ 窮舉前四個 $a,b,c,d$ 所有組合答案存進去一個容器裡(可以用hashtable或者二分搜，用map會TLE)
再花 $O(N^4)$ 窮舉後四個 $e,f,g,h$ 所有組合答案，每次 $O(lg{N^4})$ 時間去查有幾個值等於的數量
記得要處理 $e=0$ 要排除
複雜度 $O(N^4 lg N^4)$
:::spoiler Solution
```cpp=
#include<bits/stdc++.h>
#define ll long long
#define MXN 105
#define endl '\n'
using namespace std;
ll n;
ll arr[MXN];
unordered_map<ll,ll> mp;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=0;i<n;i++) cin>>arr[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
for(int l=0;l<n;l++){
mp[arr[i]*arr[j]+arr[k]*arr[l]]++;
}
}
}
}
ll ans=0;
for(int i=0;i<n;i++){
if(!arr[i]) continue; //記得特判
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
for(int l=0;l<n;l++){
if(mp.count(arr[i]*(-arr[j]+arr[k]-arr[l]))){
ans+=mp[arr[i]*(-arr[j]+arr[k]-arr[l])];
}
}
}
}
}
cout<<ans<<endl;
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet