头像

houghstc




离线:14小时前


活动打卡代码 AcWing 1532. 找硬币

#include <iostream>
#include <unordered_set>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    unordered_set<int> set;
    int v1 = 1e9, v2;
    for(int i = 0; i < n; ++i)
    {
        int a;
        cin >> a;
        int b = m - a;
        if(set.count(b))
        {
            if(a > b) swap(a, b);
            if(a < v1) v1 = a, v2 = b;
        }
        set.insert(a);
    }
    if(v1 == 1e9)
        cout << "No Solution\n";
    else
        cout << v1 << ' ' << v2 << '\n';
    return 0;
}


活动打卡代码 AcWing 196. 质数距离

houghstc
10天前
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 50010, M = 1000010;

int primes[N], cnt;
bool is_prime[N];
int l, r;
bool is_prime2[M];

void get_primes(int n)
{
    fill(is_prime, is_prime+N, true);

    for(int i = 2; i <= n; ++i)
    {
        if(is_prime[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] * i <= n; ++j)
        {
            is_prime[primes[j]*i] = false;
            if(i % primes[j] == 0) break;
        }
    }
}


int main()
{
    get_primes(50000);

    while(cin >> l >> r)
    {
        fill(is_prime2, is_prime2+M, true);
        for(int i = 0; i < cnt; ++i)
        {
            // p0 = first multiple of p greater or equal to l
            // p0 = ceil(l/p) = (l+p-1)/p
            ll p = primes[i];
            for(ll j = max(2*p, (l+p-1)/p*p); j <= r; j += p)
            {
                is_prime2[j-l] = false;
            }
        }

        int mi_a = 0, mi_b = 1e9, mx_a = -1, mx_b = -1;
        for(ll i = l, j = -1; i <= r; ++i) // i要定义成ll 类型,不然i = r之后++i会爆int
        {
            if(i >= 2 && is_prime2[i-l])  // i必须要大于2
            {
                if(j != -1)
                {
                    if(i-j < mi_b-mi_a)
                    {
                        mi_a = j, mi_b = i;
                    }
                    if(i-j > mx_b-mx_a)
                    {
                        mx_a = j, mx_b = i;
                    }
                }
                j = i;
            }
        }
        if(mi_a != 0)
        {
            cout << mi_a << ',' << mi_b << " are closest, " << mx_a << ',' << mx_b << " are most distant.\n";
        }
        else
        {
            cout << "There are no adjacent primes.\n";
        }

    }
    return 0;
}


活动打卡代码 AcWing 1208. 翻硬币

houghstc
10天前
#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;
    int n = s.size();
    int cnt = 0;
    for(int i = 0, j = -1; i < n; ++i)
    {
        if(s[i] != t[i])
        {
            if(j == -1)
                j = i;
            else
            {
                cnt += (i-j);
                j = -1;
            }
        }
    }
    cout << cnt << '\n';

    return 0;
}


活动打卡代码 AcWing 429. 奖学金

houghstc
10天前
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Data
{
    int id;
    int a;
    int b;
    int c;
    int sum;
};

int main()
{
    int n;
    cin >> n;
    vector<Data> d(n+1);
    for(int i = 1; i <= n; ++i)
    {
        cin >> d[i].a >> d[i].b >> d[i].c;
        d[i].id = i;
        d[i].sum = d[i].a + d[i].b + d[i].c;
    }

    sort(d.begin()+1, d.end(), [](const auto &d1, const auto &d2) {
        if(d1.sum != d2.sum)
            return d1.sum > d2.sum;
        else if(d1.a != d2.a)
            return d1.a > d2.a;
        else
            return d1.id < d2.id;
    });

    for(int i = 1; i <= 5; ++i)
        cout << d[i].id << ' ' << d[i].sum << '\n';

    return 0;
}



houghstc
10天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int primes[N], cnt, n;
bool is_prime[N];

void get_primes(int n)
{
    fill(is_prime, is_prime+N, true);
    for(int i = 2; i <= n; ++i)
    {
        if(is_prime[i]) primes[cnt++] = i;
        for(int j = 0; primes[j]*i <= n; ++j)
        {
            is_prime[primes[j]*i] = false;
            if(i % primes[j] == 0)
                break;
        }
    }
}

int main()
{
    cin >> n;
    get_primes(n+1);

    if(n <= 2) puts("1");
    else puts("2");

    for(int i = 2; i <= n+1; ++i)
    {
        if(is_prime[i])
            cout << "1 ";
        else
            cout << "2 ";
    }
    cout << '\n';

    return 0;
}


活动打卡代码 AcWing 1292. 哥德巴赫猜想

houghstc
11天前
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1e6;

bool is_prime[N+10];
vector<int> primes;
int cnt;


