@sensitive-cs 2017-03-03T22:41:55.000000Z 字数 4860 阅读 856

萌新集中营第一期

题解

VIRTUAL FRIENDS
题意：略
思路：并查集
坑坑坑：bob 和 Bob不是一个名字，开始用tolower函数，我脑袋卡了，题也是。。。记住这个惨痛的教训，不要意淫一些事情找事做QAQ
代码：

#include <stdio.h>
#include <string.h>
#include <map>
#include <string>
#include <ctype.h>
using namespace std;
map<string,int> mmp;
int par[200005];
int ran[200005];
int sum[200005];
int fin(int x)
{
    if (x == par[x])
        return x;
    else
        return par[x] = fin(par[x]);
}
void unit(int x,int y)
{
    int rx = fin(x);
    int ry = fin(y);
    if (rx == ry) return;
    if (ran[rx] < ran[ry])
    {
        par[rx] = ry;
        sum[ry] += sum[rx];
    }
    else
    {
        par[ry] = rx;
        sum[rx] += sum[ry];
        if (ran[rx] == ran[ry]) ran[rx]++;
    }
}
int main()
{
    int n;
    while (scanf("%d",&n) != EOF)
    {
        for (int l = 1;l <= n;l++)
        {
            int f;
            scanf("%d",&f);
            int k = 1;
            mmp.clear();
            memset(par,0,sizeof(par));
            memset(ran,0,sizeof(ran));
            memset(sum,0,sizeof(sum));
            for (int i = 1;i <= 200005;i++)
            {
                sum[i] = 1;
                par[i] = i;
            }
            for (int o = 1;o <= f;o++)
            {
                char a[25],b[25];
                scanf(" %s %s",a,b);
                if (!mmp[a])
                    mmp[a] = k++;
                if (!mmp[b])
                    mmp[b] = k++;
                int x = mmp[a],y = mmp[b];
                unit(x,y);
                int ans = 0;
                ans = fin(x);
                printf("%d\n",sum[ans]);
            }
        }
    }
    return 0;
}

BAD HAIR-DAY
题意：
有一群羊，每一只羊有一定的高度，每只羊向右看可以看到严格小于她高度的羊的头，问每只羊一共可以看到多少羊头。
思路：
可以转换为每只羊可以被多少只羊看到。我们用一个栈来记录，每次入栈一个数，把这个数跟栈中的每一个数进行比较，直到遇到比她大的数为止，整个栈就成了一个单调栈。通过例子可以很清晰的明白。比如栈中有10 5 4，那么进去7的话，栈中最后的情况就是10和7，因为7比5和4大，5和4被遮住，所以就可以直接把5和4出栈，因为他们看不到7以后的羊了。
坑！！！！：题目给出的范围是10的9次方，所以当时就没有注意和是可以超出整数范围的，所以要用long long。
代码：

#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
int a[80005];
stack<int> sta;
int main()
{
    int n;
    memset(a,0,sizeof(a));
    while (!sta.empty())
        sta.pop();
    scanf("%d",&n);
    for (int i = 1;i <= n;i++)
        scanf("%d",&a[i]);
    sta.push(a[1]);
    int pos = 2;
    long long ans = 0;
    while (pos <= n)
    {
        int t = a[pos];
        int in = sta.top();
        sta.pop();
        while (t >= in && !sta.empty())
        {
            in = sta.top();
            sta.pop();
        }
        if (t >= in)
        {
            sta.push(t);
            pos++;
            continue;
        }
        sta.push(in);
        ans += sta.size();
        sta.push(t);
        pos++;
    }
    printf("%I64d\n",ans);
    return 0;
}

