首页 > 代码库 > CUGBACM Codeforces Tranning 2 题解

CUGBACM Codeforces Tranning 2 题解

2024-07-31 23:08:22   223人阅读

链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=62027#overview

描述：现场过了四道，最后一题模拟退火。

题解：

A.Chat Server‘s Outgoing Traffic

题意：一个聊天室，每次操作有三种选择，第一种是有人进入，第二种有人出去，第三种有人发言，每次发言产生一定影响，影响为人数*字数，问总价值多少。

思路：水，模拟即可。

代码：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 10005
#define PI acos(-1.0)
#define seed 31//131,1313
//#define LOCAL
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    #endif
    int ans = 0,recent = 0;
    char ss[105];
    while(gets(ss))
    {
        if(ss[0]=='+')
            recent ++;
        else if(ss[0]=='-')
            recent --;
        else
        {
            int len=strlen(ss);
            int pos = -1;
            for(int i=0;i<len;i++)
            {
                if(ss[i]==':')
                    pos = i;
            }
            ans += recent * (len-pos-1);
        }
    }
    printf("%d\n",ans);
    return 0;
}
B.Center Alignment

题意：给N行字符串，要求用婊起来（233

思路：还是模拟，如果某行字符串左右空格数不一致，先左边少一个。对了，第一发没把LOCAL注释掉，很，b的WA的了1发

代码：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 10005
#define PI acos(-1.0)
#define seed 31//131,1313
//#define LOCAL
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    #endif
    int top = 0;
    char ss[1005][1005];
    int len[1005];
    int M_len = 0;
    while(gets(ss[top++]))
    {
        len[top-1]=strlen(ss[top-1]);
        if(len[top-1]>M_len)
            M_len=len[top-1];
    }
    top--;
    for(int i=0;i<M_len+2;i++)
        putchar('*');
    puts("");
    bool flag = 0;
    for(int i=0;i<top;i++)
    {
        int sub1,sub2;
        putchar('*');
        if((M_len-len[i])%2==0)
        {
            sub1=(M_len-len[i])/2;
            sub2=(M_len-len[i])/2;
        }
        else
        {
            if(flag == 0)
            {
                sub1 = (M_len-len[i])/2;
                sub2 = M_len-len[i]-sub1;
                flag = 1;
            }
            else
            {
                sub2 = (M_len-len[i])/2;
                sub1 = M_len-len[i]-sub2;
                flag = 0;
            }
        }
        for(int j=0;j<sub1;j++)
            putchar(' ');
        printf("%s",ss[i]);
        for(int j=0;j<sub2;j++)
            putchar(' ');
        putchar('*');
        puts("");
    }
        for(int i=0;i<M_len+2;i++)
        putchar('*');
    return 0;
}
C.Mysterious Present

题意：有若干个信封和一个卡片，卡片或信封能放入另一个信封里的条件是卡片或信封的长宽严格小于另一个信封的长宽。问最多可以用到多少信封。

思路：最长上升子序列，先按长排序，然后从大到小对于每个信封找到放入哪个比他大的信封能使他的外套最多，并且记录路径。

代码：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 10005
#define PI acos(-1.0)
#define seed 31//131,1313
//#define LOCAL
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
struct Bag
{
    int x,y,num;
} bag[5005];
bool cmp(Bag a,Bag b)
{
    return a.x<b.x;
}
int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    int tot,x,y;
    int from[5005],t[5005];
    scanf("%d%d%d",&tot,&x,&y);
    for(int i=0; i<tot; i++)
    {
        scanf("%d%d",&bag[i].x,&bag[i].y);
        bag[i].num = i;
    }
    sort(bag,bag+tot,cmp);
