2021“MINIEYE杯”中国大学生算法设计超级联赛 第九场题解

2021“MINIEYE杯”中国大学生算法设计超级联赛   第九场题解

前几场太拉胯了,也就偷懒不写题解了。(这回其实爆零了

7067 Just another board game

题意:
给你一个棋盘,对于每个坐标i,j对应一个数值a[i][j],两个人玩游戏。

规则如下:

先手方只能在当前行移动,他想要最终停下的值最大;

后手方只能在当前列移动,他想要最终停下的值最小;

任何一个人喊停 或者 达到了最大的轮次数量(题目上给的是K),游戏结束,当然那个值也就确定了。

然后询问给定n*m的棋盘上面的数字,再给定一个K(最大移动轮次),最终的值是多大?

假设他俩都以最优的方式进行移动。

一个人移动一次算1轮,也就是之后只剩下K - 1轮了。

思路:

一个很简单的贪心:

先手方需要值最大,那么他肯定移动当前行的最大值上面;

后手方需要值最小,那么他肯定移动当前列的最小值上面;

然后我们来讨论K这个值:

显然,K = 1的时候,先手肯定移动到当前行(第一行)的最大值,然后这个游戏就结束了

其次:

我们知道最终决定权(最后谁判定)在于K是奇数还是偶数:

因为K为奇数时:

先手最后一次移动,而且必定拿走当前行的最大值,这是肯定的,下面简单说明一下:

K为奇数,那么最终游戏结束前,一定是先手在移动的:

因为

如果不喊停,结束之前先手一定移动,那么拿走当前行最大值

如果先手喊停,一定是到达某一行的最大值处(不然他就可以移动到某一行的最大值处

如果后手喊停,也一定是到达某一行的最大值处(这时候先手已经移动完毕了

那么后手要使得这个值最小,他一定使得最终停在最大值最小的那一行上面

So:这样K为奇数的情况就有了

K为偶数时:

同样的,后手一定最后一次移动,而且必定拿走当前列的最小值,和上面的想法是完全一致的!

So:这样K为偶数的情况就是  最小值最大的那一列上面

注意特判!

最后还要和a[1][1]取最大值(因为最开始就在1,1处,先手可以直接拿走,结束游戏

番外一:比赛时只花了10分钟思考,第一发WA了就跑了,QAQ

最后拿两个数组记录一下 列的最小值和行的最大值即可QAQ

点击查看代码
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + 7;
const int inf = 1e9 + 7;
typedef long long ll;
inline int max(int x,int y)
{return x > y ? x : y;}
inline int min(int x,int y)
{return x < y ? x : y;}
int Mincol[MAXN];
int Maxrow[MAXN];
/*
1
2 2 3
4 2
2 3
*/
int main()
{
//    freopen("input.txt","r",stdin);
//    freopen("ans.out","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        ll k;
        scanf("%d %d %lld",&n,&m,&k);
        memset(Mincol,0x3f,sizeof Mincol);
        memset(Maxrow,0,sizeof Maxrow);
        int ans = 0;
        if(k == 1)
        {
            for(int i = 1;i <= n;++i)
            for(int j = 1;j <= m;++j)
            {
                int x;
                scanf("%d",&x);
                if(i == 1)
                ans = max(ans,x);
            }
        }
        else
        {
            int fir = 0;
            for(int i = 1;i <= n;++i)
            for(int j = 1;j <= m;++j)
            {
                int x;
                scanf("%d",&x);
                if(i == 1 && j == 1)    fir = x;
                Mincol[j] = min(Mincol[j],x);
                
                Maxrow[i] = max(Maxrow[i],x);
            }
            if(k&1)
            {
                ans = inf;
                for(int i = 1;i <= n;++i)
                ans = min(ans,Maxrow[i]);
                
                ans = max(ans,fir);
            }
            else
            {
                ans = -inf;
                for(int i = 1;i <= m;++i)
                ans = max(ans,Mincol[i]);
                
                ans = max(ans,fir);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

7068  Dota2 Pro Circuit

题意:

给定N支队伍,他们有起始分数Ai,以及比赛后会获得的分数Bi。

每一个Bi只能拿一次,要你求出最终N支队伍的最好和最坏的排名是多少。

思路:

对于 最好 排名:

对于任意一支队伍Ai起始分数,肯定拿走最大的Bk分数

然后判定可能在他前面的队伍数量

这些队伍的起始分数一定大于Ai,而且其中最小的起始分数Aj尽量拿走较大的Bh分数使得小于Ai + Bk

不然的话(如果最小的起始分数Aj,拿走最小的Bh分数还是大于Ai + Bk那么最好排名就是 j + 1

因此由于两个序列的单调性,我们使用双指针求出这个j + 1

具体做法是,A序列按照大到小排序

B序列按照大到小排序(题目已经排好

只分析最好情况,最坏情况类似:

对于任意一个Ai,能够排名超过它(Ai + B1)只能是 1 ~ i - 1的队伍

对于Ai - 1这支队伍,肯定优先从B2开始寻找Bk使得

  \[{A \left[ i \left] \text{ }+B \left[ 1 \left]  > =A \left[ i-1 \left] +B \left[ k \right] \right. \right. \right. \right. \right. \right. }\]

现在选的B一定不会影响之后的A进行选择。

证明:

因为当前Ai - 1 + Bk > Ai + B1的

那么由于A是递减有序的对于任意一个1 ~ i - 2的A,加上Bk也一定大于Ai + B1,也会抛弃这个Bk从而找后面的...

因此先拿走较大的B无后效性!

这样我们就可以通过双指针O(n)复杂度找出 j + 1 也即使当前队伍的最好排名。

点击查看代码
#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int MAXN = 5005;
int read()
{
    int x = 0,f = 1;
    char c = getchar();
    while(c > '9' || c < '0')    {if(c == '-')    f = -1;c = getchar();}
    while(c >= '0' && c <= '9')    {x = (x << 3) + (x << 1) + c - '0';c = getchar();}
    return x * f;
}
struct node{
    int dat;
    int idx;
}a[MAXN];
bool cmp(node a,node b)
{return a.dat > b.dat;}
int b[MAXN];
int ans[MAXN][2];
/*
1
3
1 1 1 
1 1 1
*/
unordered_map<int,int> mp[2];
bool cmp1(node a,node b)
{
    return a.idx < b.idx;
}
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("ans.out","w",stdout);
    int t = read();
    while(t--)
    {
        mp[0].clear();mp[1].clear();
        int n = read();
        for(int i = 1;i <= n;++i)    a[i].idx = i,a[i].dat = read();
        for(int i = 1;i <= n;++i)    b[i] = read();
        
        sort(a + 1,a + n + 1,cmp);
        for(int i = 1;i <= n;++i)
        {
            int le = i - 1,ri = 2;
            int now = a[i].dat + b[1];
            while(le >= 1 && ri <= n)
            {
                while(le >= 1 && ri <= n && a[le].dat + b[ri] > now)
                ++ri;
                if(ri > n)    break;
                --le,++ri;
                if(le < 1)    break;
            }
            ans[a[i].idx][0] = le + 1;
            if(mp[0].count(a[i].dat) == 0)    mp[0][a[i].dat] = le + 1;
            mp[0][a[i].dat] = min(mp[0][a[i].dat],le + 1);
            
            le = i + 1,ri = n - 1;
            now = a[i].dat + b[n];
            while(le <= n && ri >= 1)
            {
                while(le <= n && ri >= 1 && a[le].dat + b[ri] <= now)
                --ri;
                if(ri < 1)    break;
                ++le,--ri;
                if(le > n)    break;
            }
            ans[a[i].idx][1] = le - 1;
            if(mp[1].count(a[i].dat) == 0)    mp[1][a[i].dat] = le - 1;
            mp[1][a[i].dat] = min(mp[1][a[i].dat],le - 1);
        }
        sort(a + 1,a + n + 1,cmp1);
        for(int i = 1;i <= n;++i)
        printf("%d %d\n",mp[0][a[i].dat],mp[1][a[i].dat]);
    }
    return 0;
}

这里使用map存是因为对于同一为Ai的队伍,他们的值应该都是相同的!

番外二:不想离散化

未完待续....11:30:50

上一篇:与Java中的@Override相反的标记


下一篇:[Python学习笔记-002] lambda, map, filter and reduce