mtmatt.Page

commonPage

0%

發表於 分類於
文章字數： 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;
    }
};
閱讀全文 »

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

最近寫了一個 GRAPH_GEN.h 檔，想說可以方便生成測資。

簡介

  • 4~5 行是防禦性程式設計，避免多次引用標頭檔時發生編譯錯誤
  • 7~19 行用來生成隨機數
  • 21~32 行是帶有建構式的 edge 物件
  • 底下就是生成測資的物件

具體使用

  • GenTree(n) -> 生成一個有 n 個點，且無邊權的無根樹
  • GenConnectedGraph(n,m) -> 生成一個有 n 個點， m 條邊，且無邊權的連通圖
  • GenGraph(n,m) -> 生成一個有 n 個點， m 條邊，且無邊權的不保證連通圖
  • GenTree(n,k) -> 生成一個有 n 個點，且邊權介於 1~k 的無根樹
  • GenConnectedGraph(n,m,k) -> 生成一個有 n 個點， m 條邊，且邊權介於 1~k 的連通圖
  • GenGraph(n,m,k) -> 生成一個有 n 個點， m 條邊，且邊權介於 1~k 的不保證連通圖

前三個會回傳 vector<pair<int,int>> 每個皆有保證沒有自環，後三個則會回傳 vector<edge> ，以節省重複打 first 與 second 的時間

程式碼

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

#endif

使用範例

1
2
3
4
5
6
7
#include<bits/stdc++.h>
#include "GRAPH_GEN.h"
using namespace std;

int main(){
    vector<pair<int,int>> edges=GraphGen::GenTree(100000);
}
閱讀全文 »

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

題目連結：Sprout Online Judge No. 840

題目敘述

你有一個大整數 \(012345678910111213141516171819202122…\)

也就是說，這個大整數是把所有非負整數依序串在一起。

現在，給你 \(n\)、\(k\)，請你輸出，在這個大整數中，由左至右第 \(n\) 次出現數字 \(k\)，是出現在第幾個位置？

位置從 1 開始算，並保證 \(k\) 是介於 \(0\) 到 \(9\) 之間的整數。

注意到，因為這個大整數太特別了，你定義這個大整數的第一位是 \(0\) 。

\(n \le 10^{12}, 0 \le k \le 9\)

想法

數字這麼大，一定是二分搜尋，找出最後一個含有數字 \(k\) 小於 \(n\) 的數字，而求出在 \(num\) 之前有多少數字 \(k\) 的方法如下。

閱讀全文 »

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

Q1. 程式交易

題目連結：h081: 1. 程式交易 - 高中生程式解題系統

想法

第一天先買，維護一個 bool 變數，分為有持股與無持股兩種情況。

  1. 有持股->若當前價格>=當初買的價格(tp)+D，賣掉，tp 改為當前股價
  2. 無持股->若當前價格<=當初賣的價格(tp)-D，買起來，tp 改為當前股價

細節

若交易結束仍持有股票，則不考慮該股票買進的成本 -> 賣掉的時候再加上獲利

實作

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

bool iss=true;
int n,sum,d,tp;

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

    cin>>n>>d>>tp;

    for(int i=1;i<n;++i){
        int now;
        cin>>now;
        if(iss && tp+d<=now){
            sum+=now-tp;
            tp=now;
            iss=false;
        }else if(!iss && tp-d>=now){
            tp=now;
            iss=true;
        }
    }

    cout<<sum<<"\n";
}

Q2. 贏家預測

閱讀全文 »

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

就是下面這一行

1
#pragma GCC optimize ("O3,unroll-loops")

可以做到什麼效果呢？在某些情況下可以讓 \(O(n^2)\) 硬解 \(10^5\) 的測資。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int a[100010];

for(int i=0;i<n;++i) cin>>a[i];

for(int i=0;i<q;++i){
    int l,r;
    cin>>l>>r;

    int ret=0;
    for(int j=l;j<r;++j){
        ret+=a[j];
    }
    cout<<ret<<"\n";
}

原本要用前綴和，變爆搜就會過。

閱讀全文 »

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

題目連結：AtCoder Beginner Contest 215: D - Coprime 2

題目敘述

給定\(n, m\)下一行會有\(n\)個數字，輸出所有\(k in 1~m\)，\(k\)是與所有數字皆互質的數。

範例輸入 1

1
2
3 12
6 1 5

範例輸出 1

1
2
3
4
3
1
7
11

題解

用埃氏篩法在\(log(n)\) 的時間內做質因數分解，接著將所有數字的質因數聯集存在 bitset 中，最後判斷\(1~m\)的所有數字的質因數之中有無存於 bitset 中。

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

using ll=long long;
const ll N=100010;
#define IO_SPEEDUP ios::sync_with_stdio(0);cin.tie(0);
#define IO_INIT cout<<fixed<<setprecision(6);

int n,m;
int pri[N];
bitset<N> bt;

void init(){
    pri[1]=0;
    for(int i=2;i<N;++i){
        if(pri[i]==0){
            pri[i]=i;
            for(ll k=(ll)i*i;k<N;k+=i)
                pri[k]=i;
        }
    }
}

void div(int n){
    while(pri[n]>0){
        bt[pri[n]]=true;
        n/=pri[n];
    }
}

bool check(int n){
    while(pri[n]>0){
        if(bt[pri[n]]){
            return false;
        }
        n/=pri[n];
    }
    return true;
}

int main(){
    IO_SPEEDUP; IO_INIT;

    cin>>n>>m;
    init();

    for(int i=0;i<n;++i){
        int a;
        cin>>a;
        div(a);
    }

    vector<int> ans;
    for(int i=1;i<=m;++i){
        if(check(i)){
            ans.emplace_back(i);
        }
    }

    cout<<ans.size()<<"\n";
    for(auto i:ans){
        cout<<i<<"\n";
    }
}
閱讀全文 »