08.12 网易互娱笔试
1 2 3 AC 第四题 写完没时间调了
第一题 模拟
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
int w[10],b[10],t[10];
int tb[6][9]={
{1,4,7,2,5,8,3,6,9},
{1,4,7,3,6,9,2,5,8},
{2,5,8,3,6,9,1,4,7},
{3,6,9,2,5,8,1,4,7},
{3,6,9,1,4,7,2,5,8},
{2,5,8,1,4,7,3,6,9}
};
int wcnt=0,bcnt=0,tcnt=0;
int read(){
char ch=getchar();int f=1,t=0;
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
return t*f;
}
int getType(int x){
if (x==1||x==4||x==7) return 1;
if (x==2||x==5||x==8) return 2;
if (x==3||x==6||x==9) return 3;
return 0;
}
bool judge(){
for (int i=0;i<=5;i++){
int cnt=0;
for (int j=0;j<=8;j++){
int x=tb[i][j];
if (j<=2){
if (w[x]) cnt++;
}else if (j<=5){
if (b[x]) cnt++;
}else{
if (t[x]) cnt++;
}
}
if (cnt>=7){
return true;
}
}
return false;
}
int main(){
int T=read();
while (T--){
bool pd=true;
wcnt=0,bcnt=0,tcnt=0;
memset(w,0,sizeof w);
memset(b,0,sizeof b);
memset(t,0,sizeof t);
for (int i=1;i<=7;i++){
int x;char c;
scanf("%d%c",&x,&c);
if (getType(x)==0) {
pd=false;
}
if (c=='W'){
wcnt++;
w[x]++;
}else if (c=='B'){
bcnt++;
b[x]++;
}else {
tcnt++;
t[x]++;
}
}
if (!judge()){
pd=false;
}
if (!pd){
printf("NO\n");
}else{
printf("YES\n");
}
}
}
第二题 链表暴力 #include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
struct Point{
int x,y;
Point* nex=NULL;
Point* bef=NULL;
};
Point* st,*ed;
Point* id[505][505];
int n,a[505][505],ind=0,sumX[505],sumY[505];
int recX[505],recY[505];
int read(){
char ch=getchar();int f=1,t=0;
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
return t*f;
}
bool del(Point* p){
if (p==NULL) return false;
Point* bf=p->bef;
Point* nx=p->nex;
if (bf!=NULL){
bf->nex=nx;
}
if (nx!=NULL){
nx->bef=bf;
}
p=NULL;
return true;
}
int main(){
n=read();
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
ind++;
Point* now=new Point();
now->x=i;
now->y=j;
if (ind==1){
now->bef=NULL;
now->nex=NULL;
st=now;
ed=now;
}else{
ed->nex=now;
now->bef=ed;
ed=now;
}
id[i][j]=now;
a[i][j]=read();
sumX[i]+=a[i][j];
sumY[j]+=a[i][j];
}
for (int round=1;round<=n;round++){
if (round==n){
printf("1 1\n");
break;
}
int ansX=0,ansY=0,mx=0;
Point * now=st;
while (now!=NULL){
int val =sumX[now->x]+sumY[now->y]-a[now->x][now->y];
if (mx<val){
mx = val;
ansX = now->x;
ansY = now->y;
}
now=now->nex;
}
recX[round]=ansX;
recY[round]=ansY;
int delX=0,delY=0;
for (int j=1;j<round;j++){
if (recX[j]<ansX) delX++;
if (recY[j]<ansY) delY++;
}
printf("%d %d\n",ansX-delX,ansY-delY);
for (int i=1;i<=n;i++){
int x=i,y=ansY;
if (del(id[x][y])){
sumX[x]-=a[x][y];
sumY[y]-=a[x][y];
id[x][y]=NULL;
}
x=ansX;y=i;
if (del(id[x][y])){
sumX[x]-=a[x][y];
sumY[y]-=a[x][y];
id[x][y]=NULL;
}
}
}
}
第三题 应该算是模拟吧... #include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long ll;
struct Node{
ll tm;
int id;
int state;
ll cnt;
}q[2000005];
int read(){
char ch=getchar();int f=1,t=0;
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
return t*f;
}
int main(){
int T=read();
while (T--){
int qnum=0;
int n=read();
ll mx=0;
int mxId=0;
for (int i=1;i<=n;i++){
ll t=(ll)read();
int id=read(),s=read();
qnum++;
q[qnum].tm=t;
q[qnum].id=id;
q[qnum].state=s;
q[qnum].cnt=0;
while (qnum>0&&q[qnum].state==1){
if (q[qnum-1].state==0){
ll val=q[qnum].tm-q[qnum-1].tm-q[qnum-1].cnt;
if (val>mx){
mx=val;
mxId=q[qnum].id;
}else if (val==mx){
if (q[qnum].id<mxId){
mx=val;
mxId=q[qnum].id;
}
}
ll cost=q[qnum].tm-q[qnum-1].tm;
qnum--;
qnum--;
if (qnum==0) continue;
if (q[qnum].state==0){
q[qnum].cnt+=cost;
}
}
}
}
printf("%d\n",mxId);
}
}
第四题我的思路是 对每个宝藏做最短路 然后每个时刻 主角每次循环都判断 判断脚下是否有宝藏 有就吃掉 判断距离哪个宝藏最小 判断4个方向往哪可以走 判断有没有走过重复的路 时间原因没法调试 也没有写判断是否走过重复的路
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
char mp[55][55];
int id[55][55],ind,n,m,treasureNum;
int d[6][4];
int posX[10],posY[10],hasGet[10];
int dis[10][55*55];
int q[6000],vis[6000],hasVis[6000];
int pd[55][55][5],stPosX,stPosY;
//void insert(int x,int y){
// tot++;
// go[tot]=y;
// next[tot]=first[x];
// first[x]=tot;
// val[tot]=1;
//}
int read(){
char ch=getchar();int f=1,t=0;
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
return t*f;
}
void bfs(int key,int tmpX,int tmpY){
int st=1;
int ed=1;
q[1]=id[tmpX][tmpY];
vis[key]=1;
for (int i=0;i<=ind;i++) vis[i]=0;
for (int i=0;i<=ind;i++) dis[key][i]=99999999;
dis[key][id[tmpX][tmpY]]=0;
while (st<=ed){
int now=q[st++];
int nowX=0,nowY=0;
if (now%m==0){
nowX=now/m;
nowY=m;
}else{
nowX=(now/m)+1;
nowY=(now%m);
}
for (int i=1;i<=4;i++){
int x=nowX+d[i][0],y=nowY+d[i][1];
int toId=id[x][y];
if (vis[toId]) continue;
if (!pd[nowX][nowY][i]) continue;
vis[toId]=1;
dis[key][id[x][y]]=dis[key][id[nowX][nowY]]+1;
ed++;
q[ed]=toId;
}
}
}
int main(){
d[1][0]=-1;
d[1][1]=0;
d[2][0]=1;
d[2][1]=0;
d[3][0]=0;
d[3][1]=-1;
d[4][0]=0;
d[4][1]=1;
int T=read();
while (T--){
n=read(),m=read();
treasureNum=0;
for (int i=0;i<=9;i++)
posX[i]=posY[i]=hasGet[i]=0;
ind=0;
for (int i=1;i<=n;i++){
scanf("%s",mp[i]+1);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
id[i][j]=++ind;
hasVis[ind]=0;
pd[i][j][0]=pd[i][j][1]=pd[i][j][2]=pd[i][j][3]=pd[i][j][4]=0;
if (mp[i][j]=='*'){
stPosX=i;
stPosY=j;
}
if (mp[i][j]<='9'&&mp[i][j]>='0'){
treasureNum++;
int num=mp[i][j]-'0';
posX[num]=i;
posY[num]=j;
}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
if (mp[i][j]=='#') continue;
for (int k=1;k<=4;k++){
int x=i+d[k][0],y=j+d[k][1];
if (x<1||y<1||x>n||y>m) continue;
if (mp[x][y]=='#') continue;
pd[i][j][k]=1;
}
}
for (int i=0;i<=9;i++){
if (posX[i]!=0&&posY[i]!=0){
bfs(i,posX[i],posY[i]);
}
}
int cnt=0;
while (treasureNum>0){
int mx=0,mxId=0;
if (mp[stPosX][stPosY]<='9'&&mp[stPosX][stPosY]>='0'){
treasureNum--;
for (int i=0;i<=9;i++){
if (stPosX==posX[i]&&stPosY==posY[i]){
hasGet[i]=1;
}
}
for (int i=0;i<=ind;i++) hasVis[i]=0;
if (treasureNum==0) break;
}
for (int i=0;i<=9;i++){
if (posX[i]!=0&&!hasGet[i]){
if (mx<std::abs(stPosX-posX[i])+std::abs(stPosY-posY[i])){
mx=std::abs(stPosX-posX[i])+std::abs(stPosY-posY[i]);
mxId=i;
}
}
}
bool step=false;
for (int i=1;i<=4;i++){
int x=stPosX+d[i][0],y=stPosY+d[i][1];
if (!pd[stPosX][stPosY][i]) continue;
if (dis[mxId][id[stPosX][stPosY]]>dis[mxId][id[x][y]]){
cnt++;
stPosX=x;
stPosY=y;
step=true;
break;
}
}
if (!step){
cnt=-1;
break;
}
}
printf("%d\n",cnt);
}
}
