头像

rookie升职记




离线:4小时前


活动打卡代码 AcWing 238. 银河英雄传说

不要用ios::sync_with_stdio(false);的范例,真的要被坑死了

#include <iostream>
#include <cmath>

using namespace std;

const int N = 300010;

int f[N], d[N], si[N];

void init(int n) {
  for (int i = 1; i <= n; i ++ ) {
    f[i] = i;
    d[i] = 0;
    si[i] = 1;
  }
}
/*
我们可以先考虑没有路径压缩的情况下,f[x]的含义,含义为排在x号前面的那个战舰的编号。
一个集合的代表就是位于最前面的那个战舰。另外,我们让树上的每条边带权值为1,这样树上
两点之间的距离减1,就是二者之间间隔的战舰数量。
所以,我们根据上面的性质来进行路径压缩。
再考虑路径压缩的情况下,我们额外建立一个数组d,d[x]记录战舰x与f[x]之间的边的权值。
在路径压缩时,把x直接指向树根的同时,我们把d[x]更新为从x到树根的路径上所有边权之和。
下面的代码,对get函数稍加修改,就可以实现d数组的维护。
 */
int get(int x) {
  if (x == f[x]) return x;
  int root = get(f[x]);//递归计算集合代表,啥叫集合代表,就是能代表这个集合的元素,那不就是头结点嘛 
  d[x] += d[f[x]];//维护d数组,对边权求和
  return f[x] = root;//路径压缩
}
/*
当接收到C x y 指令时,分别执行get(x) 和 get(y)完成查询和路径压缩。当二者返回的值相同时,说明x和y处于同一列中。
因为x和y都已经指向了树根,所以d[x]保存了位于x之前的战舰数量,d[y]保存了位于y之前的战舰数量。
而这之差的绝对值再减去1,就是x和y之间间隔的战舰数量
 */
/*
当接受到M x y指令时,把x的树根作为y的树根的子结点,连接的新边的权值(注意这里,设置的是新生成的边,连接x和y的边的边权)
应该设为合并之前集合y的大小(根据题意,集合y中全部战舰都排在集合x之前)。因此,我们还需要一个size数组在每个树根上记录
集合的大小,下面是merge函数稍加修改后的代码。
 */
void merge(int x, int y) {
  x = get(x), y = get(y);
  f[x] = y;
  d[x] = si[y];
  si[y] += si[x];
}

int main() {
  //ios::sync_with_stdio(false);
  int T; cin >> T;
  init(N);
  while (T -- ) {
    char op[2]; int a, b;
    cin >> op >> a >> b;
    if (*op == 'M') {
      if (get(a) == get(b)) continue;
      merge(a, b);
    }
    else {
      if (get(a) == get(b)) {
        cout << abs(d[a] - d[b]) - 1 << endl;
      }
      else puts("-1");
    }
  }
}


活动打卡代码 AcWing 756. 蛇形矩阵

#include <iostream>

using namespace std;

const int N = 110;

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

int q[N][N];

int main() {
    int n, m; cin >> n >> m;
    int x = 0, y = 0, d = 1;
    for (int i = 1; i <= n * m; i ++  ) {
        q[x][y] = i;
        int a = x + dx[d], b = y + dy[d];
        if (a < 0 || a >= n || b < 0 || b >= m || q[a][b]) {
            d = (d + 1) % 4;
            a = x + dx[d], b = y + dy[d];
        }
        x = a, y = b;
    }

    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < m; j ++ ) 
            cout << q[i][j] << ' ';
        cout << endl;
    }

    return 0;
}


活动打卡代码 AcWing 898. 数字三角形

#include <iostream>

using namespace std;

const int N = 10010;

int n;
int f[N][N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= i; j ++ ) 
            cin >> f[i][j];

    for (int i = n; i >= 1; i -- ) 
        for (int j = 1; j <= i; j ++ )
            f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);

    cout << f[1][1] << endl;

    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n;
