论如何让AC代码爆0(然后被CY老师罚款)


T1:frog

题意:

有一个点坐标在实数范围内的凸多边形,有一只青蛙从一号顶点开始跳,每次可以从任意一个顶点跳到任意一个顶点。求这只青蛙不重复遍历多边形的每个顶点的最少跳跃距离和。节点数小于等于720(其实100000+也可以做)

思路:

我们需要脑补一个贪心思路:只有如图的4种遍历方式可能达到最优解:



所以我们可以提前算出从1号节点相邻的两个点分别顺时针和逆时针遍历到每个点的距离,就可以O(n)获得答案。但是这种方法只适用于凸多边形(所以可以通过此题),凹多边形只能用动态规划,详见其他人的题解。本人无能写出那种高深的算法。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>

#define MX 800

using namespace std;

typedef struct pot{double x,y;}pset;
pset p[MX];
int n;

double dist(pset a,pset b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

void cat()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
}

double go1[MX][MX],go2[MX][MX];
void dog()
{
    double dis1,dis2;
    int i=1;
    {
        dis1=dis2=0;
        for(int j=i+1;j<=i+n-2;j++)
        {
            dis1+=dist(p[(j-1)%n+1],p[(j+1-1)%n+1]);
            go1[i][(j+1-1)%n+1]=dis1;
        }
        for(int j=i+n-1;j>=i+2;j--)
        {
            dis2+=dist(p[(j-1)%n+1],p[(j-1-1)%n+1]);
            go2[i][(j-1-1)%n+1]=dis2;
        }
    }
}

void frog()
{
    double mndis=9999999999;
    int i=1;
    for(int j=i+1;j<=i+n-2;j++)
        mndis=min(0.0+dist(p[i],p[(i+1-1)%n+1])+go1[i][(j-1)%n+1]+dist(p[(j-1)%n+1],p[(i+n-1-1)%n+1])+go2[i][(j+1-1)%n+1],mndis);
    for(int j=i+2;j<=i+n-1;j++)
        mndis=min(0.0+dist(p[i],p[(i+n-1-1)%n+1])+go2[i][(j-1)%n+1]+dist(p[(j-1)%n+1],p[(i+1-1)%n+1])+go1[i][(j+n-1-1)%n+1],mndis);
    printf("%.3lf\n",mndis);
}

int main()
{
    freopen("frog.in","r",stdin);
    freopen("frog.out","w",stdout);
    cat();
    dog();
    frog();
    return 0;
}

*


*

T2:security

题意:

给定一棵树,每个节点i可以花wi元安排守卫,守卫可以守护节点i和i的相邻节点。求守卫整棵树的最小花费。

思路:

多么水的一道树形Dp,而我却爆0,原因很简单:没有开文件。否则这道题就是100。说说思路:令f[x][0]表示x节点所在的子树中,x节点安排守卫的最少花费;f[x][1]表示x被自己的 一个或多个儿子看到的最少花费 ,f[x][2]表示x被自己的爸爸看到的最少花费。
那么这里会有很多转移过程:(y∈x.son)

\begin{equation}
f[x][0]=min(\sum{f[y][0] or f[y][1] or f[y][2]})
\end{equation}
\begin{equation}
f[x][1]=min(\sum{f[y][0] or f[y][1]})
\end{equation}
\begin{equation}
f[x][2]=min(\sum{f[y][0] or f[y][1]})
\end{equation}

其中如果第二个转移中所有子树都选择了f[y][1],那么必须选出一个子树变为f[y][0],否则x节点就没有被任何一个子树看到。

然后我们只要确保了每个状态都正确转移就可以得到一个均摊复杂度O(n)的算法。
(你看头文件多美)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define MX 1000
#define oo 100000000090

using namespace std;

int fst[MX],nxt[MX*2],v[MX*2],w[MX];
int lnum,n;

void addeg(int nu,int nv)
{
    lnum++;
    nxt[lnum]=fst[nu];
    fst[nu]=lnum;
    v[lnum]=nv;
}

