头像

冲冲冲啊

南京航空航天大学




离线:6天前


活动打卡代码 AcWing 1010. 拦截导弹

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int n, a[N];
int g[N], f[N];

int main()
{
    while (cin >> a[n]) n++;
    int res = 0;
    for (int i = 0; i < n; i++) 
    {
        f[i] = 1;
        for (int j = 0; j < i; j++)
            if (a[i] <= a[j])   f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) 
    {
        g[i] = 1;
        for (int j = 0; j < i; j++)
            if (a[i] > a[j])   g[i] = max(g[i], g[j] + 1);
        cnt = max(cnt, g[i]);
    }
    cout << res << endl << cnt << endl;
    return 0;
}


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

#include<iostream>
#include<algorithm>
#include<unordered_set>

using namespace std;

const int N = 1000010;
int primes[N], cnt;
bool st[N];
unordered_set<int> isp;

void get_primes(int n)
{
    for (int i = 2; i <= n; i++){
        if (!st[i]) primes[cnt++] = i, isp.insert(i);
        for (int j = 0; primes[j] <= n / i; j++){
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
int main()
{
    get_primes(N);
    int n;
    while (cin >> n, n){
        for (int i = 0; i < cnt; i++){
            if (isp.count(n - primes[i])){
                printf("%d = %d + %d\n", n, primes[i], n - primes[i]);
                break;
            }
        }
    }
    return 0;
}



#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;
int a[N], f[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int res = -1;
    for (int i = 0; i < n; i++){
        f[i] = a[i];
        for (int j = 0; j < n; j++)
            if (a[i] > a[j])    f[i] = max(f[i], f[j] + a[i]);
        res = max(res, f[i]);
    }
    cout << res;
    return 0;
}


活动打卡代码 AcWing 1012. 友好城市

#include<iostream>
#include<algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

PII h[N];
int f[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> h[i].first >> h[i].second;
    sort(h, h + n);

    int res = -1;
    for (int i = 0; i < n; i++)
    {
        f[i] = 1;
        for (int j = 0; j < i; j++)
            if (h[i].second > h[j].second)
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    cout << res;

    return 0;
}


活动打卡代码 AcWing 482. 合唱队形

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 300;
int a[N], g[N], f[N];

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

    for (int i = 0; i < n; i++){
        f[i] = 1;
        for (int j = 0; j < i; j++)
            if (a[i] > a[j])    f[i] = max(f[i], f[j] + 1);
    }

    for (int i = n - 1; i >= 0; i--){
        g[i] = 1;
        for (int j = n - 1; j > i; j--)
            if (a[i] > a[j])    g[i] = max(g[i], g[j] + 1);
    }

    int res = N;
    for (int i = 0; i < n; i++){
        res = min(res, n - (f[i] + g[i] - 1));
    }
    cout << res;
    return 0;
}


活动打卡代码 AcWing 1014. 登山

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;
int a[N], f[N], g[N];

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

    for (int i = 0; i < n; i++)
    {
        f[i] = 1;
        for (int j = 0; j < i; j++)
            if (a[i] > a[j])    f[i] = max(f[i], f[j] + 1);
    }

    for (int i = n - 1; i >= 0; i--)
    {
        g[i] = 1;
        for (int j = n - 1; j > i; j--)
            if (a[i] > a[j])    g[i] = max(g[i], g[j] + 1);
    }

    int res = 0;

    for (int i = 0; i < n; i++) res = max(res, f[i] + g[i] - 1);

    cout << res;

    return 0;
}



int n;
int a[N];

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

    vector<int> q;
    for (int i = 0; i < n; i++)
    {
        if (!i || a[i] > q.back())  q.push_back(a[i]);
        else    *lower_bound(q.begin(), q.end(), a[i]) = a[i];
    }
    cout << q.size();
    return 0;
}


活动打卡代码 AcWing 872. 最大公约数

include[HTML_REMOVED]

using namespace std;

int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int n;
cin >> n;
while (n–)
{
int x, y;
cin >> x >> y;
cout << gcd(x, y) << endl;
}
return 0;
}



活动打卡代码 AcWing 871. 约数之和

#include<iostream>
#include<unordered_map>

using namespace std;

const int N = 1e9 + 7;

unordered_map<int, int> primes;

void get(int x)
{
    for (int i = 2; i <= x / i; i++)
        while (x % i == 0)
        {
            x /= i;
            primes[i]++;
        }
    if (x != 1) primes[x]++;
}
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int x;
        cin >> x;
        get(x);
    }
    long long res = 1;
    for (auto prime : primes)
    {
        int p = prime.first, a = prime.second;
        long long t = 1;
        while (a--) t = (t * p + 1) % N;
        res = res * t % N;
    }
    cout << res;

    return 0;
}


活动打卡代码 AcWing 870. 约数个数

算术基本定理,一个数可以表示为:
$$
N = p_1^{\alpha1} \times p_2^{\alpha2} \times p_3^{\alpha3} \times \cdots \times p_k^{\alpha k}
$$
任何一个约数可以表示为:
$$
d = p_1^{\beta1} \times p_2^{\beta2} \times p_3^{\beta3} \times \cdots \times p_k^{\beta k} ,
0 \le \beta_i \le \alpha_i
$$
所以由乘法原理: $ans = (\alpha_1 + 1)(\alpha_2 + 1)(\alpha_3 + 1)\cdots(\alpha_k + 1)$