头像

imnoob




离线:1天前


最近来访(62)
用户头像
Selflocking
用户头像
揽苟
用户头像
上下求索
用户头像
_不知道
用户头像
Sun@Wind
用户头像
33号花卷
用户头像
Zero_Two
用户头像
吃掉这个脆脆鲨
用户头像
今天AC了吗
用户头像
Daysgone
用户头像
肖肖_6
用户头像
心牢
用户头像
lihua
用户头像
心情不好就刷题
用户头像
忘打周赛
用户头像
白日做梦家
用户头像
半岛加珍珠
用户头像
𝐑𝐨𝐬𝐦𝐨𝐧𝐭𝐢𝐬_g
用户头像
邹梓墨
用户头像
yxc

活动打卡代码 AcWing 1085. 不要62

imnoob
2天前
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int N = 100;
int f[N][N];
int a[N], al;

int dp(int pos, int st, int op) {
  if (!pos)
    return 1;
  if (!op && ~f[pos][st])
    return f[pos][st];
  int res = 0, maxn = op ? a[pos] : 9;
  for (int i = 0; i <= maxn; i++) {
    if ((st == 6 && i == 2) || i == 4)
      continue;
    res += dp(pos - 1, i, op && i == a[pos]);
  }
  return op ? res : f[pos][st] = res;
}
int calc(int n) {
  al = 0;
  memset(f, -1, sizeof f);
  int t = n;
  while (n) {
    a[++al] = n % 10;
    n /= 10;
  }
  return dp(al, 0, 1);
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int a, b;
  while (cin >> a >> b, a || b) {
    cout << calc(b) - calc(a - 1) << "\n";
  }
}


活动打卡代码 AcWing 1084. 数字游戏 II

imnoob
2天前
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
int aa, bb, cc;
const int N = 100;
int f[N][N], a[N], al;
int dp(int pos, int st, int op) {
  if (!pos)
    return st % cc == 0;
  if (!op && ~f[pos][st])
    return f[pos][st];
  int res = 0, maxn = op ? a[pos] : 9;
  for (int i = 0; i <= maxn; i++) {
    res += dp(pos - 1, st + i, op && i == a[pos]);
  }
  return op ? res : f[pos][st] = res;
}
int calc(int n) {
  al = 0;
  memset(f, -1, sizeof f);
  while (n) {
    a[++al] = n % 10;
    n /= 10;
  }
  return dp(al, 0, 1);
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  while (cin >> aa >> bb >> cc) {
    cout << calc(bb) - calc(aa - 1) << '\n';
  }
}


活动打卡代码 AcWing 1083. Windy数

imnoob
2天前
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int N = 50;
int f[N][N];
int a[N], al;
int dp(int pos, int st, int op) {
  if (!pos)
    return 1;
  if (!op && ~f[pos][st])
    return f[pos][st];
  int res = 0, maxn = op ? a[pos] : 9;
  for (int i = 0; i <= maxn; i++) {
    if (abs(i - st) < 2)
      continue;
    res += dp(pos - 1, !i && st == -2 ? -2 : i, op && a[pos] == i);
  }
  return op && st == -2 ? res : f[pos][st] = res;
}
int calc(int n) {
  al = 0;
  memset(f, -1, sizeof f);
  while (n) {
    a[++al] = n % 10;
    n /= 10;
  }
  return dp(al, -2, 1);
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int a, b;
  cin >> a >> b;
  cout << calc(b) - calc(a - 1);
}


活动打卡代码 AcWing 1277. 维护序列

imnoob
8天前
#include <cstdio>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
int n, p, m;
int w[N];
struct Node {
  int l, r, sum, add, mul;
} tr[4 * N];

void pushup(int u) { tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p; }

void eval(Node &root, int add,
          int mul) //计算在该区间加或乘一个数,数据可能会爆int
{
  root.sum = ((LL)root.sum * mul + (LL)(root.r - root.l + 1) * add) % p;
  root.mul = (LL)root.mul * mul % p;         //根据推的公式
  root.add = ((LL)root.add * mul + add) % p; //根据推的公式
}

void pushdown(int u) {
  eval(tr[u << 1], tr[u].add, tr[u].mul);
  eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
  tr[u].add = 0;
  tr[u].mul = 1;
}