void input()
{
    freopen("security.in","r",stdin);
    freopen("security.out","w",stdout);
    int t;
    int a,b,c;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        w[a]=b;
        for(int j=1;j<=c;j++)
        {
            scanf("%d",&b);
            addeg(a,b);
            addeg(b,a);
        }
    }
}

long long f[MX][3];
void sch(int x,int fa)
{
    f[x][0]=w[x];
    f[x][1]=0;
    f[x][2]=0;
    int flg=0,t=0,fls=0;f[v[t]][0]=+oo;             //flg用于记录节点是否是叶子,fls记录转移2中是否有一个子树看到了x
    for(int i=fst[x];i;i=nxt[i])
    {
        if(v[i]==fa)continue;
        flg=1;
        sch(v[i],x);
        f[x][0]+=min(min(f[v[i]][0],f[v[i]][1]),f[v[i]][2]);
        if(f[v[i]][0]-f[v[i]][1]<f[v[t]][0]-f[v[t]][1])t=i; //先找出转移2中如果要替换一棵子树,替换谁
        f[x][2]+=min(f[v[i]][0],f[v[i]][1]);
    }
    for(int i=fst[x];i;i=nxt[i])if(v[i]!=fa)f[x][1]+=f[v[i]][1];    //先全部从f[son][1]转移
    fls=0;
    for(int i=fst[x];i;i=nxt[i])                    //将f[y][0]更优的替换为f[y][0]
        if(v[i]!=fa&&f[v[i]][0]<f[v[i]][1])
            f[x][1]+=f[v[i]][0]-f[v[i]][1],fls=1;
    if(!fls)f[x][1]+=f[v[t]][0]-f[v[t]][1];         //如果没有一个替换为f[y][0],则强制替换之前找出的哪一个
    if(flg==0)f[x][1]=+oo;
}

int main()
{
    input();
    sch(1,0);
    cout<<min(f[1][0],f[1][1])<<endl;
    return 0;
}

*


*

T3:LIS

题意:

求一个序列包含第k个元素的最长上升子序列

思路:

只需要把k之前的数列抠出来,把新数列中大于等于a[k]的元素删去,再把k之后的数列抠出来,删去小于等于a[k]的元素。分别对两个新序列做O(nlogn)的高速LIS结果相加再加一就是答案。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define MX 200000

using namespace std;

int src[MX+1],n,k;
int s1[MX+1],s2[MX+1],l1,l2;

int mp[MX*20+1];
int lis(int a[MX+1],int len)
{
    int pos,mxpos=0;
    memset(mp,0x4f,sizeof(mp));
    for(int i=1;i<=len;i++)
    {
        pos=lower_bound(mp+1,mp+len+1,a[i])-mp;
        mxpos=max(mxpos,pos);
        mp[pos]=a[i];
    }
    return mxpos;
}

void input()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&src[i]);
    for(int i=1;i<k;i++)if(src[i]<src[k])s1[++l1]=src[i];
    for(int i=k+1;i<=n;i++)if(src[i]>src[k])s2[++l2]=src[i];
}

int main()
{
    freopen("lis.in","r",stdin);
    freopen("lis.out","w",stdout);
    input();
    cout<<lis(s1,l1)+1+lis(s2,l2)<<endl;
    return 0;
}

*


*

T4:palindrome(回文串)

题意:

给定一个字符串,求最少插入几个字母可以获得一个正规的回文串?

思路:

我唯一有把握AC的题,却因为开小了数组挂了(fuck-fuck-fuck-shit)。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define MX 5005

using namespace std;

char str[MX];
int f[MX][MX],n;

int main()
{
    freopen("palindrome.in","r",stdin);
    freopen("palindrome.out","w",stdout);
    scanf("%d",&n);
    scanf("%s",str+1);
    memset(f,0x4f,sizeof(f));
    for(int i=1;i<=n;i++)f[i][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j+i<=n;j++)
        {
            if(str[j]==str[j+i]&&i>=2)f[j][i]=min(f[j][i],f[j+1][i-2]);
            if(str[j]==str[j+i]&&i==1)f[j][i]=0;
            f[j][i]=min(f[j][i],min(f[j][i-1]+1,f[j+1][i-1]+1));
        }
    }
    cout<<f[1][n-1]<<endl;
    return 0;
}

*


*


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *