HDU-2018中国大学生程序设计竞赛-网络选拔赛-部分代码

ACM模版

这次抽周末打网络赛，两个半小时就溜了，只过了五道题，后边因为网吧电脑和键盘以及 HDU$HDU$ 的原因，被打自闭了，太难了。

由于不是我自己的电脑，所以整理题解有些麻烦了，现在先给出五道题的代码，如果有时间了，题解慢慢补吧……大概率是没有了吧！

1001 Buy and Resell

描述

代码

#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;
const int MAXN = 5e5 + 10;

int n;
int a[MAXN];

struct cmp_pq2
{
    bool operator () (const pair<int, int> &x, const pair<int, int> &y) const
    {
        return a[x.second] > a[y.second];
    }
};

struct cmp_pq1
{
    bool operator () (const int &x, const int &y)
    {
        return a[x] > a[y];
    }
};

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
        }

        priority_queue<int, vector<int>, cmp_pq1> pq1;
        priority_queue<pair<int, int>, vector<pair<int, int> >, cmp_pq2> pq2;

        for (int i = 1; i <= n; i++)
        {
            int p = 0, s = 0;
            if (!pq1.empty() && a[pq1.top()] < a[i])
            {
                p = a[i] - a[pq1.top()];
            }
            if (!pq2.empty() && a[pq2.top().second] < a[i])
            {
                s = a[i] - a[pq2.top().second];
            }

            if (!p && !s)
            {
                pq1.push(i);
            }
            else if (s >= p)
            {
                int fis =pq2.top().first, sec = pq2.top().second;
                pq2.pop();
                pq2.push({fis, i});
                pq1.push(sec);
            }
            else
            {
                pq2.push({pq1.top(), i});
                pq1.pop();
            }
        }

        ll res = 0, cnt = pq2.size() * 2;
        while (!pq2.empty())
        {
            res += a[pq2.top().second] - a[pq2.top().first];
            pq2.pop();
        }
        printf("%lld %lld\n", res, cnt);
    }

    return 0;
}

1003 Dream

描述

代码

#include <cstdio>
#include <iostream>

using namespace std;

int p;

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        scanf("%d", &p);
        for (int i = 0; i < p; i++)
        {
            for (int j = 0; j < p; j++)
            {
                printf("%d%c", (i + j) % p, j == p - 1 ? '\n' : ' ');
            }
        }

        for (int i = 0; i < p; i++)
        {
            for (int j = 0; j < p; j++)
            {
                 printf("%d%c", (i * j) % p, j == p - 1 ? '\n' : ' ');
            }
        }
    }

    return 0;
}

1004 Find Integer

描述

代码

#include <iostream>
#include <cstdio>

using namespace std;

long long n, a, b, c;

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        scanf("%d%d", &n, &a);

        if (n > 2)
        {
            printf("-1 -1\n");
        }
        else if (n == 1)
        {
            printf("%d %d\n", 1, a + 1);
        }
        else if (n == 0)
        {
            printf("-1 -1\n");
        }
        else
        {
            if (a > 1)
            {
                if (a & 1)
                {
                    long long n = a >> 1;
                    printf("%lld %lld\n", 2 * n * n + 2 * n, 2 * n * n + 2 * n + 1);
                }
            }

            if (a > 4)
            {
                if ((a & 1) == 0)
                {
                    long long n = a >> 1;
                    printf("%lld %lld\n", n * n - 1, n * n + 1);
                }
            }

            if (a == 1 || a == 2)
            {
                printf("-1 -1\n");
            }

            if (a == 4)
            {
                printf("3 5\n");
            }
        }
    }

    return 0;
}

1005 GuGu Convolution

描述

代码

#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long int
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 1e6+ 5;
ll r,p;
struct juz {
    ll x, y;
    juz() { x = 0; y = 0; }
    juz operator*(const juz &b) const{
        juz ans;
        ans.x = (x*b.x%p + y * b.y%p*r) % p;
        ans.y = (x*b.y%p + y * b.x) % p;
        return ans;
    }
    juz operator-(const juz &b) const {
        juz ans;
        ans.x = x - b.x;
        ans.y = y - b.y;
        return ans;
    }

}z1,z2,cot;
juz qpow(juz x, ll y) {
    juz z ;
    z.x = 1;
    z.y = 1;
    while (y) {
        if (y & 1)z =z*x;
        x=x*x;
        y /= 2;
    }
    return z;
}
int f[1000005];
void init() {
    ll i, j;
    for (i = 1; i*i <= maxn; i++)f[i*i] = i;
    for (i = 1; i <= maxn; i++)
        for (j = i + i; j <= maxn; j += i)f[j] = max(f[j], f[i]);
}
int main() {
    #ifdef LOCAL
    freopen("D:/input.txt", "r", stdin);
#endif
    ll i, j, a, b, n;
    init();
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%lld%lld%lld%lld", &a, &b, &n, &p);
        p *= 2;
        r = b;
        z1.x = a,z1.y = 1;
        z2.x = a, z2.y = p - 1;
        cot = qpow(z1, n) - qpow(z2, n);
        cot.y = (cot.y*f[b] % p + p) % p / 2;
        printf("1 %lld %lld\n", cot.y, b / (f[b] * f[b]));
    }

    return 0;
}

