mtmatt.Page

commonPage

0%

發表於 分類於
文章字數： 12k 所需閱讀時間 ≈ 21 分鐘

前言

當初我同學有在架設我們學校的線上評測系統，而一開始我們的系統非常不穩定，因此，他想到可以寫離線的程式答題系統緩解我們上課的需求。而我看到這個系統，我覺得這是一個不錯的想法，並依此加以改良，新增 TLE 判定和超時時會強制停止，並且可以跨平台使用。

使用(解題者)

一題會是一個資料夾，裡面會有隱藏檔案和非隱藏檔案。

檔案名稱 大致內容 是否隱藏
AC ascii art 的 AC 字樣 True
WA ascii art 的 WA 字樣 True
TLE ascii art 的 TLE 字樣 True
main.h 主要程式 不用附給使用者
Run.cpp 執行程式 不用附給使用者
Run.exe 執行程式 False
Solve.cpp 使用者的程式 False
Description 題目敘述 False
README.md 說明使用方法(如下) False

README.txt 內文

以下說明檔案功能及用法

  1. 編譯並執行 Run.cpp 可以獲得評測結果
  2. 程式碼請寫在 Solve.cpp 裡面
  3. 題目敘述在 Description 裡面，一般應該是 .txt，.md 或 .pdf
  4. 標準輸入輸出用 cin 和 cout 就可以了

以下說明答題結果

  1. AC 作答正確
  2. WA 輸出結果錯誤，或不符合題目要求
  3. TLE 執行時間過長
  4. 程式跳掉 一般來說都是 RE(runtime error)
閱讀全文 »

發表於 分類於 ，
文章字數： 24k 所需閱讀時間 ≈ 43 分鐘

源起 & 說明

起心動念編纂這本「講義」的時候，正值我準備 APCS 考試期間，當時也正在就讀高中，考量到時間上的不足，我邀請 3 個人一起參與，所以，作者總共有 4 個人，而本篇貼文所摘錄的是我所創作的部分。

作者序

演算法與資料結構一直以來都是程式設計中最重要的部分。然而許多的書籍在介紹時，出於篇幅考量，字句精簡，以致晦澀難懂。本書旨在對於演算法及資料結構進行詳細的介紹，避免初學者遇到與我相同的困境，因而花費許多時間。雖說是競賽入門，然我仍有計畫放一些進階的資料結構與演算法。

後續我盡可能會將所有題目放在 ZeroJudge 的課程裡，方便大家測試自己的程式碼，也方便除錯。
(參加課程方式。從使用者選單->「參加課程」->課程代碼：a7HcCs)

這本書作為我程式設計學習的其中一個指標，也是我自主學習計畫的內容。希望能幫助到一些在資料結構與演算法的學習與運用上不知如何進展的人。

作者：李尚哲、余光磊、戴偉璿與李卓岳。

本教材歡迎分享使用，僅須註明出處，惟不得作營利用途。

樹狀樹組-BIT

快速求取區間和的助手

閱讀全文 »

發表於 分類於
文章字數： 2.8k 所需閱讀時間 ≈ 5 分鐘

題目連結

https://codeforces.com/problemset/problem/1741/D

題目概要

給你一個 \(1; 2 …m\) 但沒有排序的數列，其中 \(m=2^n, n \in N\)。 這些數字要被放在一個完全二元樹的樹葉(葉節點)中。 定義此完全二元樹是 “\(beautiful\)” 的若且唯若葉節點的數值剛好由左而右遞增。 我們可以做的操作是對任一節點，將他的左右子樹互換。 請問最少幾次操作可以讓樹變成 “\(beautiful\)” 的，如果做不到輸出 -1。

CF_1741D_1

提示 1

判斷做不做得到與怎麼做可以分開。

提示 2

怎麼做可以快速分辨是否成功。想想線段樹。

想法

閱讀全文 »

發表於 分類於
文章字數： 3.7k 所需閱讀時間 ≈ 7 分鐘

前言

重回程式設計第一天…

因為種種原因停更好久，直到最近，我決定重新開始寫題目。這次的題目選自 https://codeforces.com/contest/1790 ，剛回來想用 Div3 試個手感，沒想到也卡了許久。

本文

言歸正傳，本質上這還是一個分享網站。那我今天用了 3 個小時總共寫出 5 題(共 7 題)。以下是提示、想法、與程式碼的分享。

pA Polycarp and the Day of Pi

簡單說就是求前 30 位的圓周率他寫對幾位，比較需要注意的是範例已經給一個完整的圓周率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include
using namespace std;

// a 是輸入
string ans="314159265358979323846264338327",a;