void build(int u, int l, int r) {
  tr[u].r = r, tr[u].l = l;
  if (l == r)
    tr[u].sum = w[l], tr[u].add = 0, tr[u].mul = 1;
  else {
    int mid = l + r >> 1;
    tr[u].add = 0, tr[u].mul = 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u); //回溯时通过子区间更新父区间信息
  }
}

void modify(int u, int l, int r, int add, int mul) {
  if (tr[u].l >= l && tr[u].r <= r)
    eval(tr[u], add, mul); //若当前访问区间在查询区间内
  else {
    pushdown(u); //区间分列时需先处理懒标记
    int mid = tr[u].r + tr[u].l >> 1;
    if (mid >= l)
      modify(u << 1, l, r, add, mul); //递归处理左右子区间
    if (mid < r)
      modify(u << 1 | 1, l, r, add, mul);
    pushup(u);
  }
}

int query(int u, int l, int r) {
  if (tr[u].l >= l && tr[u].r <= r)
    return tr[u].sum; //若当前访问区间在查询区间内
  else {
    pushdown(u); //区间分列时需先处理懒标记
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if (mid >= l)
      sum = query(u << 1, l, r) % p; //递归处理左右子区间
    if (mid < r)
      sum = (sum + query(u << 1 | 1, l, r)) % p;
    return sum;
  }
}

int main() {
  scanf("%d%d", &n, &p);
  for (int i = 1; i <= n; i++)
    scanf("%d", &w[i]);
  build(1, 1, n);
  scanf("%d", &m);
  while (m--) {
    int t, l, r, d;
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1) {
      scanf("%d", &d);
      modify(1, l, r, 0, d);
    } else if (t == 2) {
      scanf("%d", &d);
      modify(1, l, r, d, 1);
    } else
      printf("%d\n", query(1, l, r));
  }
  return 0;
}



活动打卡代码 AcWing 4342. 就一勾子

imnoob
9天前
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int N = 1e5 + 10;
struct node {
  int l, r, v, t;
} tr[N << 2];
void pushup(int u) { tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v; }
void pushdown(int u) {
  auto &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
  if (root.t) {
    l.t = root.t, l.v = (l.r - l.l + 1) * root.t;
    r.t = root.t, r.v = (r.r - r.l + 1) * root.t;
    root.t = 0;
  }
}
int query(int u, int l, int r) {
  if (tr[u].l >= l && tr[u].r <= r) {
    return tr[u].v;
  } else {
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    int k = 0;
    if (l <= mid)
      k += query(u << 1, l, r);
    if (mid < r)
      k += query(u << 1 | 1, l, r);
    return k;
  }
}
void modify(int u, int l, int r, int c) {
  if (tr[u].l >= l && tr[u].r <= r) {
    tr[u].v = c * (tr[u].r - tr[u].l + 1);
    tr[u].t = c;
    return;
  } else {
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid)
      modify(u << 1, l, r, c);
    if (r > mid)
      modify(u << 1 | 1, l, r, c);
    pushup(u);
  }
}
void build(int u, int l, int r) {
  tr[u] = {l, r, 1, 0};
  if (l == r) {
    return;
  } else {
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    memset(tr, 0, sizeof tr);
    int n, m;
    cin >> n >> m;
    build(1, 1, n);
    for (int i = 0; i < m; i++) {
      int l, r, c;
      cin >> l >> r >> c;
      modify(1, l, r, c);
    }
    printf("Case %lld: The total value of the hook is %lld.\n", i,
           query(1, 1, n));
  }
}



imnoob
9天前

传统线段树

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int N = 1e5 + 10;
struct node {
  int l, r, v, t;
} tr[N << 2];
void pushup(int u) { tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v; }
void pushdown(int u) {
  auto &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
  if (root.t) {
    l.t = root.t, l.v = (l.r - l.l + 1) * root.t;
    r.t = root.t, r.v = (r.r - r.l + 1) * root.t;
    root.t = 0;
  }
}
int query(int u, int l, int r) {
  if (tr[u].l >= l && tr[u].r <= r) {
    return tr[u].v;
  } else {
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    int k = 0;
    if (l <= mid)
      k += query(u << 1, l, r);
    if (mid < r)
      k += query(u << 1 | 1, l, r);
    return k;
  }
}
void modify(int u, int l, int r, int c) {
  if (tr[u].l >= l && tr[u].r <= r) {
    tr[u].v = c * (tr[u].r - tr[u].l + 1);
    tr[u].t = c;
    return;
  } else {
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid)
      modify(u << 1, l, r, c);
    if (r > mid)
      modify(u << 1 | 1, l, r, c);
    pushup(u);
  }
}
void build(int u, int l, int r) {
  tr[u] = {l, r, 1, 0};
  if (l == r) {
    return;
  } else {
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    memset(tr, 0, sizeof tr);
    int n, m;
    cin >> n >> m;
    build(1, 1, n);
    for (int i = 0; i < m; i++) {
      int l, r, c;
      cin >> l >> r >> c;
      modify(1, l, r, c);
    }
    printf("Case %lld: The total value of the hook is %lld.\n", i,
           query(1, 1, n));
  }
}



