头像

牛奶小Q




在线 



牛奶小Q
22分钟前
排列问题
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10;
int n;
int a[N],nums[N];
bool st[N];

void dfs(int u){
    if(u == n){
        for(int i = 0;i < n;++i)    printf("%d ",nums[i]);
        puts("");
        return;
    }
    for(int i = 0;i < n;++i){
        if(!st[i]){
            nums[u] = a[i];
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
            while(i + 1 < n && a[i + 1] == a[i]) i++;
        }
    }
}

int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;++i)    scanf("%d",&a[i]);
    sort(a,a + n);
    dfs(0);
    return 0;
}
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10;
int n;
int a[N];

int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;++i)    scanf("%d",&a[i]);
    sort(a,a + n);
    do{
        for(int i = 0;i < n;++i)    printf("%d ",a[i]);
        puts("");
    }while(next_permutation(a,a + n));
    return 0;
}



牛奶小Q
43分钟前
balabala
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int Max(int a,int b){
    return  (a + b + abs(a - b)) / 2;
}

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    cout << Max(Max(a,b),c)  << " eh o maior" << endl;
    return 0;
}



典型双指针算法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,m,x;
int a[N],b[N];

int main(){
    scanf("%d%d%d",&n,&m,&x);
    for(int i = 0;i < n;++i)    scanf("%d",&a[i]);
    for(int i = 0;i < m;++i)    scanf("%d",&b[i]);
    for(int i = 0,j = m - 1;i < n;++i){
        while(j >= 0 && a[i] + b[j] > x)   j--;
        if(j >= 0 && a[i] + b[j] == x)  printf("%d %d",i,j);
    }
    return 0;
}



判断子序列问题,双指针算法
从每个数组第一位开始往右移动,当两数组数字相等时,序列位数+1,当该序列位数到头时即为子序列

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int a[N],b[N];

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;++i)    scanf("%d",&a[i]);
    for(int i = 0;i < m;++i)    scanf("%d",&b[i]);
    int i = 0,j = 0;
    while(i < n && j < m){
        if(a[i] == b[j])    i++;
        j++;
    }
    if(i == n)  puts("Yes");
    else    puts("No");
    return 0;
}


活动打卡代码 AcWing 2875. 超级胶水

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
int n,x;
LL res,sum;

int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;++i){
        scanf("%d",&x);
        sum += res * x;
        res += x;
    }
    printf("%lld\n",sum);
    return 0;
}


活动打卡代码 AcWing 2068. 整数拼接

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n,k;
int a[N],s[11][N];
LL res;

int main(){
    scanf("%d%d",&n,&k);
    for(int i = 0;i < n;++i)    scanf("%d",&a[i]);
    for(int i = 0;i < n;++i){
        LL t = a[i] % k;
        for(int j = 0;j < 11;++j){
            s[j][t]++;
            t = t * 10 % k;
        }
    }
    for(int i = 0;i < n;++i){
        LL t = a[i] % k;
        int len = to_string(a[i]).size();
        res += s[len][(k - t) % k];
        LL r = t;
        while(len--)    r = r * 10 % k;
        if(r == ((k - t) % k))  res--;
    }
    printf("%lld\n",res);
    return 0;
}



二叉树跟递归搜索树,当遇到|时,字符串长度为左右两边取最大值,遇到积答案就加一,关键点:遇到左括号时必然会遇到右括号

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 110;
int k;
string s;

int dfs(){
    int res = 0;
    while(k < s.size()){
        if(s[k] == '('){
            k++;
            res += dfs();
            k++;
        }else if(s[k] == '|'){
            k++;
            res = max(res,dfs());
        }else if(s[k] == ')')   break;
        else{
            k++;
            res++;
        }
    }
    return res;
}

int main(){
    cin >> s;
    cout << dfs() << endl;
    return 0;
}



连通块问题,balabalabala

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int p[N],cnt[N];

int find(int x){
    if(p[x] != x)   p[x] = find(p[x]);
    return p[x];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i){
        p[i] = i;
        cnt[i] = 1;
    }
    while(m--){
        string op;
        int a,b;
        cin >> op;
        if(op == "C"){
            scanf("%d%d",&a,&b);
            a = find(a),b = find(b);
            if(a != b){
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }else if(op == "Q1"){
            scanf("%d%d",&a,&b);
            if(find(a) == find(b))  puts("Yes");
            else    puts("No");
        }else{
            scanf("%d",&a);
            printf("%d\n",cnt[find(a)]);
        }
    }
    return 0;
}



并查集模板题,关键是find函数,当前节点不是根节点时,让它指向祖宗节点
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int p[N];

int find(int x){
    if(p[x] != x)   p[x] = find(p[x]);
    return p[x];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i)   p[i] = i;
    while(m--){
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(*op == 'M')  p[find(a)] = find(b);
        else{
            if(find(a) == find(b))  puts("Yes");
            else    puts("No");
        }
    }
    return 0;
}



合并建立新节点

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int p[N],d[N];

int find(int x){
    if(p[x] != x){
        if(p[p[x]] == p[x]) return p[x];
        int r = find(p[x]);
        d[x] += d[p[x]];
        p[x] = r;
    }
    return p[x];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i < N;++i)    p[i] = i;
    int k = n;
    while(m--){
        int t,a,b;
        scanf("%d%d%d",&t,&a,&b);
        if(t == 1){
            a = find(a),b = find(b);
            if(a != b){
                k++;
                p[a] = p[b] = k;
            }
        }else{
            a = find(a);
            d[a] += b;
        }
    }
    for(int i = 1;i <= n;++i){
        if(i == find(i))    printf("%d ",d[i]);
        else    printf("%d ",d[i] + d[find(i)]);
    }
    puts("");
    return 0;
}

合并不建立新节点

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int p[N],d[N];

int find(int x){
    if(p[x] != x){
        if(p[p[x]] == p[x]) return p[x];
        int r = find(p[x]);
        d[x] += d[p[x]];
        p[x] = r;
    }
    return p[x];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i < N;++i)    p[i] = i;
    while(m--){
        int t,a,b;
        scanf("%d%d%d",&t,&a,&b);
        if(t == 1){
            a = find(a),b = find(b);
            if(a != b){
                d[a] -= d[b];
                p[a] = b;
            }
        }else{
            a = find(a);
            d[a] += b;
        }
    }
    for(int i = 1;i <= n;++i){
        if(i == find(i))    printf("%d ",d[i]);
        else    printf("%d ",d[i] + d[find(i)]);
    }
    puts("");
    return 0;
}