头像

九命之猫




离线:6个月前


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

九命之猫
10个月前
#include <bits/stdc++.h>
using namespace std;

int n, m;
const int N = 105;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int grid[N][N], vis[N][N];
queue<pair<int, int>> q;
int bfs(){
    memset(vis, -1, sizeof vis);
    vis[0][0] = 0;
    q.push({0, 0});
    while(q.size()){
        pair<int, int> p = q.front();
        q.pop();
        int x = p.first;
        int y = p.second;
        for(int i = 0; i < 4; ++i){
            int a = x + dx[i];
            int b = y + dy[i];
            if(a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == 0 && vis[a][b] == -1){
                q.push({a, b});
                vis[a][b] = vis[x][y] + 1;
            }
        }
    }
    return vis[n - 1][m -1];
}
int main(){
    cin >> n >> m;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            cin >> grid[i][j];

    cout << bfs() << endl;
    return 0;
}



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

九命之猫
10个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u){
    if(u == n){
        for(int i = 0; i < n; ++i) puts(g[i]);
        puts("");
        return;
    }
    for (int i = 0; i < n; i ++ )
        if (!col[i] && !dg[u + i] && !udg[n - u + i])
        {
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
}
int main(){
    cin >> n;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j)
            g[i][j] = '.';
    }
    dfs(0);
    return 0;
}


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

九命之猫
10个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include <bits/stdc++.h>
using namespace std;
int path[10];
bool vi[10];
int n;
void dfs(int x){
    if(x == n){
        for(int i = 0; i < n; ++i) cout << path[i] << " ";
        cout << endl;
        return;
    }
    for(int i = 1; i <= n; ++i){
        if(vi[i] == false){
            path[x] = i;
            vi[i] = true;
            dfs(x + 1);
            vi[i] = false;
        }
    }
}
int main(){
    cin >> n;
    dfs(0);
    return 0;
}


活动打卡代码 AcWing 835. Trie字符串统计

九命之猫
11个月前
#include <iostream>

using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }

    return 0;
}



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

九命之猫
11个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int a[N];
int r = -1;
int main(){
    int n; cin >> n;
    while(n--){
        int x; cin >> x;
        while(r >= 0 && a[r] >= x) r--;
        if(r < 0) cout << -1 << " ";
        else cout << a[r] << " ";
        a[++r] = x;
    }
    cout << endl;
    return 0;
}


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

九命之猫
11个月前
#include <iostream>

using namespace std;

const int N = 1000010;

int a[N], q[N];

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    int f = 0, r = -1;
    for (int i = 0; i < n; i ++ )
    {
        if (f <= r && i - k + 1 > q[f]) f ++ ;

        while (f <= r && a[q[r]] >= a[i]) r -- ;
        q[ ++ r] = i;

        if (i >= k - 1) cout << a[q[f]] << " ";
    }

    cout << endl;

    f = 0, r = -1;
    for (int i = 0; i < n; i ++ )
    {
        if (f <= r && i - k + 1 > q[f]) f ++ ;

        while (f <= r && a[q[r]] <= a[i]) r -- ;
        q[ ++ r] = i;

        if (i >= k - 1) cout << a[q[f]] << " ";
    }

    return 0;
}



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

九命之猫
11个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <utility>
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int MOD = 1e9 + 7;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

const int N = 100010;
int a[N];
int front, real;
int main() {
    front = 0;
    real = 0;
    int m; cin >> m;
    while(m--){
        string s; cin >> s;
        if(s == "push"){
            int x; cin >> x;
            a[real] = x;
            real++;
        }
        else if(s == "pop"){
            front++;
        }
        else if(s == "empty"){
            if(real == front) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
        else{
            cout << a[front] << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 828. 模拟栈

九命之猫
11个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include <iostream>

using namespace std;

const int N = 10010;
int s[N], top;
void init(){
    top = 0;
}
void push(int x){
    s[top] = x;
    top++;
}
void pop(){
    top--;
}
bool empty(){
    if(top == 0) return true;
    return false;
}
int query(){
    if(!empty()) return s[top - 1];
}
int main(){
    int m; cin >> m;
    init();
    while(m--){
        string str;
        cin >> str;
        if(str == "push"){
            int x; cin >> x;
            push(x);
        }
        else if(str == "query") cout <<  query() << endl;
        else if(str == "pop") pop();
        else{
            if(empty()) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 827. 双链表

九命之猫
11个月前
#include <iostream>

using namespace std;

const int N = 100010;

int m;
int e[N], l[N], r[N], idx;


void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

int main()
{
    cin >> m;

    r[0] = 1, l[1] = 0;
    idx = 2;

    while (m -- )
    {
        string op;
        cin >> op;
        int k, x;
        if (op == "L")
        {
            cin >> x;
            insert(0, x);
        }
        else if (op == "R")
        {
            cin >> x;
            insert(l[1], x);
        }
        else if (op == "D")
        {
            cin >> k;
            remove(k + 1);
        }
        else if (op == "IL")
        {
            cin >> k >> x;
            insert(l[k + 1], x);
        }
        else
        {
            cin >> k >> x;
            insert(k + 1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}



活动打卡代码 AcWing 826. 单链表

九命之猫
12个月前
#include <iostream>

using namespace std;

const int N = 100010;
int head, e[N], ne[N], idx;

//初始化
void init() {head = -1; idx = 0;}
//在头节点后添加元素
void add_head(int x) {e[idx] = x; ne[idx] = head; head = idx; idx++;}
//在下表k的节点后添加元素
void add(int k, int x) {e[idx] = x; ne[idx] = ne[k]; ne[k] = idx; idx++;}
//讲下表为k的节点后面的那个节点删除掉
void remove(int k) {ne[k] = ne[ne[k]];}

int main(){
    init();
    int m; cin >> m;
    while(m--){
        char opt; cin >> opt;
        if(opt == 'H') {int x; cin >> x; add_head(x);}
        else if(opt == 'D') {
            int k; cin >> k; 
            if (!k) head = ne[head];
            else remove(k - 1);

        }
        else {int k, x; cin >> k >> x; add(k - 1, x);}
    }
    for(int i = head; i != -1; i = ne[i]) cout << e[i] << " ";
    cout << endl;
    return 0;
}