头像

心影




在线 


最近来访(3)
用户头像
用户头像
nut96

活动打卡代码 AcWing 845. 八数码

心影
23小时前
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
int bfs(string start)
{
    unordered_map<string,int> d{{start,0}};//创建一个q用以存储状态所对应的次数,设置一开始的状态对应次数为0
    queue<string> q;//用一个q来存储枚举的所有可能,当q队伍为空时说明情况已经全部枚举了一次
    q.push(start);//初始化队伍
    string end="12345678x";
    while(!q.empty())//当q不为空的时候一直循环下去
    {
        string st=q.front();//创建一个st存储当前的队伍头
        q.pop();//将队伍头弹出,使之后循环的队伍头不再是这个队伍头
        int distance=d[st];//创建一个distanc存储距离
        if(st==end) return d[st];//如果目前状态为所求状态 则return输出目前状态的距离 结束函数
        int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
        int k=st.find('x');//创建一个k来存储x字符的下标
        int a=k/3,b=k%3;//              对应的横坐标为下标除以列数,而纵坐标为下标取模于列数!!!!
        for(int i=0;i<4;i++)
        {
            int x=a+dx[i],y=b+dy[i];
            if(x>=0&&x<3&&y>=0&&y<3)
            {
                swap(st[k],st[x*3+y]);//下标为横坐标乘以列数再加上纵坐标
                if(!d.count(st))
                {
                    d[st]=distance+1;
                    q.push(st);//将当前状态存入数组中,进入下一次循环枚举这种状态所有的可能
                }
                 swap(st[k],st[x*3+y]);//恢复原来的样子,让for循环的下一种状态能够顺利达成
            }
        }

    }
    return -1;//如果枚举了所有的可能都达不到目标状态,则返回-1
}
int main()
{
    string c,s;
    for(int i=0;i<9;i++)
    {
        cin>>c;s+=c;//通过c将字符串输入
    }
    cout<<bfs(s);
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



心影
1天前

为了保证数组中一个区间内元素永远为k个
例: for(int j = 0 ; j < p[i].size() - k +1; j ++ ) {

            res = min(p[i][j + k - 1] - p[i][j]+1 ,res ) ;

            j<size-k+1保证了j不会移出数组最靠右的一组k的左边界
            依据下标相减加一即为元素个数  我们可以保证在j移动过程中左右边界的变化规律即保证右边界恒为j+k-1,左边界恒为k即可让此区间内元素个数永远为k


活动打卡代码 AcWing 844. 走迷宫

心影
2天前
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int ,int > PII;
int n,m;
const int N=110;
int g[N][N];//存储地图
int f[N][N];//存储点(x,y)的距离
void bfs(int a,int b)
{
    queue<PII> q;//创建名为q的队列存储可能坐标
    q.push({a,b});
    while(!q.empty())//当每一种坐标的可能性没有遍历完的时候
    {
        PII st=q.front();//创建一个st存储队头,以便于下一步删去队头后依旧能使用队头元素
                q.pop();//删去队头元素 ,使下一次循环可以使用新的队头元素
                g[st.first][st.second]=1;//标记初始(a,b)位置为1,使后面不会再经过此地
                int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
                for(int i=0;i<4;i++)
                {
                    int x=st.first+dx[i],y=st.second+dy[i];//使x,y分别为上下左右移动后的坐标
                    if(g[x][y]==0) //如果此坐标对应的值为0,即没被经过,且不为墙
                    {
                        g[x][y]=1;//将此时坐标看作经过了,定为1
                        f[x][y]=f[st.first][st.second]+1;//此时的坐标对应的距离值为上次坐标距离值+1
                        q.push({x,y});//将此时坐标套入q中,作为某一次循环的队头进入循环再枚举可能
                    }
                }
    }
    cout<<f[n][m];
}

int main()
{
    memset(g,1,sizeof(g));//将g数组全设置为二码值1对应的字符,接下来通过填入元素,以达到边界作用
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>g[i][j];//填入地图
    //为了满足题目左上角为(1,1)需求,从i=1,j=1开始填数字
    bfs(1,1);//传入初始坐标
}




心影
3天前

vector(变长数组),倍增的思想,支持比较运算(按字典序)
定义::
vector [HTML_REMOVED] a; 定义:一个vector数组a
vector [HTML_REMOVED] a(10); 定义:一个长度为10的vector数组a
vector [HTML_REMOVED] a(10,3); 定义:一个长度为10的vector数组a,并且所有元素都为3
常用函数::
size(); 返回元素个数
empty(); 返回是否是空
clear(); 清空
front(); 返回vector的第一个数
back(); 返回vector的最后一个数
push_back(); 向vector的最后插入一个数
pop_back(); 把vector的最后一个数删掉
begin(); vector的第0个数
end(); vector的最后一个的数的后面一个数
倍增的思想:
系统为某一程序分配空间是,所需时间,与空间大小无关,与申请次数有关
遍历方法
假设有个vector [HTML_REMOVED] a;
第一种:
for(int i = 0;i < a.size();i ) cout<[HTML_REMOVED]::iterator i = a.begin();i != a.end();i ) cout<<*i<<” “; vector [HTML_REMOVED]::iterator可以写为auto
第三种:
for(auto x : a) cout<<x<<” “;

pair,支持比较运算,以first为第一关键字,以second为第二关键字(按字典序)
定义::
pair <类型,类型> 变量名; 两个类型可以不同
初始化方式:
假设有个pair [HTML_REMOVED] p;
第一种:
p = make_pair(10,”abc”);
第二种:
p = {10,”abc”);
常用函数::
first(); 第一个元素
second(); 第二个元素

string(字符串)
常用函数::
substr(); 返回每一个子串
c_str(); 返回这个string对应的字符数组的头指针
size(); 返回字母个数
length(); 返回字母个数
empty(); 返回字符串是否为空
clear(); 把字符串清空
queue(队列)
定义::
queue <类型> 变量名;
常用函数::
size(); 这个队列的长度
empty(); 返回这个队列是否为空
push(); 往队尾插入一个元素
front(); 返回队头元素
back(); 返回队尾元素
pop(); 把队头弹出
注意:队列没有clear函数!!!
清空:
变量名 = queue [HTML_REMOVED] ();
priority_queue(优先队列,堆)
注意:默认是大根堆!!!
定义::
大根堆:priority_queue <类型> 变量名;
小根堆:priority_queue <类型,vecotr <类型>,greater <类型>> 变量名
常用函数:
size(); 这个堆的长度
empty(); 返回这个堆是否为空
push();往堆里插入一个元素
top(); 返回堆顶元素
pop(); 弹出堆顶元素
注意:堆没有clear函数!!!

stack(栈)
常用函数:
size(); 这个栈的长度
empty(); 返回这个栈是否为空
push(); 向栈顶插入一个元素
top(); 返回栈顶元素
pop(); 弹出栈顶元素

deque(双端队列)
常用函数:
size(); 这个双端队列的长度
empty(); 返回这个双端队列是否为空
clear(); 清空这个双端队列
front(); 返回第一个元素
back(); 返回最后一个元素
push_back(); 向最后插入一个元素
pop_back(); 弹出最后一个元素
push_front(); 向队首插入一个元素
pop_front(); 弹出第一个元素
begin(); 双端队列的第0个数
end(); 双端队列的最后一个的数的后面一个数

set,map,multiset,multimap 基于平衡二叉树(红黑树),动态维护有序序列
set/multiset
注意:set不允许元素重复,如果有重复就会被忽略,但multiset允许!!!
常用函数:
size(); 返回元素个数
empty(); 返回set是否是空的
clear(); 清空
begin(); 第0个数,支持或–,返回前驱和后继
end(); 最后一个的数的后面一个数,支持
或–,返回前驱和后继
insert(); 插入一个数
find(); 查找一个数
count(); 返回某一个数的个数
erase();
(1)输入是一个数x,删除所有x O(k + log n)
(2)输入一个迭代器,删除这个迭代器
lower_bound(x); 返回大于等于x的最小的数的迭代器
upper_bound(x); 返回大于x的最小的数的迭代器
map/multimap
常用函数:
insert(); 插入一个数,插入的数是一个pair
erase();
(1)输入是pair
(2)输入一个迭代器,删除这个迭代器
find(); 查找一个数
lower_bound(x); 返回大于等于x的最小的数的迭代器
upper_bound(x); 返回大于x的最小的数的迭代器

unordered_set,unordered_map,unordered_muliset,unordered_multimap 基于哈希表
和上面类似,增删改查的时间复杂度是O(1)
不支持lower_bound()和upper_bound()

bitset 压位
定义:
bitset <个数> 变量名;
支持:
~,&,|,^
>>,<<
==,!=
[]
常用函数:
count(); 返回某一个数的个数
any(); 判断是否至少有一个1
none(); 判断是否全为0
set(); 把所有位置赋值为1
set(k,v); 将第k位变成v
reset(); 把所有位变成0
flip(); 把所有位取反,等价于~
flip(k); 把第k位取反

作者:yxc
链接:https://www.acwing.com/video/20/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



活动打卡代码 AcWing 843. n-皇后问题

心影
4天前
#include <iostream>
using namespace std;
int n;//棋盘为n*n类型
const int N=20;//对角线个数为2n-1条,为了保证bool类型中的数组存储空间足够,开2n个
char a[N][N];//棋盘,大小为n*n,存储‘Q’与‘.’
bool col[N],dg[N],udg[N];//col数组存储纵列,dg与udg分别存储两种对角线,以y=x+b与y=-x+b中的b作为下标,保证对角线被标记
//以u为y,i为x,且为了保证下标不为负数,当b=y-x时令b+n,即b=y-x+n,此时的b作为下标依旧具有独一性且能对应所应对角线
void dfs(int u)
{
    if(u==n)//当数组n-1行填补完成后进入n,此时函数开始回溯并输出所有结果
    {
        for(int i=0;i<n;i++) puts(a[i]);//输出第i行所有的字符并换行
        puts(" ");
        return;
    }
    for(int i=0;i<n;i++)//i为对应纵列编号
    {
        if(!col[i]&&!dg[u-i+n]&&!udg[u+i])
        {
            a[u][i]='Q';//如果纵列 正反对角线皆未被标记,将Q填入
            col[i]=dg[u-i+n]=udg[u+i]=true;//Q填入后将Q所在对角线,纵列标记,不再能被填入Q
            dfs(u+1);//进入下一横行搜索
             col[i]=dg[u-i+n]=udg[u+i]=false;//回溯要将所有数值恢复false状态,使下次搜索可以使用
             a[u][i]='.';//回溯的时候将Q变为‘.’,恢复原状
        }
    }
}


int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++) a[i][j]='.';//遍历i,j使a数组上全存储‘.’
      dfs(0);//设第一横行为0,开始搜索
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

