头像

史一帆

洛阳师范学院




离线:3天前


最近来访(325)
用户头像
Serendipity_833
用户头像
肥肠煎蛋
用户头像
incra
用户头像
ZhgDgE
用户头像
acwing_74240
用户头像
一别长白灬思无邪
用户头像
l_y_f
用户头像
清风.
用户头像
招柴猫
用户头像
影乐
用户头像
一万小时定律
用户头像
大楼和
用户头像
Liyb
用户头像
你干嘛
用户头像
Thelittleprince
用户头像
MarkCup马克杯
用户头像
南岸以南南岸哀
用户头像
BE-ABLE-N
用户头像
洛洛
用户头像
DDF

分享 2022/8/13

字符环

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

int main(){
    string s1, s2;
    cin >> s1 >> s2;
    int cnt = 0, res = 0;
    int len1 = s1.size(), len2 = s2.size();
    for (int i = 0; i < len1; i ++ )
        for (int j = 0; j < len2; j ++ ){
            cnt = 0;
            if (s1[i] == s2[j]){
                for (int k = 0; k < len1 && k < len2; k ++ ){
                    if (s1[(i + k) % len1] != s2[(j + k) % len2])
                        break;
                    cnt ++ ;
                }
                res = max(res, cnt);
            }
        }
    cout << res << endl;
    return 0;
}

合成分子

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

int a[10], res;
int n;

void dfs(int u, int sum, int op){
    if (u == 10){
        if (sum == n){
            if (op == 1){
                for (int i = 0; i < 10; i ++ )
                    cout << a[i] << ' ';
                cout << endl;
            }else res ++ ;
        }
        return;
    }
    if (sum >= n) return;
    for (int i = 1; i <= 3; i ++ ){
        a[u] = i;
        dfs(u + 1, sum + i, op);
    }
}

int main(){
    cin >> n;
    if (n < 10 || n > 30){
        puts("0");
        return 0;
    }
    dfs(0, 0, 0);
    cout << res << endl;
    dfs(0, 0, 1);
    return 0;
}

单词接龙

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int N = 25;

int n;
string word[N];
int used[N];
char head;
int g[N][N], ans;

void dfs(string str, int last){
    ans = max(ans, (int)str.size());
    used[last] ++ ;
    for (int i = 1; i <= n; i ++ )
        if (g[last][i] && used[i] < 2)
            dfs(str + word[i].substr(g[last][i]), i);
    used[last] -- ;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> word[i];
    cin >> head;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ ){
            string a = word[i], b = word[j];
            for (int k = 1; k < min(a.size(), b.size()); k ++ )
                if (a.substr(a.size() - k, k) == b.substr(0, k)){
                    g[i][j] = k;
                    break;
                }   
        }
    for (int i = 1; i <= n; i ++ )
        if (word[i][0] == head)
            dfs(word[i], i);
    cout << ans << endl;
    return 0;
}


分享 2022/8/12

Palindromes

#include <stdio.h>
#include <string.h>
#include <ctype.h>

const char *rev = "A   3  HIL JM O   2TUVWXY51SE Z  8 ";
const char *msg[] = {"not a palindrome", "a regular palindrome", "a mirrored string", "a mirrored palindrome"};

char r(char ch) {
    if (isalpha(ch))
        return rev[ch - 'A'];
    return rev[ch - '0' + 25];
}

int main() {
    char s[30];

    while (scanf("%s", s) == 1) {
        int len = strlen(s);
        int p = 1, m = 1;

        for (int i = 0; i < (len + 1) / 2; i ++ ) {

            if (s[i] != s[len - 1 - i])
                p = 0; // 不是回文串

            if (r(s[i]) != s[len - 1 - i])
                m = 0; // 不是镜像串
        }

        printf("%s -- is %s.\n\n", s, msg[m * 2 + p]);
    }

    return 0;
}

Periodic Strings

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

