头像

darkFlameMaster


访客:576

离线:2天前


活动打卡代码 AcWing 792. 高精度减法

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

bool cmp(vector<int> A, vector<int> B) {
  if (A.size() != B.size()) return A.size() > B.size();
  for (int i = A.size() - 1; i >= 0; i--)
    if (A[i] != B[i]) return A[i] > B[i];

  return true;
}

vector<int> sub(vector<int> A, vector<int> B) {
  vector<int> C;
  int t = 0;
  for (int i = 0; i < A.size(); i++) {
    if (t < 0) t = 1; else t = 0;
    t = A[i] - t;
    if (i < B.size()) t -= B[i];
    C.push_back((t+10)%10);
  }
  while (C.size() > 1 && C.back() == 0) C.pop_back();
  return C;
}

int main() {
  string a, b;
  vector<int> A, B;
  cin >> a >> b;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

  vector<int> C;

  if (cmp(A, B)) C = sub(A, B);
  else C = sub(B, A), cout << '-';

  for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
  cout << endl;

  return 0;
}



活动打卡代码 AcWing 791. 高精度加法

#include <bits/stdc++.h>

using namespace std;

vector<int> add(vector<int> A, vector<int> B) {
  vector<int> C;
  int i = 0;
  int c = 0;
  while (i < A.size() || i < B.size()) {
    if (i < A.size()) c += A[i];
    if (i < B.size()) c += B[i];
    C.push_back(c % 10);
    c = c / 10;
    i++;
  }
  if (c) C.push_back(c);
  return C;
}

int main() {
  string a, b;
  vector<int> A, B;
  cin >> a >> b;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

  auto C = add(A, B);
  for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
  cout << endl;

  return 0;
}




活动打卡代码 AcWing 867. 分解质因数

```
#include [HTML_REMOVED]

using namespace std;

void divide(int x) {
for (int i = 2; i <= x / i; i) {
if (x % i == 0) {
int s = 0;
while (x % i == 0) x /= i, s
;
cout << i << ” ” << s << endl;
}
}
if (x > 1) cout << x << ” ” << 1 << endl;
return ;
}

int main() {
int n; cin >> n;
while (n–) {
int a;
cin >> a;
divide(a);
cout << endl;
}
return 0;
}

```




#include <bits/stdc++.h>

using namespace std;

int n;

int main() {
  cin >> n;
  while (n--) {
    int a;
    scanf ("%d", &a);
    bool pri = true;
    if (a == 1) pri = false;
    for (int i = 2; i <= sqrt(a); i++) {
      if (a % i == 0) {pri = false; break;}
    }
    if (pri) puts ("Yes");
    else puts("No");
  }

  return 0;
}



活动打卡代码 AcWing 1273. 天才的记忆

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

using namespace std;

const int N = 200010, M = 18;

int n, m;
int q[N];
int f[N][M];

void init() {
  for (int j = 0; j < M; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      if (!j) f[i][j] = q[i];
      else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}

int query(int l, int r) {
  int k  = log(r - l + 1) / log(2);

  return max(f[l][k], f[r - (1 << k) + 1][k]);
}

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

  init();

  cin >> m;
  while (m--) {
    int l, r;
    scanf ("%d%d", &l, &r);
    printf ("%d\n", query(l, r));
  }
}


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

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int p[N];

int main() {
  cin >> n;
  for (int i = 0; i <= n; i++) cin >> p[i];

  sort(p, p + n);

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

  cout << res << endl;

  return 0;
}



活动打卡代码 AcWing 913. 排队打水

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int t[N];

int main() {
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> t[i];

  sort(t, t + n);

  LL ac = 0;
  LL sum = 0;
  for (int i = 0; i < n; i++) {
    sum += ac;
    ac += t[i];
  }

  cout << sum << endl;
}



#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
PII segs[N];

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

  sort(segs, segs + n);

  int cnt = 0;
  int pre = -0x3f3f3f3f;
  for (int i = 0; i < n; i++) {
    int l = segs[i].second, r = segs[i].first;
    if (pre >= l) continue;
    pre = r;
    cnt++;
  }

  cout << cnt << endl;
  return 0;
}


活动打卡代码 AcWing 905. 区间选点

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
PII segs[N];

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

  sort(segs, segs + n);

  int cnt = 0;
  int pre = -0x3f3f3f3f;
  for (int i = 0; i < n; i++) {
    int l = segs[i].second, r = segs[i].first;
    if (pre >= l) continue;
    pre = r;
    cnt++;
  }

  cout << cnt << endl;
  return 0;
}



#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n1, n2, m;
int h[N], e[N], ne[N], idx;
int match[N];
bool st[N];

void add(int a, int b) {
  e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool find(int x) {
  for (int i = h[x]; i != -1; i = ne[i]) {
    int j = e[i];
    if (!st[j]) {
      st[j] = true;
      if(!match[j] || find(match[j])) {
    match[j] = x;
    return true;
      }
    }
  }

  return false;
}

int main() {
  memset(h, -1, sizeof h);

  cin >> n1 >> n2 >> m;
  while (m--) {
    int a, b;
    cin >> a >> b;
    add(a, b);
  }

  int res = 0;
  for (int i = 1; i <= n1; i++) {
    memset(st, false, sizeof st);
    if (find(i)) res++;
  }

  cout << res << endl;

  return 0;
}