第二组模板

#include <iostream>
using namespace std;
int n;
const int N=20;
char a[N][N];
bool row[N],col[N],dg[N],udg[N];//用以标记横行,纵行,正反对角线
void dfs(int x,int y,int s)
{
   if(y==n) //如果纵列超过下标n-1横行就加一且纵列归零
    {
        x+=1;y=0;
    }


    if(x==n)//当横行也超过下标n-1时回溯,并判断是否能输出
    {
        if(s==n) //如果Q的元素个数达到n个
    {
        for(int i=0;i<n;i++) puts(a[i]);
        puts(" ");
    }
    return;
    }


    dfs(x,y+1,s);//不放皇后的可能
    if(!row[x]&&!col[y]&&!dg[y-x+n]&&!udg[y+x])//放皇后的可能
    {
        a[x][y]='Q';
        row[x]=col[y]=dg[y-x+n]=udg[y+x]=true;
        dfs(x,y+1,s+1);//如果放了皇后将进行下一个格子的枚举,且令皇后的数量s+1
        a[x][y]='.';//回溯时将场景复原,以便其他情况枚举时正常进行
        row[x]=col[y]=dg[y-x+n]=udg[y+x]=false;
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
     for(int j=0;j<n;j++) a[i][j]='.';
    dfs(0,0,0);
}


活动打卡代码 AcWing 842. 排列数字

心影
4天前
#include <iostream>
using namespace std;
int n;
const int N=10;
int a[N];
bool flag[N];//标记被使用过的数字
void DFS(int u)//u从0开始
{
    if(u==n) //如果搜寻层数到达顶端,则输出并回溯
    {
        for(int i=0;i<n;i++) printf("%d ",a[i]);
        puts(" ");
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!flag[i])
        {
           a[u] =i;
           flag[i]=true;//标记数字i为true,即已使用,后续不再调用
           DFS(u+1);//进行下一层查找
           flag[i]=false;//查找结束后将数字解除标记,以便下一次查找可以使用

        }
    }

}
int main()
{
    scanf("%d",&n);
    DFS(0);
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 154. 滑动窗口

心影
5天前
#include <iostream>
using namespace std;
int hh=0,tt=-1,k,n;
const int N=1e6+10;
int a[N],q[N];//q[N]用以存储下标
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++)//输出最小值
    {
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;//当队尾元素大于a[i]元素时将队尾元素删去
        if(hh<=tt&&q[hh]<i-k+1) hh++;//当hh存储的下标脱离窗口时,将队头元素删去

        q[++tt]=i;//添加新队尾为i下标
        if(i>=k-1) printf("%d ",a[q[hh]]);//将队尾元素作为所求值输出
    }
    cout<<endl;
    hh=0,tt=-1;//将hh与tt初始化
       for(int i=0;i<n;i++)//输出最大值
    {
        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;//当队尾元素小于于a[i]元素时将队尾元素删去
        if(hh<=tt&&q[hh]<i-k+1) hh++;//当hh存储的下标脱离窗口时,将队头元素删去

        q[++tt]=i;//添加新队尾为i下标
        if(i>=k-1) printf("%d ",a[q[hh]]);//将队尾元素作为所求值输出
    }

}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 154. 滑动窗口