int main(){
    int T;
    cin >> T;
    while (T -- ){
        char s[110];
        scanf("%s", s);
        int len = strlen(s);
        int tot;
        for (int i = 1; i <= len; i ++ )
            if (len % i == 0){
                for (tot = i; tot <= len; tot ++ )
                    if (s[tot] != s[tot % i])
                        break;
                if (tot == len){
                    cout << i << endl;
                    break;
                }
            }
        if (T) cout << endl;
    }
    return 0;
}

Circular Sequence

#include <stdio.h>
#include <string.h>

#define maxn 105

int less(const char *s, int p, int q) {
    int n = strlen(s);

    for (int i = 0; i < n; i ++ )

        if (s[(p + i) % n] != s[(q + i) % n])
            return s[(p + i) % n] < s[(q + i) % n];
    return 0;
}

int main() {
    int T;
    char s[maxn];
    scanf("%d", &T);

    while (T -- ) {
        scanf("%s", s);
        int ans = 0;
        int n = strlen(s);

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

            if (less(s, i, ans))
                ans = i;

        for (int i = 0; i < n; i ++ )

            putchar(s[(i + ans) % n]);
        putchar('\n');
    }

    return 0;
}


分享 2022/8/11

单源最短路径(标准版)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5 + 10, M = 2e5 + 10;

struct Edge{
    int e, w, ne;
}E[M];
int h[N], idx;
int n, m, s;
int dist[N];
bool st[N];

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

void dijkstra(){
    memset(st, false, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII,vector<PII>,greater<PII>> q;
    dist[1] = 0;
    q.push({0,1});
    while (!q.empty()){
        PII t = q.top();
        q.pop();
        int ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; ~i; i = E[i].ne){
            int j = E[i].e;
            if (dist[j] > dist[ver] + E[i].w){
                dist[j] = dist[ver] + E[i].w;
                q.push({dist[j],j});
            }
        }
    }
}

int main(){
    memset(h, -1, sizeof h);
    cin >> n >> m >> s;
    while (m -- ){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    dijkstra();
    for (int i = 1; i <= n; i ++ )
        cout << dist[i] << ' ';
    return 0;
}

HDU Today

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>

using namespace std;

const int N = 160;

int n, cnt;
int g[N][N];
int dist[N];
bool st[N];
map<string, int> mp;

int dijkstra(int n)
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[2] == 0x3f3f3f3f) return -1;
    return dist[2];
}

int main()
{
    while (~scanf("%d", &n) && n != -1)
    {
        memset(st, false, sizeof st);
        mp.clear();
        string start, end;
        cin >> start >> end;
        mp[start] = 1;
        mp[end] = 2;
        int cnt = 3;

        memset(g, 0x3f, sizeof g);
        while (n -- )
        {
            string a, b;
            int c;
            cin >> a >> b >> c;
            if (!mp.count(a)) mp[a] = cnt ++ ;
            if (!mp.count(b)) mp[b] = cnt ++ ;
            g[mp[a]][mp[b]] = min(g[mp[a]][mp[b]], c);
            g[mp[b]][mp[a]] = min(g[mp[b]][mp[a]], c);
        }

        if (start == end) printf("0\n");
        else printf("%d\n", dijkstra(cnt));
    }
    return 0;
}


分享 2022/8/10

Silver Cow Party

#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1010;

int g[N][N];
int dist[N], st[N], d1[N], d2[N];
int n, m, x, y, k, t;

void dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    dist[t] = 0;
    for (int i = 0; i < n; i ++ ){
        int u = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (u == -1 || dist[u] > dist[j]))
                u = j;
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[u] + g[u][j]);
        st[u] = true;   
    }
}

int main(){
    scanf("%d%d%d", &n, &m, &t);
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= m; i ++ ){
        scanf("%d%d%d", &x, &y, &k);
        g[x][y] = min(g[x][y], k);
    }
    dijkstra();
    memcpy(d1, dist, sizeof dist);
    for (int i = 1; i <= n; i ++ )
        for (int j = i + 1; j <= n; j ++ )
            swap(g[i][j], g[j][i]);
    dijkstra();
    memcpy(d2, dist, sizeof dist);
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        res = max(res, d1[i] + d2[i]);
    printf("%d\n", res);
}

