头像

zoomdong




离线:4天前



为啥这样的代码在 vscode 上报错误,expected expression:

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

typedef pair<int, int> PII;

const int N = 110;
int n,m;
int d[N][N];
int g[N][N];

PII q[N * N];


int bfs () {
  int hh = 0, tt = 0;

  q[0] = {0, 0};

  memset(d, -1, sizeof(d));
  d[0][0] = 0;

  int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

// 维护两根指针去表示队列,其中 hh 为队列头, tt 为队列尾部
  while (hh <= tt)
  {
    auto t = q[hh++];

    for (int i = 0;i < 4;i++) {
      int x = t.first + dx[i], y = t.second + dy[i];
      if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
        d[x][y] = d[t.first][t.second] + 1;
        q[++tt] = {x, y};
      }
    }
  }
  return d[n-1][m-1];
}

int main () {
   cin >> n >> m;
   for (int i = 0;i<n;i++) {
     for (int j = 0;j<m;j++) {
       cin >> g[i][j];
     }
   }
   cout << bfs() << endl;
  return 0;
}
走迷宫.cpp:20:10: error: expected expression
  q[0] = {0, 0};
         ^
走迷宫.cpp:30:5: warning: 'auto' type specifier is a C++11 extension [-Wc++11-extensions]
    auto t = q[hh++];
    ^
走迷宫.cpp:36:19: error: expected expression
        q[++tt] = {x, y};
                  ^
1 warning and 2 errors generated.

在 acwing 上能编译通过



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

搞个队列,宽搜记录一下就行了:

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

typedef pair<int, int> PII;

const int N = 110;
int n,m;
int d[N][N];
int g[N][N];

PII q[N * N];


int bfs () {
  int hh = 0, tt = 0;

  q[0] = {0, 0};

  memset(d, -1, sizeof(d));
  d[0][0] = 0;

  int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

  while (hh <= tt)
  {
    auto t = q[hh++];

    for (int i = 0;i < 4;i++) {
      int x = t.first + dx[i], y = t.second + dy[i];
      if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
        d[x][y] = d[t.first][t.second] + 1;
        q[++tt] = {x, y};
      }
    }
  }
  return d[n-1][m-1];
}

int main () {
   cin >> n >> m;
   for (int i = 0;i<n;i++) {
     for (int j = 0;j<m;j++) {
       cin >> g[i][j];
     }
   }
   cout << bfs() << endl;
  return 0;
}


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

#include<iostream>
#include<cstdio>
using namespace std;
// 注意这个 N 值不要开太小了,因为下面 bool 数组会使用
const int N = 20;

char g[N][N];

bool col[N], dg[N], udg[N];

int n;

void dfs(int u) {
    if (u == n) {
        for (int i = 0;i<n;i++) {
            puts(g[i]);
        }
        puts("");
        return;
    }
    // 枚举一下当前行可以用的列此时坐标 为 (u, i)
    for (int i = 0;i<n;i++) {
        // 判断当前坐标所在的斜线、反斜线上有没有使用过这个点
        // dg 表示正对角线、udg 是反对角线
        // 这里对角线的坐标通过截距来进行计算 b = y -x || b = y + x 因为偏移量不能是负,所以第一种 + n
        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. 排列数字

dfs 的经典 template 题目

#include<iostream>

using namespace std;

const int N = 10;

int path[N];
bool st[N];
int n;

void dfs(int u) {
    if (u == n) {
        for (int i = 0;i<n;i++) cout << path[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1;i<=n;i++) {
        if (!st[i]) {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            // 搜完之后把状态回溯一下
            st[i] = false;
        }
    }
}

int main () {
    cin >> n;
    dfs(0);
    return 0;
}



拓扑序列原理就是根据出度、入度去进行一个删除相关边的操作即可。
每次宽搜的时候去删除一下当前点对应的另外一边点的入度(-1),入度为0了就可以放进队列了。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
// d 表示存 入度的数组
int q[N], d[N];

// 这一步是构建图的操作,没看太明白
void add(int a, int b) {
  e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool topsort() {
  int hh = 0, tt = -1;

  for (int i = 1; i <= n;i ++) {
    if (!d[i]) {
      // 这里是用数组来模拟
      q[++ tt] = i;
    }
  }
  while (hh <= tt) {
    int t = q[hh ++];
    for (int i = h[t]; i != -1; i=ne[i]) {
      int j = e[i];
      d[j] --;
      if (!d[j]) q[++tt] = j;
    }
  }
  // 如果队列里面存的值
  return tt == n - 1;
}

int main () {
  cin >> n >> m;

  memset(h, -1, sizeof(h));

// 一共有 m 条边
  for (int i = 0;i < m;i++) {
    int a, b;
    cin >> a >> b;
    add(a, b);
    // 有一条a 指向 b 的边,那么b 的入度就可以 ++
    d[b] ++;
  }
  // 判断是否存在拓扑序列
  if (topsort()) {
   for (int i = 0;i < n; i++) cout << q[i] << " ";
  } else {
    cout << -1 << endl;
  }
  return 0;
}


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

zoomdong
11天前

这里采用的是静态链表:

#include<iostream>

using namespace std;

const int N = 100010;

// head 表示头节点的下标
// e[i] 表示节点 i 的值
// ne[i] 表示节点 i 的 next 指针的值
// idx 存当前可以使用的最新的节点的下标
int head, e[N], ne[N], idx;

// 初始化操作
void init () {
  head = -1;
  idx = 0;
}

// 把 x 插入头节点
// 分两步来完成 让 x 节点的 next 指针指过去 head 存的值
// 第二步让 head 指向新增的节点(更新一下idx)
void add_to_head(int x) {
  e[idx] = x;
  ne[idx] = head;
  head = idx;
  idx ++;
}

void add(int x, int k) {
  e[idx] = x;
  ne[idx] = ne[k];
  ne[k] = idx;
  idx ++;
}

// 删除下标为k的点后面的点删掉
void remove(int k) {
  // 直接跳到它后面点的next上面去
  ne[k] = ne[ne[k]];
}

int main () {
  int m;
  cin >> m;
  init();
  while (m --) {
    int x,k;
    char op;
    cin >> op;
    if (op == 'H') {
      cin >> x;
      add_to_head(x);
    }else if (op == 'D') {
      cin >> k;
      // 特判一下 k 为 0 的情况
      if (k == 0) {
        head = ne[head];
      }
      remove(k - 1);
    } else {
      cin >> k >> x;
      add(x, k - 1);
    }
  }
   for (int i = head;i!=-1;i=ne[i]) {
      cout << e[i] << " ";
    }
    cout << endl;
  return 0;
}


活动打卡代码 AcWing 803. 区间合并

zoomdong
20天前

区间合并,注意先排序,然后考虑后面几种情况:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<int, int> PII;
const int N = 100010;

int n;
vector<PII> segs;

void merge(vector<PII> &segs) {
    vector<PII> res;

    // 这里会默认根据 pair 的第一个值去进行排序
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;

    for (auto seg: segs) {
        // 如果后面区间在前面这个
        if (ed < seg.first) {
            if (st != -2e9) {
                res.push_back({st, ed});
            }
            st = seg.first, ed = seg.second;
        } else {
            ed = max (ed, seg.second);
        }
    }
    if (st != -2e9) {
        res.push_back({st, ed});
    }
    segs = res;
}

int main () {
    cin >> n;

    for (int i = 0;i<n;i++) {
        int l, r;
        cin >> l >> r;
        segs.push_back({l , r});
    }
    merge(segs);

    cout << segs.size() << endl;
    return 0;
}


活动打卡代码 AcWing 2816. 判断子序列

zoomdong
20天前

双指针去扫就行了hhh,代码写的有点丑,调试了一下才出来:

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

const int N = 1e5 + 7;
int a[N], b[N];

int main () {
  int n, m;
  cin >> n >> m;
  for (int i = 0;i<n;i++) {
    cin >> a[i];
  }

  for (int i = 0;i<m;i++) {
    cin >> b[i];
  }

  int count = 0;
  for (int i = 0, j = 0;i<n;i++) {
    while (a[i] != b[j] && j < m - 1) {
      j ++;
    }
    if (a[i] == b[j] && j < m) {
      j ++;
      count ++;
    }
  }
  if (count == n) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}



zoomdong
20天前

利用升序数组这个条件去做双指针就行了:

#include<iostream>
#include<cmath>

using namespace std;
const int N = 100007;
int a[N], b[N];

int main () {
    int n, m, x;
    cin >> n >> m >> x;
    for (int i = 0; i < n;i++) {
        cin >> a[i];
    }
    for (int i = 0;i<m;i++) {
        cin >> b[i];
    }
    int p, q;
    for (int i = 0,j = m - 1;i<m;i++) {
        while (a[i] + b[j] > x && j > 0) {
            j--;
        }
        if (j >= 0 && a[i] + b[j] == x) {
            p = i;
            q = j;
            break;
        }
    }
    cout << p << " " << q;
    return 0;
}


活动打卡代码 AcWing 802. 区间和

zoomdong
20天前

因为这里是分为插入和查询,我们先对值进行离散化,注意查询的数组下标值也要放进离散化数组去进行处理,然后根据前缀和去把结果跑出来就行:
好好理解一下这里的写法:

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

const int N = 300010;
int n, m;
// a 数组是存的数字, s 是前缀和
int a[N], s[N];
vector<int>arr;

// 因为每次会有两组数,所以使用 pair 来存取
typedef pair<int, int>PII;
vector<PII> add, query;

int find (int x) {
  int l = 0, r = arr.size() - 1;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (arr[mid] >= x) r = mid;
    else l = mid + 1;
  }
  return r + 1;
}

int main () {
  cin >> n >> m;
  while (n --) {
    int x, c;
    cin >> x >> c;
    add.push_back({x, c});
    arr.push_back(x);
  }
  while(m--) {
    int l ,r;
    cin >> l >> r;
    query.push_back({l, r});
    arr.push_back(l);
    arr.push_back(r);
  }
  // 去重
  sort(arr.begin(), arr.end());
  arr.erase(unique(arr.begin(), arr.end()), arr.end());

  // 处理插入
  for (auto item: add) {
    int x = find(item.first);
    a[x] += item.second;
  }
  // 前缀和
  for (int i =1;i<=arr.size();i++) {
    s[i] = s[i-1] + a[i];
  }
  // 询问
  for (auto item: query) {
    int l = find(item.first), r= find(item.second);
    cout << s[r] - s[l-1] << endl;
  }
  return 0;
}