UOJ Logo insilent的博客

博客

张乙己

2018-10-13 19:28:45 By insilent

我从十二岁起,便在临汾第一中学校里学OI,老师说,样子太傻,怕刷不了几道题,就在洛谷里水点题罢。外面的UVa题库,虽然容易刷,但是题意唠唠叨叨缠夹不清的也很不少。他们往往要亲眼一个字一个字的看,看过到底是不是红题,又亲看将AC代码提交,然后放心:在这严重监督下,抄题解也很为难,所以又过了几天,教练又说我干不了这事。幸亏lris的情面大,劝退不得,便改为专刷Libre题库的一种无聊任务了。

  我从此便整天的坐在电脑前,专刷我的题目。虽然没有什么不好,但总觉得有些单调,有些无聊。教练是一副凶脸孔,教人活泼不得;只有张乙己到店,才可以笑几声,所以至今还记得。

张乙己一上洛谷,所有做题的人便都看着他笑,有的叫道,“张乙己,你门前又长出主席树了!”他不回答,对老师说,“开两台电脑,要一堆毒瘤题。”便排出一堆AC代码。他们又故意的高声嚷道,“你一定又AK了人家的比赛了!”张乙己睁大眼睛说,“你怎么这样凭空污人蒟蒻……”“蒟蒻?什么蒟蒻?我前天亲眼见你虐了insilent,吊着打。”张乙己便涨红了脸,额上的青筋条条绽出,争辩道,“AK不能算AK……AK!……巨佬的事,能算AK么?”接连便是难懂的话,什么“我是神犇”,什么“insilent是蒟蒻”之类,引得众人都哄笑起来:机房内外充满了快活的空气。

听人家背地里谈论,张乙己原来也做NOI的题,但终于不屑于再做,又不会出这种对他来说特别水的题目;于是做的题愈做愈难,难到我一看就吓晕了。幸而做得所有题目,便替人家做水题,换一道神仙毒瘤题做。可惜他又有一样坏脾气,便是不屑于做。做不到几天,便连人和电脑程序代码,一齐失踪。如是几次,叫他做水题的人也没有了。张乙己没有法,便免不了偶然做些AK神仙毒瘤比赛的事。但他在洛谷里,品行却比别人都好,就是从不拖欠;虽然间或不屑于做洛谷的题,暂时记在任务计划上,但不出一小时,定然全A,从任务计划上拭去了这些题目的名字。

张乙己做过几道神仙毒瘤题,涨红的脸色渐渐复了原,旁人便又问道,“张乙己,你当真能AK NOIP么?”张乙己看着问他的人,显出不屑、鄙视的神气。他们便接着说道,“你怎的连洛谷的题目也不刷光呢?”张乙己立刻显出藐视嘲讽模样,脸上笼上了一层红色,嘴里说些话;这回可是全是“全是水题”之类,一些不懂了。在这时候,众人也都哄笑起来:机房内外充满了快活的空气。

在这些时候,我可以附和着笑,老师是决不责备的。而且老师见了张乙己,也每每这样问他,引人发笑。张乙己自己知道不能和他们谈天,便只好向蒟蒻说话。有一回对我说道,“你会做旷野大计算么?”我略略摇一摇头。他说,“不会做,……我便考你一考。洛谷的深蓝题,怎样做的?”我想,这么大佬的人,也能考我么?便回过脸去,不再理会。张乙己等了许久,很恳切的说道,“不会做罢?……我教给你,记着!这些题应该记着。将来打我出的比赛的时候,做题要用。”我暗想我和他的等级还很远呢,而且我也从不敢打他出的神仙毒瘤比赛;又好笑,又不耐烦,懒懒的答他道,“谁要你教,不是只有你才会做的题目么?”张乙己显出极不高兴的样子,将两个指头的长指甲敲着键盘,点头说,“错啦错啦!……这些题目都是超级水的红题,你知道么?”我愈不耐烦了,努着嘴走远。张乙己刚打了一堆毒瘤算法以及宏函数,想在NOI官网上AK,见我毫不热心,便又叹一口气,显出极惋惜的样子。