Currency Exchange

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 110;

int n, m, s;
double v;
double dist[N];
bool st[N];
struct node {
    int to;
    double p;
    double q;
};
vector<node> V[N];

bool spfa() {
    memset(st, false, sizeof st);
    memset(dist, 0, sizeof dist);
    queue<int> q;
    q.push(s);
    st[s] = true;
    dist[s] = v;
    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = 0; i < V[t].size(); i ++ ) {
            int To = V[t][i].to;
            double P = V[t][i].p, Q = V[t][i].q;
            if (dist[To] < (dist[t] - Q) * P) {
                dist[To] = (dist[t] - Q) * P;
                if (dist[s] > v)
                    return true;
                if (!st[To]) {
                    q.push(To);
                    st[To] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    while (~scanf("%d%d%d%lf", &n, &m, &s, &v)) {
        for (int i = 1; i <= n; i ++ )
            V[i].clear();
        while (m -- ) {
            int a, b;
            double c, d;
            node ans;
            scanf("%d%d", &a, &b);
            scanf("%lf%lf", &c, &d);
            ans.to = b, ans.p = c, ans.q = d;
            V[a].push_back(ans);
            scanf("%lf%lf", &c, &d);
            ans.to = a, ans.p = c, ans.q = d;
            V[b].push_back(ans);
        }
        if (spfa())
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}


分享 2022/8/9

缩点

#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = 500010;

vector<int> pre[N], v[N];
int n, m, in[N], w[N], sum[N], f[N], tp[N], cntq;
int h[N], e[M], ne[M], idx;
int belong[N], bent, stk[N], top, dfn[N], low[N], instk[N], timestamp;

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

void tarjan(int u){
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u, instk[u] = true;
    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if (!dfn[j]){
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }else if(instk[j]) low[u] = min(low[u], dfn[j]);
    }
    if (dfn[u] == low[u]){
        int v;
        ++ bent;
        do{
            v = stk[top --];
            instk[v] = false;
            belong[v] = bent;
            sum[bent] += w[v];
        } while(v != u);
    }
}

void topsort(){
    queue<int> q;
    for (int i = 1; i <= bent; i ++ )
        if (!in[i])
            q.push(i);
    while (!q.empty()){
        int t = q.front();
        q.pop();
        tp[++ cntq] = t;
        for (int i = 0; i < v[t].size(); i ++ ){
            int j = v[t][i];
            in[j] -- ;
            if (!in[j]) q.push(j);
        }
    }
}

int main(){
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int i = 1; i <= m; i ++ ){
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    for (int i = 1; i <= n; i ++ )
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; ~j; j = ne[j]){
            int k = e[j];
            if (belong[i] != belong[k]){
                int x = belong[i], y = belong[k];
                in[y] ++ ;
                v[x].push_back(y);
                pre[y].push_back(x);
            }
        }
    topsort();
    for (int i = 1; i <= cntq; i ++ ){
        int u = tp[i];
        f[u] = sum[u];
        for (int j = 0; j < pre[u].size(); j ++ )
            f[u] = max(f[u], f[pre[u][j]] + sum[u]);
    }
    int res = 0;
    for (int i = 1; i <= bent; i ++ )
        res = max(res, f[i]);
    printf("%d\n", res);
    return 0;
}

Popular Cows

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#define lowbit(x) -x&x
#define LL long long 
#define INF 0x3f3f3f3f
using namespace std;
const int N = 10010, M = N * N;

int n, m, in[N], out[N];
int h[N], e[M], ne[M], idx;
int belong[N], bent, stk[N], top, dfn[N], low[N], instk[N], timestamp;

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

void tarjan(int u){
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u, instk[u] = true;
    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if (!dfn[j]){
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }else if(instk[j]) low[u] = min(low[u], dfn[j]);
    }
    if (dfn[u] == low[u]){
        int v;
        ++ bent;
        do{
            v = stk[top --];
            instk[v] = false;
            belong[v] = bent;
        } while(v != u);
    }
}