int a[N];

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

    sort(a, a + n);

    int res = 0;
    for (int i = 0; i < n; i ++ ) {
        res += abs(a[i] - a[n / 2]);
    }

    cout << res << endl;

    return 0;
}



用数组模拟队列的时候,在给hh和tt赋初值的时候,hh都是赋值为0,tt有时候赋值为0, 有时候赋值为-1.
这中间有什么讲究的吗,不知道啥时候给tt赋值为0或者是-1.
求大佬指教。




class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stk;
    stack<int> stk_min;

    MinStack() {

    }

    void push(int x) {
        stk.push(x);
        if (stk_min.size()) x = min(x, stk_min.top());
        stk_min.push(x);
    }

    void pop() {
        //因为前面每次都往里面插入x,所以,可以直接弹掉
        //这是你没有想到的
        stk.pop();
        stk_min.pop();
    }

    int top() {
        return stk.top();
    }

    int getMin() {
        return stk_min.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */


活动打卡代码 AcWing 200. Hankson的趣味题

/*
 *@author SunLakeWalk
 */
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

#define x first
#define y second

typedef long long ll;
typedef pair<ll, ll> PLL;

const int N = 100010, C = 1010, inf = 0x3f3f3f3f;

ll primes[N], cnt;
bool st[N];
//存一下b1的质因子,和质因子的个数
PLL factor[N];
ll cntf;
//存一下y约数
ll divider[N], cntd;

void get_primes(ll n) {
  for (ll i = 2; i <= n; i ++ ) {
    if (!st[i]) primes[cnt ++ ] = i;

    for (ll j = 0; primes[j] * i <= n; j ++ ) {
      st[i * primes[j]] = true;
      if (i % primes[j] == 0) break;
    }
  }
}
//求出b1的所有质因子,和质因子的个数
void divide(ll n) {
  for (ll i = 0; primes[i] <= n / primes[i]; i ++ ) {
    int p = primes[i];
    if (n % primes[i] == 0) {
      ll s = 0;
      while (n % primes[i] == 0) s ++, n /= p;
      factor[++ cntf] = {p, s};
    }
  }
  if (n > 1) factor[++ cntf] = {n, 1};
}

ll gcd(ll a, ll b) {
  return b ? gcd(b, a % b) : a;
}

void dfs(ll u, ll p) {
  if (u > cntf) {
    divider[cntd ++ ] = p;
    return;
  }

  for (ll i = 0; i <= factor[u].y; i ++ ) {
    dfs(u + 1, p);
    p *= factor[u].x;
  }
}
void work() {
  get_primes(N);
  ll T; cin >> T;
  while (T -- ) {
    ll a0, a1, b0, b1; cin >> a0 >> a1 >> b0 >> b1;

    cntf = 0;
    divide(b1);

    cntd = 0;
    dfs(1, 1);

    ll res = 0;
    for (ll i = 0; i < cntd; i ++ ) {
      int d = divider[i];
      if (gcd(a0, d) == a1 && b0 * d / gcd(b0, d) == b1)
        res ++;

    }

    cout << res << endl;
  }
}

int main() {

  work();

  return 0;
}




数字三角形
这一到题目,安y总讲的,从上往下搜的时候,需要初始化边界为一个非常小的数,那为什么从下往上搜的时候却不需要初始化边界呢?好疑惑,有大佬可以解答一下嘛~~



活动打卡代码 AcWing 171. 送礼物

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

using namespace std;

typedef long long ll;

const int N = 1 << 24;

int n, m, k;
int g[50], weights[N];
int cnt, ans;

void dfs(int u, int s) {
  if (u == k) {//k为边界,搜到k不向下执行
    weights[cnt ++ ] = s;//搜到边界,赋值
    return;
  }

  if ((ll)s + g[u] <= m) dfs(u + 1, s + g[u]);//选当前
  dfs(u + 1, s);//不选当前
}

void dfs2 (int u, int s) {
  if (u == n) {
    int l = 0, r = cnt - 1;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (weights[mid] + (ll)s <= m) l = mid;
      else r = mid - 1;
    }

    if (weights[l] + (ll)s <= m) ans = max(ans, weights[l] + s);

    return;
  }

  if ((ll)s + g[u] <= m) dfs2(u + 1, s + g[u]);//选当前
  dfs2(u + 1, s);//不选当前
}
int main() {
  cin >> m >> n;
  for (int i = 0; i < n; i ++ ) cin >> g[i];

  sort(g, g + n, greater<int>());//从大到小排序

  k = n / 2 + 2;//后半搜索有二分,这里多分配两个
  dfs(0, 0);

  sort(weights, weights + cnt);//将打包好后排个序

  int t = 1;
  for (int i = 1; i < cnt; i ++ )//去重
    if (weights[i] != weights[i - 1])
      weights[t ++ ] = weights[i];

    cnt = t;//去重后t个包

    dfs2(k, 0);//从k开始搜

    cout << ans << endl;

    return 0;
}