有几回,邻居 lris 和 一帮大佬听得笑声,也赶热闹,拦住了张乙己。他便给他们神仙毒瘤题,一人几十道。他们做完题,仍然不散,眼睛都望着他的个人题库。张乙己着了慌,退出题目将屏幕锁住,弯腰下去说道,“太简单了了,这都太简单了。”直起身又看一看题目,自己摇头说,“简单简单!难乎哉?不难也。”于是这一群神犇巨佬都在笑声里走散了。

张乙己是这样的使人快活,可是没有他,别人也便这么过。

有一天,大约是国庆后的两三天,lris正在慢慢的算AC题目,取下粉板,忽然说,“张乙己长久没有打洛谷的题了。任务计划里还有十九道题呢!”我才也觉得他的确长久没有打洛谷的题了。一个蒟蒻的insilent说道,“他怎么会打我们这些水题?……他打神仙毒瘤题去了。”老师说,“哦!”“他总仍旧是AK。这一回,是自己太强,竟AK到雅礼集训里去了。雅礼集训的神仙毒瘤题,AK得的么?”“后来怎么样?”“怎么样?先拉他去了机房,把7天的题给他,后来是做题,做了几分钟,就直接AK了。”“后来呢?”“后来他AC完所有的神仙毒瘤题了。”“刷完了怎样呢?”“怎样?……谁晓得?许是去出神仙毒瘤题然后自己AC了。”老师也不再问,仍然不住地感叹张乙己是历史上最强的神犇大佬。

........

“insilent脑子发昏,竟想AC张柯尧大佬做的题,他家的题,做的了吗?”“后来怎样呢”“被张柯尧打,吊着打”


原帖

线段树

2018-05-29 18:08:07 By insilent
#include<cstdio>
#define umax 1000001
#define ll long long


ll ans[umax<<2],tag[umax<<2],n,m,a[umax];

inline ll ls(ll p)
{
    return p<<1;
}
inline ll rs(ll p)
{
    return p<<1|1;
}

inline void push_up(ll p)
{
    ans[p]=ans[ls(p)]+ans[rs(p)];
}
void build(ll p,ll l,ll r)
{
    tag[p]=0;
    if(l==r)    {ans[p]=a[l]; return;}
    ll mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}

inline void f(ll p,ll l,ll r,ll k)
{
    tag[p]+=k;
    ans[p]+=k*(r-l+1);
}
inline void push_down(ll p,ll l,ll r)
{
    ll mid=(l+r)>>1;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;
}
void update(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
    if(nl<=l&&r<=nr)
    {
        ans[p]+=k*(r-l+1);
        tag[p]+=k;
        return;
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
    if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
    push_up(p);
}

ll query(ll nl,ll nr,ll l,ll r,ll p)
{
    ll res=0;
    if(nl<=l&&r<=nr)
        return ans[p];
    ll mid=(l+r)>>1;
    push_down(p,l,r);
    if(nl<=mid)
        res+=query(nl,nr,l,mid,ls(p));
    if(nr>mid)
        res+=query(nl,nr,mid+1,r,rs(p));
    return res;
}

int main()
{
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);
    int tmp;
    ll opa,opb,uk;
    for(ll i=0;i<m;i++)
    {
        scanf("%d",&tmp);
        if(tmp==1)
        {
            scanf("%lld%lld%lld",&opa,&opb,&uk);
            update(opa,opb,1,n,1,uk);
        }
        else if(tmp==2)
        {
            scanf("%lld%lld",&opa,&opb);
            printf("%lld\n",query(opa,opb,1,n,1));
        }
    }
    return 0;
}

素数筛之神仙代码

