Udsnf

3162

Udsnf
2个月前

# 没思路

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool cmp(string &s1, string &s2)
{
if (s1.size() > s2.size() || (s1.size() == s2.size() && s1 >= s2)) return true;
else return false;
}

vector<int> sub(vector<int> &a, vector<int> &b)
{
vector<int> res;
int t = 0;
for (int i = 0; i < a.size(); ++i) {
t = a[i] - t;
if (i < b.size()) {
t -= b[i];
}
res.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
for (int i = res.size() - 1; i > 0 && res[i] == 0; --i) res.pop_back();
return res;
}

int main()
{
string s1, s2;
cin >> s1 >> s2;
vector<int> a, b, res;
for (int i = s1.size() - 1; i >= 0; --i) a.push_back(s1[i] - '0');
for (int i = s2.size() - 1; i >= 0; --i) b.push_back(s2[i] - '0');
if (cmp(s1, s2)) res = sub(a, b);
else {
res = sub(b, a);
cout << '-';
}
for (int i = res.size() - 1; i >= 0; --i) cout << res[i];
cout << endl;
return 0;
}


Udsnf
2个月前

# 压9位

#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int base = 1e9;

{
vector<int> res;
if (A.size() < B.size()) return add(B, A);
int c = 0;
for (int i = 0; i < A.size(); ++i) {
c += A[i];
if (i < B.size()) c += B[i];
res.push_back(c % base);
c /= base;
}
return res;
}

int main()
{
string a, b;
cin >> a >> b;
vector<int> A, B;
for (int i = a.size() - 1, t = 0, j = 0, bs = 1; i >= 0; --i) {
++j;
t += (a[i] - '0') * bs;
bs *= 10;
if (j == 9 || i == 0) {
A.push_back(t);
t = j = 0;
bs = 1;
}
}
for (int i = b.size() - 1, t = 0, j = 0, bs = 1; i >= 0; --i) {
++j;
t += (b[i] - '0') * bs;
bs *= 10;
if (j == 9 || i == 0) {
B.push_back(t);
t = j = 0;
bs = 1;
}
}
cout << sum[sum.size() - 1];
for (int i = sum.size() - 2; i >= 0; --i) printf("%09d", sum[i]);
cout << endl;
return 0;
}


# 不压位

## 数组实现

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

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

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


## 字符串实现

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

{
string sum;
int u = 0;
int i = a.length() - 1, j = b.length() - 1;
while (i >= 0 && j >= 0) {
int t = (a[i--] - '0') + (b[j--] - '0') + u;
//cout << "t is " << t << endl;
sum += t % 10 + '0';
u = t / 10;
}
while (i >= 0) {
int t = a[i--] - '0' + u;
sum += t % 10 + '0';
u = t / 10;
}
while (j >= 0) {
int t = a[j--] - '0' + u;
sum += t % 10 + '0';
u = t / 10;
}
if (u) sum += '1';
reverse(sum.begin(), sum.end());
return sum;
}

int main()
{
string a, b;
cin >> a >> b;
for (auto i : c) cout << i;
cout << endl;
return 0;
}


Udsnf
2个月前

# 没思路

#include <cstdio>

int main()
{
double n;
scanf("%lf", &n);
double l = -100, r = 100, mid;
while (r - l > 1e-8) {
mid = (l + r) / 2;
if (mid * mid * mid <= n) l = mid;
else r = mid;
}
printf("%.6lf\n", mid);
return 0;
}


Udsnf
2个月前
#include <cstdio>
const int N = 1e5 + 10;
int a[N];

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

while (q--) {
int k;
scanf("%d", &k);
int start = -1, end = -1;
int i = 0, j = n - 1;
while (i < j) {
int mid = i + j >> 1;
if (a[mid] >= k) j = mid;
else i = mid + 1;
}
if (a[i] == k) start = i;
i = 0, j = n - 1;
while (i < j) {
int mid = i + j + 1 >> 1;
if (a[mid] <= k) i = mid;
else j = mid - 1;
}
if (a[i] == k) end = i;
printf("%d %d\n", start, end);
}
return 0;
}


Udsnf
2个月前
#include <cstdio>
const int N = 1e5 + 5;
int a[N];
typedef long long ll;

ll rpair(int l, int r)
{
if (l >= r) return 0;
int mid = l + r >> 1;
ll res = rpair(l, mid) + rpair(mid + 1, r);
int i = l, j = mid + 1, k = 0;
int len = r - l + 1, tmp[len];
while (i <= mid && j <= r) {
if (a[i] > a[j]) {
res += (mid - i + 1);
tmp[k++] = a[j++];
}
else {
tmp[k++] = a[i++];
}
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (int u = 0; u < len; ++u) {
a[l + u] = tmp[u];
}
return res;
}

int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
printf("%lld\n", rpair(0, n - 1));
return 0;
}


