头像

魚ヾ




离线:26天前


最近来访(30)
用户头像
C++小郑
用户头像
Lukesu
用户头像
AC_Zenbg
用户头像
zzr0126
用户头像
饭堂阿叔
用户头像
RyanMoriarty
用户头像
白马金羁侠少年
用户头像
谁扔的炮仗
用户头像
咚咚小圆帽
用户头像
封禁用户
用户头像
hfuu1
用户头像
吃糖葫芦的兔子
用户头像
多财多亿
用户头像
998
用户头像
FingerOne
用户头像
星逐月丶
用户头像
有机物
用户头像
Kirito_9
用户头像
x6x
用户头像
我要出去乱说

活动打卡代码 AcWing 3. 完全背包问题

魚ヾ
11个月前
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e4+5;

int v[N],w[N];
int f[N][N];

int main(){
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) scanf("%d %d",&v[i],&w[i]);
    for(int i=1; i<=n; i++)
        for(int j=0; j<=m; j++){
            f[i][j] = f[i-1][j];
            if(v[i] <= j)   f[i][j] = max( f[i][j], f[i][j-v[i]]+w[i]);
        }
    printf("%d",f[n][m]);
    return 0;
}


活动打卡代码 AcWing 2. 01背包问题

魚ヾ
11个月前
/*
    有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

    第 i 件物品的体积是 vi,价值是 wi。

    求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
    输出最大价值。

    输入格式
    第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

    接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

    输出格式
    输出一个整数,表示最大价值。

    数据范围
    0<N,V≤1000
    0<vi,wi≤1000
    输入样例
    4 5
    1 2
    2 4
    3 4
    4 5
    输出样例:
    8
*/
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e4+5;

int n,m;        //物品个数n,背包容量m
int v[N],w[N];  //第N个物品的体积为v[N]、价值为w[N]
int f[N][N];    //背包中装入前N个物品、体积大于N的情况下的价值

int main(){
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> v[i] >> w[i];    //初始化第[0,n]个物品的体积v和价值w 。 第0个物品默认体积为0、价值为0
    for(int i=1; i<=n; i++)                         //因为第0个物品价值为0   所以从第1个物品考虑
        for(int j=0; j<=m; j++){
            f[i][j] = f[i-1][j];                    //状态计算方程      
            if( j>=v[i] )   f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);
        }
    cout << f[n][m] << endl;
    return 0;
}


活动打卡代码 AcWing 840. 模拟散列表

魚ヾ
2021-12-02 22:07
/*
    维护一个集合,支持如下几种操作:

    I x,插入一个数 x;
    Q x,询问数 x 是否在集合中出现过;
    现在要进行 N 次操作,对于每个询问操作输出对应的结果。

    输入格式
    第一行包含整数 N,表示操作数量。

    接下来 N 行,每行包含一个操作指令,操作指令为 I x,Q x 中的一种。

    输出格式
    对于每个询问指令 Q x,输出一个询问结果,如果 x 在集合中出现过,则输出 Yes,否则输出 No。

    每个结果占一行。

    数据范围
    1≤N≤105
    −109≤x≤109
    输入样例:
    5
    I 1
    I 2
    I 3
    Q 2
    Q 5
    输出样例:
    Yes
    No
*/
#include<iostream>
#include<cstring>
using namespace std;

const int N = 1e5+5;
int h[N],e[N],ne[N];
int idx=0;