1009 Tree and Permutation

描述

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;

struct TNode
{
    int v, w;
    TNode() {}
    TNode(int v, int w) : v(v), w(w) {}
};

int N;
long long ans;
long long sum[MAXN];
long long inv[MAXN];
vector<TNode> G[MAXN];

void dfs(int root, int pre)
{
    sum[root] = 1;
    for (int i = 0; i < G[root].size(); i++)
    {
        TNode &e = G[root][i];
        int s = e.v;
        if (s == pre)
        {
            continue;
        }

        dfs(s, root);

        sum[root] += sum[s];
        sum[root] %= MOD;
        ans += (long long)(sum[s] * (N - sum[s]) * e.w);
        ans %= MOD;
    }
}

void init()
{
    inv[0] = 1;
    for (int i = 1; i < MAXN; i++)
    {
        inv[i] = inv[i - 1] * i % MOD;
    }
}

int main()
{
    init();

    while (cin >> N)
    {
        ans = 0;
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i <= N; i++)
        {
            G[i].clear();
        }

        int X, Y, L;
        for (int i = 1; i < N; i++)
        {
            scanf("%d%d%d", &X, &Y, &L);
                G[X].push_back(TNode(Y, L));
               G[Y].push_back(TNode(X, L));
        }

        dfs(1, 0);

        printf("%lld\n", ans * inv[N - 1] % MOD * 2 % MOD);
    }

    return 0;
}

1010 YJJ’s Salesman

描述

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
int mx[4 * maxn];
int b[maxn];
struct Node
{
    int x;
    int y;
    int val;
    bool operator <(const Node &p)const
    {
        if(x == p.x)return y < p.y;
        return x < p.x;
    }
}a[maxn];
int ql, qr;
int query(int o, int l, int r)
{
    if(qr < ql)return 0;
    if(ql <= l && qr >= r)
    {
        return mx[o];
    }
    int m = l + (r - l) / 2;
    int ans = - 1;
    if(ql <= m)ans = max(ans, query(o * 2, l, m));
    if(qr > m)ans = max(ans, query(o * 2 + 1, m + 1, r));
    return ans; 
}
void update(int o, int l, int r, int pos, int val)
{
    if(l == r)
    {
        mx[o] = max(val, mx[o]) ;
        //cout << l << " "  << mx[o] << endl;
        return ;
    }
    int m = l + (r - l) / 2;
    if(pos <= m)update(o * 2, l, m, pos, val);
    else update(o * 2 + 1, m + 1, r, pos, val);
    mx[o] = max(mx[o * 2], mx[o * 2 + 1]);
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d", &n);
        int cnt = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].val);
            b[cnt++] = a[i].y;    
        }
        memset(mx, 0, sizeof(mx));
        sort(b, b + cnt);
        int m = 1;
        for(int i = 1; i < cnt; i++)
        {
            if(b[i] != b[i - 1])b[m++] = b[i];
        }
        sort(a, a + n);
        int res = -1;
        for(int i = 0; i < n; i++)
        {
            vector<pair<int, int> >cc;
            int mxx = -1;
            int j;
            for(j = i; j < n; j++)
            {
                if(a[j].x != a[i].x)break;
                int pos1 = lower_bound(b, b + m, a[j].y) - b;
                int pos2 = lower_bound(b, b + m, a[j].y - 1) - b;
                if(b[pos2] != a[j].y - 1)pos2 --;
                   ql = 0;qr = pos2;
                int ans = query(1, 0, m - 1);
                ql = pos1;
                qr = pos1;

                ans = max(ans + a[j].val, query(1, 0, m - 1));
                if(ans > mxx)
                {
                    mxx = ans;
                }
                else
                {
                    ans = mxx;
                }
                res = max(res, ans);
                cc.push_back(make_pair(pos1, ans));    
            }
            for(int k = 0; k < cc.size(); k++)
            {
                update(1, 0, m - 1, cc[k].first, cc[k].second);
            }
            i = j - 1;

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

啊啊啊啊，才发现竟然是六道题，昨天下午两点半我撤了以后，我队友明明去参加面试了，怎么面试完回来又 A$A$ 了一题，好强啊……从代码风格上可以区分出来哪些题是我写的，哪些不是，就这样把，懒得都格式化成我的习惯了。

有趣的是，网赛都打得好猛啊！！！感觉人均五题啊……不对，是队。尤其是我们河南，每次网络赛成绩都出奇的好，太牛逼了吧！！！