int main(){
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i ++ ){
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    for (int i = 1; i <= n; i ++ )
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; ~j; j = ne[j]){
            int k = e[j];
            if (belong[i] != belong[k])
                out[belong[i]] ++;
        }
    int ans, cnt = 0;
    for (int i = 1; i <= bent; i ++ )
        if (!out[i])
            cnt ++ , ans = i;
    if (cnt == 1){
        int res = 0;
        for (int i = 1; i <= n; i ++ )
            if (belong[i] == ans)
                res ++ ;
        printf("%d\n", res);
    }else printf("0\n");
    return 0;
}

Network of Schools

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#define lowbit(x) -x&x
#define LL long long 
#define INF 0x3f3f3f3f
using namespace std;
const int N = 110, M = N * N;

int n, m, in[N], out[N];
int h[N], e[M], ne[M], idx;
int belong[N], bent, stk[N], top, dfn[N], low[N], instk[N], timestamp;

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

void tarjan(int u){
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u, instk[u] = true;
    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if (!dfn[j]){
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }else if(instk[j]) low[u] = min(low[u], dfn[j]);
    }
    if (dfn[u] == low[u]){
        int v;
        ++ bent;
        do{
            v = stk[top --];
            instk[v] = false;
            belong[v] = bent;
        } while(v != u);
    }
}

int main(){
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        while (~scanf("%d", &m) && m)
            add(i, m);
    for (int i = 1; i <= n; i ++ )
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; ~j; j = ne[j]){
            int k = e[j];
            if (belong[i] != belong[k]){
                out[belong[i]] ++;
                in[belong[k]] ++ ;
            }
        }
    int ans1 = 0, ans2 = 0;
    for (int i = 1; i <= bent; i ++ ){
        if (!in[i])
            ans1 ++ ;
        if (!out[i])
            ans2 ++ ;
    }
    if (bent == 1)
        printf("1\n0\n");
    else printf("%d\n%d\n", ans1, max(ans1, ans2));
    return 0;
}



史一帆
11天前

A.



B.交通改造

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#define lowbit(x) -x&x
#define LL long long 
#define INF 0x3f3f3f3f
using namespace std;
const int N = 310;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim(){
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    int MAX = 0;
    for (int i = 0; i < n; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        if (i && dist[t] == INF) return INF;
        if (i) res += dist[t], MAX = max(MAX, dist[t]);
        st[t] = true;
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], g[t][j]);
    }
    return MAX;
}

int main(){
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m -- ){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    cout << n - 1 << ' ' << prim() << endl;
    return 0;
}

C.丢手绢

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#define lowbit(x) -x&x
#define LL long long 
using namespace std;
const int N = 1e5 + 10;

int n, m, k, x;