Udsnf
2个月前
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int a[N],t[N], n;

void Msort(int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
Msort(l, mid);
Msort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) t[k++] = a[i++];
else t[k++] = a[j++];
}
while (i <= mid) t[k++] = a[i++];
while (j <= r) t[k++] = a[j++];
for (int u = 0; u < k; ++u) a[l + u] = t[u];
}

int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
Msort(0, n - 1);
for (int i = 0; i < n; ++i) printf("%d ", a[i]);
return 0;
}


Udsnf
3个月前

# yls 思路

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
char t[N];
int main()
{
string s;
int k;
cin >> s >> k;
int i = -1;
for (auto c : s)
{
while (i >= 0 && c < t[i] && k)
{
--i;
--k;
}
t[++i] = c;
}
while (k--)
{
--i;
}
if (i < 0) cout << 0 << endl;
for (int j = 0, f = 0; j <= i; ++j)
{
if (!f && t[j] != '0') f = 1;
if (f) cout << t[j];
}
return 0;
}



# yls code C++ style

#include <bits/stdc++.h>
using namespace std;

int main()
{
string s;
int k;
cin >> s >> k;
string res = "0";
for (auto c : s)
{
while (c < res.back() && k)
{
--k;
res.pop_back();
}
res.push_back(c);
}
while (k--) res.pop_back();
int i = 0;
while (i < res.size() && res[i] == '0') ++i;
if (i == res.size()) cout << 0 << endl;
else cout << res.substr(i) << endl;
return 0;
}


Udsnf
3个月前

# 递归版本不会写

yls思路
pre指向反转后链表的头部

ListNode * pre = nullptr;
class Solution {
public:
auto nxt = head -> next;
return reverseList(nxt);
}
};



class Solution {
public:
ListNode* pre = nullptr;
}
{
auto nxt = head -> next;
return reverse(nxt, pre);
}
};


# 另一种递归

class Solution {
public:
auto r = reverseList(head -> next);
return r;
}
};


# 迭代版本 背熟了

class Solution {
public:
auto dummy = new ListNode(-1);
{
auto nxt = head -> next;
head -> next = dummy -> next;
}
return dummy -> next;
}
};


Udsnf
3个月前

# 不熟练

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int fast_pow(int a, int b, int p)
{
int res = 1;
while (b)
{

int d = b & 1;
b >>= 1;
if (d) res = (LL)res * a % p;
a = (LL)a * a % p;
}
return res;
}

int main()
{
int n;
cin >> n;
while (n--)
{
int a, b, p;
cin >> a >> b >> p;
cout << fast_pow(a, b, p) << endl;
}
return 0;
}


Udsnf
3个月前

# 没思路

leetcode 样例都没过。

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
{

{
return;
}
// cout << head -> val << endl;
// if (tail) cout << tail -> val << endl;
// else cout << "tail is null" << endl;
// cout << "===" << endl;
int t = head -> val;
auto left = new ListNode(-1), mid = new ListNode(-1), right = new ListNode(-1),
pl = left, pm = mid, pr = right, p = head;
while (p)
{
auto nxt = p -> next;
if (p -> val < t)
{
p -> next = pl -> next;
pl -> next = p;
pl = pl -> next;
}
else if(p -> val == t)
{
p -> next = pm -> next;
pm -> next = p;
pm = pm -> next;
}
else
{
p -> next = pr -> next;
pr -> next = p;
pr = pr -> next;
}
p = nxt;
}
qs(left -> next, pl);
qs(right -> next, pr);
if (left -> next)
{
pl -> next = mid -> next;
if (right -> next)
{
pm -> next = right -> next;
tail = pr;
}
else
tail = pm;
}
else
{
if (right -> next)
{
pm -> next = right -> next;
tail = pr;
}
else
tail = pm;
}
}
while (tail && tail -> next)
tail = tail -> next;
}
};


# ylsNB

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
{
}
auto left = new ListNode(-1), mid = new ListNode(-1), right = new ListNode(-1);
auto ltail = left, mtail = mid, rtail = right;
int val = head -> val;
for (auto p = head; p; p = p -> next)
{
if (p -> val < val) ltail = ltail -> next = p;
else if (p -> val == val) mtail = mtail -> next = p;
else rtail = rtail -> next = p;
}
ltail -> next = mtail -> next = rtail -> next = NULL;
left -> next = sortList(left -> next);
right -> next = sortList(right -> next);
get_tail(left) -> next = mid -> next;
mtail -> next = right -> next;
return left -> next;
}
};