头像

zhangxu




离线:4个月前



zhangxu
2020-03-15 08:04

题目描述

blablabla

还有 交换链表节点的 待补
看了 yxc 已补 自己写的 其实没有mid这个 一直wa 最后看了视频想了回 一样大的 应该插中间 直接放后面导致链表没有拍对

样例

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

    ListNode* get_tail(ListNode* head) {
        while(head->next != NULL) head = head->next;
        return head;
    }

    ListNode* quickSortList(ListNode* head) {
        // QuiSort(headm NULL); return head; // 交换val的
        // 归并排序 也是交换val;
        // return ListMergeSort(head);

        if(head == NULL) return head;

        ListNode* left = new ListNode(-1);
        ListNode* mid = new ListNode(-1);
        ListNode* right = new ListNode(-1);
        ListNode* ltail = left;
        ListNode* mtail = mid;
        ListNode* rtail = right;

        int k = head->val;
        for(ListNode* p = head; p != NULL; p = p->next) {
            if(p->val < k) ltail->next = p, ltail = ltail->next;
            else if(p->val == k) mtail->next = p, mtail = mtail->next;
            else rtail->next = p, rtail = rtail->next;
        }

        ltail->next = NULL, mtail->next = NULL, rtail->next = NULL;

        left->next = quickSortList(left->next);
        right->next = quickSortList(right->next);

        get_tail(left)->next = mid->next;
        get_tail(left)->next = right->next;
        return left->next;
    }



    void QuickSort(ListNode* l, ListNode* r) {
        if (l == r) return;
        // printf("%d %d\n", l?l->val:0, r?r->val:0);
        ListNode* cur = l; 
        int key = l->val;
        ListNode* p = l->next;
        while(p != r) {
            if (p->val < key) {
                cur = cur->next; 
                swap(p->val, cur->val);
            }
            p = p->next;
        }
        swap(l->val, cur->val);
        QuickSort(l, cur);
        QuickSort(cur->next, r);
    }

    ListNode* ListMergeSort(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* pFast = head;
        ListNode* pSlow = head;
        // 中间节点,快慢指针
        while (pFast != NULL && pFast->next == NULL) {
            pFast = pFast->next->next;
            pSlow = pSlow->next;
        }
        pFast = pSlow;
        pSlow = pSlow->next; 
        pFast->next = NULL;// 分割成2段
        head = ListMergeSort(head);
        pSlow = ListMergeSort(pSlow);
        head = merge(head, pSlow);
        return head;
    };

    ListNode* merge(ListNode* p1, ListNode* p2) {
        if (p1 == NULL || p2 == NULL) {
            return p1 == NULL ? p2 : p1;
        }
        // 找出合并后的链表头
        ListNode* head = NULL;
        if (p1->val > p2->val) {
            head = p2;
            p2 = p2->next;
        } else {
            head = p1;
            p1 = p1->next;
        }
        // 将2个链表中值较小的节点依次链接到结果链表中
        ListNode* res = head;
        while (p1 != NULL && p2 != NULL) {
            if (p1->val > p2->val) {
                head->next = p2;
                p2 = p2->next;
            } else {
                head->next = p1;
                p1 = p1->next;
            }
            head = head->next;
        }
        if (p1 == NULL) head->next = p2;
        else head->next = p1;
        return res;
    }

};

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



zhangxu
2020-02-08 09:41

17点49分改:
想了好久64M肯定够了,
发现问题 大小写L, l 打fan了
线段树已经过了 ma=-1 改成-inf 就行
-----------------------------------------
醉了 在acber 那个应用做了下 4分钟敲完线段树 mle了 我还敲了2次在那个应用上
到原题这里 还mle 就上st表了

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

// const int N = 2e5 + 5;
// int n, m;
// int a[N << 2];

// void build(int l, int r, int rt) {
//     if(l == r) {
//         cin >> a[rt];
//         return ;
//     }
//     int mid = l + r >> 1;
//     build(l, mid, rt << 1);
//     build(mid + 1, r, rt << 1 | 1);
//     a[rt] = max(a[rt << 1], a[rt << 1 | 1]);
// }

// int query(int L, int R, int l, int r, int rt) {
//     if(l <= L && R >= r) {
//         return a[rt];
//     }
//     int mid = l + r >> 1, ma = -1;
//     if(L <= mid) ma = max(ma, query(L, R, l, mid, rt << 1));
//     if(R > mid) ma = max(ma, query(L,R,mid + 1, r,rt << 1 | 1));
//     return ma;
// }