int qmi(int a, int k, int p){
    int res = 1 % p;
    while (k){
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int main(){
    cin >> n >> m >> k >> x;
    cout << (x + m * qmi(10, k, n)) % n << endl;
    return 0;
}

D.


E.


F.分割草坪

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#define lowbit(x) -x&x
#define LL long long 
#define INF 0x3f3f3f3f
using namespace std;

int n;

int main(){
    LL res = 0;
    cin >> n;
    for (; n >= 3; n -- )
        res += n * (n - 1);
    cout << res << endl; 
    return 0;
}

G.



H.


I.



J.



K.矩阵生成

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#define lowbit(x) -x&x
#define LL long long 
using namespace std;
const int N = 1e5 + 10;

int g[50][50];
int n;

int main(){
    cin >> n;
    int cnt = 1;
    int x = 1, y = (n + 1) / 2;
    while (cnt <= n * n){
        g[x][y] = cnt;
        if (x == 1 && y != n) x = n, y ++ ;
        else if (y == n && x != 1) y = 1, x -- ;
        else if (x == 1 && y == n) x ++ ;
        else if (x != 1 && y != n){
            if (!g[x-1][y+1]) x -- , y ++ ;
            else x ++ ;
        } 
        cnt ++ ;
    }
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= n; j ++ )
            cout << g[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

L.




分享 2022/8/6

史一帆
13天前

Stars

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#define lowbit(x) -x&x
#define LL long long 
using namespace std;
const int N = 32010;

int ans[N], tr[N];
int n;

void add(int i, int z){
    for (; i < N; i += lowbit(i))
        tr[i] += z;
}

int ask(int i){
    int res = 0;
    for (; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ){
        int x, y;
        scanf("%d%d", &x, &y);
        x ++ ;
        ans[ask(x)] ++ ;
        add(x, 1);
    }
    for (int i = 0; i < n; i ++ )
        printf("%d\n", ans[i]);
    return 0;
}

Japan

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#define lowbit(x) -x&x
#define LL long long 
using namespace std;
const int N = 1010;

int tr[N];
int n, m, k, casei;
LL ans;

struct Node{
    int x, y;
    bool operator<(const Node& t)const{
        return x < t.x || (x == t.x && y < t.y);
    }
}p[1000010];

void add(int i, int z){
    for (; i < N; i += lowbit(i))
        tr[i] += z;
}

int ask(int i){
    int res = 0;
    for (; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

int main(){
    int T;
    scanf("%d", &T);
    while (T -- ){
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= k; i ++ )
            scanf("%d%d", &p[i].x, &p[i].y);
        sort(p + 1, p + 1 + k);
        ans = 0;
        memset(tr, 0, sizeof tr);
        for (int i = 1; i <= k; i ++ ){
            ans += i - 1 - ask(p[i].y);
            add(p[i].y, 1);
        }
        printf("Test case %d: %lld\n", ++ casei, ans);
    }
    return 0;
}


分享 2022/8/5

史一帆
14天前

二维树状数组 1:单点修改,区间查询

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lowbit(x) -x&x
typedef long long LL;
using namespace std;
const int N = 1024 * 4 + 10;

LL tr[N][N];
LL n, m;

void add(LL x, LL y, LL z)
{
    for (LL i = x; i <= n; i += lowbit(i))
        for (LL j = y; j <= m; j += lowbit(j))
            tr[i][j] += z;
}

LL sum(LL x, LL y)
{
    LL res = 0;
    for (LL i = x; i; i -= lowbit(i))
        for (LL j = y; j; j -= lowbit(j))
            res += tr[i][j];
    return res;
}

LL sum2(LL x1, LL y1, LL x2, LL y2)
{
    return sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) + sum(x1 - 1, y1 - 1);
}

int main()
{
    cin >> n >> m;
    LL op;
    LL x1, y1, x2, y2, z;
    while (scanf("%lld", &op) != EOF){
        if (op == 1){
            scanf("%lld%lld%lld", &x1, &y1, &z);
            add(x1, y1, z);
        }else{
            scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
            printf("%lld\n", sum2(x1, y1, x2, y2));
        }
    }
    return 0;
}

二维树状数组 2:区间修改,单点查询

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lowbit(x) -x&x
typedef long long LL;
using namespace std;
const int N = 1024 * 4 + 10;

LL tr[N][N];
LL n, m;

void add(LL x, LL y, LL z)
{
    for (LL i = x; i <= n; i += lowbit(i))
        for (LL j = y; j <= m; j += lowbit(j))
            tr[i][j] += z;
}

LL sum(LL x, LL y)
{
    LL res = 0;
    for (LL i = x; i; i -= lowbit(i))
        for (LL j = y; j; j -= lowbit(j))
            res += tr[i][j];
    return res;
}

LL sum2(LL x1, LL y1, LL x2, LL y2)
{
    return sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) + sum(x1 - 1, y1 - 1);
}

int main()
{
    cin >> n >> m;
    LL op;
    LL x1, y1, x2, y2, z;
    while (scanf("%lld", &op) != EOF){
        if (op == 1){
            scanf("%lld%lld%lld%lld%lld", &x1, &y1, &x2, &y2, &z);
            add(x1, y1, z), add(x2 + 1, y1, -z), add(x1, y2 + 1, -z), add(x2 + 1, y2 + 1, z);
        }else{
            scanf("%lld%lld", &x1, &y1);
            printf("%lld\n", sum(x1, y1));
        }
    }
    return 0;
}

二维树状数组 3:区间修改,区间查询

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lowbit(x) -x&x
typedef long long LL;
using namespace std;
const int N = 1024 * 4 + 10;

LL tr1[N][N], tr2[N][N], tr3[N][N], tr4[N][N];
LL n, m;

void add(LL x, LL y, LL z)
{
    for (LL i = x; i <= n; i += lowbit(i))
        for (LL j = y; j <= m; j += lowbit(j)){
            tr1[i][j] += z;
            tr2[i][j] += z * x;
            tr3[i][j] += z * y;
            tr4[i][j] += z * x * y;
        }
}

LL sum(LL x, LL y)
{
    LL res = 0;
    for (LL i = x; i; i -= lowbit(i))
        for (LL j = y; j; j -= lowbit(j))
            res += tr1[i][j] * (x + 1) * (y + 1) - tr2[i][j] * (y + 1) - tr3[i][j] * (x + 1) + tr4[i][j];
    return res;
}

LL sum2(LL x1, LL y1, LL x2, LL y2)
{
    return sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) + sum(x1 - 1, y1 - 1);
}

int main()
{
    cin >> n >> m;
    LL op;
    LL x1, y1, x2, y2, z;
    while (scanf("%lld", &op) != EOF){
        if (op == 1){
            scanf("%lld%lld%lld%lld%lld", &x1, &y1, &x2, &y2, &z);
            add(x1, y1, z), add(x2 + 1, y1, -z), add(x1, y2 + 1, -z), add(x2 + 1, y2 + 1, z);
        }else{
            scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
            printf("%lld\n", sum2(x1, y1, x2, y2));
        }
    }
    return 0;
}


分享 2022/8/4

史一帆
15天前

贪婪大陆

#include <bits/stdc++.h>
#define lowbit(x) -x&x
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;

int tou[N], wei[N], n, m;

void add_tou(int i){
    for (; i <= n; i += lowbit(i))
        tou[i] ++;
}

int ask_tou(int i){
    int res = 0;
    for (; i; i -= lowbit(i))
        res += tou[i];
    return res;
}

void add_wei(int i){
    for (; i <= n; i += lowbit(i))
        wei[i] ++;
}

int ask_wei(int i){
    int res = 0;
    for (; i; i -= lowbit(i))
        res += wei[i];
    return res;
}

int main()
{
    cin >> n >> m;
    while (m -- ){
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1)
            add_tou(l), add_wei(r);
        else
            cout << ask_tou(r) - ask_wei(l - 1) << endl;
    }
    return 0;
}