void get_primes()
{
    primes.reserve(N);
    memset(is_prime, true, sizeof is_prime);
    for(int i = 2; i <= N; ++i)
    {
        if(is_prime[i]) primes.push_back(i);
        for(int j = 0; primes[j]*i <= N; ++j)
        {
            is_prime[primes[j] * i] = false;
            // cout << "set false to: " << primes[j] * i << endl;
            if(i % primes[j] == 0) break;
        }
    }
}

void solve(int x)
{
    for(int i = 1; i < primes.size() && primes[i] <= x/2; ++i)
    {
        auto it = lower_bound(primes.begin(), primes.end(), x-primes[i]);
        if(it != primes.end() && *it == x-primes[i])
        {
            cout << x << " = " << primes[i] << " + " << *it << '\n';
            return;
        }
    }
}

int main()
{
    get_primes();
    int x;
    while(cin >> x, x)
    {
        solve(x);
    }
    return 0;
}


活动打卡代码 AcWing 422. 校门外的树

houghstc
12天前
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int, int> pii;

int main()
{
    int l, m;
    cin >> l >> m;
    vector<pii> ranges(m);
    for(int i = 0; i < m; ++i)
        cin >> ranges[i].first >> ranges[i].second;

    sort(ranges.begin(), ranges.end(), [](const pii p1, const pii p2) { return p1.first < p2.first; });

    vector<pii> merged;
    pii curr = ranges[0];
    for(int i = 1; i < m; ++i)
    {
        if(ranges[i].first > curr.second)
        {
            merged.push_back(curr);
            curr = ranges[i];
        }
        else
        {
            if(ranges[i].second > curr.second)
            {
                curr.second = ranges[i].second;
            }
        }
    }
    merged.push_back(curr);

    int cnt = 0;
    for(auto p: merged)
        cnt += (p.second-p.first+1);

    cout << l+1-cnt << '\n';

    return 0;
}


活动打卡代码 AcWing 1227. 分巧克力

houghstc
12天前
#include <iostream>

using namespace std;

typedef pair<int, int> pii;

const int N = 100010;
pii arr[N];
int n, k;

bool check(int len)
{
    int cnt = 0;
    for(int i = 0; i < n; ++i)
    {
        auto [a, b] = arr[i];
        cnt += (a / len) * (b / len);
    }
    return cnt >= k;
}

int main()
{
    cin >> n >> k;

    int max_len = 0;
    for(int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        arr[i] = {a, b};
        max_len = max(max_len, min(a, b));
    }

    int l = 1, r = max_len;
    while(l < r)
    {
        int mid = (l+r+1)/2;
        if(check(mid))
            l = mid;
        else
            r = mid - 1;
    }

    cout << l << '\n';
    return 0;
}


活动打卡代码 AcWing 680. 剪绳子

houghstc
12天前
#include <iostream>
#include <iomanip>

using namespace std;

const int N = 100010;
int arr[N];
int n, m;

bool check(double len)
{
    int cnt = 0;
    for(int i = 0; i < n; ++i)
    {
        cnt += (arr[i]/len);
        if(cnt >= m)
            return true;
    }
    return false;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; ++i)
        cin >> arr[i];

    double l = 0, r = 1e9;
    while(r-l > 1e-4)
    {
        double mid = (r+l)/2;
        if(check(mid))
            l = mid;
        else
            r = mid;
    }
    cout << fixed << setprecision(2) << l << '\n';

    return 0;
}


活动打卡代码 AcWing 1346. 回文平方

houghstc
12天前
#include <iostream>
#include <string>
#include <cmath>

const int N = 18;
int base[N];
int n;

using namespace std;

char to_char(int x)
{
    if(x <= 9)
        return '0' + x;
    else
        return 'A' + (x-10);
}

bool is_palindrome(const string &s)
{
    int n = s.size();
    for(int i = 0; i < n/2; ++i)
    {
        if(s[i] != s[n-1-i])
            return false;
    }
    return true;
}

string to_base_b(int x)
{
    string s;
    for(int j = n; j >= 0; --j)
    {
        int y = x / base[j];
        s.push_back(to_char(y));
        x = x % base[j];
    }

    // remove prefix '0'
    int j = 0;
    for(; j < s.size(); ++j)
    {
        if(s[j] != '0')
            break;
    }
    s = s.substr(j);
    return s;
}

int main()
{
    int B;
    cin >> B;
    n = log2(90000)/log2(B) + 1;

    base[0] = 1;
    for(int i = 1; i <= n; ++i)
    {
        base[i] = base[i-1] * B;
    }

    for(int i = 1; i <= 300; ++i)
    {
        int x = i * i;
        string s = to_base_b(x);

        // check palindrome
        if(is_palindrome(s))
            cout << to_base_b(i) << ' ' << s << '\n';
    }
    return 0;
}