2018-03-31 09:34:45 By insilent
#include<cstdio>
using namespace std;
inline char _(){
    static char _____________[1<<17],*______________=_____________,*_______________=_____________;
    return ______________==_______________&&(_______________=(______________=_____________)+fread(_____________,1,1<<17,stdin),______________==_______________)?EOF:*______________++;
}
template <class T> inline void __(T&____,register char ___=_(),int _____=1){
    for(____=0;(___<'0'||___>'9')&&___!='-';___=_());
    for(___=='-'?_____=-1,___=_():0;(___>='0'&&___<='9');___=_()) (____*=10)+=___-'0'; ____*=_____;
}
bool ______[10000007];
int _______[10000007];
inline void ________(){
    ______[1]=1;
    for(register int _________=2;_________<=10000000;++_________){
        if(!______[_________]) _______[++_______[0]]=_________;
        for(register int __________=1;__________<=_______[0]&&_________*_______[__________]<=10000000;++__________){
            ______[_________*_______[__________]]=1,_______[_________*_______[__________]]=1;
            if(_________%_______[__________]==0) break;
        }
    }
}
int main(){
    ________();
    int ____,___________,____________;
    __(____),__(___________);
    for(register int _________=1;_________<=___________;++_________){
        __(____________);
        if(!______[____________]) puts("Yes");
        else puts("No"); 
    }
    return 0;
}

#115. 幻想乡的烤红薯队伍比较坚强

2018-03-14 18:29:20 By insilent

事实证明暴力一个点都过不了


本题主要求和(以及快速幂)

当k为偶数时:

比如 k=6,那么 A+A^2+A^3+A^4+A^5+A^6=A+A^2+A^3+ A^3*(A+A^2+A^3)

s(k)=s(k/2)+A^(n/2) s(k/2)=s(k/2)\(1+A^(n/2))

当k为奇数时:

s(k)=s(k-1)+A^k , 那么k-1为偶数,可以按照上面的二分


再加上取模的基本运算:

(a*b)%m=((a%m)*(b%m))%m

(a+b)%m=((a%m)+(b%m))%m


上代码

#include<bits/stdc++.h>
using namespace std;
//(a*b)%c=((a%c)*(b%c))%c
int m;
long long power(long long n,long long b)        //快速幂
{
    if(b==1)
        return n%m;
    long long ans=power(n,b/2);
    ans=(ans*ans)%m;
    if(b%2==1)
        ans=(ans*(n%m))%m;
    return ans;
}
long long Mod(long long n,long long k)
{
    if(k==1)
        return n%m;
    if(k&1)
    {
        return (Mod(n,k-1)+power(n,k))%m;        //当k为奇数时,减1变为偶数 S(K)=S(K-1)+A^K  
    }
    else
    {
        return (((1+power(n,k>>1)))%m*Mod(n,k>>1))%m;        //当K为偶数时,S(K)=(1+A^(K/2))*S(K/2)  
    }
}
int main()
{
    long long n,k;
    cin>>n>>k>>m;
    printf("%lld",Mod(n,k));
    return 0;
}

#8. 【模板】单调队列(Sliding Window)

2018-02-24 04:22:52 By insilent

本题用到deque(双端队列)~~~~STL大法好

单调队列有两个性质:

1.队列中的元素其对应在原来的列表中的顺序必须是单调递增的。

2.队列中元素的大小必须是单调递(增/减/甚至是自定义也可以)

单调队列与普通队列不一样的地方就在于单调队列既可以从队首出队,也可以从队尾出队。

由此可见 用deque非常合适(当然也可以自己模拟)


就拿样例来谈谈,设以最小的为标准

8 3
1 3 -1 -3 5 3 6 7

>

下文中我们用q来表示单调队列,p来表示其所对应的在原列表里的序号。

1.由于此时队中没有一个元素,我们直接令1进队。此时,q={1},p={1}。

2.现在3面临着抉择。下面基于这样一个思想:假如把3放进去,如果后面2个数都比它大,那么3在其有生之年就有可能成为最小的。此时,q={1,3},p={1,2}

3.下面出现了-1。队尾元素3比-1大,那么意味着只要-1进队,那么3在其有生之年必定成为不了最小值,原因很明显:因为当下面3被框起来,那么-1也一定被框起来,所以3