逆序对

#include <iostream>
typedef long long LL;
using namespace std;
const int N = 500010;
int n;
int q[N], tmp[N];
LL merge_sort(int l, int r) {
    if (l >= r) return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);

    //归并的过程
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else {
            tmp[k++] = q[j++];
            res += mid - i + 1;
        }
    }

    //扫尾
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];

    //物归原主
    for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    return res;
}
int main() {
    //ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> q[i];
    cout << merge_sort(0, n - 1) << endl;
    return 0;
}

最接近神的人

#include <iostream>
typedef long long LL;
using namespace std;
const int N = 500010;
int n;
int q[N], tmp[N];
LL merge_sort(int l, int r) {
    if (l >= r) return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);

    //归并的过程
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else {
            tmp[k++] = q[j++];
            res += mid - i + 1;
        }
    }

    //扫尾
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];

    //物归原主
    for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    return res;
}
int main() {
    //ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> q[i];
    cout << merge_sort(0, n - 1) << endl;
    return 0;
}


分享 2022/8/3

史一帆
15天前

Hotel

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e4 + 10;

struct Node{
    int l, r, s, ls, rs, add;
}tr[N << 2];

void pushup(int u, int len)
{
    if(len == 1) return;
    tr[u].ls = tr[u << 1].ls;
    tr[u].rs = tr[u << 1 | 1].rs;
    if(tr[u].ls == (len - len / 2)) tr[u].ls += tr[u << 1 | 1].ls;
    if(tr[u].rs == len / 2) tr[u].rs += tr[u << 1].rs;
    tr[u].s = max(tr[u << 1].rs + tr[u << 1 | 1].ls, max(tr[u << 1].s, tr[u << 1 | 1].s));
}

