如有侵权立即删除

7-1

#include <bits/stdc++.h>

#define pii pair<int,int>

using namespace std;

const int N = 1e4 + 10;

int t[N];

int n;

int w[N],p[N],idx;

int a[N];

int res;

int main(){

//     freopen("data.in","r",stdin);
//     freopen("data.out","w",stdout);

    cin >> n;

    for(int i=0;i<n;i++) cin >> t[i];

    for(int i=0;i<n;)
    {
        int x = t[i];
        int c=0;
        while(i < n && t[i] == x) i ++ ,c++;
        ++ idx;
        p[idx] = c;
        w[idx] =x;
    }

    a[1] = 2;

    for(int i=2;i<=idx;i++)
    {
        if(w[i] > w[i - 1]) a[i] = a[i - 1] + 1;
        else
        {
            int last = i;
            while(i <= idx && w[i] < w[i - 1]) i ++ ;
            i -- ;
            a[i] = 2;

            for(int j=i-1;j>=last-1;j--)
            {
                if(j != last - 1)
                    a[j] = a[j + 1] + 1;
                else
                    a[j] = max(a[j],a[j + 1] + 1);
            }
        }
    }

    for(int i=1;i<=idx;i++)
    {
        res += a[i] * p[i] * 100;
    }
    cout << res << endl;


    return 0;
}

7-2

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int n,m;

int sum[N];

int main(){

//     freopen("data.in","r",stdin);
//     freopen("data.out","w",stdout);

    cin >> n >> m;

    for(int i=1;i<=n;i++){
        int x;
        cin >> x;
        sum[i] = x + sum[i - 1];
    }

    int res = 0;

    for(int i=1,j=0;i<=n;i++)
    {
        while(sum[i] - sum[j] > m) j ++ ;
        res += i - j;
    }

    cout << res << endl;

    return 0;
}

7-3

#include <bits/stdc++.h>

using namespace std;

const int N = 25;

int n;

int pre[N],in[N];

map<int,int> pos;

int l[N],r[N],w[N],idx;

int d[N],st[N];

int build(int pl,int pr,int il,int ir)
{
    if(pl > pr) return 0;

    int root = ++idx;
    w[root] = pre[pl];

    int p = pos[w[root]];

    l[root] = build(pl + 1,pl + p -il,il,p-1);
    r[root] = build(pl + p -il + 1,pr,p+1,ir);

    return root;
}

void bfs(int root)
{
    vector<int> res;
    d[root] = 1;

    queue<int> q;

    q.push(root);

    while(q.size())
    {
        int t = q.front();
        if(!st[d[t]])
        {
            st[d[t]] = true;
            res.push_back(w[t]);
        }
        q.pop();
        if(l[t]) q.push(l[t]),d[l[t]] = d[t] + 1;
        if(r[t]) q.push(r[t]),d[r[t]] = d[t] + 1;
    }

    for(int i=0;i<res.size();i++)
    {
        if(!i) cout << res[i];
        else cout << " " << res[i];
    }
    puts("");
}

int main(){

//      freopen("data.in","r",stdin);
//      freopen("data.out","w",stdout);

    cin >> n;

    for(int i=0;i<n;i++) 
    {
        cin >> in[i];
        pos[in[i]] = i;
    }
    for(int i=0;i<n;i++) cin >> pre[i];

    int root = build(0,n-1,0,n-1);

    bfs(root);



    return 0;
}

7-4

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int d[N];

vector<int> ver[N],w1[N],w2[N];

int n,m;

vector<int> v;

int f1[N],f2[N];

int pre[N];

void topsort()
{
    queue<int> q;

    memset(f1,0x3f,sizeof f1);

    for(int i=0;i<n;i++)
    {
        if(d[i] == 0)
        {
            f1[i] = 0;
            f2[i] = 0;
        }
    }


    for(int i=0;i<n;i++)
        if(d[i] == 0)
            q.push(i);

    while(q.size())
    {
        int t = q.front();
        q.pop();
        v.push_back(t);
        for(auto x : ver[t])
        {
            if(--d[x] == 0)
                q.push(x);
        }
    }

    for(auto x : v)
    {
        for(int i=0;i<ver[x].size();i++)
        {
            int a = ver[x][i];
            int b = w1[x][i];
            int c = w2[x][i];

            if(f1[a] > f1[x] + b || f1[a] == f1[x] + b && f2[a] < f2[x] + c)
            {
                f1[a] = f1[x] + b;
                f2[a] = f2[x] + c;
                pre[a] = x;
            }
        }
    }

}

int main(){

    memset(pre,-1,sizeof pre);

//     freopen("data.in","r",stdin);
//     freopen("data.out","w",stdout);

    cin >> n >> m;

    while(m -- )
    {
        int a,b,c1,c2;
        cin >> a >> b >> c1 >> c2;
        ver[a].push_back(b);
        w1[a].push_back(c1);
        w2[a].push_back(c2);
        d[b] ++ ;
    }

    topsort();

    cin >> m;

    vector<int> f(m);

    bool flag = false;

    for(auto &x : f) 
    {
        cin >> x;
        if(d[x] != 0)
            flag = true;
    }

    if(flag) puts("Impossible.");
    else puts("Okay.");

    for(auto x : f)
    {
        if(f1[x] == 0 && f2[x] == 0) printf("You may take test %d directly.\n",x);
        else if(d[x] != 0) puts("Error.");
        else
        {
            int t = x;
            vector<int> res;
            while(t != -1)
            {
                res.push_back(t);
                t = pre[t];
            }
            reverse(res.begin(),res.end());

            for(int i=0;i<res.size();i++)
            {
                if(!i) cout << res[i];
                else cout << "->" << res[i];
            }
            cout << endl;
        }
    }



    return 0;
}