永远不能当最小值。所以,3从队尾出队。同理,1从队尾出队。最后-1进队,此时q={-1},p={3}

4.出现-3,同上面分析,-1>-3,-1从队尾出队,-3从队尾进队。q={-3},p={4}。

5.出现5,因为5>-3,同第二条分析,5在有生之年还是有希望的,所以5进队。此时,q={-3,5},p={4,5}

6.出现3。3先与队尾的5比较,3<5,按照第3条的分析,5从队尾出队。3再与-3比较,同第二条分析,3进队。此时,q={-3,3},p={4,6}

7.出现6。6与3比较,因为3<6,所以3不必出队。3以前元素都<3,不必再比较,6进队。因为-3此时已经在滑动窗口之外,所以-3从队首出队。此时,q={3,6},p={6,7}

8.出现7。队尾元素6小于7,7进队。此时,q={3,6,7},p={6,7,8}。

那么,我们对单调队列的基本操作已经分析完毕。因为单调队列中元素大小单调递*(增/减/自定义比较),因此,队首元素必定是最值。按题意输出即可。


#include<bits/stdc++.h>
#include<deque>
using namespace std;
int a[1000005];
int n,k;
struct node{
    int zhi,num;
};
void tmax()
{
    deque <node> du;
    for(int i=1;i<=n;i++)
    {
        while((!du.empty())&&a[i]<=du.back().zhi)
            du.pop_back();
        du.push_back((node){a[i],i});
        if(i>=k)
        {
            while((!du.empty())&&i-k>=du.front().num)
                du.pop_front();
            printf("%d ",du.front().zhi);
        }
    }
}
void tmin()
{
    deque <node> du;
    for(int i=1;i<=n;i++)
    {
        while((!du.empty())&&a[i]>=du.back().zhi)
            du.pop_back();
        du.push_back((node){a[i],i});
        if(i>=k)
        {
            while((!du.empty())&&i-k>=du.front().num)
                du.pop_front();
            printf("%d ",du.front().zhi);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    tmax();
    printf("\n");
    tmin();
}

#63. 超市

2018-02-24 03:06:20 By insilent

解题思路:

用贪心的思想,将商品的价值从大到小排序,找到销售的最大期限,用ti数组标记,如果它的期限没有被占用,就在该天销售,如果占用,则从它的前一天开始向前查找有没有空闲的日期,如果有则占用。这样就可以得到最大销售量。


以下是我的贪心写法:


#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
struct subject{
    int price,deadline;
};
bool cmp(subject a,subject b)
{
    return a.price>b.price;
}
subject op[100005];
bool ti[100005];
int ans;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&op[i].price,&op[i].deadline);
    }
    sort(op+1,op+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(!ti[op[i].deadline])
        {
            ans+=op[i].price;
            ti[op[i].deadline]=1;
        }
        else
        {
            for(int j=op[i].deadline-1;j>=1;j--)
            {
                if(!ti[j])
                {
                    ans+=op[i].price;
                    ti[j]=1;
                    break;
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}



但据说本题应是贪心+并查集 以下引用于 kuangbin

这里其实用贪心做,并查集只是用来作为工具,使得速度更加快。 题目大意是买卖N件东西,每件东西都有个截止时间,在截止时间之前买都可以,而每个单位时间只能买一件。问最大获利。 如果购买不冲突,那么全部买下来就可以了。存在冲突,就需要取舍。显然在冲突的时候我们选择价格高的更优,如此就可以用贪心的算法。先将物品按照价格从高到底的顺序排列,购买一个就在时间点上做一个标记,只要不冲突就可以购买。 如何快速找到第一个不冲突的时间点呢,个人感觉使用并查集很好得解决了这个问题。 这里并查集的作用类似于链表指针,压缩的过程就是删掉节点的过程。从而在O(1)的时间内找到那个不冲突的点。


/*
POJ 1456
贪心处理。
按照获利p从大到小排序。
处理的时候选择最后的一个不冲突点。

用并查集实现链表的作用,快速找到不冲突点
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=10010;
int F[MAXN];
struct Node
{
    int p,d;
}node[MAXN];
bool cmp(Node a,Node b)//按p从大到小排序。d没有关系
{
    return a.p>b.p;
}
int find(int x)
{
    if(F[x]==-1)return x;
    return F[x]=find(F[x]);
}
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        memset(F,-1,sizeof(F));
        for(int i=0;i<n;i++)
          scanf("%d%d",&node[i].p,&node[i].d);
        sort(node,node+n,cmp);
        int ans=0;
        for(int i=0;i<n;i++)
        {
            int t=find(node[i].d);
            if(t>0)
            {
                ans+=node[i].p;
                F[t]=t-1;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

#74. 面积

2018-02-23 13:33:28 By insilent

本题思路:

染色

从正方形的四边开始找

数没被染色的块的个数

具体实现:

从正方形的四边开始,如果是0,就把它变成2(区分1)

被1包围的部分因为停止条件不会被染色

所以只需数仍是0的块


以下代码:

#include<cstdio>
#include<iostream>
using namespace std;
int a[20][20],ans;
bool mark[20][20];
void ufind(int x,int y)
{
    if(x<1||y<1||x>10||y>10||a[x][y]!=0)   //防止越界以及停止条件
        return;
    a[x][y]=2;
    ufind(x-1,y);
    ufind(x+1,y);
    ufind(x,y-1);
    ufind(x,y+1);
}
int main()
{
    for(int i=1;i<=10;i++)
        for(int j=1;j<=10;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=10;i++)
    {
        ufind(i,10);
        ufind(i,1);
        ufind(10,i);
        ufind(1,i);
    }
    for(int i=1;i<=10;i++)
    for(int j=1;j<=10;j++)
        if(a[i][j]==0)
            ans++;
    cout<<ans<<endl;
    return 0;
}

1519392762x-1404817587.jpg

#72. 细胞

2018-02-23 12:09:26 By insilent
#include<bits/stdc++.h>
using namespace std;
int ans,a[1000][1000],m,n;
bool mark[1000][1000];
void dfs(int x,int y,int lolo)
{
    if(x>m||y>n||mark[x][y]==1)
        return;
    mark[x][y]=1;
    if(a[x][y]==0)
        return;
    if(lolo==0&&a[x][y]!=0)
    {
        ans++;
        lolo=1;
    }
    dfs(x+1,y,lolo);
    dfs(x,y+1,lolo);
    dfs(x-1,y,lolo);
    dfs(x,y-1,lolo);
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%1d",&a[i][j]);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            dfs(i,j,0);
    cout<<ans<<endl;
    return 0;
}

#76. 家庭问题

2018-02-23 12:05:31 By insilent

这是bfs的做法

我认为本题应是并查集


#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int ans;
int n,k;
int u_max;
int board[105],zhi[105];  //zhi是记录家庭人数的  board是记录所属家庭的 
bool road[105][105];      //记录节点之间的关系 
int num;
void bfs(int place)
{
    ans++;                  //此时ans是家族编号 
    board[place]=ans;
    queue <int> q;          //经典队列做法 
    q.push(place);
    num=0;
    while(!q.empty())
    {
        num+=1;
        int tmp=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
        {
            if((!board[i]) && road[tmp][i])
            {
                board[i]=ans;
                q.push(i);
            }
        }    
    } 
    zhi[ans]=num;        //记录此家族人数 
}
int main()
{
    scanf("%d%d",&n,&k);
    int op1,op2;
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&op1,&op2);
        road[op1][op2]=road[op2][op1]=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(!board[i])
        {
            bfs(i);
            u_max=max(u_max,zhi[board[i]]);
        } 
    }
    printf("%d %d",ans,u_max);
    return 0;
}

大家写博客时把题目写在标签里吧,方便找

2018-02-23 11:26:37 By insilent

谢谢大家配合


1519385036x-1404817587.jpg

共 14 篇博客