//    for(int i=0;i<tot;i++)
//        cout<<bag[i].x<<" "<<bag[i].y<<" "<<bag[i].num<<endl;
    for(int i=tot-1; i>=0; i--)
    {
        t[i]=1;
        from[i]=i;
        for(int j=i+1; j<tot; j++)
        {
            if(bag[i].x<bag[j].x&&bag[i].y<bag[j].y&&t[j]+1>t[i])
            {
                t[i]=t[j]+1;
                from[i]=j;
            }
        }
    }
    int head = -1,m = 0;
    for(int i=0; i<tot; i++)
    {
        if(bag[i].x>x&&bag[i].y>y&&t[i]>m)
        {
            m=t[i];
            head=i;
        }
    }
    printf("%d\n",m);
    if(m!=0)
    {
        while(from[head]!=head)
        {
            printf("%d ",bag[head].num+1);
            head=from[head];
        }
        printf("%d",bag[head].num+1);
        printf("\n");
    }
    return 0;
}


D.Lorry

题意：给出两种若干条救生船，第一种救生船体积是一单位，第二种是两单位，每艘船有各自能容纳的人数，现给定体积，问最多能容纳多少人。

思路：贪心，两种情况，一种是第一种救生船只剩一艘，那么只要第二种能容纳的比该艘多，那么就不断的选第二种，否则选第一种。另一种是如果第一种容纳最多的船和容纳次多的船的容纳人数之和大于第二种容纳最多的，选第一种，否则选第二种。

代码：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 10005
#define PI acos(-1.0)
#define seed 31//131,1313
//#define LOCAL
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
struct Bag
{
    int ca;
    int num;
} ta[100005],tb[100005];
bool cmp(Bag a,Bag b)
{
    return a.ca>b.ca;
}
int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    int a,v;
    scanf("%d%d",&a,&v);
    int topa = 0 , topb = 0;
    for(int i=1; i<=a; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==2)
        {
            ta[topa].num=i;
            ta[topa++].ca=y;

        }
        else
        {
            tb[topb].num=i;
            tb[topb++].ca=y;
        }
    }
    sort(ta,ta+topa,cmp);
    sort(tb,tb+topb,cmp);
    int posa = 0 , posb = 0 ;
    int now = 0;
    int ans = 0;
    if(topa*2+topb<=v)
    {
        for(int i=0; i<topa; i++)
            ans+=ta[i].ca;
        for(int i=0; i<topb; i++)
            ans+=tb[i].ca;
        printf("%d\n",ans);
        bool flag3 = 0;
        for(int i=0;i<topa;i++)
            {
                if(flag3 == 0)
                {
                    printf("%d",ta[i].num);
                    flag3 = 1;
                }
                else printf(" %d",ta[i].num);
            }
            for(int i=0;i<topb;i++)
            {
                if(flag3 == 0)
                {
                    printf("%d",tb[i].num);
                    flag3 = 1;
                }
                else printf(" %d",tb[i].num);
            }
            printf("\n");
    }
    else
    {
        while((topa>posa&&topb>posb)&&(v-now>=2))
        {
            if(posb==topb-1)
            {
                while(v-now>=2&&ta[posa].ca>tb[posb].ca&&posa<topa)
                {
                    ans+=ta[posa].ca;
                    posa++;
                    now+=2;
                }
                if(v-now>=1)
                {
                    ans+=tb[posb].ca;
                    posb++;
                    now++;
                }
            }
            else
            {
                if(tb[posb].ca+tb[posb+1].ca>=ta[posa].ca)
                {
                    ans+=tb[posb].ca;
                    posb++;
                    now++;
                }
                else
                {
                    ans+=ta[posa].ca;
                    posa++;
                    now+=2;
                }
            }
        }
        while(topa>posa&&v-now>=2)
        {
            ans+=ta[posa].ca;
            posa++;
            now+=2;
        }
        while(topb>posb&&v-now>=1)
        {
            ans+=tb[posb].ca;
            posb++;
            now++;
        }
        if(v-now==1)
        {
            if(posb<topb)
            {
                now++;
                ans+=tb[posb].ca;
                posb++;
            }
        }
        //cout<<posa<<" "<<posb<<endl;
        printf("%d\n",ans);
        bool flag = 0;
        for(int i=0;i<posa;i++)
        {
            //cout<<i<<"->";
            if(flag == 0)
            {
                printf("%d",ta[i].num);
                flag = 1;
            }
            else printf(" %d",ta[i].num);
        }
        for(int i=0;i<posb;i++)
        {
            //cout<<i<<"->";
            if(flag == 0)
            {
                printf("%d",tb[i].num);
                flag = 1;
            }
            else printf(" %d",tb[i].num);
        }
        printf("\n");
    }
    return 0;
}
E.Commentator problem

