mtmatt.Page

commonPage

0%

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

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

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

閱讀全文 »