Sunscreen

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2510;

struct node {
    int l;
    int r;
} a[N];

bool cmp1(node x, node y) {
    if (x.r < y.r)
        return true;
    else if (x.r == y.r && x.l < y.l )
        return true;
    return false;
}

struct Node {
    int spf;
    int sum;
} b[N];

bool cmp2(Node x, Node y) {
    return x.spf < y.spf;
}

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

    for (int i = 0; i < n; i ++ )

        cin >> a[i].l >> a[i].r;
    sort(a, a + n, cmp1);

    for (int i = 0; i < m; i ++ )

        cin >> b[i].spf >> b[i].sum;
    sort(b, b + m, cmp2);

    int res = 0;

    for (int i = 0; i < n; i ++ ) {

        for (int j = 0; j < m; j ++ ) {

            if (b[j].sum && b[j].spf >= a[i].l && b[j].spf <= a[i].r) {
                b[j].sum --;
                res ++ ;
                break;
            }
        }
    }

    cout << res << endl;
    return 0;
}

Prime Distance

#include <iostream>
#include <cstring>

using namespace std;

#define INF 0x3f3f3f3f

const int N = 1e6 + 10;

int cnt;
int primes[N];
bool st[N];

void get_primes() {
    for (int i = 2; i < N; i ++ ) {

        if (st[i])
            continue;
        primes[cnt ++ ] = i;

        for (int j = i + i; j < N; j += i)

            st[j] = true;
    }
}

int main() {

    get_primes();
    int l, u;

    while (cin >> l >> u) {
        memset(st, false, sizeof st);

        for (int i = 0; i < cnt; i ++ ) {

            int a = l / primes[i];
            int b = u / primes[i];

            for (int j = max(a, 2); j <= b; j ++ )

                st[primes[i]*j - l] = true;
        }

        if (l == 1)
            st[0] = true;
        int mark = -1;
        int minl, minr;
        int maxl, maxr;
        int max = -INF;
        int min = INF;

        for (int i = 0; i <= u - l; i ++ ) {

            if (st[i])
                continue;

            if (mark == -1) {
                mark = i;
                continue;
            }

            if (i - mark > max) {
                max = i - mark;
                maxl = mark;
                maxr = i;
            }

            if (i - mark < min) {
                min = i - mark;
                minl = mark;
                minr = i;
            }

            mark = i;
        }

        if (min == INF || max == -INF)
            printf("There are no adjacent primes.\n");
        else
            printf("%d,%d are closest, %d,%d are most distant.\n", minl + l, minr + l, maxl + l,
                   maxr + l);
    }

    return 0;
}

Missile Defence System

#include <iostream>
#include <algorithm>
#include <cstring>

#define INF 0x3f3f3f3f

using namespace std;

const int N = 60;

int n;
int a[N];
int up[N], down[N];
int ans;

void dfs(int u, int d, int t) { // u:需要的上升系统的个数，d:需要的下降系统的个数,t:当前搜索到了第t个导弹
    if ((u + d) >= ans)
        return; // 剪枝

    if (t > n) {
        if ((u + d) < ans)
            ans = u + d;
        return;
    }

    int i, tmp;

    // up
    for (i = 1; i <= u; i ++ )

        if (up[i] > a[t])
            break;
    tmp = up[i];
    up[i] = a[t];
    dfs(max(i, u), d, t + 1);
    up[i] = tmp;

    // down
    for (i = 1; i <= d; i ++ )

        if (down[i] < a[t])
            break;
    tmp = down[i];
    down[i] = a[t];
    dfs(u, max(i, d), t + 1);
    down[i] = tmp;
}

int main() {
    while (~scanf("%d", &n) && n) {
        ans = INF;

        for (int i = 1; i <= n; i ++ )

            scanf("%d", &a[i]);
        dfs(0, 0, 1);
        printf("%d\n", ans);
    }

    return 0;
}

最优贸易

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=100005;
const int MAXM=500005;
const int INF=100000;
int N,M,np=0,np2=0,last[MAXN],last2[MAXN],MAX[MAXN],MIN[MAXN],in[MAXN],a[MAXN];
struct edge{
    int to,pre;
};
edge E[MAXM*2],G1[MAXM*2];
char c;
void read(int &x)
{
    for(c=getchar();c<'0'||c>'9';c=getchar());
    for(x=0;c>='0'&&c<='9';c=getchar())
        x=x*10+c-'0';
}

void addedge(int u,int v)
{
    E[++np]=(edge){v,last[u]};
    last[u]=np;
}

void addedgG1(int u,int v)
{
    G1[++np2]=(edge){v,last2[u]};
    last2[u]=np2;
}

void spfa1()
{
    queue<int>q;
    for(int i=1;i<=N;i++) MIN[i]=INF;
    MIN[1]=a[1]; q.push(1);
    while(!q.empty())
    {
        int i=q.front(); q.pop();
        in[i]=0;
        for(int p=last[i];p;p=E[p].pre)
        {
            int j=E[p].to;
            if(MIN[j]==INF||MIN[j]>MIN[i])
            {
                MIN[j]=min(a[j],MIN[i]);
                if(!in[j])
                {
                    in[j]=1;
                    q.push(j);
                }
            }
        }
    }
}

void spfa2()
{
    queue<int>q;
    memset(in,0,sizeof(in));
    for(int i=1;i<=N;i++)
        MAX[i]=-1;
    MAX[N]=a[N];
    q.push(N);
    while(!q.empty())
    {
        int i=q.front(); q.pop(); in[i]=0;
        for(int p=last2[i];p;p=G1[p].pre)
        {
            int j=G1[p].to;
            if(MAX[j]==-1||MAX[j]<MAX[i])
            {
                MAX[j]=max(a[j],MAX[i]);
                if(!in[j])
                {
                    in[j]=1;
                    q.push(j);
                }
            }
        }
    }
}

int main()
{
    int i,u,v,op;
    read(N);
    read(M);
    for(i=1;i<=N;i++)
        read(a[i]);
    for(i=1;i<=M;i++)
    {
        read(u);
        read(v);
        read(op);
        if(op==2)
            addedge(v,u),addedgG1(u,v);
        addedge(u,v);addedgG1(v,u);
    }
    spfa1();
    spfa2();
    int ans=0;
    for(i=1;i<=N;i++)
        ans=max(ans,MAX[i]-MIN[i]);
    printf("%d",ans);
}