void insert(int x){
    int k = (x%N +N)%N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

string find(int x){
    int k = (x%N +N)%N;
    for(int i=h[k]; i!=-1; i=ne[i]) 
        if(e[i] == x)   return "Yes";
    return "No";
}

int main(){
    int n;
    cin >> n;

    memset(h, -1, sizeof h);    //memset(void *s,int c,size_t n)  将已开辟内存空间 s 的首 n 个字节的值设为值 c

    while(n--){
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        if( *op=='I')   insert(x);
        else    cout << find(x) <<endl;
    }
    return 0;
}


活动打卡代码 AcWing 143. 最大异或对

魚ヾ
2021-12-02 18:01
/*
    在给定的 N 个整数 A1,A2……AN 中选出两个进行 xor(异或)运算,得到的结果最大是多少?

    输入格式
    第一行输入一个整数 N。

    第二行输入 N 个整数 A1~AN。

    输出格式
    输出一个整数表示答案。

    数据范围
    1≤N≤105,
    0≤Ai<231
    输入样例:
    3
    1 2 3
    输出样例:
    3
*/
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5+5;
int a[N],son[N*31][2];
int idx=0;

void toTrie(int x){
    int p = 0;  //结点层数指针 
    for(int i=30; i>=0; i--){
        int y = x>>i&1; //得到x二进制形式的第i位数 
        if( !son[p][y]) son[p][y] = ++idx;  //son[p][y]在Tire里不存在? 创建结点(idx++) 
        p = son[p][y];//指针指向操作节点 
    } 
}

//查找x在Tire中的异或结果最大的数
int search(int x){
    int p=0;        //结点层数指针 
    int ans=0;      //x在Tire中的异或结果最大的数 
    for(int i=30; i>=0; i--){
        int y = x>>i&1; //得到x二进制的第i位数
        if( son[p][!y]) {
            p = son[p][!y];
            ans = (ans<<1) + 1;
        }
        else{
            p = son[p][y];
            ans = (ans<<1) + 0;
        }
    }
    return ans;
}

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

    int ans=0;
    for(int i=0; i<n; i++)  ans = max(ans,search(a[i]) );
    cout << ans;
    return 0;
}


活动打卡代码 AcWing 839. 模拟堆

魚ヾ
2021-12-02 16:42
/*
    维护一个集合,初始时集合为空,支持如下几种操作:

    I x,插入一个数 x;
    PM,输出当前集合中的最小值;
    DM,删除当前集合中的最小值(数据保证此时的最小值唯一);
    D k,删除第 k 个插入的数;
    C k x,修改第 k 个插入的数,将其变为 x;
    现在要进行 N 次操作,对于所有第 2 个操作,输出当前集合的最小值。

    输入格式
    第一行包含整数 N。

    接下来 N 行,每行包含一个操作指令,操作指令为 I x,PM,DM,D k 或 C k x 中的一种。

    输出格式
    对于每个输出指令 PM,输出一个结果,表示当前集合中的最小值。

    每个结果占一行。

    数据范围
    1≤N≤105
    -109≤x≤109
    数据保证合法。

    输入样例:
    8
    I -10
    PM
    I -10
    D 1
    C 2 8
    I 6
    PM
    DM
    输出样例:
    -10
    6
*/

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

const int N = 1e5+5;
int h[N],ph[N],hp[N]; //堆;第k个插入的数是堆的第ph[n]个数;堆的第k个数是第hp[k]个插入的数 
int cut=0;      //堆的长度 (初始化为0的堆) 
int idx=0;      //第k个插入数 

void heap_swap(int a,int b){
    swap( ph[ hp[a]],ph[ hp[b] ] );
    swap( hp[a], hp[b]);
    swap( h[a],h[b]);
}

void down(int u){
    int t = u;
    if( u*2<=cut && h[u*2]<h[t])    t = u*2;
    if( u*2+1<=cut && h[u*2+1]<h[t])    t = u*2+1;
    if(t != u){
        heap_swap(t,u);
        down(t);
    }
}

void up(int u){
    while( u/2 && h[u]<h[u/2] ){
        heap_swap(u,u/2);
        u >>= 1;
    }
}

int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        char op[3];
        scanf("%s",op);
        if(!strcmp(op,"I")){
            int x;
            scanf("%d",&x);
            idx++;
            cut++;
            ph[idx] = cut;
            hp[cut] = idx;
            h[cut] = x;
            up(cut);
        }       
        if(!strcmp(op,"PM")){
            printf("%d\n",h[1]);
        }
        if(!strcmp(op,"DM")){
            heap_swap( 1, cut);
            cut--;
            down(1);
        }
        if(!strcmp(op,"D")){
            int k;
            scanf("%d",&k);
            k = ph[k];
            heap_swap(k,cut);   //因为 heap_swap()交换的是堆里面的数,因此用ph[k]求出了在对堆中的第k个数 
            cut--;
            up(k);
            down(k);
        }
        if(!strcmp(op,"C")){
            int k,x;
            scanf("%d %d",&k,&x);
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }
    return 0;
}


活动打卡代码 AcWing 838. 堆排序

