【今日三题】素数回文(模拟) / 活动安排(区间贪心) / 合唱团(动态规划)

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

bool isprime(long long n)
{
    if (n < 2) return false;
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}
int main()
{
    string s;
    cin >> s;
    for (int i = s.size() - 2; i >= 0; i--) s += s[i];
    if (isprime(stoll(s))) cout << "prime" << endl;
    else cout << "noprime" << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2e5 + 1;
using pii = pair<int, int>;
pii arr[N];
int n, a, b, res;

int main() 
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
        arr[i].first = a;
        arr[i].second = b;
    }
    sort(arr, arr + n);
    int l = arr[0].first, r = arr[0].second;
    for (int i = 1; i < n; i++)
    {
        int a = arr[i].first, b = arr[i].second;
        if (a >= r) res++;
        else b = min(b, r);
        l = a;
        r = b;
    }
    cout << res + 1 << endl;
    return 0;
}

#include <iostream>
using namespace std;

const long INF = 0x3f3f3f3f3f;
const int M = 55, N = 15;
long f[M][N], g[M][N];
long arr[M];
int n, a, k, d;
long res = -INF;

int main() 
{
    cin >> n; 
    for (int i = 1; i <= n; i++) cin >> arr[i];
    cin >> k >> d;
    for (int i = 1; i <= n; i++)
    {
        f[i][1] = g[i][1] = arr[i];
        for (int j = 2; j <= min(i, k); j++)
        {
            f[i][j] = -INF;
            g[i][j] = INF;
            for (int prev = max(i - d, j - 1); prev <= i - 1; prev++)
            {
                f[i][j] = max(max(f[prev][j - 1] * arr[i], g[prev][j - 1] * arr[i]), f[i][j]);
                g[i][j] = min(min(f[prev][j - 1] * arr[i], g[prev][j - 1] * arr[i]), g[i][j]);
            }
        }
    }
    for (int i = k; i <= n; i++) res = max(res, f[i][k]);
    cout << res << endl;
    return 0;
}