# 第二次社內賽題解

## A. 史考特序列

:::spoiler subtask 1
用個set維護
用陣列的話比較麻煩，如果想要快速的把陣列裡重複的刪掉可以用以下

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

:::

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int x, y;
    set<int> a;
    for(int i = 0; i < n; i++){
        cin >> x;
        a.insert(x);
    }
    for(int i = 0; i < m; i++){
        cin >> y;
        if(a.find(y) != a.end())
            a.erase(a.find(y));
        else
            a.insert(y);
    }
    for(auto i : a)
        cout << i << ' ';
    cout << '\n';
}

## B. 幫我撐個10秒左右就好

:::spoiler subtask 1
沒意義，就只是沒有多筆測資
:::

:::spoiler subtask 2
經典括號匹配問題，把左括號存到stack，遇到右括號時看能不能跟stack最上面的配對，可以就pop，否則答案+1
最後答案再加上stack裡未配對到的
:::

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    int t;
    cin >> t;
    while(t--){
        cin >> s;
        vector<char> stk;
        int n = s.size();
        int cnt = 0;
        for(int i = 0; i < n; i++){
            if(s[i] == '(' || s[i] == '{'){
                stk.push_back(s[i]);
            }else if(s[i] == ')'){
                if(stk.empty() || stk.back() != '('){
                    cnt++;
                }else
                    stk.pop_back();
            }else {
                if(stk.empty() || stk.back() != '{')
                    cnt++;
                else
                    stk.pop_back();
            }
        }
        cout << cnt + stk.size() << '\n';
    }
}

## C. 修陷運動

:::spoiler subtask 1
看看有誰厲害到做出這個複雜度
:::

:::spoiler subtask 2
每次都減到比前一個少1(除非本來就比較小)
:::

#include <bits/stdc++.h>
#define pb push_back
#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 main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vector<int> a(n);
	rep(i,0,n) cin>>a[i];
	ll ans=0;
	rep(i,1,n){
		ans+=max(0, a[i]-a[i-1]+1);
		a[i]=min(a[i-1]-1, a[i]);
	}
	cout<<ans<<NL;
}

## D. 字典人2

:::spoiler subtask 1
枚舉所有空格的切割順序，因為每個底線至少配一個字，所以大約最多10個空格，$O(n!)$ 會過
:::

:::spoiler subtask 2
每次切中間就好 $O(n)$
:::

:::spoiler subtask 3
考慮dp，如果要把一個區間都分割完，可以先枚舉第一次切割的位置，再dp把切割點左右邊切完的值，會發現其實解法跟 https://atcoder.jp/contests/dp/tasks/dp_n 一模一樣。
$O(n^3)$
:::

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll dp[310][310];

int main(){
    string str;
    cin>>str;
    vector<ll> val;
    ll cnt=0;
    for(auto a:str){
        if(a=='_') val.push_back(cnt), cnt=0;
        else cnt++;
    }
    val.push_back(cnt);
    int n=val.size();
    for(int k=1;k<n;++k){
        for(int i=0;i+k<n;++i){
            int j=i+k;
            ll sum=0;
            dp[i][j]=1e11;
            for(int x=i;x<=j;++x) sum+=val[x];
            for(int x=i;x<j;++x) dp[i][j]=min(dp[i][j], dp[i][x]+dp[x+1][j]+sum);
        }
    }
    cout<<dp[0][n-1]<<"\n";
}

## E. 資治通鍵

:::spoiler subtask 1
~~我也不知道怎麼做到這複雜度~~
:::

:::spoiler subtask 2
把題目用圖論的方式思考，把$a_i, b_i$當作邊，發現只有當圖形成鏈時才會yes
*鏈即為一條直線*
判斷是鏈與否有兩個關鍵
1. 每個點度一定要<=2
2. 不能出現環(還有可能點度都<=2)，這個用個dfs或是dsu(並查集)就可以判斷
$O(n)$
:::

#include<bits/stdc++.h>
using namespace std;
#define ALAN ios_base::sync_with_stdio(0); cin.tie(0)
#define ll long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a,b) for(int X=a;X<b;++X)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second

#define lpos pos<<1
#define rpos pos<<1|1

const int MAXN = 1e6+5, MOD = 1e9+7;

int ind[MAXN]={0}, n, m, a, b, rec=0;
bool vis[MAXN]={0};
vector<int> adj[MAXN];

void dfs(int pa, int v){
	if(vis[v]) return;
	vis[v]=1;
	for(auto e : adj[v]){
		if(e != pa && vis[e]){
			rec = 1;
			return;
		}
		else dfs(v, e);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	rep(i, 0, m){
		cin >> a >> b;
		ind[a]++, ind[b]++;
		adj[a].pb(b), adj[b].pb(a);
		if(ind[a] > 2 || ind[b] > 2){
			rec++;
			break;
		}
	}
	rep(i, 0, n){
		if(!vis[i]) dfs(0, i);
		if(rec) break;
	}
	if(rec) cout << "No";
	else cout << "Yes";

}

*code from justinshao*

## F. 快樂的搖曳露營

:::spoiler subtask 1
$2^n$枚舉選或不選
$O(2^n\times n)$
:::

:::spoiler subtask 2
k=0沒有代價，還b>=0，那就全部都選
~~甚麼智障subtask~~
$O(n)$
:::

:::spoiler subtask 3
b>0的都選
$O(n)$
:::

:::spoiler subtask 4
做類似longest increasing subsequence的dp
dp[i]=選擇的子序列最後一個是第i個露營地的值
轉移：往前看i應該跟哪個露營地接在一起，對於j=1~i-1，dp[i]=max(dp[i], dp[j]+b[i]-issame(i, j))
issame(i, j)是看是不是同種露營地，是的話會return k
$O(n^2)$
:::

:::spoiler subtask 5, 6
兩個subtask幾乎一樣

再考慮dp，dp[i]=選擇的子序列最後一個是露營地地區編號為i的最大值
轉移：當迴圈走到i時，有兩種轉移
1. 如果要接在*最後一個為a[i]的子序列*的後面，最大值會是dp[a[i]]+b[i]-k
2. 否則，最大值是max(dp[j]+b[i])，j為任意的露營地編號
算出這兩種再更新答案
$O(n)$時間和空間

但我們又發現過程中只要維護兩個dp值，分別是最大的和次大的。因為如果最大的dp其最後一個露營地編號跟a[i]不一樣，那接再最大的那個必定最佳，因為也不用減k。
那如果最大的dp其最後一個露營地編號=a[i]，那次大的一定不會是a[i]，所以這時只要看接再最大-k或次大哪個較好
並且不斷更新最大和次大

$O(n)$時間
$O(1)$空間
:::

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
	ll n, k;
	cin>>n>>k;
	vector<pair<ll, ll> > val(n);
	for(int i=0;i<n;++i) cin>>val[i].first>>val[i].second;
	ll a=-1, b=-1, va=0, vb=0;
	for(int i=0;i<n;++i){
		ll tmp;
		if(a!=val[i].first) tmp=val[i].second+va;
		else{
			tmp=max(val[i].second+va-k, val[i].second+vb);
		}
		if(tmp>va){
		    vb=va;
		    b=a;
			va=tmp;
			a=val[i].first;
		}
		else if(tmp>vb){
			vb=tmp;
			b=val[i].first;
		}
	}
	cout<<va<<"\n";
}