魚ヾ
2021-12-01 22:42
/*
    输入一个长度为 n 的整数数列,从小到大输出前 m 小的数。

    输入格式
    第一行包含整数 n 和 m。

    第二行包含 n 个整数,表示整数数列。

    输出格式
    共一行,包含 m 个整数,表示整数数列中前 m 小的数。

    数据范围
    1≤m≤n≤105,
    1≤数列中元素≤109
    输入样例:
    5 3
    4 5 1 3 2
    输出样例:
    1 2 3
*/
#include<iostream>
using namespace std;

const int N =1e5+5;
int h[N],count;

void down(int u){
    int t = u;
    if( u*2<=count && h[u*2]<h[t] )  t = u*2;
    if( u*2+1<=count && h[u*2+1]<h[t])    t = u*2+1;
    if(t != u){
        swap(h[t],h[u]);
        down(t);
    }
}


int main(){
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) scanf("%d",&h[i]);
    count = n;
    for(int i=n/2; i>0; i--)    down(i);
    while(m--){
        printf("%d ",h[1]);
        h[1] = h[count--];
        down(1);
    }
    return 0;
}



魚ヾ
2021-12-01 21:28

/*
    给定一个包含 n 个点(编号为 1∼n)的无向图,初始时图中没有边。

    现在要进行 m 个操作,操作共有三种:

    C a b,在点 a 和点 b 之间连一条边,a 和 b 可能相等;
    Q1 a b,询问点 a 和点 b 是否在同一个连通块中,a 和 b 可能相等;
    Q2 a,询问点 a 所在连通块中点的数量;
    输入格式
    第一行输入整数 n 和 m。

    接下来 m 行,每行包含一个操作指令,指令为 C a b,Q1 a b 或 Q2 a 中的一种。

    输出格式
    对于每个询问指令 Q1 a b,如果 a 和 b 在同一个连通块中,则输出 Yes,否则输出 No。

    对于每个询问指令 Q2 a,输出一个整数表示点 a 所在连通块中点的数量

    每个结果占一行。

    数据范围
    1≤n,m≤105
    输入样例:
    5 5
    C 1 2
    Q1 1 2
    Q2 1
    C 2 5
    Q2 5
    输出样例:
    Yes
    2
    3
*/
#include<iostream>
using namespace std;

const int N = 1e5+5;
int p[N],count[N];

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

