头像

魚ヾ




离线:2天前


最近来访(17)
用户头像
吃糖葫芦的兔子
用户头像
RyanMoriarty
用户头像
甘棠
用户头像
多财多亿
用户头像
998
用户头像
FingerOne
用户头像
星逐月丶
用户头像
IER
用户头像
Kirito_9
用户头像
x6x
用户头像
我要出去乱说

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

魚ヾ
3天前
/*
    维护一个集合,支持如下几种操作:

    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. 最大异或对

魚ヾ
3天前
/*
    在给定的 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. 模拟堆

魚ヾ
3天前
/*
    维护一个集合,初始时集合为空,支持如下几种操作:

    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. 堆排序

魚ヾ
4天前
/*
    输入一个长度为 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;
}



魚ヾ
4天前

/*
    给定一个包含 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. 合并集合

魚ヾ
4天前
/*
    一共有 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字符串统计

魚ヾ
4天前
/*
    维护一个字符串集合,支持两种操作:

    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. 表达式求值

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

    注意:

    数据保证给定的表达式合法。
    题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-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;
}


活动打卡代码 AcWing 831. KMP字符串

魚ヾ
4天前
#include<iostream>

using namespace std;

const int N = 1e5+5;
const int M = 1e6+5;
char p[N],s[M];
int ne[N];

int main(){
    int n,m;
    cin >> n >> p+1 >> m >> s+1;

    //ne[]
    for(int i=2,j=0; i<=n; i++){
        while( j!=0 && p[i]!=p[j+1] )   j=ne[j];
        if(p[i]==p[j+1])   j++;
        ne[i] = j;
    }
    //匹配    
    for(int i=1,j=0; i<=m; i++){
        while( j!=0 && s[i]!=p[j+1])    j=ne[j];    //失配 返回到标记点
        if( s[i]==p[j+1] )  j++;                    
        if(j==n){                                   //匹配结束
            printf("%d ",i-n);
  //          j = ne[j];
        }
    }
    return 0;
}


活动打卡代码 AcWing 154. 滑动窗口

魚ヾ
5天前
/*
    给定一个大小为 n≤106 的数组。

    有一个大小为 k 的滑动窗口,它从数组的最左边移动到最右边。

    你只能在窗口中看到 k 个数字。

    每次滑动窗口向右移动一个位置。

    以下是一个例子:

    该数组为 [1 3 -1 -3 5 3 6 7],k 为 3。

    窗口位置            最小值 最大值
    [1 3 -1] -3 5 3 6 7 -1  3
    1 [3 -1 -3] 5 3 6 7 -3  3
    1 3 [-1 -3 5] 3 6 7 -3  5
    1 3 -1 [-3 5 3] 6 7 -3  5
    1 3 -1 -3 [5 3 6] 7 3   6
    1 3 -1 -3 5 [3 6 7] 3   7
    你的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

    输入格式
    输入包含两行。

    第一行包含两个整数 n 和 k,分别代表数组长度和滑动窗口的长度。

    第二行有 n 个整数,代表数组的具体数值。

    同行数据之间用空格隔开。

    输出格式
    输出包含两个。

    第一行输出,从左至右,每个位置滑动窗口中的最小值。

    第二行输出,从左至右,每个位置滑动窗口中的最大值。

    输入样例:
    8 3
    1 3 -1 -3 5 3 6 7
    输出样例:
    -1 -3 -3 -3 3 3
    3 3 5 5 6 7
*/

#include<iostream>

using namespace std;

const int N =1e6+5;
int a[N];//存放数列 
int q[N];//存放满足某条件的a元素的下标 
int hh=0,tt=-1;//队头,队尾 

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

    for(int i=0; i<n; i++){
        if( hh<=tt && q[hh]<i-k+1 ) hh++;
        while(hh<=tt && a[q[tt]]>=a[i] )    tt--;
        q[++tt] = i;
        if(i-k+1>=0 )   printf("%d ",a[ q[hh] ] );
    }
    cout << endl;

    hh=0;
    tt=-1;
    for(int i=0; i<n; i++){
        if(hh<=tt && q[hh]<i-k+1)   hh++;
        while(hh<=tt && a[q[tt]]<=a[i]) tt--;
        q[++tt] = i;
        if(i-k+1>=0)    printf("%d ",a[q[hh]]);
    }
    return 0;
}