// int main() {
//     cin >> n;
//     build(1, n, 1);
//     cin >> m;
//     for(int i = 1, a, b; i <= m; i++) {
//         cin >> a >> b;
//         cout << query(a, b, 1, n, 1) << endl;
//     }
//     return 0;
// }
#include <cstdio>
#include <iostream>
using namespace std;

const int maxn = 2e5 + 5;

int lg[maxn];
int a[maxn], f[maxn][30];

int n, m;

void STbuild() {
    for(int i = 1; i <= n; i ++ ) f[i][0] = a[i];
    int t = (lg[n]-1)/(lg[2]-1) + 1;
    for(int j = 1; j < t; j ++ ) {
        for(int i = 1; i <= n - (1 << j) + 1; i ++ ) {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int STquery(int l, int r){
    int k = (lg[r - l + 1] - 1);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main() {
    for(int i = 1; i < maxn; i ++){
        lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);
    }


    scanf("%d", &n);

    for(int i = 1; i <= n; i ++){

        scanf("%d", &a[i]);
    }

    scanf("%d", &m);
    STbuild();
    for(int i = 1; i <= m; i ++) {
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", STquery(x, y));
    }
    return 0;
}



zhangxu
2019-09-08 14:29

感觉 书上写的 如果状态转移复杂了 不好对付
有等可能的挺在原地 或者是 掉到之前某个点 计算就必须 单独分开 而不能 直接 每次for ++ 了
按照 直接理解重写了分 同事 2019 南昌网络赛 D 题 也是 差不多的思路

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, m;
int head[maxn], cnt;
int to[maxn], nxt[maxn];
int from[maxn], pre[maxn], come[maxn], val[maxn], tot;
int out[maxn], deg[maxn];
double dis[maxn];

void cometo(int a, int b, int c) {
    come[++ tot] = b, val[tot] = c;
    pre[tot] = from[a],  from[a] = tot;
}

void ade(int a, int b) {
    to[++ cnt] = b;
    nxt[cnt] = head[a], head[a] = cnt;
}

double redis(int u) {
    if(u == n) return 0;
    double res = 0;
    for(int i = from[u]; i; i = pre[i]) {
        res += (dis[come[i]] + 1.0 * val[i]) / deg[u];
    }
    return res;
}

void topsort() {
    queue<int> que;
    que.push(n);
    while(!que.empty()) {
        int x = que.front(); que.pop();
        dis[x] = redis(x);
        for(int i = head[x]; i; i = nxt[i]) {
            out[to[i]] --;
            if(out[to[i]] == 0) que.push(to[i]);
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1, a, b, c; i <= m; ++ i) {
        scanf("%d %d %d", &a, &b, &c);
        cometo(a, b, c), ade(b, a);
        deg[a] ++, out[a] ++;
    }
    topsort();
    printf("%.2lf\n", dis[1]);
    return 0;
}


活动打卡代码 AcWing 267. 莫基亚

zhangxu
2019-08-21 05:23

终于过了

```




zhangxu
2019-08-07 01:05

题目链接 https://www.acwing.com/problem/content/382/

我感觉 是我dinic完 给tarjan跑的图 建图写错了
虽然最后 一直改 试输出 给AC了orz 但是不理解

错误的代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 150000 + 100;

int n, m, k;
int s, t;
int head[maxn], depth[maxn], cur[maxn], cnt;
int nxt[maxn << 2], to[maxn << 2], cap[maxn << 2];  

void ade(int a, int b, int c) {
    to[++cnt] = b;
    cap[cnt] = c;
    nxt[cnt] = head[a];
    head[a] = cnt;
}

bool bfs(){
    queue<int> que;
    que.push(s);
    memset(depth, 0, sizeof(depth));
    depth[s] = 1;
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; i != -1; i = nxt[i]) {
            if(cap[i] > 0 && depth[to[i]] == 0) {
                depth[to[i]] = depth[u] + 1;
                que.push(to[i]);
            }
        }
    }
    if(depth[t]) return 1;
    else return 0;
}

int dfs(int u, int dist) {
    if(u == t) return dist;
    for(int &i = cur[u]; i != -1; i = nxt[i]) {
        if(depth[to[i]] == depth[u] + 1 && cap[i] > 0) {
            int tmp = dfs(to[i], min(dist, cap[i]));
            if(tmp > 0) {
                cap[i] -= tmp;
                cap[i ^ 1] += tmp;
                return tmp; 
            }
        }
    }
    return 0;
}

int dinic() {
    int res = 0, d;
    while(bfs()) {
        for(int i = 0; i < n + m + 5; i ++) cur[i] = head[i];
        while(d = dfs(s, INF)) res += d;
    }
    return res;
}

int dfn[maxn], low[maxn];
bool vis[maxn];
stack<int> stac;
int scc_cnt, idx, cmp[maxn];

int thead[maxn], tcnt;
int tto[maxn << 2], tnxt[maxn << 2];

void tade(int a, int b) {
    tto[++ tcnt] = b;
    tnxt[tcnt] = thead[a];
    thead[a] = tcnt;
}

void tarjan(int x) {
    dfn[x] = low[x] = ++idx;
    stac.push(x);
    vis[x]=true;
    for(int i = thead[x]; i; i = tnxt[i]) {
        int u = tto[i];
        if(!dfn[u]) {
            tarjan(u);
            low[x] = min(low[x], low[u]);
        } else if(vis[u])low[x] = min(low[x], dfn[u]);
    }//tarjan模板
    int k;
    if(low[x] == dfn[x]) {
        ++scc_cnt;
        do {
            k = stac.top();
            stac.pop();
            vis[k] = false;
            cmp[k] = scc_cnt;
        } while(x!=k);
    }
}

int a[maxn], b[maxn], e[maxn];

int main() {
    cin >> n >> m >> k;
    memset(head, -1, sizeof(head));
    cnt = -1;
    for(int i = 1; i <= k; i ++) {
        cin >> a[i] >> b[i];
        ade(a[i], b[i] + n, 1), e[i] = cnt;
        ade(b[i] + n, a[i], 0);
    }                                       
    s = 0, t = n + m + 1;
    for(int i = 1; i <= n; i ++) ade(s, i, 1), ade(i, s, 0);
    for(int i = 1; i <= m; i ++) ade(i + n, t, 1), ade(t, i + n, 0);
    dinic();

    for(int u = 0; u <= n + m + 1; u ++) for(int i = head[u]; ~i; i = nxt[i])
            if(cap[i]) tade(u, to[i]);

    for(int i = 0; i <= n + m + 1; i ++) 
        if(!dfn[i]) tarjan(i);

    int ans = k;
    for(int i = 1; i <= k; i++) 
        if(cmp[a[i]] == cmp[b[i] + n] || !cap[e[i]])
            ans --;

    cout << ans << endl;
    for(int i = 1; i <= k; i ++) {
        if(cmp[a[i]] != cmp[b[i] + n] && cap[e[i]]) {
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

编译器报了什么错误?Compile Error? Runtime Error?



活动打卡代码 AcWing 211. 计算系数

zhangxu
2019-08-06 00:56
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int mod = 10007;
int a, b, n, m, k;
int f[maxn][maxn];

int q_mod(int a, int b, int mod) {
    int res = 1;
    for(; b; b >>= 1) {
        if(b & 1) res = 1ll* res * a % mod;
        a = 1ll * a * a % mod;
    }
    return res;
}

void init() {
    f[0][0] = 1, f[1][0] = f[1][1] = 1;
    for(int i = 2; i < maxn; i ++) {
        f[i][0] = 1, f[i][i] = 1;
        for(int j = 1; j <= i; j ++) {
            f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % mod;
        }
    }
}

int main() {
    init();
    cin >> a >> b >> k >> n >> m;
    cout << (((q_mod(a, n, mod) * q_mod(b, m, mod)) % mod) * f[k][n]) % mod << endl;
    return 0;
}




活动打卡代码 AcWing 176. 装满的油箱

zhangxu
2019-07-31 12:40

应该叫不叫DJ 就是搜索搜到t 不需要开什么d[][]数组。。。 orz

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;

int head[maxn], fcst[maxn], cnt;
int nxt[maxn * 20], to[maxn * 20], dis[maxn * 20];
bool vis[maxn][105];

struct node{
    int u, f, cst;
    bool operator < (const node & a) const {
        return cst > a.cst;
    }
};

void ade(int a, int b, int v) {
    to[++cnt] = b, dis[cnt] = v;
    nxt[cnt] = head[a], head[a] = cnt;
    to[++cnt] = a, dis[cnt] = v;
    nxt[cnt] = head[b], head[b] = cnt;
}

int dj(int c, int s, int t){
    priority_queue<node> que;
    memset(vis, 0, sizeof vis);
    que.push(node{s, 0, 0});
    while(!que.empty()) {
        node p = que.top(); que.pop();
        if(p.u == t) return p.cst;
        if(vis[p.u][p.f]) continue;
        vis[p.u][p.f] = 1;
        if(p.f < c && !vis[p.u][p.f + 1]) {
            que.push(node{p.u, p.f + 1, p.cst + fcst[p.u]});
        }
        for(int i = head[p.u]; i; i = nxt[i]) {
            int v = to[i];
            if(p.f >= dis[i] && !vis[v][p.f - dis[i]]) {
                que.push(node{v, p.f - dis[i], p.cst});
            }
        }
    }
    return -1;
}

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i ++) cin >> fcst[i];
    for(int i = 1, a, b, c; i <= m; i ++) 
        cin >> a >> b >> c, ade(a, b, c);
    cin >> m;
    for(int i = 1, c, s, t; i <= m; i ++) {
        cin >> c >> s >> t;
        int ans = dj(c, s, t);
        if(ans == -1) cout << "impossible\n";
        else cout << ans << endl;
    }
    return 0;
}


活动打卡代码 AcWing 374. 导弹防御塔

zhangxu
2019-07-29 12:45

这题得开多少啊 哭了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 50000;

int n, m;
double t1, t2, v;
int s, t;
int head[maxn], depth[maxn], cur[maxn], cnt;
int nxt[maxn << 3], to[maxn << 3], cap[maxn << 3];  

void ade(int a, int b, int c) {
    to[cnt] = b;
    cap[cnt] = c;
    nxt[cnt] = head[a];
    head[a] = cnt ++;
}

bool bfs(){
    queue<int> que;
    que.push(s);
    memset(depth, 0, sizeof(depth));
    depth[s] = 1;
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; i != -1; i = nxt[i]) {
            if(cap[i] > 0 && depth[to[i]] == 0) {
                depth[to[i]] = depth[u] + 1;
                que.push(to[i]);
            }
        }
    }
    if(depth[t]) return 1;
    else return 0;
}

int dfs(int u, int dist) {
    if(u == t) return dist;
    for(int &i = cur[u]; i != -1; i = nxt[i]) {
        if(depth[to[i]] == depth[u] + 1 && cap[i] > 0) {
            int tmp = dfs(to[i], min(dist, cap[i]));
            if(tmp > 0) {
                cap[i] -= tmp;
                cap[i ^ 1] += tmp;
                return tmp; 
            }
        }
    }
    return 0;
}

struct node{
    int x, y;
}army[55], tower[55];

int dinic() {
    int res = 0, d;
    while(bfs()) {
        for(int i = 0; i < maxn; i ++) cur[i] = head[i];
        while(d = dfs(s, INF)) res += d;
    }
    return res;
}

double getdis(node a, node b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

void init(double time){
    memset(head, -1, sizeof(head));
    cnt = 0;
    for(int i = 1; i <= n; i ++) for(int j = 0; j <= m; j ++) 
            ade(s, i + j * 100, 1), ade(i + j * 100, s, 0);
    for(int i = 1; i <= n; i ++) {
        double sec;
        for(int j = 0; j < m; j ++) {
            sec = (1.0 * t1 + 1.0 * j * (t1 + t2));
            for(int k = 1; k <= m; k ++) {
                if(sec + getdis(army[k], tower[i]) / v < time)
                    ade(i + j * 100, 14000 + k, 1), ade(14000 + k, i + j * 100, 0);
            }
        }
    }
    for(int i = 1; i <= m; i ++)
        ade(14000 + i, t, 1), ade(t, 14000 + i, 0);
}

int main(){
    cin >> n >> m >> t1 >> t2 >> v;
    t1 /= 60;
    s = 0, t = 42850;
    for(int i = 1; i <= m; i ++) cin >> army[i].x >> army[i].y;
    for(int i = 1; i <= n; i ++) cin >> tower[i].x >> tower[i].y;
    double l = 0, r = 200000;
    while((r - l) > 1e-7) {
        double mid = (l + r) / 2;
        init(mid);
        if(dinic() == m) r = mid;
        else l = mid;
    }
    printf("%.6lf\n", r);
    return 0;
}


活动打卡代码 AcWing 265. 营业额统计

zhangxu
2019-07-16 13:47
#include <bits/stdc++.h>
#define A first
#define B second
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = 5e4 + 5;
const int maxm = 2e5 + 5;

int n, m;
set<int> S;

int main(){
    fastio;
    cin >> n;
    S.insert(-1e7);
    S.insert(1e7);
    ll ans = 0;
    for(int i = 1, a; i <= n; i ++) {
        cin >> a;
        if(S.size() == 2){
            ans += a;
        //   cout << "[[[]]]." << ans << endl;
            S.insert(a);
            continue;
        }else{
            auto p1 = S.lower_bound(a);
            auto p2 = p1;
            p2 --;
            S.insert(a);
            ans += min(abs(*p2 - a) , abs(*p1 - a));
         //   cout << "......." << ans << endl;
        }
    }
    cout << ans << endl;
    return 0;
}



zhangxu
2019-06-27 07:42

有负数的树 他直径还是最长(权值和最大的)链吗?