UOJ Logo chtomede的博客

博客

标签

来诈尸了捏

2022-06-03 02:56:01 By chtomede

学弟们好好努力捏 爱拼才会赢 大学也不能躺平捏 不说了 准备补考去了

身败名裂

2019-12-18 18:40:45 By chtomede

想着拿树状数组做个A+B给高一的教一下A+B的正确姿势,然而失败了(luogu上就A了,LFYZOJ的数据还是强,233)

Update:第二天cyx也失败了,比我还惨,233,update里没开ll

STL封装版 单调队列

2019-11-07 19:48:49 By chtomede
struct QueueNode{int pos,val;};
struct HD_Queue
{
    deque<QueueNode> Q1,Q2;int k;
    inline void init(int length){k=length;}
    inline void clear(){Q1.clear();Q2.clear();}
    inline void push_max(int pos,int val)
    {
        while(!Q1.empty()&&pos-Q1.front().pos>=k)    Q1.pop_front();
        while(!Q1.empty()&&val>=Q1.back().val) Q1.pop_back();
        Q1.push_back((QueuNode){pos,val}); 
    }
    inline void push_min(int pos,int val)
    {
        while(!Q2.empty()&&pos-Q2.front().pos>=k)    Q2.pop_front();
        while(!Q2.empty()&&val<=Q2.back().val) Q2.pop_back();
        Q2.push_back((QueueNode){pos,val}); 
    }
    inline ll the_max(int pos)
    {
        while(!Q1.empty()&&pos-Q1.front().pos>=k)    Q1.pop_front();
        if(!Q1.empty())    return Q1.front().val;
        else            return 0;
    }
    inline ll the_min(int pos)
    {
        while(!Q2.empty()&&pos-Q2.front().pos>=k)    Q2.pop_front();
        if(!Q2.empty())    return Q2.front().val;
        else            return (ll)1e20;
    }
}q[N];

Treap(数组实现)

2019-04-27 06:38:07 By chtomede
#include<iostream>
#include<cstdio>
#include<cstdlib>
const int MaxN=100500,INF=0x7fffffff;
using namespace std;
struct Node{int cnt,lc,rc,val,siz,key;}a[MaxN];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int n,tot,root;
inline void update(int pos){a[pos].siz=a[a[pos].lc].siz+a[a[pos].rc].siz+a[pos].cnt;}
inline void zig(int & pos){int x=a[pos].rc;a[pos].rc=a[x].lc;a[x].lc=pos;a[x].siz=a[pos].siz;update(pos);pos=x;}
inline void zag(int & pos){int x=a[pos].lc;a[pos].lc=a[x].rc;a[x].rc=pos;a[x].siz=a[pos].siz;update(pos);pos=x;}
inline void insert(int & pos,const int va)
{
    if(!pos)    pos=++tot,a[pos].val=va,a[pos].cnt=1,a[pos].key=-rand();
    else if(a[pos].val==va)    a[pos].cnt++;
    else if(a[pos].val<va)
    {
        insert(a[pos].rc,va);
        if(a[a[pos].rc].key<a[pos].key)    zig(pos);    
    }
    else if(a[pos].val>va)    
    {
        insert(a[pos].lc,va);
        if(a[a[pos].lc].key<a[pos].key)    zag(pos);
    }
    update(pos);
}
inline void Dlt(int & pos,int va)
{
    if(a[pos].val<va)    Dlt(a[pos].rc,va);
    else if(a[pos].val>va)    Dlt(a[pos].lc,va);
    else if(a[pos].val==va)
    {
        if(a[pos].cnt>1)    a[pos].cnt--;
        else if(!a[pos].lc&&!a[pos].rc)    pos=0;
        else if(!a[pos].lc&&a[pos].rc)    pos=a[pos].rc;
        else if(!a[pos].rc&&a[pos].lc)    pos=a[pos].lc;
        else
        {
            if(a[a[pos].lc].key>a[a[pos].rc].key)    zig(pos),Dlt(a[pos].lc,va);
            else    zag(pos),Dlt(a[pos].rc,va);
        }
    }
    update(pos);
}
inline int rank(int pos,const int va,int k)
{
    if(!pos)    return 0;
    if(a[pos].val==va)    return k+a[a[pos].lc].siz+1;
    if(a[pos].val<va)    {k+=a[a[pos].lc].siz+a[pos].cnt;return rank(a[pos].rc,va,k);}
    else    return rank(a[pos].lc,va,k);
}
inline int srank(int pos,const int rk,int k)
{
    if(!pos)    return 0;
    if(a[a[pos].lc].siz+1+k<=rk&&a[a[pos].lc].siz+a[pos].cnt+k>=rk)    return a[pos].val;
    if(a[a[pos].lc].siz+a[pos].cnt+k<rk){k+=a[a[pos].lc].siz+a[pos].cnt;return srank(a[pos].rc,rk,k);}
    else    return srank(a[pos].lc,rk,k);
}
inline int lst(int pos,const int va)
{
    int ans=-INF;
    while(pos)
    {
        if(a[pos].val<va&&a[pos].val>ans)    ans=a[pos].val;
        if(va<=a[pos].val)    pos=a[pos].lc;
        else                pos=a[pos].rc;
    }
    return ans;
}
inline int nxt(int pos,const int va)
{
    int ans=INF;
    while(pos)
    {
        if(a[pos].val>va&&a[pos].val<ans)    ans=a[pos].val;
        if(a[pos].val>va)    pos=a[pos].lc;
        else                pos=a[pos].rc;
    }
    return ans;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)
    {
        int op=read(),x=read();
        if(op==1)    insert(root,x);
        if(op==2)    Dlt(root,x);
        if(op==3)    printf("%d\n",rank(root,x,0));
        if(op==4)    printf("%d\n",srank(root,x,0));
        if(op==5)    printf("%d\n",lst(root,x));
        if(op==6)    printf("%d\n",nxt(root,x));
    }
    return 0;
}

