對我來說不知道要用什麼演算法，或是沒用任何演算法卻有挑戰性的題目都會放這。

f855: 線段覆蓋長度 加強版

這題是b966的進階版，這題如果用暴力法，也就是開一個空間為1000萬的array，有覆蓋到的為true，沒蓋到的為false，在b966據說是行得通，可以AC的，不過這題就不可能，畢竟給的時間和空間限制都被壓縮很多。

我的作法是先依據線的左端位置從左排到右，然後設定一個區間，並檢查這些線是否和這個區間有聯集，如果某條線完全沒有，就將它當作新的區間，並將前一個區間的長度加到總長度裡。如果有的話，就看區間的最左和最右需不需要更新。等所有線都檢查完後，將剩下的區間加到總長度就能得到答案。

AC (7ms, 428KB)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<algorithm>
using namespace std;

typedef struct node{
    int l,r;
}line;

bool cmp(line a, line b){
    return a.l<b.l;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    line a[10000];
    int n,i,len=0,low,high;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>a[i].l>>a[i].r;
    }
    sort(a,a+n,cmp);
    low=a[0].l;high=a[0].r;
    for(i=1;i<n;i++){
        //不在區間內->開新區間
        if(a[i].l>high){
            len = len + high - low;
            low=a[i].l;high=a[i].r;
            continue;
        }
        //在區間內->檢查是否需要擴展
        if(a[i].l<low){low=a[i].l;}
        if(a[i].r>high){high=a[i].r;}
    }
    len = len + high - low;
    cout<<len<<"\n";
    return 0;
}

c292. APCS2017-0304-3數字龍捲風

我覺得這題不是難，它算複雜，因為要把輸出的規則變成能用迴圈跑，實在是讓我死了很多腦細胞。

解題想法

首先，以5x5的矩陣、方向為0為例，會先輸出中心，然後是左1個、上1個、右2個、下2個、左3個、…。我們把左上右下4個方向當作一個循環，可以發現，每輸出完兩個方向後，下一個方向要輸出的數就多一個 。然後3x3的矩陣需要輸出5個方向，5x5的矩陣需要輸出9個方向，7x7的矩陣需要輸出13個方向，可以得知NxN的矩陣需要N/2(用Python的角度來看是N//2)個循環 ，之後再輸出最後一個方向。

AC (3ms, 100KB)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<stdio.h>

int arr[50][50], n;

//i.p. = initial position
int left(int len, int ip, int y){
    int i;
    for(i=ip ; i>ip-len ; i--){
        printf("%d",arr[y][i]);
    }
    return ip - len;
}

int up(int len, int ip, int x){
    int i;
    for(i=ip ; i>ip-len ; i--){
        printf("%d",arr[i][x]);
    }
    return ip - len;
}

int right(int len, int ip, int y){
    int i;
    for(i=ip ; i<ip+len ; i++){
        printf("%d",arr[y][i]);
    }
    return ip + len;
}

int down(int len, int ip, int x){
    int i;
    for(i=ip ; i<ip+len ; i++){
        printf("%d",arr[i][x]);
    }
    return ip + len;
}

int main(){
    int way, i, j;
    scanf("%d%d",&n,&way);

    //input matrix
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            scanf("%d",&arr[i][j]);
        }
    }

    //judge way and output
    //we need n/2 cycles
    int cx=n/2, cy=n/2;
    if(way == 0){
        //run cycles
        for(i=1;i<=n/2;i++){
            cx = left(i*2-1, cx, cy);
            cy = up(i*2-1, cy, cx);
            cx = right(i*2, cx, cy);
            cy = down(i*2, cy, cx);
        }

        //last line
        cx = left(n, cx, cy);
    }

    else if(way == 1){
        //run cycles
        for(i=1;i<=n/2;i++){
            cy = up(i*2-1, cy, cx);
            cx = right(i*2-1, cx, cy);
            cy = down(i*2, cy, cx);
            cx = left(i*2, cx, cy);
        }

        //last line
        cx = up(n, cy, cx);
    }
    
    else if(way == 2){
        //run cycles
        for(i=1;i<=n/2;i++){
            cx = right(i*2-1, cx, cy);
            cy = down(i*2-1, cy, cx);
            cx = left(i*2, cx, cy);
            cy = up(i*2, cy, cx);
        }

        //last line
        cx = right(n, cx, cy);
    }
    
    else if(way == 3){
        //run cycles
        for(i=1;i<=n/2;i++){
            cy = down(i*2-1, cy, cx);
            cx = left(i*2-1, cx, cy);
            cy = up(i*2, cy, cx);
            cx = right(i*2, cx, cy);
        }

        //last line
        cy = down(n, cy, cx);
    }

    return 0;
}

a821. 4.王者之路

AC (2ms, 324KB)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
#define speedup ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

struct team{
    string name;
    int w=0,l=0;
};

