ProjectEuler 011 - 020

可以回顾的题目:

• 016
• 017

011

思路

略

AC Code

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int main(){
    vector< vector<int> > grid(20,vector<int>(20));
    for(int grid_i = 0;grid_i < 20;grid_i++){
        for(int grid_j = 0;grid_j < 20;grid_j++){
            cin >> grid[grid_i][grid_j];
        }
    }
    int ans = 0;
    // 可能会忘记反对角线
    int dx[4] = {1, 1, 1, 0};
    int dy[4] = {-1, 0, 1, 1};
    for(int ay = 0; ay < 20; ay++){
        for(int ax = 0; ax < 20; ax++){
            for(int d = 0; d < 4; d++){
                if(ax + 3 * dx[d] < 0 || ax + 3 * dx[d] >= 20 || ay + 3 * dy[d] < 0 || ay + 3 * dy[d] >= 20) continue;
                int res = grid[ax][ay] * grid[ax + dx[d]][ay + dy[d]] * grid[ax + 2 * dx[d]][ay + 2 * dy[d]] * grid[ax + 3 * dx[d]][ay + 3 * dy[d]];
                ans = max(ans, res);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

012

思路

略

AC Code

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

bool check(int n, int k){
    int res = 1;
    for(int i = 2; i <= k / i; i++){
        int s = 0;
        while(k % i == 0){
            s++;
            k /= i;
        }
        res *= (s + 1);
    }
    if(k > 1) res *= 2;
    return res > n;
}

int f(int n){
    for(int j = 1; ; j++){
        int k = j * (j + 1) / 2;
        if(check(n, k)){
            return k;
        }
    }
    return 0;
}

int main() {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        cout << f(n) << endl;
    }
    return 0;
}

013

思路

略

AC Code

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e3 + 10;
string s[N];
vector<int> a[N];
vector<int> res;
int n;

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> s[i];
    for(int i = 0; i < n; i++){
        for(int j = 49; j >=0; j--){
            a[i].push_back(s[i][j] - '0');
        }
    }
    for(int i = 0, carry = 0; i < 50 || carry; i++){
        if(i < 50)
            for(int j = 0; j < n; j++){
                carry += a[j][i];
            }
        res.push_back(carry % 10);
        carry /= 10;
    }
    int len = res.size();
    for(int i = len - 1; i >= len - 10; i--) cout << res[i];
    return 0;
}

014

思路

记忆化，注意用long long处理溢出

AC Code

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

// 否则卡四个例子
typedef long long ll;

const int N = 5000010;
int q[N];
int step[N];
int dp[N];

void init(int n){
    step[1] = 0;
    step[2] = 1;
    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3; i <= n; i++){
        ll s = 0, t = i;
        while((t <= n && step[t] == 0) || t > n){
            if(t & 1){
                t = t * 3 + 1;
            }else{
                t = t / 2;
            }
            s++;
        }
        step[i] = s + step[t];
        if(step[i] >= step[dp[i - 1]]){
            dp[i] = i;
        }else{
            dp[i] = dp[i - 1];
        }
    }
}

int main() {
    int t;
    cin >> t;
    int mx = 0;
    for(int i = 0; i < t; i++) {
        cin >> q[i];
        mx = max(mx, q[i]);
    }
    init(mx);
    for(int i = 0; i < t; i++) {
        cout << dp[q[i]] << endl;
    }
    return 0;
}

015

思路

略

AC Code

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 510, mod = 1e9 + 7;
int dp[N][N];

void init(){
    dp[0][0] = 1;
    for(int i = 1; i < N; i++) dp[i][0] = dp[i - 1][0];
    for(int j = 1; j < N; j++) dp[0][j] = dp[0][j - 1];
    for(int i = 1; i < N; i++){
        for(int j = 1; j < N; j++){
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
        }
    }
}

int main() {
    int t;
    cin >> t;
    init();
    while(t--){
        int n, m;
        cin >> n >> m;
        cout << dp[n][m] << endl;
    }

    return 0;
}

016

思路

想多了，正常记忆化就行

AC Code

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;

int main() {
    int t;
    cin >> t;
    vector<vector<int>> s;
    s.push_back({1});
    while(t--){
        int n;
        cin >> n;
        int k = s.size();
        for(int i = k; i <= n; i++){
            vector<int> t = s.back();
            vector<int> res;
            int m = t.size();
            for(int i = 0, carry = 0; i < m || carry; i++){
                if(i < m) carry += t[i] * 2;
                res.push_back(carry % 10);
                carry /= 10;
            }
            s.push_back(res);
        }
        cout << accumulate(s[n].begin(), s[n].end(), 0) << endl;
    }
    return 0;
}

017

思路

感觉每次都要写错几次系列。。。

AC Code

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
vector<string> v1 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
vector<string> v2 = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

string convertHundred(int num){
    string res;
    int a = num / 100, b = num % 100, c = num % 10;
    res = b < 20 ? v1[b] : v2[b / 10] + (c ? " " + v1[c] : "");
    if(a > 0) res = v1[a] + " Hundred" + (b ? " " + res : "");
    return  res;
}

string numberToWords(ll num) {
    string res = convertHundred(num % 1000);
    vector<string> v = {"Thousand", "Million", "Billion", "Thousand Billion"};
    for(int i = 0; i < 4; i++){
        num /= 1000;
        res = num % 1000 ? convertHundred(num % 1000) + " " + v[i] + " " + res : res;
    }
    while(res.back() == ' ') res.pop_back();
    return res.empty() ? "Zero" : res;
}

int main() {
    int t;
    cin >> t;
    while(t--){
        ll n;
        cin >> n;
        cout << numberToWords(n) << endl;
    }
    return 0;
}

018

思路

略

AC Code

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 26;
int g[N][N];

int main() {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                cin >> g[i][j];
            }
        }
        for(int i = n - 1; i >= 1; i--){
            for(int j = 1; j <= i; j++){
                g[i][j] += max(g[i + 1][j], g[i + 1][j + 1]);
            }
        }
        cout << g[1][1] << endl;
    }
    return 0;
}

019

思路

看着都烦，也是一写必错系列。。。

AC Code

#

020

思路

记忆化就够了

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    int t;
    cin >> t;
    vector<vector<int>> s;
    s.push_back({1});
    while(t--){
        int n;
        cin >> n;
        int k = s.size();
        for(int i = k; i <= n; i++){
            vector<int> res;
            vector<int> t = s.back(); // (k - 1)!
            int m = t.size();
            for(int j = 0, carry = 0; j < m || carry; j++){
                if(j < m) carry += t[j] * i;
                res.push_back(carry % 10);
                carry /= 10;
            }
            s.push_back(res);
        }
        cout << accumulate(s[n].begin(), s[n].end(), 0) << endl;
    }
    return 0;
}