int main(){
    int n,m;
    cin >> n>> m;
    for(int i=1; i<=n; i++){
        p[i] = i;
        count[i] = 1;
    }
    while(m--){
        char op[2];
        int a,b;
        scanf("%s %d %d",op,&a,&b);
        if(op[0] == 'C'){
            int fa = find(a);
            int fb = find(b);
            if(fa != fb){
                p[fa] = fb;
                count[fb] += count[fa];
            }
        }
        if(op[0]=='Q' && op[1]=='1'){
            if(find(a) == find(b))  puts("Yes");
            else    puts("No");
        } 
        if(op[0]=='Q' && op[1]=='2'){
            cout << count[ find(a) ] << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 836. 合并集合

魚ヾ
2021-12-01 20:52
/*
    一共有 n 个数,编号是 1∼n,最开始每个数各自在一个集合中。

    现在要进行 m 个操作,操作共有两种:

    M a b,将编号为 a 和 b 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;
    Q a b,询问编号为 a 和 b 的两个数是否在同一个集合中;
    输入格式
    第一行输入整数 n 和 m。

    接下来 m 行,每行包含一个操作指令,指令为 M a b 或 Q a b 中的一种。

    输出格式
    对于每个询问指令 Q a b,都要输出一个结果,如果 a 和 b 在同一集合内,则输出 Yes,否则输出 No。

    每个结果占一行。

    数据范围
    1≤n,m≤105
    输入样例:
    4 5
    M 1 2
    M 3 4
    Q 1 2
    Q 1 3
    Q 3 4
    输出样例:
    Yes
    No
    Yes
*/

#include<iostream>
using namespace std;

const int N = 1e5+5;
int p[N];


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

int main(){
    int n,m;
    cin >> 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[0] == 'M'){
            p[find(a)] = find(b);
        }else{
            if(find(a) == find(b) )
                    puts("Yes");
            else    puts("No");
        }
    }
    return 0;
}


活动打卡代码 AcWing 835. Trie字符串统计

魚ヾ
2021-12-01 20:01
/*
    维护一个字符串集合,支持两种操作:

    I x 向集合中插入一个字符串 x;
    Q x 询问一个字符串在集合中出现了多少次。
    共有 N 个操作,输入的字符串总长度不超过 105,字符串仅包含小写英文字母。

    输入格式
    第一行包含整数 N,表示操作数。

    接下来 N 行,每行包含一个操作指令,指令为 I x 或 Q x 中的一种。

    输出格式
    对于每个询问指令 Q x,都要输出一个整数作为结果,表示 x 在集合中出现的次数。

    每个结果占一行。

    数据范围
    1≤N≤2∗104
    输入样例:
    5
    I abc
    Q abc
    Q ab
    I ab
    Q ab
    输出样例:
    1
    0
    1
*/
#include<iostream>
using namespace std;

const int N = 2e4+5;
int son[N][26],flag[N];
char str[N];
int index=0;

void insert(char* str){
    int p=0;
    for(int i=0; str[i]!='\0'; i++){
        int u = str[i] - 'a';
        if( son[p][u] == NULL ) son[p][u] = ++index;
        p = son[p][u];
    }
    flag[p] ++;
}

int query(char* str){
    int p=0;
    for(int i=0; str[i]!='\0'; i++){
        int u = str[i] - 'a';
        if( son[p][u] == NULL ) return 0;
        p = son[p][u];
    }
    return flag[p];
}

int main(){
    int n;
    cin >> n;
    while(n--){
        char op[2];
        scanf("%s %s",op,str);
        if(op[0]=='I'){
            insert(str);
        }
        if(op[0]=='Q'){
            cout << query(str) << endl;
        }
    }

    return 0;
}


活动打卡代码 AcWing 3302. 表达式求值

魚ヾ
2021-12-01 18:05
/*
    给定一个表达式,其中运算符仅包含 +,-,*,/(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。

    注意:

    数据保证给定的表达式合法。
    题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
    题目保证表达式中所有数字均为正整数。
    题目保证表达式在中间计算过程以及结果中,均不超过 231−1。
    题目中的整除是指向 0 取整,也就是说对于大于 0 的结果向下取整,例如 5/3=1,对于小于 0 的结果向上取整,例如 5/(1−4)=−1。
    C++和Java中的整除默认是向零取整;Python中的整除//默认向下取整,因此Python的eval()函数中的整除也是向下取整,在本题中不能直接使用。
    输入格式
    共一行,为给定表达式。

    输出格式
    共一行,为表达式的结果。

    数据范围
    表达式的长度不超过 105。

    输入样例:
    (2+2)*(1+1)
    输出样例:
    8
*/

#include<iostream>
//#include<cstring>
//#include<algorithm>
#include<stack>
#include<unordered_map>

using namespace std;

stack<int> num;
stack<char> op;

void eval(){
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    int result;
    if( c == '+' )  result = a+b;
    if( c == '-' )  result = a-b;
    if( c == '*' )  result = a*b;
    if( c == '/' )  result = a/b;
    num.push(result);
}

int main(){
    unordered_map<char,int> pr{ {'+',1},{'-',1},{'*',2},{'/',2}};
    string str;
    cin >> str;
    for(int i=0; i<str.size(); i++){
        auto c = str[i];
        if( isdigit(c) ){
            int x = 0;
            int j = i;
            while( j<str.size() && isdigit(str[j]) )    //直到碰到运算符 
                x = x*10 + (str[j++] - '0');        //字符转整形 
            i = j-1;            //使i定位到运算符前一个数字 
            num.push(x); 
        }
        else{
            if( c == '(')   op.push(c);     
            else{
                if(c == ')'){
                    while(op.top() != '(')
                        eval();
                    op.pop();   //弹出( 
                }
                else{
                    while(op.size() && pr[c]<=pr[op.top()]) //当前扫描到的运算符的优先级小于等于栈顶运算符优先级 
                        eval();
                    op.push(c);             //压入扫描到的运算符 
                }
            }
        }
    }
    while( op.size() )  eval();     //计算剩下的数 
    cout << num.top() <<endl;
    return 0;
}