心影
6天前
#include <iostream>
using namespace std;
int n,k;
const int N=1e6+10;
int a[N],q[N];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    int hh=0,tt=-1;
    for(int i=0;i<n;i++)
    {
        if(hh<=tt&&q[hh]<i-k+1)  hh++;
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
        q[++tt]=i;
        if(i>=k-1) printf("%d ",a[q[hh]]);
    }
    puts(" ");
    hh=0,tt=-1;
     for(int i=0;i<n;i++)
    {
        if(hh<=tt&&q[hh]<i-k+1)  hh++;
        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
        q[++tt]=i;
        if(i>=k-1) printf("%d ",a[q[hh]]);
    }
    puts(" ");
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 830. 单调栈

心影
6天前
#include <iostream>
using namespace std;
int n,tt;
const int N=1e5+10;
int q[N],s[N];//s[N]为创建的存储数值的栈
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    for(int i=0;i<n;i++)//每个值所求的左边第一个最小值为栈顶 
    {
        while(tt&&s[tt]>=q[i]) tt--;//如果栈顶大于所给元素,删去栈顶得到一窜单调递增的数字
        if(!tt) printf("-1 ");
        else printf("%d ",s[tt]);
        s[++tt]=q[i];//tt从1开始存储数值,如果tt为0说明栈内为空,返回-1
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 829. 模拟队列

心影
6天前
#include <iostream>
using namespace std;
int m,x;
const int N=1e5+10;
int q[N],hh,tt=-1;
int main()
{
    scanf("%d",&m);
    while(m--)
    {
       string op;
       cin>>op;
       if(op=="push")
       {
           scanf("%d",&x);
           q[++tt]=x;
       }
       else if(op=="pop")
       {
           hh++;
       }
       else if(op=="empty")
       {
           cout<<(hh<=tt?"NO":"YES")<<endl;
       }
       else 
       {
           cout<<q[hh]<<endl;
       }
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~