# S3 演算法期中考題解
###### tags: `S3 演算法課程`

## A. DNA 比對 ( DNA )

出題：fishhh

:::spoiler 賽中參考解答
其實直接做就AC了

#include "iostream"
using namespace std;
int main(){
    string a,b;
    cin>>a>>b;
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        bool faild=0;
        l--,r--;
        for(int i=l;i<=r;i++){
            if(a[i]!=b[i]){
                faild=1;
                break;
            }
        }
        if(faild){
            cout<<"I am so weak.\n";
        }
        else{
            cout<<"Really?!\n";
        }
    }
}

:::
<br/>

:::spoiler 出爛了

1. 我沒有想到可以用 substr 寫 QQ

2. 也是因為大家分數都太低，最後賽中臨時決定把它變成水題。

3. 原本有另外一個版本(解法都相同)
如果出這樣是不是就沒辦法 substr 了XD

於是後來出完全相同的版本 燒雞
:::

<br/>

::: spoiler 正解

* 子任務 1 暴力做，第一時間會想到的作法

* 子任務 2 建表：建一個 $ary[i][j]$ 如果是 $1$ 代表兩個字串 $s_i~s_j$ 完全相同。

> 在講子任務 3 之前先來討論一下複雜度!
字串最大長度 $10^5$ 詢問次數最大 $2\times10^5$ 每次詢問最多可以從 $1$ 問到 $n$ 所以每次詢問最多需要跑 $10^5$。
如果暴力，就會是 $O(nq)$ 就是接近 $10^{10}$ 顯然TLE。

* 子任務 3 前綴合
當 $s_{1_i}==s_{2_i}$ 那就建立一個ary 紀錄為 1 其他則為 0。

可以發現一件事，當一個區間字串完全相同時，這個區間ary的合就會剛好是區間的長度!
(好像只有一個人做出正確解法)

||@鯨魚島麻糬#5110 在pA砸了線段樹 毒瘤!||

#include "iostream"
using namespace std;
int pre[100010]={};
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    string s1,s2;
    cin>>s1>>s2;
    for(int i=0;i<s1.size();i++){
        pre[i+1]=pre[i];
        if(s1[i]==s2[i]){
            pre[i+1]+=1;
        }
    }
    int q,l,r;
    cin>>q;
    while(q--){
        cin>>l>>r;
        if(pre[r]-pre[l-1]==r-l+1){
            cout<<"Really?!\n";
        }
        else{
            cout<<"I am so weak.\n";
        }
    }
}

:::

## B. YTP 的記分板（YTP Scoreboard）

出題：Koying

:::spoiler 子任務 1：沒有 AC
維護一個二維陣列，每次都將對應位置 -1 即可

:::

:::spoiler 滿分解
需要注意兩個細節：
1. 當該題 AC 時需要有正號
2. 0 可能有 0、+0 兩種情況（沒上傳過 or 一發 AC）
3. AC 過了之後記分板不會再改變

我的作法：AC 時再 +1（意思是兩次 WA 之後 AC 會存 $3$），最後輸出時再 -1 即可
:::

:::spoiler 參考程式：

#include <bits/stdc++.h>

using namespace std;

#define MAXN 105

int n, m, p;
string name[MAXN];
int score[MAXN][MAXN];

void print() {
    for (int i = 0; i < n; i++) {
        cout << name[i] << ' ';
        for (int j = 0; j < p; j++) {
            cout << (score[i][j] > 0 ? "+" + to_string(score[i][j] - 1) : to_string(score[i][j])) << ' ';
        }
        cout << '\n';
    }
}

void update(string user, int p, string res) {
    --p;
    for (int i = 0; i < n; i++) {
        if (name[i] == user) {
            if (res == "AC" && score[i][p] <= 0) {
                score[i][p] = abs(score[i][p]) + 1;
            }
            else if (score[i][p] <= 0) {
                score[i][p] -= 1;
            }
            break;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m >> p;

    for (int i = 0; i < n; i++)
        cin >> name[i];
    
    string op, res;
    int p;
    while (m--) {
        cin >> op;

        if (op == "view") {
            print();
        }
        else {
            cin >> p >> res;
            update(op, p, res);
        }
    }
} 

:::

## C. 神奇的環狀數列 ( Circle )

出題：fisl℩l℩

:::spoiler 題解
> 前綴和前綴和前綴和!!

* 子任務 1：直接實作即可 複雜度：$O(k)$ 顯然在 $k$ 接近 $10^9$ 顯然TLE。
<br/>
* 子任務 2：發現到不管從哪個地方開始 都會先走 $\lfloor k/n \rfloor$ 再回到出發點。所以可以先做掉 然後再走剩下的就好。<br/>但起點還是要窮舉一次，所以每次會跑 $n \times (k\%n)$ 考慮到最糟情況 $k \% n = n-1$ 時複雜度就會是 $O(n^2)$。 當 $(10^5)^2$ 顯然也會TLE。
<br/>
* 子任務 3：可以發現一件事情，在最後窮舉起點的時候，需要去求區間 $[i,i+(k\%n)]$ 的合。說到區間合，那麼前綴合$o(n)$ 建表 $O(1)$ 查詢再好不過了! 整題複雜度 $O(n)$ 超漂亮的><
<br/>

#include "iostream"
using namespace std;
#define int long long
int ary[400010]={};
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>ary[i];
    }
    int base=0;
    int cir=k/n;
    for(int i=1;i<=n;i++){
        int nxt=max((int)1,ary[i]-cir+1);
        base+=(ary[i]+nxt)*(ary[i]-nxt+1)/2;
        nxt--;
        ary[i]=nxt;
        ary[i+n]=nxt;
    }
    for(int i=1;i<=2*n;i++){
        ary[i]+=ary[i-1];
    }
    int ans=0;
    k-=cir*n;
    for(int i=1;i<=n;i++){
        ans=max(ans,ary[i+k]-ary[i]);
    }
    cout<<ans+base<<"\n";
}

