没思路

#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;
}

压9位

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

vector<int> add(vector<int> &A, vector<int> &B) 
{
    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;
        }
    }
    auto sum = add(A, B);
    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;

vector<int> add(vector<int> &A, vector<int> &B)
{
    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');
    auto sum = add(A, B);
    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 add(string &a, string &b)
{
    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;
    string c = add(a, b);
    for (auto i : c) cout << i;
    cout << endl;
    return 0;
}

没思路

#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;
}

#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;
}

#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;
}

#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;
}

yls 思路

这就属于没理解本质，然后下次做还是不会的类型。
考虑顺序即从小到大(准确的说是非递减序)，一定是删除最后的k个数，否则后面大的数前移可能会导致答案变大。
再考虑局部，两个相邻的数，如果构成逆序，一定要删除大的那个，否则其他方案有可能不会构成最优，故本质是贪心。

#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;
}

递归版本不会写

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

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

奇怪的是leetcode提交后就“执行出错了”
改成如下版本就AC

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

另一种递归

这个是yls的思路，上一个是yls的迭代思路，我给写成递归了。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head -> next) return head;
        auto r = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = nullptr;
        return r;
    }
};

迭代版本 背熟了

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

不熟练

#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;
}

没思路

看到思路，想着自己实现一下，gg了。
leetcode 样例都没过。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void qs(ListNode* head, ListNode* tail)
    {

        if (!head || head == tail) 
        {
            // cout << "(!head || head == tail)" << endl;
            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;
            head = left;
            if (right -> next)
            {
                pm -> next = right -> next;
                tail = pr;
            }
            else
                tail = pm;
        }
        else
        {
            head = mid;
            if (right -> next)
            {
                pm -> next = right -> next;
                tail = pr;
            }
            else
                tail = pm;
        }
    }
    ListNode* sortList(ListNode* head) {
        auto tail = head;
        while (tail && tail -> next)
            tail = tail -> next;
        qs(head, tail);
        return head;
    }
};

ylsNB

/**
 * Definition for singly-linked list.
 * 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:
    ListNode* get_tail(ListNode* head)
    {
        while (head -> next) head = head -> next;
        return head;
    }
    ListNode* sortList(ListNode* head) {
        if (!head || !head -> next) return head;
        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;
    }
};