Codeforces 976 正方格蛇形走位二维偏序包含区间度数图构造贪心心火牧最大dmg

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

int main()

{

        int n;

        cin >> n;

        string a;

        cin >> a;

        int one = ;

        int zero = ;

        for (int i = ; i < a.size(); i++)

        {

                if (a[i] == '')

                {

                        one++;

                }

                else

                {

                        zero++;

                }

        }

        while (one >= )

        {

                one--;

        }

        for (int i = ; i <= one; i++)

        {

                cout << ;

        }

        for (int i = ; i <= zero; i++)

        {

                cout << ;

        }

        cout << endl;

}

模拟题注意细节

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

int main()

{

        ll n, m, k;

        cin >> n >> m >> k;

        ll ansx, ansy;

        if (k <= n - )

        {

                cout << k +  << " " <<  << endl;

                return ;

        }

        if (k <= n + m - )

        {

                k -= n - ;

                cout << n << " " <<  + k << endl;

                return ;

        }

        k -= n + m - ;

        //cout << "k " << k << endl;

        ll duce = k / (m - );

        //cout << "duce " << duce << endl;

        int flag = ;

        if (1LL * duce * (m - ) == k)

        {

                flag = ;

        }

        ll cha;

        cha = k - 1LL * duce * (m - );

        //cout << "cha " << cha << endl;

        if (1LL * duce * (m - ) < k)

        {

                cha--;

                duce++;

        }

        //cout << "cha " << cha << endl;

        //cout << "duce " << duce << endl;

        ansy = n - duce;

        if ((duce + flag) % )

        {

                ansx = m - cha;

        }

        else

        {

                ansx =  + cha;

        }

        cout << ansy << " " << ansx << endl;

}

先按L坐标从小到大排 L相等的时候R也从小到大排

从1到N遍历

假设存在一对i,j符合条件(i<j)且i与j之间的与i不满足与j也不满足则[i].R>=[j].R 且 [k].R>=[i].R(i<k<j) 这样的话k与j也满足假设不成立

所以我们知道只要比较相邻的两项就可以了

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct node

{

        ll l, r;

        ll index;

} num[];

bool operator <(node x, node y)

{

        if (x.l == y.l)

        {

                return x.r < y.r;

        }

        return x.l < y.l;

}

int main()

{

        int n;

        cin >> n;

        for (int i = ; i <= n; i++)

        {

                cin >> num[i].l >> num[i].r;

                num[i].index = i;

        }

        sort(num + , num +  + n);

        for (int i = ; i <= n; i++)

        {

                if (num[i].l == num[i - ].l)

                {

                        cout << num[i - ].index << " " << num[i].index << endl;

                        return ;

                }

                if (num[i].r <= num[i - ].r)

                {

                        cout << num[i].index << " " << num[i - ].index << endl;

                        return ;

                }

        }

        cout << - << " " << - << endl;

}

给N(N<=300)个数 Di (di<=1000) 要求你构建出一个无向图使得图满足有Dn+1个节点这些节点的度数形成的集合为给你的数列

给你N,A,B N个生物每个生物有HP和DMG两个属性你可以进行A次操作每次使得一个生物的HP翻倍 B次操作每次使得一个生物的DMG=HP

问你最后这些生物最大的DMG和是多少

贪心枚举情况思考很容易可以想到A次操作要全部放在一个生物上施展接下来就是怎么用B和怎么算总DMG的问题了

计算CHA=HP-DMG B操作肯定是用在选择一个生物操作A后的前B大的非负CHA生物

有两种情况

1.当前选择操作A的生物是前B大的 2.当前选择操作A的不是前B大的

分类讨论就行了

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll sum = ;

ll ansernow;

ll anser = ;

ll add = ;

struct node

{

        ll hp;

        ll dmg;

        ll cha;

} crea[];

bool operator <(node a, node b)

{

        return a.cha > b.cha;

}

int main()

{

        ll n, a, b;

        cin >> n >> a >> b;

        b = min(b, n);

        for (int i = ; i <= n; i++)

        {

                cin >> crea[i].hp >> crea[i].dmg;

                sum += crea[i].dmg;

                crea[i].cha = crea[i].hp - crea[i].dmg;

        }

        sort(crea + , crea +  + n);

        if (b == )

        {

                cout << sum << endl;

                return ;

        }

        ll bi = crea[b].cha;

        for (int i = ; i <= b; i++)

        {

                //cout<<crea[i].cha<<" ";

                if (crea[i].cha > )

                {

                        add += crea[i].cha;

                }

        }

        //cout<<endl;

        //cout << "add:" << add << endl;

        anser = add + sum;

        if (a == )

        {

                cout << anser << endl;

                return ;

        }

        ll chanow;

        ll yuan;

        ll cnt;

        for(int i=;i<=b;i++)

        {

                ansernow=sum+add-max(0LL,crea[i].cha)+max(0LL,crea[i].hp*(1LL<<a)-crea[i].dmg);

                anser=max(anser,ansernow);

        }

        for (int i = b+; i <= n; i++)

        {

                ansernow=sum+add-max(0LL,crea[b].cha)+max(0LL,crea[i].hp*(1LL<<a)-crea[i].dmg);

                anser=max(anser,ansernow);

        }

        cout << anser << endl;

}

巴特西

Codeforces 976 正方格蛇形走位二维偏序包含区间度数图构造贪心心火牧最大dmg

最新文章

热门文章

巴特西

Codeforces 976 正方格蛇形走位 二维偏序包含区间 度数图构造 贪心心火牧最大dmg

最新文章

热门文章

Codeforces 976 正方格蛇形走位二维偏序包含区间度数图构造贪心心火牧最大dmg