topcoder SRM 602 Div1 250+550

250:TypoCoder

题面:

给出给出一些比赛,每次比赛你可以使自己的分数加上比赛分数或者减去比赛分数,然后你不能连续两回合高于2200分,然后问你你最后有多少次再2200分上下波动(由下到上或者相反)

分析:

我们发现如果我们要在中间进行升阶操作,那么我们必须再下一次进行降阶操作所以我们只要维护到了每一位分数为2200以下的每一种取法的答案,然后最后选取停在2200上或者下方的答案就好了…

代码:

int siz;
map<LL,int> Map[55];
int TypoCoderDiv1::getmax(vector <int> D, int X) 
{
    int ret=0;
    siz=D.size();
    for(int i=0;i<=siz;i++) Map[i].clear();
    Map[0][X]=0;
    for(int i=0;i<siz;i++)
    {
        for(auto v:Map[i])
        {
            if(v.fi+D[i]<2200)
                Map[i+1][v.fi+D[i]]=v.se;
            Map[i+1][max(0LL,v.fi-D[i])]=max(Map[i+1][max(0LL,v.fi-D[i])],v.se);
        }
        if(i-1>=0)
        {
            int tag=D[i-1]-D[i];
            for(auto v:Map[i-1])
                if(v.fi+D[i-1]>=2200&&v.fi+tag<2200)
                    Map[i+1][max(0LL,v.fi+tag)]=max(Map[i+1][max(0LL,v.fi+tag)],v.se+2);
        }
    }
    for(auto v:Map[siz]) ret=max(ret,v.se);
    for(auto v:Map[siz-1]) 
        if(v.fi+D[siz-1]>=2200)
            ret=max(ret,v.se+1);
    return ret;
}

550:PilingRects

题面:

给出一些矩形,然后让你分成两组,然后让你求出两边矩阵的最大重合面积之和(要所有都重合…)

分析:

我们直接按照矩阵小的那一维排序,然后已知最小的长是一定的我们只要枚举另一遍最小的长,然后维护两边的高…

代码:

P node[N];
multiset<LL> st1,st2;
long long PilingRectsDiv1::getmax(int n, vector <int> XS, vector <int> YS, int XA, int XB, int XC, int YA, int YB, int YC) 
{
    LL ret=0;
    for (int i = 0; i < XS.size(); i++) 
        node[i].fi = XS[i],node[i].se = YS[i];
    for (int i = XS.size(); i < 2 * n; i++) 
        node[i].fi = (node[i - 1].fi * XA * 1LL + 1LL * XB) % XC + 1, node[i].se = (node[i - 1].se * YA * 1LL + 1LL * YB) % YC + 1;
    for (int i = n * 2; i >=1; i--)
    {
        if(node[i-1].fi>node[i-1].se)
            swap(node[i-1].fi,node[i-1].se);
        node[i]=node[i-1];
    }
    sort(node+1,node+n*2+1);
    st1.clear();st2.clear();
    for(int i=1;i<=n;i++) st1.insert(node[i].se),st2.insert(node[i+n].se);
    for(int i=n;i;i--)
    {
        ret=max(ret,node[1].fi * (*st1.begin()) + node[i+1].fi * (*st2.begin()));
        st1.erase(st1.find(node[i].se)); st1.insert(*st2.begin());
        st2.erase(st2.begin()); st2.insert(node[i].se);
    }
    st1.clear();st2.clear();
    for(int i=1;i<=n;i++) st1.insert(node[i].se),st2.insert(node[i+n].se);
    for(int i=n;i;i--)
    {
        ret=max(ret,node[1].fi * (*st1.begin()) + node[i+1].fi * (*st2.begin()));
        st1.erase(st1.find(node[i].se));
        st1.insert(*(--st2.end()));
        st2.erase((--st2.end()));
        st2.insert(node[i].se);
    }
    return ret;
}

发表评论

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