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