void pushdown(int u, int len)
{
    if(len == 1) return;
    if (tr[u].add){
        tr[u << 1].add = tr[u << 1 | 1].add = tr[u].add;
        if (tr[u].add == 2){
            tr[u << 1].s = tr[u << 1].ls = tr[u << 1].rs = len - len / 2;
            tr[u << 1 | 1].s = tr[u << 1 | 1].ls = tr[u << 1 | 1].rs = len / 2;
        }
        else if(tr[u].add == 1){
            tr[u << 1].s = tr[u << 1].ls = tr[u << 1].rs = 0;
            tr[u << 1 | 1].s = tr[u << 1 | 1].ls = tr[u << 1 | 1].rs = 0;
        }
        tr[u].add = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u].l = l, tr[u].r = r;
    tr[u].ls = tr[u].rs = tr[u].s = 1;
    tr[u].add = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u, r - l + 1);
}

void modify(int u, int l, int r, int z)
{
    if(tr[u].l >= l && tr[u].r <= r){
        if (z == 1)
            tr[u].s = tr[u].ls = tr[u].rs = 0;
        else if(z == 2)
            tr[u].s = tr[u].ls = tr[u].rs = tr[u].r - tr[u].l + 1;
        tr[u].add = z;
        return;
    }
    pushdown(u, tr[u].r - tr[u].l + 1);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) modify(u << 1, l, r, z);
    if(r > mid) modify(u << 1 | 1, l, r, z);
    pushup(u, tr[u].r - tr[u].l + 1);
}

int query(int u, int len)
{
    if(tr[u].l == tr[u].r) return tr[u].l;
    pushdown(u, tr[u].r - tr[u].l + 1);
    int mid = tr[u].l + tr[u].r >> 1;
    if(tr[u << 1].s >= len) return query(u << 1, len);
    else if(tr[u << 1].rs + tr[u << 1 | 1].ls >= len) return mid - tr[u << 1].rs + 1;
    else return query(u << 1 | 1, len);
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    int op;
    while (m -- ){
        scanf("%d", &op);
        if (op == 1){
            int k;
            scanf("%d", &k);
            if (tr[1].s >= k){
                int pos = query(1, k);
                printf("%d\n", pos);
                modify(1, pos, pos + k - 1, 1);
            }
            else printf("0\n");
        }
        else if(op == 2){
            int l, len;
            scanf("%d%d", &l, &len);
            modify(1, l, l + len - 1, 2);
        }
    }
    return 0;
}



Lost Cows

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define lowbit(x) -x&x
using namespace std;
typedef long long LL;
const int N = 8e4 + 10;

int tr[N], a[N], ans[N], n;

void add(int i, int z){
    for (; i <= n; i += lowbit(i))
        tr[i] += z;
}

int ask(int i){
    int res = 0;
    for (; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

int main()
{
    scanf("%d", &n);
    a[1] = 0;
    for (int i = 2; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = n; i; i -- ){
        int l = 1, r = n;
        while (l < r){
            int mid = l + r >> 1;
            if (mid - ask(mid) > a[i]) r = mid;
            else l = mid + 1;
        }
        ans[i] = l;
        add(l, 1);
    }
    for (int i = 1; i <= n; i ++ )
        printf("%d\n", ans[i]);
    return 0;
}