SDNU ACM-ICPC 2016-2017 Training Weekly Contest 1 【--完结--】

题目链接：

https://vjudge.net/contest/152755#overview

A - Skip the Class

HDU - 6015

思路：贪一贪

AC代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
struct ss
{
    string les;
    int val;
};
int cmp(ss x, ss y)
{
    if(x.les == y.les)
    return x.val > y.val;
    return x.les > y.les;
}
int main()
{
    int t, n, ans, flag;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            map<string, int> qq;
            ss f[105];
            ans = flag = 0;
            scanf("%d",&n);
            for(int i = 0; i < n; ++i)
                cin >> f[i].les >> f[i].val;
            sort(f, f+n, cmp);
            for(int i = 0; i < n; ++i)
            {
                //cout << f[i].les << endl;
                //cout << f[i].val << endl;
                qq[f[i].les]++;
                if(qq[f[i].les] <= 2) ans += f[i].val;
            }
            cout << ans << endl;
        }
    }
    return 0;
}

B - Count the Sheep

HDU - 6016

思维练习。（数据比较大，用cin会超时）

题意：有n只公羊和m只母羊，以及k个关系，k个关系为编号为x的公羊和编号为y的母羊是好朋友。问从任意一只羊开始沿着朋友关系数够4只羊的方法有多少种。

思路：可以把给出的关系构造成一个图来看，从任意一点出发，沿着关系网找到目标。拿第一个样例来说，（为方便观察把母羊编号为3和4）从公羊出发的不同方式为1324，1423，2314，2413共四种，同理，从母羊出发也是四种（把母羊看作1，2，把公羊看作3，4），到这里，我们能看出：从公羊出发的情况乘以二就是答案。而从公羊出发到不同母羊的情况数就等于（这个公羊的度-1）*（母羊的度-1）（度是指与这个点相连的点的个数）.

AC代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn = 100005;
LL a[maxn], b[maxn], na[maxn], nb[maxn];
int main()
{
    int t;
    int n, m, k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        memset(na, 0, sizeof(na));
        memset(nb, 0, sizeof(nb));
        for(int i = 0; i < k; ++i)
        {
            scanf("%lld%lld",&a[i],&b[i]);
            na[a[i]]++;
            nb[b[i]]++;
        }
        LL sum = 0;
        for(int i = 0; i < k; ++i)
            sum += (na[a[i]] - 1) * (nb[b[i]] - 1);
        printf("%lld\n",sum << 1);
    }
    return 0;
}

C - Lotus and Characters

HDU - 6011

开始以为是不要负数，自始至终一直在这样做。看两队1A了，继续提交，继续WA。

这道题看完样例后很多人会和我一样误认为把负数都不算上才能得出最优解，其实不然。给出两组测试数据就知道了：

1 2	3 -1 3 2 1 1 1 答案:8 2 -1 5 4 2 答案:27

正确的做法是把所有数据从大到小排序，然后从前往后加，直到新加的数小于0时停止相加。其实理解了就很简单。
AC代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct ss
{
    int val;
    int amo;
};
int cmp(ss x, ss y)
{
    return x. val > y.val;
}
int main()
{
    int t, n;
    long long cnt, ans;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            cnt = ans = 0;
            ss f[30];
            scanf("%d",&n);
            for(int i = 0; i < n; ++i)
                scanf("%d%d",&f[i].val, &f[i].amo);
            sort(f, f+n, cmp);
            for(int i = 0; i < n; ++i)
            {
                for(int j = 0; j < f[i].amo; ++j)
                {
                    cnt += f[i].val;
                    if(cnt < 0) break;
                    ans += cnt;
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}

D - Lotus and Horticulture

HDU - 6012

思维。

在温室里种花，给出n朵花的适宜生长温度，如果温室温度在这范围内的话，成熟后的每朵花价值为a，高于所给温度，价值为b，低于所给温度，价值为c。问需要让温室温度为多少才能获得最大价值。

一开始让室内温度为-inf,此时答案为∑c，然后模拟温度上升，不断更新最大价值，直到达到所给的最大温度。

这个过程可以用map来实现，first为温度，second为价值。

（这里的温度可以是实数，所以用到了点小技巧：让温度都扩大两倍避免了出现小数的情况）

AC代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
const int maxn = 50005;
int main()
{
    int t, n;
    int l, r, x, y, z;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        map<int, LL> s;
        while(n--)
        {
            scanf("%d%d%d%d%d",&l,&r,&x,&y,&z);
            s[0] += z;
            s[l * 2] += x - z;
            s[r * 2 + 1] += y - x;
        }
        LL ans = 0;
        LL tem = 0;
        for(map<int,LL>::iterator it = s.begin(); it != s.end(); ++it)
        {
            tem += it -> second;
            ans = max(ans, tem);
        }
        cout << ans << endl;
    }
    return 0;
}

E - The Third Cup is Free

HDU - 5999

一眼看出是贪心，然后全部浏览完一遍题目后，把这道题敲完交上，9minA了全场第一题。

AC代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int a[100005];
int main()
{
    int t, n, ans, flag, cou = 0;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            ans = flag = 0;
            scanf("%d",&n);
            for(int i = 0; i < n; ++i)
                scanf("%d",&a[i]);
            sort(a, a+n);
            for(int i = n-1; i >= 0; --i)
            {
                if(flag == 2)
                {
                    flag = 0;
                    continue;
                }
                flag++;
                ans += a[i];
            }
            printf("Case #%d: ",++cou);
            cout << ans << endl;
        }
    }
    return 0;
}

