Java教程

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

本文主要是介绍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

这篇关于2021“MINIEYE杯”中国大学生算法设计超级联赛 第九场题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航