:::

## D. 這是一個佇列問題（Queue）

出題：Koying

:::spoiler 子任務 1、3：
你只要會 stack or queue，然後暴力做就可以了
:::

:::spoiler 子任務 2、4：
利用兩個 queue or stack，一個紀錄字元，一個紀錄數量，每次操作只會 push 一次

均攤複雜度：$\mathcal{O}(n)$
:::

:::spoiler 滿分解：
需要同時用到 stack、queue，所以我們需要 deque

用陣列實作或是直接用 `std::deque` 都可以
:::

:::spoiler 參考解答：

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200005

#define int long long

int n, x;
char c;
char s[MAXN];
int cnt[MAXN];

void print(int l, int r) {
    int sum = cnt[l];
    char ch = s[l];

    for (int i = l + 1; i < r; i++) {
        if (s[i] == ch)
            sum += cnt[i];
        else {
            cout << sum << ch;
            sum = cnt[i];
            ch = s[i];
        }
    }

    cout << sum << ch << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    int l = n, r = n, op;
    while (n--) {
        cin >> op;
        if (op == 5)
            print(l, r);

        if (op == 1) {
            cin >> x >> c;
            s[r] = c;
            cnt[r++] = x;
        }
        if (op == 2) {
            cin >> x >> c;
            s[--l] = c;
            cnt[l] = x;
        }
        if (op == 3) {
            cin >> x;
            int sum = 0;
            for (int i = r - 1; i >= l; i--) {
                sum += cnt[i];
                if (sum >= x) {
                    if (sum == x) {
                        r = i;
                        break;
                    }
                    else {
                        cnt[i] -= x - (sum - cnt[i]);
                        r = i + 1;
                        break;
                    }
                }
            }
        }

        if (op == 4) {
            cin >> x;
            int sum = 0;
            for (int i = l; i < r; i++) {
                sum += cnt[i];
                if (sum >= x) {
                    if (sum == x) {
                        l = i + 1;
                        break;
                    }
                    else {
                        cnt[i] -= x - (sum - cnt[i]);
                        l = i;
                        break;
                    }
                }
            }
        }
    }
}

:::

## E. 字串反轉 ( Reverse )

出題：f1sh

:::spoiler 題解
* 子任務 1 就直接實作即可~
* 子任務 2 有兩種做法其中一個是迴圈一個是遞迴

這裡分享一下遞迴的做法：

#include "iostream"
using namespace std;
string s;
int ary[2000]={},ed=0;
void push(int num){
	ary[ed++]=num;
	return ;
}
void reverse(int beg,int end){
	for(int i=beg,j=end;i<j;i++,j--){
		swap(ary[i],ary[j]);
	}
	return ;
}
int recur(int pos,int bg,int inl){ //return endpoint
	int i;
	for(i=pos;i<s.size();i++){
		if(s[i]=='['){
			i=recur(i+2,ed,1);
		}
		else if(s[i]==']'){
			i++;
			break;
		}
		else{
			int ret=0;
			while (s[i]==' '){
				i++;
			}
			
			while(i<s.size()&&s[i]!=' '){
				ret*=10;
				ret+=s[i]-'0';
				i++;
			}
			push(ret);
		}
	}
	if(inl)reverse(bg,ed-1);
	return i;
}
int main(){
    int n;
    getline(cin,s);
	getline(cin,s);
	s+=' ';
	recur(0,0,0);
	for(int i=0;i<ed;i++)cout<<ary[i]<<' ';
	cout<<"\n";
}

下面是 korzying 提供的迴圈做法

#include <bits/stdc++.h>

using namespace std;

#define MAXN 2005

string s[MAXN];
int pos[MAXN];

signed main() {
    // I am so dian
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string input;
    int nowsize = 0;
    int leftcnt = 0;
    while (cin >> input) {
        s[nowsize++] = input;

        if (input == "]") {
            for (int i = nowsize - 1; i >= 0; i--) {
                if (s[i] == "[") {
                    for (int j = i + 1; j < (nowsize - 1) - (j - (i + 1)); j++) {
                        swap(s[j], s[(nowsize - 1) - (j - i)]);
                    }
                    for (int j = i; j < nowsize - 1; j++) {
                        swap(s[j], s[j + 1]);
                    }
                    nowsize -= 2;
                    break;
                }
            }
        }
    }

    for (int i = 0; i < nowsize; i++) {
        cout << s[i] << ' ';
    }
    cout << endl;


}

:::