题意：给出三个圆，要找一个点，要求这个点对于三个圆的视角大小是相同的。

思路：模拟退火，现学的。很好理解，现在三个三角形“外接矩形”里随便找若干个点，dist定为矩形的长，然后不断缩小dist，同时每次在每个点周围再次找若干个点，同时找到一个参考值，用来表示这个点符合要求的程度，如果参考值比当前点参考值小，就用这个店取代当前点。参考了芳哥的思路，

但是有小问题，导致“随机算法小概率得到正确答案”，就改了一下参考值，改为：Σdis(aa,edge[i])/edge[i].r-dis(aa,edge[(i+1)%3])/edge[(i+1)%3].r)，减少误差，并且改了最后的判断条件。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#include <ctime>
#define PI acos(-1.0)
#define maxn 10005
#define INF 0x7fffffff
#define eps 1e-6
typedef long long LL;
using namespace std;
struct point
{
    double x,y,r;
    point(){}
    point(double _x,double _y):x(_x),y(_y) {}
    double val;
};
double dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
point a[25];
point edge[5];
double get_val(point aa)
{
    double s[5],sum = 0 ;
    for(int i=0; i<3; i++)
    {
        s[i]=(dis(aa,edge[i])/edge[i].r-dis(aa,edge[(i+1)%3])/edge[(i+1)%3].r);//判断符合值
        s[i]=s[i]*s[i];
        sum+=s[i];
    }
    return sum ;
}
point rand_point(point aa,point bb)//随机取点
{
    double x = aa.x+(bb.x-aa.x)*((double)(rand()%10001)/10000.0);
    double y = aa.y+(bb.y-aa.y)*((double)(rand()%10001)/10000.0);
    point tmp=point(x,y);
    tmp.val=get_val(tmp);
    return tmp;
}
int main()
{
    srand(time(0));
    point ld,ru;
    ld=point(INF,INF);
    ru=point(-INF,-INF);
    for(int i=0; i<3; i++)
    {
        scanf("%lf%lf%lf",&edge[i].x,&edge[i].y,&edge[i].r);
        ld.x=min(ld.x,edge[i].x);
        ld.y=min(ld.y,edge[i].y);
        ru.x=max(ru.x,edge[i].x);
        ru.y=max(ru.y,edge[i].y);
    }
    double dist = max(ru.x-ld.x,ru.y-ld.y);
    for(int i=0; i<20; i++)
        a[i]=rand_point(ld,ru);
    while(dist > 0.0001)//不断缩小每个点的周围点
    {
        for(int i=0; i<20; i++)
        {
            for(int j=0; j<20; j++)
            {
                point tmp;
                point L,R;
                L=point(max(ld.x,a[i].x-dist),max(ld.y,a[i].y-dist));
                R=point(min(ru.x,a[i].x+dist),min(ru.y,a[i].y+dist));
                tmp=rand_point(L,R);
                if(tmp.val<a[i].val)
                    a[i]=tmp;
            }
        }
        dist *= 0.9;
    }
    point ans;
    double ss=0;
    ans.val = INF;
    for(int i=0; i<20; i++)
    {
        double rec=edge[0].val/(dis(edge[0],a[i]));
        if(a[i].val<=ans.val&&rec>=ss||(a[i].val<eps&&rec>=ss))
        {
            ans=a[i];
            ss=rec;
        }
    }
    if(ans.val<eps)
        printf("%.5lf %.5lf\n",ans.x,ans.y);
    return 0;
}


CUGBACM Codeforces Tranning 2 题解


联系
我们