头像

wuwendongxi

干啥啥不行,颓废第一名




离线:26天前


新鲜事 原文

wuwendongxi
3个月前
祝RP++


新鲜事 原文

wuwendongxi
4个月前
连以前写了题解的题目都看不到了


新鲜事 原文

wuwendongxi
4个月前
差评、acwing不报名不给题


新鲜事 原文

wuwendongxi
4个月前
虽然已经过了,但还是来存个图
图片


新鲜事 原文

wuwendongxi
5个月前
之前好像问了一个问题,dp和搜索能否互换 [链接](https://www.acwing.com/file_system/file/content/whole/index/content/1117315/) 记得当时想了很久 后来突然想到这俩最大的一个差别:一个枚举所有方案,一个只求方案数 真是学数据结构学傻了。。。


新鲜事 原文

wuwendongxi
6个月前
问答有没有人来看看啊(`Δ´)!



wuwendongxi
6个月前

萌新刚学左偏树(可并堆)
网上找了几个板子
板子马蜂都很好,但有点小问题求dalao解答

int merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(a[x].val>a[y].val||(a[x].val==a[y].val&&x>y)) swap(x,y);//************************
    a[x].right=merge(a[x].right,y);
    if(a[a[x].left].dis<a[a[x].right].dis) swap(a[x].left,a[x].right);
    fa[a[x].left]=fa[a[x].right]=fa[x]=x; a[x].dis=a[a[x].right].dis+1;
    return x;
}

merge函数,合并操作;
从操作原理来看,标记的那一行写成:if(a[x].val>a[y].val) swap(x,y);也是对的(堆操作)
并且提交也是满分
有点不解代码都是对的,但为什么所有板子(看到的)都要加(a[x].val==a[y].val&&x>y)
或者说加了有什么优点?
时间更优?还是?



新鲜事 原文

wuwendongxi
6个月前
怀恋前右下角绿色小窗口~


问题 DP VS 搜索

wuwendongxi
7个月前

一个奇异的问题(突然想到来着):

DP和搜索思想差别是什么(尤其宽搜)?

不也是枚举出了每时刻每种情况然后向后推?

蒟蒻对DP和搜索的错误理解望指出


那么有一个拓展的问题:

DP所用空间内存相较搜索更优?能否把关于DP的优化运用到搜索?

此处问题可能比较奇异,大佬勿嘲,望解答


那么有了第二个拓展的问题:

在内存允许的情况下,普通DP能否用搜索代替? 优化后的DP能否用搜索代替?




wuwendongxi
7个月前

毒瘤大模拟没有人来玩呢。。。已自毙

其实我只是想让看到的朋友帮我找找错(虽然应该没人想看毒瘤题,但还是来发一发)

不带算法,小白都能做的简单题,做完它,得满分,你将体验升华的美妙感觉

这里给一份对2/20的我的lj原创代码(在题目下面),欢迎找错,欢迎挑战,自闭不负责,想提交的也可以发给我,这里还附一个大样例详情请点击: https://pan.baidu.com/s/1Moagud3g3KhR224mThR3_g

提取码:vq9i

这可是算法竞赛的某作者出的题

【NOIP2016模拟3】战棋游戏

Description

Rainbow擅长玩战棋类游戏。著名的战棋游戏有很多,例如《曹操传》、《瓦岗山异闻录》等。在本题中,我们考虑战棋游戏的一个简单版本,基于以下规则:
  地图
  地图是一个N行M列的矩阵,矩阵中的不同位置有不同的地形,例如平原、树林、山地、河流、雪原等。在这里,我们给矩阵中的每个位置规定一个正整数,这个整数会对在矩阵中的移动产生影响。
  角色
  每个角色均可被视作位于矩阵中某个位置上的人物。每个角色具有生命值HP, 攻击力AT, 移动力MV和攻击范围[AD1 AD2]。角色被分为两个阵营,第0阵营被玩家控制,第1阵营被系统控制。
  当两个不同阵营的角色p和q的曼哈顿距离处于p的攻击范围内(包含端点)时,p可以攻击q。若q被p攻击,则q的生命值被减去p的攻击力。当一个角色的生命值<=0时,它将立即被移除出地图,离开游戏。
  每个角色均占领地图上的一个位置,并且可以在地图上移动,遵循以下规则:
  占领
  最初,每个角色在地图的不同位置生成。他们各自占领自己所在的位置。当一个角色在移动时,其它角色均不能移动。
  一个角色开始移动前失去对所在位置的占领权,停止移动时获得所在位置的占领权。
  “移动”与“步”
  一次移动由若干步组成。在每一步中,一个角色可以从当前位置走向四个方向上相邻的位置,但不能走到被其它角色占领的位置上。
  当一个角色从i,j 走到x,y 时, 它的移动力会被扣除Gx,y。使得移动力变为负数的“步”是不合法的。在合法的一“步”完成后,若该角色正处于与对方阵营某个角色相邻(四个方向)的位置上,则该角色的移动力立即被减为0,换句话说,他将不能再走另外一步。
  当一次“移动”结束后,角色的移动力恢复为初始值。
  能被一个角色通过若干合法“步”到达的位置集合称为该角色的移动范围。停留在原地也是合法的,故也被算入移动范围。
  游戏的过程由若干轮组成,每轮玩家阵营先行动,系统阵营后行动。对于每个阵营,该阵营的所有角色轮流行动。在每次行动中,一个角色先移动到移动范围内的任意一个位置,然后可能会攻击对方阵营的一个角色(或什么也不做)。 当一个阵营的所有角色均被移除出地图时,另外一个阵营获胜。
  Rainbow得到了一份游戏日志,请帮他复原这个游戏的过程。

Input

第一行 4 个整数 N,M,C,E(1≤N,M≤100,2≤C≤min(N×M,100),1≤E≤3000) 表示地图行数、列数、角色数、日志事件数。 接下来N行每行M个整数Gi,j(1≤Gi,j≤10^2) 。
  接下来 C 行每行 8 个整数 HP,AT,MV,AD 1 ,AD 2 ,ST x ,ST y ,GR(1≤HP,AT,MV≤10^3, 1≤AD1≤AD2≤20,1≤STx≤N,1≤STy≤M,0≤GR≤1) , 表示角色的 5 个属性以及初始位置、所属阵营。
  接下来 E 行描述日志中的事件,每个事件都是以下格式之一:
  Round of GR – 阵营 GR 行动回合开始。
  Action of character ID – 角色ID 行动开始。
  Move to (x,y) – 当前行动角色通过若干步移动到 (x,y) 。
  Attack ID – 当前行动角色攻击角色ID 但是角色 ID在攻击后未被移除。
  Drive out ID – 当前行动角色攻击角色ID并造成ID 被移出游戏。
  在事件中,1≤x≤N,1≤y≤M,1≤ID≤C,0≤GR≤1 。 行列标号从1开始,每个阵营初始至少拥有1个角色。

Output

对于每个Move to事件, 若无法到达,输出“INVALID”,否则输出当它进入终点,准备结束“移动”前最多剩余多少移动力(移动力变化的优先顺序为:减去G→ G→ 若与对方阵营相邻扣为 0→ 0→ 输出→ → 恢复初始值)。
  对于每个Attack or Drive out事件,若不能攻击或者攻击造成的是否移出地图的情况与输入不相符,输出“INVALID”,否则输出攻击后被攻击角色剩余 HP HP 。
  不合法的事件在处理后续事件时应当被忽略。数据保证输入完成时游戏恰好结束,并且Round of and Action of类事件被正确记录,没有缺失或者矛盾。

Sample Input

5 5 4 12
1 9 1 4 4
1 9 1 2 4
1 9 1 1 2
2 9 2 7 3
2 3 2 6 1
10 5 8 1 3 1 1 0
20 10 5 1 2 2 1 0
19 10 5 1 2 5 2 1
25 25 3 1 1 5 5 0
Round of 0
Action of character 2
Move to (5,1)
Attack 3
Action of character 1
Move to (3,1)
Round of 1
Action of character 3
Drive out 1
Round of 0
Action of character 2
Drive out 3

Sample Output

0
9
6
INVALID
-1

Hint

【数据规模与约定】
对于80%的数据,不存在不合法事件。
对于100%的数据,参见输入输出格式中给定的范围与保证。


有几个需要注意的地方:

  • 不能攻击队友。

  • 可以走到原地。

  • 移动中碰到队友是不会把移动力变成0的。

  • 注意死亡的人要移除游戏,死亡后再操作是非法的。

  • 本题的输入有点奇怪。有时会多几个空格。


我的代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;
int n,m,c,e,g[105][105],gr[2][105],died[105];
int people,endx,endy,kill,nowgr,flag[105][105],nflag;
int fx[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct node{int x,y,s;}q[205];
//生命值 HP, 攻击力 AT, 移动力 MV, 攻击范围 [AD1 AD2]
struct fdfdfd{int hp,at,mv,ad1,ad2,st1,st2,gr;}a[105];
int abnum(char temp[],int len)//提取数字 
{
    int ans=0,flag=0;
    for(int i=0;i<len;++i)
    {
        if(temp[i]>='0'&&temp[i]<='9')
        {
            ans*=10; ans+=temp[i]-'0';
            flag=1;
            temp[i]='o';//销毁此位 
        }
        else if(flag==1) break;
    }
    return ans;
}
bool judge(int x,int y)//判断四周是否有敌方 
{
    for(int i=1;i<=gr[!nowgr][gr[!nowgr][0]];++i)
    {
        int nowx=a[gr[!nowgr][gr[!nowgr][i]]].st1,nowy=a[gr[!nowgr][gr[!nowgr][i]]].st2;
        for(int j=0;j<4;++j)
            if(x==nowx+fx[i][0]&&y==nowy+fx[i][1]) return 1;
    }
    return 0;
}
int bfs(int endx,int endy,int stax,int stay,int stamv)//move 
{
    int t=1,h=1,maxx=-1; q[t].x=stax; q[t].y=stay; q[t].s=stamv;
    memset(flag,0,sizeof(flag));
    while(h<=t)
    {
        if(q[h].x==endx&&q[h].y==endy) maxx=max(maxx,q[h].s);
        for(int i=0;i<4;++i)
        {
            int tx=q[h].x+fx[i][0],ty=q[h].y+fx[i][1],ts=judge(tx,ty)?0:q[h].s-g[tx][ty];
            if(tx>0&&tx<=m&&ty>0&&ty<=n&&ts>=max(maxx,0)&&!flag[tx][ty])
            {
                flag[tx][ty]=1;
                q[++t].x=tx; q[t].y=ty; q[t].s=ts;
            }
        }
        ++h;
    }
    return maxx==-1?-1:maxx;
}
int caldis(int sx,int sy,int ex,int ey) {return abs(ex-sx)+abs(ey-sy);}//曼哈顿距离 
int killid(int mid,int oid) 
{
    int cal=caldis(a[mid].st1,a[mid].st2,a[oid].st1,a[oid].st2);
    if(cal<a[mid].ad1||cal>a[mid].ad2) {nflag=1; return 1;}//随便返回一个值 
    else {a[oid].hp-=a[mid].at; return a[oid].hp;}
}
int main()
{
    freopen("4869.in","r",stdin);
    freopen("4869.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&c,&e);
    for(int i=1;i<=n;++i)
        for(int j=1,temp;j<=m;++j) scanf("%d",&g[i][j]);
    for(int i=1;i<=c;++i)
    {
        scanf("%d%d%d%d%d%d%d%d",&a[i].hp,&a[i].at,&a[i].mv,&a[i].ad1,&a[i].ad2,&a[i].st1,&a[i].st2,&a[i].gr);
        gr[a[i].gr][++gr[a[i].gr][0]]=i;
    }
    char temp[25]; cin.getline(temp,24);
    while(e--)
    {
        cin.getline(temp,24); int len=strlen(temp);
        if(temp[0]=='R'&&temp[1]=='o') {nowgr=abnum(temp,len); continue;}//Round of 0/1
        else if(temp[0]=='A'&&temp[1]=='c') {people=abnum(temp,len); continue;}//Action of character x
        else if(temp[0]=='M'&&temp[1]=='o')//Move to (x,y)
        {
            if(died[people]==1) continue;
            endx=abnum(temp,len),endy=abnum(temp,len);
            int temp=bfs(endx,endy,a[people].st1,a[people].st2,a[people].mv);
            if(temp==-1) puts("INVALID");
            else printf("%d\n",temp),a[people].st1=endx,a[people].st2=endy;
        }
        else if(temp[0]=='A'&&temp[1]=='t')//Attack x
        {
            if(died[people]==1) continue;
            nflag=0;
            kill=abnum(temp,len);
            if(a[kill].gr!=a[people].gr)
            {
                int temp=killid(people,kill);
                if(nflag==0&&temp<=0) died[kill]=1;
                if(nflag==1||temp<=0) puts("INVALID");
                else printf("%d\n",temp);
            }
            else puts("INVALID");
        }
        else if(temp[0]=='D'&&temp[1]=='r')//Drive out x
        {
            if(died[people]==1) continue;
            nflag=0;
            kill=abnum(temp,len);
            if(a[kill].gr!=a[people].gr)
            {
                int temp=killid(people,kill);
                if(nflag==0&&temp<=0) died[kill]=1;
                if(nflag==1||temp>0) puts("INVALID");
                else printf("%d\n",temp);
            }
            else puts("INVALID");
        }
    }
    return 0;
}

还有一个小样例:(曾经能卡我的代码)

cin:

5 5 4 17
1 9 1 4 4
1 9 1 2 4
1 9 1 1 2
2 9 2 7 3
2 3 2 6 1
10 5 8 1 3 1 1 0
20 10 5 1 2 2 1 0
19 10 5 1 2 5 2 1
25 25 3 1 1 5 5 0
Round of 0
Action of character 2
Move to (5,1)
Attack 3
Action of character 1
Move to (3,1)
Action of character 4
Move to (4,5)
Attack 2
Round of 1
Action of character 3
Attack 3
Round of 0
Action of character 1
Attack 2
Action of character 2
Drive out 3

cout:

0
9
6
0
INVALID
INVALID
INVALID
-1

祝您旅途愉快!