活动打卡代码 AcWing 170. 加成序列

/*
我们在做题前就可以进行判断一下迭代的深度,并确定使用迭代加深的方法
因为n是一个不大于100的数。
我们知道,任意的一个数 2 ^ (k - 1) < x <= 2 ^ k,都可以用k个从1开始的二进制的数和的表示
1 2 4 8 16 32 64 128
我们可以轻松的使用这8个数中若干个数的和来表示小于100的任何一个数。
所以我们迭代的次数最多不会超过10,符合我们迭代加深的方法
*/
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 110;

int n;
int path[N];

bool dfs(int u, int depth){
    //如果已经迭代到了当前最深,判断最后一次是否达到n
    if (u == depth) return path[u - 1] == n;//当前层u为未进行确定下path值的层数,这里使边界条件

    bool st[N] = {false};//将所有元素置为false

    //剪枝1,优化搜索顺序,我们求的是最短的序列长度,所以我们搜的时候,让i和j尽可能得大,更快得接近m,(x[m]=n)
    for (int i = u - 1; i >= 0; i -- )
        for (int j = i; j >= 0; j -- ) {
            int s = path[i] + path[j];//和
            /*
            剪枝2
            题目里有了:
            x[1] < x[2] < x[3] < ... < x[m - 1] < x[m]
            对于每个k(2 <= k <= m)都存在两个整数i和j(1 <= i , j <= k - 1, i和j可以相等),是的x[k] = x[i] + x[j]
            所以我们这里i最大为u-1,j最大为i。
            同样,s 即 x[k] 因为x[m] = n;且k <= m;所以s是不能大于n的。
            同样,序列x[1], x[2], ... , x[m]是一个严格单调递增的序列,s为x[m] 一定要大于前面出现过的任何的数
            同样,对于不同的i和j,x[i] + x[j]的值可能相同,这是我们就要运用到剪枝当中的第二个方法,排除等效冗余。因为相同的s,效果
            是相同的,只需要搜s一次就可以了,所以我们可以用bool数组对s = x[i] + x[j] 进行判重避免之后搜索到同一个和s
            */
            if (s > n || s <= path[u - 1] || st[s]) continue;
            path[u] = s;
            st[s] = true;
            if (dfs(u + 1, depth)) return true;//如果搜到了n,就返回true
        }
    //cout << "----------------" << endl;
    return false;//如果都没有搜到就返回false
}
int main() {
    while (cin >> n, n) {
        path[0] = 1;//路径从0开始计算

        int depth = 1;
        //迭代加深
        //每次搜索从第一个数也就是第一层开始搜索,然后迭代depth次,如果没有得到答案,将深度加一,重新搜索
        while (!dfs(1, depth)) depth ++;

        for (int i = 0; i < depth; i ++ ) printf("%d ", path[i]);
        puts("");
    }

    return 0;
}