SLIDING WINDOW
题意：中文题意。
思路：线段树水过
坑：以后交poj，再也不用g++了
代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int maxn[4000005];
int minn[4000005];
int a[1000005];
int ans[1000005][2];
int min(int a,int b)
{
    return a >= b ? b : a;
}
int max(int a,int b)
{
    return a >= b ? a : b;
}
void pushupa(int rt)
{
    maxn[rt] = max(maxn[rt << 1],maxn[rt << 1|1]);
}
void pushupi(int rt)
{
    minn[rt] = min(minn[rt << 1],minn[rt << 1|1]);
}
void builda(int l,int r,int rt)
{
    if (l == r)
    {
        maxn[rt] = a[l];
        return;
    }
    int m = (l+r) >> 1;
    builda(l,m,rt << 1);
    builda(m+1,r,rt << 1|1);
    pushupa(rt);
}
void buildi(int l,int r,int rt)
{
    if (l == r)
    {
        minn[rt] = a[l];
        return;
    }
    int m = (l+r) >> 1;
    buildi(l,m,rt << 1);
    buildi(m+1,r,rt << 1|1);
    pushupi(rt);
}
int querya(int ll,int rr,int l,int r,int rt)
{
    if (ll <= l && r <= rr)
    {
        return maxn[rt];
    }
    int m = (l+r) >> 1;
    int ans1 = -1000000000,ans2 = -1000000000;
    if (ll <= m) ans1 = querya(ll,rr,l,m,rt << 1);
    if (rr > m) ans2 = querya(ll,rr,m+1,r,rt << 1|1);
    return max(ans1,ans2);
}
int queryi(int ll,int rr,int l,int r,int rt)
{
    if (ll <= l && r <= rr)
    {
        return minn[rt];
    }
    int m = (l+r) >> 1;
    int ans1 = 1000000000,ans2 = 1000000000;
    if (ll <= m) ans1 = queryi(ll,rr,l,m,rt << 1);
    if (rr > m) ans2 = queryi(ll,rr,m+1,r,rt << 1|1);
    return min(ans1,ans2);
}
int main()
{
    int n,k;
    while (scanf("%d%d",&n,&k) != EOF)
    {
        memset(a,0,sizeof(a));
        memset(maxn,0,sizeof(maxn));
        memset(minn,0,sizeof(minn));
        memset(ans,0,sizeof(ans));
        for (int i = 1;i <= n;i++)
            scanf("%d",&a[i]);
        builda(1,n,1);
        buildi(1,n,1);
        for (int i = 1;i <= n-k+1;i++)
        {
            ans[i][0] = queryi(i,i+k-1,1,n,1);
            ans[i][1] = querya(i,i+k-1,1,n,1);
        }
        for (int i = 1;i <= n-k+1;i++)
            if (i == 1) printf("%d",ans[i][0]);
            else printf(" %d",ans[i][0]);
        printf("\n");
        for (int i = 1;i <= n-k+1;i++)
            if (i == 1) printf("%d",ans[i][1]);
            else printf(" %d",ans[i][1]);
        printf("\n");
    }
    return 0;
}

Sumsets
题意：
Given S, a set of integers, find the largest d such that a + b + c = d
where a, b, c, and d are distinct elements of S.
思路：
构造a+b，用二分，魔改pair，记录下标，因为数是不能重复的。
代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[1005];
typedef pair<int,int> p;
pair<p,int> pp[1000005];
int b[1000005];
bool cmp(pair<p,int> &a,pair<p,int> &b)
{
    return a.second < b.second;
}
int main()
{
    int n;
    while (scanf("%d",&n) == 1 && n)
    {
        memset(a,0,sizeof(a));
        memset(pp,0,sizeof(pp));
        memset(b,0,sizeof(b));
        for (int i = 0;i < n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        int sum = 0;
        for (int i = 0;i < n;i++)
            for (int j = 0;j < n;j++)
        {
            if (j == i) continue;
            pp[sum].second = a[i] + a[j];
            pp[sum].first.first = i;
            pp[sum].first.second = j;
            sum++;
        }
        sort(pp,pp+sum,cmp);
        for (int i = 0;i < sum;i++)
            b[i] = pp[i].second;
        int mark = -1;
        for (int i = n-1;i >= 0;i--)
        {
            for (int j = n - 1;j >= 0;j--)
            {
                if (j == i) continue;
                int *pos = NULL;
                int key = a[i] - a[j];
                pos = lower_bound(b,b+sum,key);
                int r = pos - b;
                if (*pos == key && pos != b+sum && pp[r].first.second != i && pp[r].first.first != j && pp[r].first.second != j && pp[r].first.first != i)
                {
                    mark = i;
                    break;
                }
            }
            if (mark != -1)
                break;
        }
        if (mark == -1) printf("no solution\n");
        else printf("%d\n",a[mark]);
    }
    return 0;
}

Stripies
题意：
n只变形虫，他们中的任意两只遇到后质量会变成2*(sqrt(m1*m2))，问n只变形虫最后的质量最小是多少。
思路：
先把质量最大的拉出来续了，因为的续一次质量就会减少，我们要让质量越大的被续的次数越多才行，直到最后剩一个。而最理想的数据结构呢，就是优先队列了哦。
代码：

#include <stdio.h>
#include <string.h>
#include <queue>
#include <cmath>
using namespace std;
priority_queue<double> pp;
int main()
{
    int n;
    while (~scanf("%d",&n))
    {
        while (!pp.empty()) pp.pop();
        for (int i = 1;i <= n;i++)
        {
            int t;
            scanf("%d",&t);
            pp.push(t);
        }
        while (pp.size() > 1)
        {
            double x = pp.top();
            pp.pop();
            double y = pp.top();
            pp.pop();
            double k = 2*sqrt(x*y);
            pp.push(k);
        }
        double ans = pp.top();
        printf("%.3f\n",ans);
    }
    return 0;
}

萌新集中营第一期

内容目录