int main(){
    string a,b;
    int n,r,i,j;
    while(cin>>n>>r){
        int tcnt=0,find;
        team t[n];
        for(i=0;i<r;i++){
            cin>>a>>b;

            //建立勝利隊伍資料
            find=0;
            for(j=0;j<tcnt;j++){
                if(t[j].name == a){
                    t[j].w++;
                    find=1;
                    break;
                }
            }
            if(!find){
                t[tcnt].name = a;
                t[tcnt].w++;
                tcnt++;
            }

            //建立失敗隊伍資料
            find=0;
            for(j=0;j<tcnt;j++){
                if(t[j].name == b){
                    t[j].l++;
                    find=1;
                    break;
                }
            }
            if(!find){
                t[tcnt].name = b;
                t[tcnt].l++;
                tcnt++;
            }
        }

        //找出勝場最多且在相同勝場中最少敗場的隊伍
        int mw=0,ml=999,loc;
        for(i=0;i<n;i++){
            if(t[i].w > mw){
                loc = i;
                mw = t[i].w;
                ml = t[i].l;
            }
            else if(t[i].w == mw){
                if(t[i].l < ml){
                    loc = i;
                    ml = t[i].l;
                }
            }
        }

        cout << t[loc].name << "\n";
    }
	return 0;
}

e840. P7. 密碼強度測試(Passwords)

這題也是那種不難但判斷條件多，所以會弄的很複雜的題目。

AC (2ms, 96KB)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<stdio.h>
#include<ctype.h>
#include<string.h>

int main(){
    char ps[22];
    while(scanf("%s",ps) != EOF){
        int i,psl=strlen(ps),strong=0;

        //檢查是否有英文字母和數字
        int ha=0,hn=0;
        for(i=0;i<psl;i++){
            if(isdigit(ps[i])){hn++;}
            if(isalpha(ps[i])){ha++;}
        }

        //檢查是否符合最低要求
        if(psl>=8 && ha>0 && hn>0){
            strong += 10;
        }
        else{
            strong -= 5;
        }

        //密碼字數
        strong += psl*3;

        //英文字元
        strong += ha*3;
        
        //數字字元
        strong += hn*2;

        //只有英文字元
        if(hn == 0){
            strong -= psl;
        }

        //只有數字字元
        if(ha == 0){
            strong -= psl;
        }

        //連續數字
        int cnt = 0;
        for(i=0;i<psl;i++){
            if(isdigit(ps[i])){
                cnt++;
            }
            else{
                if(cnt>0){
                    strong -= (cnt-1)*2;
                    cnt = 0;
                }
            }
        }

        if(cnt>0){
            strong -= (cnt-1)*2;
        }
        printf("%d\n",strong);
    }
    return 0;
}

b304. 00673 - Parentheses Balance

這題我之前有用stack做過，這次看到討論區有人提議用replace，真的妙，討論區的人真的有夠聰明。

AC (18ms, 3.3MB)

1
2
3
4
5
6
7
8
9
10
11
n = int(input())
for i in range(n):
    s = input()
    sl = len(s)//2
    for j in range(sl):
        s = s.replace('()','')
        s = s.replace('[]','')
    if s=='':
        print('Yes')
    else:
        print('No')

b139. NOIP2005 2.校门外的树

這題我在處理路段所用的方法和上面的f855一致，只是要注意這題是頭尾都要算，所以記得要+1。

AC (3ms, 344KB)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<algorithm>
#define speedup ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

struct line{
    int l,r;
};

bool cmp(line a, line b){
    return a.l<b.l;
}

int main(){
    speedup;
    int l,m,len,low,high,i;
    while(cin >> l >> m){
        len = l+1; //因為是0到l，要把0考慮進去。
        line sec[m];
        for(i=0;i<m;i++){
            cin >> sec[i].l >> sec[i].r;
        }
        sort(sec,sec+m,cmp);
        low = sec[0].l;
        high = sec[0].r;
        for(i=1;i<m;i++){
            //不在區間內->開新區間
            if(sec[i].l > high){
                len = len - (high - low + 1);
                low = sec[i].l;
                high = sec[i].r;
                continue;
            }
            //在區間內->檢查是否需要擴展
            if(sec[i].l < low){low = sec[i].l;}
            if(sec[i].r > high){high = sec[i].r;}
        }
        len = len - (high - low + 1);
        cout << len << "\n";
    }
    return 0;
}

c048. 10161 - Ant on a Chessboard

這題我對於條的定義是：

第1條：號碼1*1
第2條：號碼1*1+1 ~ 2*2
第3條：號碼2*2+1 ~ 3*3
以此類推

然後每一條又分成轉彎前、轉彎後

AC (2ms, 108KB)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<stdio.h>
#include<math.h>

int main(){
    int n;
    while(scanf("%d",&n) && n){
        int sn = sqrt(n),loc;
        if(sn*sn != n){sn += 1;}
        //找到n在它那一條的位置
        loc = n - (sn-1)*(sn-1);

        //奇數條
        if(sn%2){
            //轉彎前
            if(loc <= sn){
                printf("%d %d\n",sn,loc);
            }

            //轉彎後
            else{
                printf("%d %d\n",sn*2-loc,sn);
            }
        }

        //偶數條
        else{
            //轉彎前
            if(loc <= sn){
                printf("%d %d\n",loc,sn);
            }

            //轉彎後
            else{
                printf("%d %d\n",sn,sn*2-loc);
            }
        }
    }
    return 0;
}

封面圖源：Pixiv