DDJ Regular Contest Round#3 Tutorial

A. 質數總和

tags: brute force, number theory

窮舉所有區間，用

$O(\sqrt{N})$ 或以下的複雜度 判斷當下區間是不是質數，是就加上總和

複雜度

$O(T\sqrt{N})$

判斷質數教學: http://web.ntnu.edu.tw/~algo/Prime2.html#2

Solution

#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. 模除排列

tags: brute force

爆搜剪枝

直接遞迴窮舉所有組合，
記得每次要先判斷當下要放的數字排在是否能排在前一個數字後面
不能最後窮舉完排列才檢查
由於多筆測資，可能會出現重複的詢問，如果每次都重新計算會TLE
因此算過的詢問要建表記起來，重複就直接查表

然後原題網址XD: https://codeforces.com/gym/103102/problem/I

Solution

#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. 水庫危機

tags: dsu, LCT

可以直接砸LCT

想想看，如果題目要求反過來把原本每個

$\mathrm{\#}$ 變成

$W$ 有沒有比較好做

如果有想到作法的話，那就可以直接從最後面反過來做回去，
把每個操作紀錄起來
接著把原本的圖變成最後的情況，然後反向依序做回來
用一個並查集維護是不是同一個水區

複雜度

$O(NM\alpha (NM))$

並查集教學: https://cp-algorithms.com/data_structures/disjoint_set_union.html

Solution

#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. 茴芠數回文數

tags: strings, manacher, palindrome tree

可以用 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)$ 查表，有興趣的再自已去查

Solution

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. 填填看

tags: brute force, meet in the middle

總共有8個變數，如果直接窮舉

$O(N^8)$ 複雜度是爛掉

先把式子簡化：

${\displaystyle \frac{a\ast b+c\ast d}{e}+f=g-h}$

變成

$a\ast b+c\ast d=e\ast (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)$

Solution

#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;
}