F - Pseudoprime numbers

HDU - 1905

数论。

题目解法：先判断p是不是合数，是的话再判断a的p次方%p是否等于a，是输出yes，否输出no，简单地题套个快速幂模板一套带走..

AC代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
long long quickpow(long long a, long long b, long long c)
{
    long long ans = 1;
    a = a % c;
    while(b)
    {
        if(b & 1)  ans = ans * a % c;
        b >>= 1;
        a = a*a % c;
    }
    return ans;
}
int main()
{
    int flag;
    long long a, p;
    while(~scanf("%lld%lld",&p,&a) && (a || p))
    {
        flag = 0;
        for(int i = 2; i * i < p; ++i)
            if(p % i == 0)
            {
                flag = 1;
                break;
            }
        if(flag == 0)  cout << "no" << endl;
        else
        {
            long long tem = quickpow(a, p, p);
            //cout << tem << endl;
            if(tem == a) cout << "yes" << endl;
            else cout << "no" << endl;
        }
    }
    return 0;
}

G - 小明系列问题――小明序列

HDU - 4521

最长上升子序列的O(nlogn)算法。

AC代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = 1e5 + 10;
int a[MAX], b[MAX], DP[MAX];
int n, m;
int main()
{
    int ans;
    while(~scanf("%d%d",&n, &m))
    {
        ans = 1;
        fill(DP, DP + MAX, INF);
        for(int i = 0; i < n; ++i)
        {
            scanf("%d",&a[i]);
            b[i] = 1;
        }
        for(int i = m; i < n; ++i)
        {
            b[i] = lower_bound(DP, DP + MAX, a[i]) - DP + 1;
            if(b[i] > ans) ans = b[i];
            if(DP[b[i-m]-1] > a[i-m]) DP[b[i-m]-1] = a[i-m];
        }
        cout << ans << endl;
    }
    return 0;
}

H - Doing Homework again

HDU - 1789

上学期，江西师范新生赛见过这道题，当时排序是按的时间优先，后来看题解知道应该分数优先。这也是道贪心哦。

AC代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1005;
int a[10005];
struct node
{
    int sco, ded;
};
int cmp(node x, node y)
{
    if(x.sco == y.sco)
        return x.ded < y.ded;
    return x.sco > y.sco;
}
int main()
{
    int t, n;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            node f[maxn];
            scanf("%d",&n);
            for(int i = 0; i < n; ++i)
                scanf("%d",&f[i].ded);
            for(int i = 0; i < n; ++i)
                scanf("%d",&f[i].sco);
            sort(f, f+n, cmp);
            int ans = 0;
            memset(a, 0, sizeof(a));
            for(int i = 0; i < n; ++i)
            {
                int tem;
                for(tem = f[i].ded; tem > 0; --tem)
                {
                    if(a[tem] == 0)
                    {
                        a[tem] = 1;
                        break;
                    }
                }
                if(tem == 0)
                    ans += f[i].sco;
            }
            cout << ans << endl;
        }
    }
    return 0;
}

I - 敌兵布阵

HDU - 1166

这个以为是模拟，结果TLE，赛后得知要用线段树或树状数组，会了的话这就是道裸题。

【补】AC代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = 50010;
long long ans;
struct node
{
    int l, r;
    int sum;
} tree[MAX<<2];

void pushup(int rt)
{
    tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
}

void build(int l, int r, int rt)
{
    tree[rt].l = l;
    tree[rt].r = r;
    tree[rt].sum = 0;
    if(l == r) //叶子结点
    {
        scanf("%d",&tree[rt].sum);
        return ;
    }
    int mid = (l+r)>>1;
    //递归建树
    build(l, mid, rt<<1);
    build(mid+1, r, rt<<1|1);
    pushup(rt);
}

void update(int pos, int val, int rt)
{
    //更新这个区间的值
    if(tree[rt].l == tree[rt].r)
    {
        tree[rt].sum += val;
        return ;
    }
    int mid = (tree[rt].l+tree[rt].r)>>1;
    if(pos <= mid)
        update(pos, val, rt<<1);
    else
        update(pos, val, rt<<1|1);
    pushup(rt);
}

void query(int x, int y, int rt)
{
    if(x == tree[rt].l && y == tree[rt].r)
    {
        ans += tree[rt].sum;
        return ;
    }
    int mid = (tree[rt].l+tree[rt].r)>>1;
    if(y <= mid)
        query(x, y, rt<<1);
    else if(x > mid)
        query(x, y, rt<<1|1);
    else
    {
        query(x, mid, rt<<1);
        query(mid+1, y, rt<<1|1);
    }
}
int main()
{
    int T;
    int n, pos, val;
    string s;
    scanf("%d",&T);
    for(int cas = 1; cas <= T; ++cas)
    {
        printf("Case %d:\n",cas);
        scanf("%d",&n);
        build(1, n, 1);
        while(cin >> s)
        {
            if(s == "End") break;
            scanf("%d%d",&pos,&val);
            if(s == "Add")
            {
                update(pos, val, 1);
            }
            else if(s == "Sub")
            {
                update(pos, -val, 1);
            }
            else if(s == "Query")
            {
                ans = 0;
                int x = pos;
                int y = val;
                if(x > y) swap(x, y);
                query(x, y, 1);
                cout << ans << endl;
            }
        }
    }
    return 0;
}