BST

2019-04-26 17:05:31 By chtomede
#include<iostream>
#include<cstdio>
const int MaxN=100500,INF=0x7fffffff;
using namespace std;
struct Node{int cnt,lc,rc,val,siz;}a[MaxN];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int n,tot,root;
inline void update(int pos)
{
    a[pos].siz=a[a[pos].lc].siz+a[a[pos].rc].siz+a[pos].cnt;
}
inline void insert(int & pos,const int va)
{
    if(!pos)    pos=++tot,a[pos].val=va,a[pos].cnt=1;
    else if(a[pos].val==va)    a[pos].cnt++;
    else if(a[pos].val<va)    insert(a[pos].rc,va);
    else if(a[pos].val>va)    insert(a[pos].lc,va);
    update(pos);
}
inline Node DltMin(int & pos)
{
    if(a[pos].lc){Node y=DltMin(a[pos].lc);update(pos); return y;}
    Node x=a[pos]; pos=a[pos].rc; return x;
}
inline void Dlt(int & pos,const int va)
{
    if(a[pos].val<va)            Dlt(a[pos].rc,va);
    else if(a[pos].val>va)       Dlt(a[pos].lc,va);
    else if(a[pos].val==va)
    {
        if(a[pos].cnt>1)    a[pos].cnt--;
        else if(a[pos].lc&&a[pos].rc)    {Node x=DltMin(a[pos].rc);a[pos].cnt=x.cnt;a[pos].val=x.val;}
        else if(a[pos].lc&&!a[pos].rc)    pos=a[pos].lc;
        else if(a[pos].rc&&!a[pos].lc)    pos=a[pos].rc;
        else if(!a[pos].lc&&!a[pos].rc)    pos=0;
    }
    update(pos);
}
inline int rank(int pos,const int va,int k)
{
    if(a[pos].val==va)    return k+a[a[pos].lc].siz+1;
    if(a[pos].val<va)    {k+=a[a[pos].lc].siz+a[pos].cnt;return rank(a[pos].rc,va,k);}
    else    return rank(a[pos].lc,va,k);
}
inline int srank(int pos,const int rk,int k)
{
//    cout<<a[a[pos].lc].siz<<" "<<k<<" "<<rk<<endl;
    if(a[a[pos].lc].siz+1+k<=rk&&a[a[pos].lc].siz+a[pos].cnt+k>=rk)    return a[pos].val;
    if(a[a[pos].lc].siz+a[pos].cnt+k<rk){k+=a[a[pos].lc].siz+a[pos].cnt;return srank(a[pos].rc,rk,k);}
    else    return srank(a[pos].lc,rk,k);
}
inline int lst(int pos,const int va)
{
    int ans=-INF;
    while(pos)
    {
        if(a[pos].val<va&&a[pos].val>ans)    ans=a[pos].val;
        if(va<=a[pos].val)    pos=a[pos].lc;
        else                pos=a[pos].rc;
    }
    return ans;
}
inline int nxt(int pos,const int va)
{
    int ans=INF;
    while(pos)
    {
        if(a[pos].val>va&&a[pos].val<ans)    ans=a[pos].val;
        if(a[pos].val>va)    pos=a[pos].lc;
        else                pos=a[pos].rc;
    }
    return ans;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)
    {
        int op=read(),x=read();
        if(op==1)    insert(root,x);
        if(op==2)    Dlt(root,x);
        if(op==3)    cout<<rank(root,x,0)<<endl;
        if(op==4)    cout<<srank(root,x,0)<<endl;
        if(op==5)    cout<<lst(root,x)<<endl;
        if(op==6)    cout<<nxt(root,x)<<endl;
    }
    return 0;
}

小奇的矩阵

2019-03-22 18:30:36 By chtomede

#236. 病毒

2019-02-24 18:05:15 By chtomede