imnoob
9天前
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

// using ll = long long;
// using vi = vector<long long>;
// using vvi = vector<vector<long long>>;
const long long N = 1e5 + 10;
struct node {
  long long l, r, v, t;
} tr[N << 2];
__inline__ void pushup(long long u) { tr[u].v = tr[u << 1 | 1].v + tr[u << 1].v; }
__inline__ void pushdown(long long u) {
  if (tr[u].t) {
    node &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
    l.t += root.t;
    l.v += (l.r - l.l + 1) * root.t;
    r.v += (r.r - r.l + 1) * root.t;
    r.t += root.t;
    root.t = 0;
  }
}
void build(long long u, long long l, long long r) {
  tr[u] = {l, r, 0, 0};
  if (l == r) {
    cin >> tr[u].v;
    return;
  }
  long long mid = (tr[u].l + tr[u].r) >> 1;
  build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  pushup(u);
}
void modify(long long u, long long l, long long r, long long c) {
  if (l <= tr[u].l && r >= tr[u].r) {
    tr[u].t += c;
    tr[u].v += (tr[u].r - tr[u].l + 1) * c;
  } else {
    pushdown(u);
    long long mid = (tr[u].r + tr[u].l) >> 1;
    if (l <= mid)
      modify(u << 1, l, r, c);
    if (r > mid)
      modify(u << 1 | 1, l, r, c);
    pushup(u);
  }
}
long long query(long long u, long long l, long long r) {
  if (l <= tr[u].l && r >= tr[u].r) {
    return tr[u].v;
  } else {
    pushdown(u);
    long long mid = (tr[u].r + tr[u].l) >> 1;
    long long v = 0;
    if (l <= mid)
      v = query(u << 1, l, r);
    if (r > mid)
      v += query(u << 1 | 1, l, r);
    return v;
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, m;
  cin >> n >> m;
  build(1, 1, n);
  // cerr << 1;
  for (long long i = 0; i < m; i++) {
    char op;
    cin >> op;
    if (op == 'Q') {
      long long a, b;
      cin >> a >> b;
      cout << query(1, a, b) << '\n';
      // cerr << 1;
    } else {
      long long a, b, c;
      cin >> a >> b >> c;
      modify(1, a, b, c);
    }
  }
}


活动打卡代码 AcWing 4340. 我讨厌它

imnoob
10天前
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int N = 2e5 + 10;
struct node {
  int l, r, v;
} tr[N << 2];
__inline__ void pushup(int u) { tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v); }
void build(int u, int l, int r) {
  tr[u] = {l, r, 0};
  if (l == r) {
    cin >> tr[u].v;
    return;
  }
  int mid = (l + r) >> 1;
  build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  pushup(u);
}
void modify(int u, int n, int x) {
  if (tr[u].l == tr[u].r && tr[u].l == n) {
    tr[u].v = x;
  } else {
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (mid >= n) {
      modify(u << 1, n, x);
    } else {
      modify(u << 1 | 1, n, x);
    }
    pushup(u);
  }
}
int query(int u, int l, int r) {
  if (l <= tr[u].l && tr[u].r <= r) {
    return tr[u].v;
  } else {
    int mid = (tr[u].l + tr[u].r) >> 1;
    int k = 0;
    if (l <= mid) {
      k = query(u << 1, l, r);
    }
    if (r > mid) {
      k = max(k, query(u << 1 | 1, l, r));
    }
    return k;
  }
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  while (cin >> n >> m) {
    memset(tr, 0, sizeof tr);
    build(1, 1, n);
    for (int i = 0; i < m; i++) {
      char op;
      int a, b;
      cin >> op >> a >> b;
      if (op == 'Q') {
        cout << query(1, a, b) << '\n';
      } else {
        modify(1, a, b);
      }
    }
  }
}