void solve(){
    cin>>a;
    int same=0;
//  逐位判斷
    for(int i=0;i
int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

pB Taisia and Dice

閱讀全文 »

發表於 分類於
文章字數： 2.3k 所需閱讀時間 ≈ 4 分鐘

想法

由題目可知，必須由甲開始，甲結束。因此，取的次數是奇數。我們可以將第一個甲獨立判斷，後面乙甲都綁定在一起。於是，可以得到。
\(dp_n = dp_{n-2} + 2 \times dp_{n-3} + dp_{n-4}\)

其中，\(dp_{n-2}\) 是最後乙甲都取 1 個棋子；\(dp_{n-3}\) 是最後乙甲其中一個取 1 個棋子，\(dp_{n-4}\) 是最後乙甲都取 2 個棋子的方法數。

由於這是一個線性遞迴的轉移式，因此我們可以用矩陣乘法進一步優化。
$$
\begin{pmatrix}dp_{n} \ dp_{n-1} \ dp_{n-2} \ dp_{n-3} \end{pmatrix} =
\begin{pmatrix}
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 0 \
0 & 0 & 1 & 0
\end{pmatrix}
\times
\begin{pmatrix}dp_{n-1} \ dp_{n-2} \ dp_{n-3} \ dp_{n-4} \end{pmatrix}
$$

最後，\(dp_0=0, ; dp_1 = dp_2 = dp_3 =1\)，因此，可以整理如下。
$$
\begin{pmatrix}dp_{n} \ dp_{n-1} \ dp_{n-2} \ dp_{n-3} \end{pmatrix} =
\begin{pmatrix}
0 & 1 & 2 & 1 \
1 & 0 & 0 & 0 \
0 & 1 & 0 & 0 \
0 & 0 & 1 & 0
\end{pmatrix} ^ {n-3}
\times
\begin{pmatrix};1; \ 1 \ 1 \ 0 \end{pmatrix}
$$
用快速冪的技巧將複雜度優化至 \(O(4^3 \times \log_{2}{n})\)

實作

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using vll=vector<ll>;
using Mer=vector<vll>;

const ll MOD=1e9+7;

Mer operator*(Mer a,Mer b){
    Mer ret(a.size(),vll(b[0].size()));
    for(int i=0;i<a.size();++i){
        for(int j=0;j<b[0].size();++j){
            for(int k=0;k<a.size();++k){
                ret[i][j]=(ret[i][j]+a[i][k]*b[k][j])%MOD;
            }
        }
    }
    return ret;
}

Mer POW(Mer a,ll x){
    Mer ret(a.size(),vll(a[0].size(),0));
    for(int i=0;i<a.size();++i) ret[i][i]=1;
    while(x>0){
        if(x&1) ret=ret*a;
        a=a*a;
        x>>=1;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    ll n;
    cin>>n;

    if(n<=3){
        cout<<1<<"\n";
    }else{
        Mer t=Mer({
            {0,1,2,1},
            {1,0,0,0},
            {0,1,0,0},
            {0,0,1,0}
        });

        t=POW(t,n-3);

        Mer ans=Mer({{1},{1},{1},{0}});

        ans=t*ans;

        cout<<ans[0][0]<<"\n";
    }
}
閱讀全文 »

發表於 分類於
文章字數： 2.2k 所需閱讀時間 ≈ 4 分鐘

Introduction

程式撰寫時，若寫得很亂或是很醜，極有可能導致無法找到錯誤的情況發生。在多人協作以及詢問他人問題時，好的程式碼風格可以使他人更快了解你在寫什麼。進而快速解決問題。

Detail

基本排版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//首先，各層級之間應該要有 44 個空格。

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cout<<"Hello";

    if(1==1){
        cout<<"\n";
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//再者，有些東西可以按照個人習慣，例如大括號的位置。
//但，筆者主觀認為除了 main 以外千萬不要用第三種(如下)，看了還滿痛苦的。

//(↓)第一種
int f(){

}

/*--------------------------------------分隔線--------------------------------------*/

//(↓)第二種
int f() {

}

/*--------------------------------------分隔線--------------------------------------*/

//(↓)第三種
int f()
{

}

行內空格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//行內空格排版，有兩種做法。
//原則上，如果習慣將程式碼放很大的人用第一種，其餘可以自由選擇，然而我較習慣用第一種。

//(↓)第一種
for(int i=0;i<n;++i){
    cout<<a[i]<<" ";
}

/*--------------------------------------分隔線--------------------------------------*/

//(↓)第二種
for(int i=0; i<n; ++i) {
    cout << a[i] << " " ; 
}
1
2
3
4
5
6
7
//如果有需求將多個簡單指令壓在一行的話，建議使用空格。

for(auto u:g[n]) if(u!=p){
    dfs(n);
}

a=0; b=0; c=0;
閱讀全文 »

發表於 分類於
文章字數： 7.8k 所需閱讀時間 ≈ 14 分鐘

先來一個

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
#include<bits/stdc++.h>
using namespace std;

#define ALL(v) v.begin(),v.end()
using ll=long long;

unsigned seed=chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 rng=mt19937_64(seed);

long long RandomNumber(long long a,long long b){
    uniform_int_distribution<long long> dis(a,b);
    return dis(rng);
}

long long RandomNumber(long long n){
    return RandomNumber(1,n);
}

void SubTesk1(int a){
    string fileName=to_string(a);

    ofstream ques(fileName+".in"),ans(fileName+".out");

    int n=RandomNumber(90000,100000);
    ques<<n<<"\n";

    vector<int> LIS;
    for(int i=0;i<n;++i){
        int a=RandomNumber(100000000);
        ques<<a<<" ";

        if(LIS.empty() || lower_bound(ALL(LIS),a)==LIS.end()){
            LIS.emplace_back(a);
        }else{
            int pos=lower_bound(ALL(LIS),a)-LIS.begin();
            LIS[pos]=a;
        }
    }

    ans<<LIS.size();

    cout<<a<<endl;
}

#define REP(i,a,b) for(int i=(a);i<(b);++i)
int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    clock_t startTime=clock();
    REP(i,1,20+1){
        SubTesk1(i);
    }
    clock_t endTime=clock();

    cout<<double(endTime-startTime)/1000<<"\n";
}

還有一個 for 圖論題目的

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#include<bits/stdc++.h>
using namespace std;

#ifndef GRAPH_GEN
#define GRAPH_GEN

unsigned seed=chrono::steady_clock().now().time_since_epoch().count();
mt19937_64 rng(seed);

using ll=long long;

ll Rand(ll a,ll b){
    uniform_int_distribution<ll> dis(a,b);
    return dis(rng);
}

ll Rand(ll a){
    return Rand(1,a);
}

struct edge{
    int from,to;
    long long dis;

    edge(){}

    edge(int f,int t,long long d){
        from=f;
        to=t;
        dis=d;
    }
};

class GraphGen{
    private :
        struct DSU{
            vector<int> dsu,rk;

            DSU(int n){
                dsu.resize(n+10);
                rk.resize(n+10);
                init();
            }

            void init(){
                for(int i=0;i<dsu.size();++i){
                    dsu[i]=i;
                }
            }

            int find(int a){
                if(dsu[a]==a){
                    return a;
                }else{
                    return dsu[a]=find(dsu[a]);
                }
            }

            bool same(int a,int b){
                return find(a)==find(b);
            }

            void uni(int a,int b){
                if(same(a,b)){
                    return;
                }

                if(rk[find(a)]==rk[find(b)]){
                    dsu[find(b)]=find(a);
                    rk[a]++;
                }else if(rk[find(a)]>rk[find(b)]){
                    dsu[find(b)]=find(a);
                }else{
                    dsu[find(a)]=find(b);
                }
            }
        };
    public :
//      nodes 1~n
        static vector<pair<int,int>> GenTree(int n){
            DSU dsu(n);
            vector<pair<int,int>> result;

            while(result.size()<n-1){
                int a=Rand(n),b=Rand(n);
                if(!dsu.same(a,b)){
                    result.emplace_back(a,b);
                    dsu.uni(a,b);
                }
            }

            return result;
        }
//      n nodes m edges, m need to bigger than n-1
        static vector<pair<int,int>> GenConnectedGraph(int n,int m){
            vector<pair<int,int>> result=GenTree(n);

            for(int i=0;i<m-n+1;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                result.emplace_back(a,b);
            }

            return result;
        }
//      n nodes m edges, m need to bigger than n-1
        static vector<pair<int,int>> GenGraph(int n,int m){
            vector<pair<int,int>> result;

            for(int i=0;i<m;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                result.emplace_back(a,b);
            }

            return result;
        }
//      nodes 1~n, and weight in 1~k
        static vector<edge> GenTree(int n,int k){
            DSU dsu(n);
            vector<edge> result;

            while(result.size()<n-1){
                int a=Rand(n),b=Rand(n),c=Rand(k);
                if(!dsu.same(a,b)){
                    result.emplace_back(a,b,c);
                    dsu.uni(a,b);
                }
            }

            return result;
        }

        static vector<edge> GenConnectedGraph(int n,int m,int k){
            vector<edge> result=GenTree(n,k);

            for(int i=0;i<m-n+1;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                int c=Rand(k);

                result.emplace_back(a,b,c);
            }

            return result;
        }

        static vector<edge> GenGraph(int n,int m,int k){
            vector<edge> result;

            for(int i=0;i<m;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                int c=Rand(k);

                result.emplace_back(a,b,c);
            }

            return result;
        }
//      nodes 1~n, and weight in l~r
        static vector<edge> GenTree(int n,int l,int r){
            DSU dsu(n);
            vector<edge> result;

            while(result.size()<n-1){
                int a=Rand(n),b=Rand(n),c=Rand(l,r);
                if(!dsu.same(a,b)){
                    result.emplace_back(a,b,c);
                    dsu.uni(a,b);
                }
            }

            return result;
        }

        static vector<edge> GenConnectedGraph(int n,int m,int l,int r){
            vector<edge> result=GenTree(n,l,r);

            for(int i=0;i<m-n+1;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                int c=Rand(l,r);

                result.emplace_back(a,b,c);
            }

            return result;
        }

        static vector<edge> GenGraph(int n,int m,int l,int r){
            vector<edge> result;

            for(int i=0;i<m;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                int c=Rand(l,r);

                result.emplace_back(a,b,c);
            }

            return result;
        }
};

#endif
閱讀全文 »

發表於 分類於
文章字數： 1.6k 所需閱讀時間 ≈ 3 分鐘

題目連結：Add Two Numbers - LeetCode

想法

我的作法可能沒有那麼好，我是用 vector 存數字，接著進行運算，最後再轉成 link-list。

code

1
2
3
4
5
6
7
8
9
10
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
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
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<int> n1,n2;
        n1.emplace_back(l1->val);
        while(l1->next!=nullptr){
            l1=l1->next;
            n1.emplace_back(l1->val);
        }

        n2.emplace_back(l2->val);
        while(l2->next!=nullptr){
            l2=l2->next;
            n2.emplace_back(l2->val);
        }

        vector<int> ans(max(n1.size(),n2.size())+1);
        for(int i=0;i<n1.size();++i){
            ans[i]+=n1[i];
        }

        for(int i=0;i<n2.size();++i){
            ans[i]+=n2[i];
        }

        for(int i=0;i<max(n1.size(),n2.size());++i){
            if(ans[i]>=10){
                ans[i+1]++;
                ans[i]-=10;
            }
        }

        if(ans.back()==0){
            ans.pop_back();
        }

        ListNode *ret=new ListNode(ans[0]),*a=ret,*b=nullptr;
        for(int i=1;i<ans.size();++i){
            b=new ListNode(ans[i]);
            a->next=b;
            a=b;
        }

        return ret;
    }
};
閱讀全文 »

發表於 分類於
文章字數： 8.2k 所需閱讀時間 ≈ 15 分鐘

前言

最近我同學有在架設我們學校的線上評測系統，而一開始我們的系統非常不穩定，因此，他想到可以寫離線的程式答題系統緩解我們上課的需求。而我看到這個系統，我覺得這是一個不錯的想法，並依此加以改良，新增 TLE 判定和超時時會強制停止，並且可以跨平台使用。

使用(解題者)

一題會是一個資料夾，裡面會有隱藏檔案和非隱藏檔案。

檔案名稱 大致內容 是否隱藏
AC ascii art 的 AC 字樣 True
WA ascii art 的 WA 字樣 True
TLE ascii art 的 TLE 字樣 True
main.h 主要程式 原則上 True
Run.cpp 執行程式 False
Solve.h 使用者的程式 False
Description 題目敘述 False
README.txt 說明使用方法(如下) False

README.txt 內文

以下說明檔案功能及用法

  1. 編譯並執行 Run.cpp 可以獲得評測結果
  2. 程式碼請寫在 Solve.h 裡面
  3. 題目敘述在 Description 裡面，一般應該是 .txt，.md 或 .pdf
  4. 標準輸入輸出用 cin 和 cout 就可以了

以下說明答題結果

  1. AC 作答正確
  2. WA 輸出結果錯誤，或不符合題目要求
  3. TLE 執行時間過長
  4. 程式跳掉 一般來說都是 RE(runtime error)
閱讀全文 »

發表於 分類於
文章字數： 1k 所需閱讀時間 ≈ 2 分鐘

題目連結： Two Sum - LeetCode

前言

最近想說來寫一下許多人推薦的 LeetCode。

想法

我是用 pair 額外儲存陣列中元素的 index ，並用排序加上二分搜的方法。因為這題的 n 最多是 10000，我不確定 O(n^2) 的演算法會不會過，所以就決定用 O(nlog(n))，…一個比較保險的概念。

code

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
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int,int>> v(nums.size());
        for(int i=0;i<nums.size();++i){
            v[i].first=nums[i];
            v[i].second=i;
        }
        sort(v.begin(),v.end());

        vector<int> ret;
        for(int i=0;i<nums.size();++i){
            int a=v[i].first;
            int it=lower_bound(v.begin()+i+1,v.end(),make_pair(target-a,0))-v.begin();
            if(it>=nums.size()) continue;
            int b=v[it].first;
            if(a+b==target){
                ret.emplace_back(v[i].second);
                ret.emplace_back(v[it].second);
                return ret;
            }
        }
        return ret;
    }
};
閱讀全文 »