网易互娱笔试2021批题解

总结:不给数据范围超级差评…

(待更)

T4

题目大意:a和b轮流出牌,打n轮。每一轮中你点数大分数+3平局分数+1,。给出了你手上有的手牌,以及b的出牌顺序。你要确定自己的出牌顺序,使得自己的总得分最大。牌面大小范围

[

3

,

13

]

[3,13]

[3,13]
数据范围未知。

有个十分显然的费用流模型…

将自己的手牌一列,对方的手牌一列,变成一个二分图模型…然后连

n

2

n^2

n2条边直接跑费用流即可。

有个显然的优化:还是二分图,每边放11个点,代表权值,然后连边方式类似,就能跑

n

=

1

e

6

n=1e6

n=1e6的数据范围了。

由于没有Java费用流板子…以下是从网上扒的板子

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class zbr01 {
static class InputReader
{
BufferedReader buf;
StringTokenizer tok;
InputReader()
{
buf = new BufferedReader(new InputStreamReader(System.in));
}
boolean hasNext()
{
while(tok == null || !tok.hasMoreElements())
{
try
{
tok = new StringTokenizer(buf.readLine());
}
catch(Exception e)
{
return false;
}
}
return true;
}
String next()
{
if(hasNext()) return tok.nextToken();
return null;
}
int nextInt()
{
return Integer.parseInt(next());
}
long nextLong()
{
return Long.parseLong(next());
}
double nextDouble()
{
return Double.parseDouble(next());
}
BigInteger nextBigInteger()
{
return new BigInteger(next());
}
BigDecimal nextBigDecimal()
{
return new BigDecimal(next());
}
}
static Queue<Integer> q;
static int n,m,con,start,end;
static int cost,minflow;
static int[]head ,dis, vis,belong_e , pre;
static class e{
int u,v,next,w, cost;
}static e[]es;
static void add(int u,int v,int w, int cost) {
if(es[con]==null) es[con]=new e();
es[con].cost=cost;es[con].v=v;es[con].w=w;es[con].next=head[u];head[u]=con++;
}
//这个本质也是dfs
//就是为了找一条从源点到汇点的最短路
static boolean spfa() {
for(int i=0;i<=2*n+3;i++) {
dis[i]=0x3f3f3f3f;
vis[i]=0;
}
dis[start]=0;vis[start]=1;
q.clear();q.add(start);
while(!q.isEmpty()) {
int u=q.poll();
vis[u]=0;
for(int i=head[u];i!=-1;i=es[i].next) {
int v=es[i].v;
if( es[i].w>0 && dis[v]> dis[u]+es[i].cost ) {
pre[v]=u;belong_e[v]=i;
dis[v]=dis[u]+es[i].cost;
if(vis[v]==0) {
q.add(v);
vis[v]=1;
}
}
}
}
return dis[end]<0x3f3f3f3f;
}

public static int a[]={8,7,5};
public static int b[]={7,4,9};

public static int wk(int a[],int b[])
{
InputReader sc=new InputReader();
head=new int[5005];
belong_e=new int[150000];
pre=new int[5005];
dis=new int[5005];
vis=new int[5005];
es=new e[150005];
q=new LinkedList<Integer>();

n=a.length;
start=2*n+1; end=2*n+2;

Arrays.fill(head, -1);con=0;

for(int i=0;i<n;i++) for(int j=0;j<n;j++)
{
if(a[i]>a[j])
{
add(i,n+j,1,-3);
add(n+j,i,0,3);
}

else if(a[i]==a[j])
{
add(i,n+j,1,-1);
add(n+j,i,0,1);
}

else
{
add(i,n+j,1,0);
add(n+j,i,0,0);
}
}

for(int i=0;i<n;i++)
{
add(start,i,1,0);
add(i,start,0,0);

add(n+i,end,1,0);
add(end,n+i,1,0);
}

cost=0;
minflow=0;
while(spfa())
{
int temp=0x3f3f3f3f;
for(int i=end;i!=start;i=pre[i]) {
temp=Math.min(temp, es[belong_e[i]].w);
}
cost+=dis[end]*temp;
minflow+=temp;
for(int i=end; i!=start; i=pre[i]) {
es[belong_e[i]].w-=temp;
es[belong_e[i] ^1 ].w+=temp;
}
}
return -cost;
}

public static void main(String[] args)
{
System.out.println(wk(a,b));
}
}


T3

题目大意:求

m

a

x

(

m

i

n

(

a

[

i

]

,

a

[

j

]

)

(

j

i

)

)

max( min(a[i],a[j])*(j-i) )

max(min(a[i],a[j])∗(j−i))

(

j

>

i

)

(j>i)

(j>i)
数据范围未知

二重循环可过?

import java.io.*;
import java.util.*;

public class zbr01
{
public static int mn[][]=new int[1005][1005];
public static int mx[][]=new int[1005][1005];
public static int a[]=new int[1000005];

public static int wk(int[] x)
{
int n=x.length;
for(int i=0;i<n;i++) a[i+1]=x[i];
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
int tmp=Math.min(a[i],a[j]);
tmp*=(j-i);
ans=Math.max(ans,tmp);
}
}

return ans;
}

public static void main(String args[])
{
Scanner S=new Scanner(System.in);
int []a={1,8,6,2,5,4,8,3,7};
System.out.println(wk(a));
}
}

T2

题目大意:

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

网易互娱笔试2021批题解

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 网易互娱笔试2021批题解
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