活动打卡代码 AcWing 4339. 敌兵布阵

imnoob
10天前

线段树做法

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int N = 5e4 + 10;
struct node {
  int l, r, v;
} tr[N << 2];
void pushup(int u) { tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v; }
void build(int u, int l, int r) {
  tr[u] = {l, r, 0};
  if (l == r) {
    cin >> tr[u].v;
    return;
  }
  int mid = (l + r) >> 1;
  build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  pushup(u);
}
int query(int u, int l, int r) {
  if (tr[u].l >= l && tr[u].r <= r) {
    return tr[u].v;
  }
  int mid = (tr[u].l + tr[u].r) >> 1;
  int v = 0;
  if (l <= mid)
    v += query(u << 1, l, r);
  if (r > mid)
    v += query(u << 1 | 1, l, r);
  return v;
}
void modify(int u, int n, int x) {
  if (tr[u].l == tr[u].r && n == tr[u].l) {
    tr[u].v += x;
  } else {
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (mid < n)
      modify(u << 1 | 1, n, x);
    else if (mid >= n)
      modify(u << 1, n, x);
    pushup(u);
  }
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    printf("Case %lld:\n", i);
    memset(tr, 0, sizeof tr);
    int n;
    cin >> n;
    build(1, 1, n);
    string op;
    while (cin >> op, op != "End") {
      if (op == "Query") {
        int l, r;
        cin >> l >> r;
        printf("%lld\n", query(1, l, r));
      } else if (op == "Add") {
        int n, x;
        cin >> n >> x;
        modify(1, n, x);
      } else {
        int n, x;
        cin >> n >> x;
        modify(1, n, -x);
      }
    }
  }
}

树状数组做法

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int N = 5e4 + 10;
int tr[N];
int n;
inline int lowbit(int x) { return x & -x; }
void update(int x, int c) {
  for (int i = x; i <= n; i += lowbit(i))
    tr[i] += c;
}
int query(int c) {
  int res = 0;
  for (int i = c; i; i -= lowbit(i)) {
    res += tr[i];
  }
  return res;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    printf("Case %lld:\n", i);
    memset(tr, 0, sizeof tr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
      int p;
      cin >> p;
      update(i, p);
      // cerr << query(i) << ' ';
    }
    string op;
    while (cin >> op, op != "End") {
      if (op == "Add") {
        int n, x;
        cin >> n >> x;
        update(n, x);
      } else if (op == "Sub") {
        int n, x;
        cin >> n >> x;
        update(n, -x);
      } else {
        int l, r;
        cin >> l >> r;
        printf("%lld\n", query(r) - query(l - 1));
      }
    }
  }
}


活动打卡代码 AcWing 4339. 敌兵布阵

imnoob
10天前
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int N = 5e4 + 10;
struct node {
  int l, r, v;
} tr[N << 2];
void pushup(int u) { tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v; }
void build(int u, int l, int r) {
  tr[u] = {l, r, 0};
  if (l == r) {
    cin >> tr[u].v;
    return;
  }
  int mid = (l + r) >> 1;
  build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  pushup(u);
}
int query(int u, int l, int r) {
  if (tr[u].l >= l && tr[u].r <= r) {
    return tr[u].v;
  }
  int mid = (tr[u].l + tr[u].r) >> 1;
  int v = 0;
  if (l <= mid)
    v += query(u << 1, l, r);
  if (r > mid)
    v += query(u << 1 | 1, l, r);
  return v;
}
void modify(int u, int n, int x) {
  if (tr[u].l == tr[u].r && n == tr[u].l) {
    tr[u].v += x;
  } else {
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (mid < n)
      modify(u << 1 | 1, n, x);
    else if (mid >= n)
      modify(u << 1, n, x);
    pushup(u);
  }
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    printf("Case %lld:\n", i);
    memset(tr, 0, sizeof tr);
    int n;
    cin >> n;
    build(1, 1, n);
    string op;
    while (cin >> op, op != "End") {
      if (op == "Query") {
        int l, r;
        cin >> l >> r;
        printf("%lld\n", query(1, l, r));
      } else if (op == "Add") {
        int n, x;
        cin >> n >> x;
        modify(1, n, x);
      } else {
        int n, x;
        cin >> n >> x;
        modify(1, n, -x);
      }
    }
  }
}