直接用邻接矩阵储存(x[i][j]表示i优先级在j前面),然后将边连通,优先级与其......(不想写了)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,x[300][300],y[300][300],vis[300];
string a[50010],b,ans;
char mm;
int main()
{
    cin>>n>>a[1];

    for(int i=2;i<=n;i++)
    {
        cin>>a[i];
        for(int j=0;j<a[i].length();j++)
            mm=max(a[i][j],mm);
        for(int j=0;j<a[i].length()&&j<a[i-1].length();j++)
            if(a[i][j]!=a[i-1][j])
            {
                x[a[i-1][j]][a[i][j]]=1;
                break;
            }
    }

    cin>>b;

    for(int i='a';i<=mm;i++)
        for(int j='a';j<=mm;j++)
            for(int k='a';k<=mm;k++)
                if(x[j][i]&&x[i][k])
                    x[j][k]=1;

    for(int i='a';i<=mm;i++)
        for(int j='a';j<=mm;j++)
            if(x[i][j])
                x[i][0]++;

    int pp='a';
    for(int i=mm;i>='a';i--)
    {
        int flag=0,pos=0;
        for(int j='a';j<=mm;j++)
            if(x[j][0]==i-'a')
            {
                flag++;
                pos=j;
            }
        if(flag!=1)
        {
            cout<<0<<endl;
            return 0;
        }
        y[pos][pp++]=1;
    }
    for(int i=0;i<b.length();i++)
    {
        int flag=0;
        for(int j='a';j<=mm;j++)
            if(y[b[i]][j])
            {
                ans[i]=j;
                flag++;
            }
        if(flag!=1)
        {
            cout<<0<<endl;
            return 0;
        }
    }    
    for(int i=0;i<b.length();i++)
        cout<<ans[i];
    return 0;
}

#193. 鱼塘钓鱼

2019-02-14 09:03:47 By chtomede

思路:依次枚举可能到达的最远鱼塘的可能性,然后拿总时间减去到达最远鱼塘所需的时间,把人看成可瞬移,不断在可到达的范围内选鱼最多的掉即可

#include<iostream> 
using namespace std;
int n,a[100000],dis[100000],t[100000],aaa,T;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)    cin>>a[i];
    for(int i=1;i<=n;i++)    cin>>dis[i];
    for(int i=1;i< n;i++)    cin>>t[i];
    cin>>T;
    for(int i=2;i<n;i++)    t[i]+=t[i-1];
    for(int i=1;i<=n;i++){
        int tt=T-t[i-1],ans=0,sum[10000]={0};
        for(int j=1;j<=i;j++)
            sum[j]=a[j];
        while(tt>0){ //这里tt必须是>0,写成“tt”是不行的(非零即真) 
            int pos=0;
            for(int j=1;j<=i;j++)
                if(sum[j]>sum[pos])
                    pos=j;
            if(!pos)    break;
            ans+=sum[pos];
            sum[pos]-=dis[pos];
            tt--;
        }
        aaa=max(ans,aaa);
    }
    cout<<aaa<<endl;
    return 0;
}

优先队列优化后风味更佳哦

快读快写

2019-02-04 04:46:22 By chtomede

网传快读快写原理是读入和打印单个字符比整串数字快很多;

#include<iostream>
using namespace std;
inline int read(){//这个“inline”好像很*的样子 ,据说很方便啊 
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){//while 来读空格啥的 
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';//x=(x<<1)+(x<<3)+(ch^48);也不知道哪个速度快 
        c=getchar();
    }
    return x*f;
}
inline void write(long long x){
    char f[100];
    int t=0;
    if(x<0) {putchar('-');x*=-1;}
    while(x){
        f[++t]=x%10+'0';
        x/=10;
    }
    while(t) putchar(f[t--]);
}
/*void write(llg x){
      if(x>9)write(x/10);
      int xx=x%10;
      putchar(xx+'0');
}神仙写法*/
int n,x; 
int main(){
    n=read();
    write(n);
    return 0;
}
/*
putchar函数的基本格式为:putchar(c)。
(1)当c为一个被单引号(英文状态下)引起来的字符时,输出该字符(注:该字符也可为转义字符);
(2)当c为一个介于0~127(包括0及127)之间的十进制整型数时,它会被视为对应字符的ASCII代码,输出该ASCII代码对应的字符;
(3)当c为一个事先用char定义好的字符型变量时,输出该变量所指向的字符。
(百度百科) 
*/

ps:其实我感觉也没多快#8.用 scanf 388ms,用快读466ms,又是什么鬼?

#61. 新新汉诺塔

2019-02-03 22:56:53 By chtomede

代码:

#include<iostream>
#include<cstring>
using namespace std;
int a[13],b[13];//a数组中存放三级汉诺塔步数,b数组即为答案
int main(){
    memset(b,0x3f,sizeof(b));
    b[1]=1;

    for(int i=1;i<=12;i++)
        a[i]=2*a[i-1]+1; 

    for(int i=1;i<=12;i++)
        for(int j=1;j<i;j++)
            b[i]=min(b[i],2*b[j]+a[i-j]); 

    for(int i=1;i<=12;i++)
        cout<<b[i]<<endl;

    return 0;
}

b需要DP(感觉很暴力,一点没有递推的感觉)求出:

    b[i]=min(b[i],2*b[j]+a[i-j]);

b[j]表示的是上层的j个盘子到达目的地的次数(此时有4个柱子参与)

a[i-j]为剩下i-j个盘子的次数(此时就只有3个柱子参与,前j个占了一个柱子)

由于把前j个得挪回去,所以要把b[j]乘2;

共 12 篇博客