UOJ Logo lris的博客

博客

人世无常,学弟学妹加我啊

2020-09-20 16:15:06 By lris

转眼间就毕业了。

看了一眼,我大概不会做自己出的题了……

最近大学开学了,打算看看雅礼的题复健一下,结果发现居然有人在写,tql

有兴趣的话可以翻翻我以前的博客,好像是有雅礼的题解的(不过我的博客挂了,你可以试试这个看看能不能访问,如果不能就是我太懒了)

总之希望感兴趣的学弟学妹加我(qq2443064471)

有没有什么有趣的夏令营啊

2019-06-10 11:15:54 By lris

高二鶸省一选手(315pts),无其他奖项。

综合成绩以前100-(上次133,这次9),有什么适合的夏令营推荐么qwq

老咸鱼祝学习快乐~顺便宣传指针……

2019-02-12 16:48:07 By lris

这里是书名号《 》,退役老学长一枚,祝大家学习快乐~

以及别听老韩的,指针大法好! 给学妹看的指针简要介绍

为什么是学妹?我校自古有OIers女装的传统,学弟思考一下。

我都女装了qwq,你们不试试?

并查集的正确使用方式

2018-12-03 16:44:33 By lris
struct UFS
{
    int *f, *siz;
    UFS(int n): f(new int[n+1]), siz(new int[n+1]) {}
    void Find(int x)
      { return x==f[x]? x:f[x]=Find(f[x]); }
    void Union(int x, int y)
    {
        x=Find(x), y=Find(y);
        if(siz[x]>siz[y]) swap(x, y);
        f[x]=y, siz[y]+=(x==y);    
    }
}*s;

复杂度为反阿克曼函数,可以认为是O(1),这样Kruscal的复杂度才为O(n+mlogm)

一些简单的封装

2018-10-29 20:07:11 By lris

邻接表

struct Edge
{
    int v, w; Edge* nxt;
    Edge(int v, int w, Edge* nxt):
        v(v), w(w), nxt(nxt) {}
}*hd[N];
void AddEdge(int u, int v, int w)
  { hd[u]=new Edge(v, w, hd[u]); }

并查集

struct UFS
{
    int* f;
    UFS(int n): f(new int [n+1])
      { for(int i=1; i<=n; ++i) f[i]=i; }
    int Find(int x) 
      { return x==f[x]? x:f[f[x]]=Find(f[x]); }
    bool Merge(int a, int b)
    {
        a=Find(a), b=Find(b);
        return a==b? 0:f[a]=b;
    } 
}*s;

线段树(标记)

struct Tree
{
    Tree *lc, *rc;
    int l, r;
    ll dat, add, mul;
    Tree(int l, int r, Tree* lc, Tree* rc):
        l(l), r(r), lc(lc), rc(rc), dat((lc->dat+rc->dat)%p), add(0), mul(1) {}
    Tree(int l, int r):        //叶节点
        l(l), r(r), lc(NULL), rc(NULL), dat(a[l]), add(0), mul(1) {}
    static Tree* Build(int l, int r)
    {
        if(l>r) return NULL;
        if(l==r) return new Tree(l, r);
        int mid=l+(r-l)/2;
        return new Tree(l, r, Build(l, mid), Build(mid+1, r));
    }
    void Covermul(ll x)
      { dat=dat*x%p, mul=mul*x%p, add=add*x%p; }
    void Coveradd(ll x)
      { add=(add+x)%p, dat=(dat+x*(r-l+1))%p; }
    void Pushup()
      { dat=(lc->dat+rc->dat)%p; }
    void Pushdown()
    {
        lc->Covermul(mul); lc->Coveradd(add);
        rc->Covermul(mul); rc->Coveradd(add);
        mul=1, add=0;
    }
    void Multi(int l, int r, ll k)
    {
        if(l>this->r || r<this->l) return;
        if(l<=this->l && r>=this->r) Covermul(k);
        else
        {
            Pushdown();
            lc->Multi(l, r, k);
            rc->Multi(l, r, k);
            Pushup(); 
        }
    }
    void Addit(int l, int r, ll k)
    {
        if(l>this->r || r<this->l) return;
        if(l<=this->l && r>=this->r) Coveradd(k);
        else
        {
            Pushdown();
            lc->Addit(l, r, k);
            rc->Addit(l, r, k);
            Pushup(); 
        }
    }
    ll Ask(int l, int r)
    {
        if(l>this->r || r<this->l) return 0;
        if(l<=this->l && r>=this->r) return dat;
        Pushdown();
        return (lc->Ask(l, r)+rc->Ask(l, r))%p;
    }
};

内存池

struct Tree
{
    Tree *l, *r; int tot;
    Tree(Tree* l=NULL, Tree* r=NULL):
        l(l), r(r), tot(0) {}
}poorpool[PS], *root[N+3];
Tree* New()
{
    static int c_pool=0;
    if(c_pool==PS) return new Tree();
    return &poorpool[c_pool++];
}

有关根是否为割点的疑惑

2018-09-18 17:35:59 By lris

在部分书籍中若根在搜索树中有一颗以上的子树则根为割点,部分书籍中则为若子树中存在割点则根为割点,这两者本质上是相同的么?

对快读给函数传参产生疑惑

2018-09-17 17:59:14 By lris

如代码所示,使用快读给函数传参

#include<iostream>
#include<cstdio>
using namespace std;
int a[123];
inline int read()
{
    int t=0, f=0; char c;
    while(!isdigit(c=getchar())) f|=(c=='-');
    do t=(t<<3)+(t<<1)+c-'0';
    while(isdigit(c=getchar()));
    return f? -t:t;
}
void debug(int a, int b)
{
    printf("%d %d\n", a, b);
}
int main()
{
    int a=read(), b=read();
    debug(a, b);
    debug(read(), read());    
    return 0;
}

输入:

2 3 4 5

输出:

2 3

5 4

高一T5与高二T3题解

2018-08-28 14:19:55 By lris

推荐在我的博客 上浏览。 顺便征集友链qwq

高二T3

  • 最简单的三层for循环肯定会吧,我自己现场出数据在1000以内都可过。

  • 优化:考虑计算逆序对,在数值范围内建立树状数组:

    int ask(int x)
    {
        if(x<1) return 0;
        int ans=0;
        while(x)
            ans+=c[x], x-=x&-x;
        return ans;
    }
    void add(int p, int x)
    {
        while(p<=N-5)
            c[p]+=x, p+=p&-p;
    }
    int main()
    {
        int n=read();
        ll ans=0;
        for(int i=1; i<=n; i++) a[i]=read();
        for(int i=n; i; i--)
        {
            b[a[i]]=ask(a[i]-1);
            add(a[i], 1);
        }
        for(int i=1; i<=n; i++)
            for(int j=i+1; j<=n; j++)
                if(a[i]>a[j]) ans+=b[a[j]];
        printf("%lld", ans);
        return 0;
    }

如上述代码,我们求出了在某个数ai之后比它小的数的数量,我们用一个数组bi记录下来,就只需要两层循环了。

  • 优化++:但上述方式只能得90分,正解应该是再统计一遍ai之前比它大的数的数量ci,那么显然有:

    以ai为中间数的“弱点”的个数=bi*ci,累加即可。

    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=1000005;
    typedef long long ll;
    inline int read()
    {
        int t=0, f=0; char c;
        while(!isdigit(c=getchar())) f|=(c=='-');
        do t=(t<<3)+(t<<1)+c-'0';
        while(isdigit(c=getchar()));
        return f? -t:t;
    }
    int a[N], b[N], t_post[N], t_pre[N];
    int ask(int x, int t[])
    {
        if(x<1) return 0;
        int ans=0;
        while(x)
            ans+=t[x], x-=x&-x;
        return ans;
    }
    void add(int p, int x, int t[])
    {
        while(p<=N-5)
            t[p]+=x, p+=p&-p;
    }
    int main()
    {
        int n=read(), zd=0;
        ll ans=0;
        for(int i=1; i<=n; i++)
            a[i]=read(), zd=max(zd, a[i]);
        for(int i=n; i; i--)
        {
            b[a[i]]=ask(a[i]-1, t_post); //统计在ai之后比它小的数的数量
            add(a[i], 1, t_post);
        }
        for(int i=1; i<=n; i++)
        {
            ans+=(ll)(ask(zd, t_pre)-ask(a[i], t_pre))*b[a[i]];
            add(a[i], 1, t_pre);
        }
        printf("%lld", ans);
        return 0;
    }

高一T5

  • 对于1-3个点,可以看出就是求区间最大值,对于100000规模的数据暴力扫过就好了,为什么没有人拿分呢qwq

  • 对于4-6个点,我们可以根据深度dep将深度大的节点拉到与深度低的节点的同一深度,沿途更新答案。

    若同深度之后两节点重合,则答案显然,不然则同时将两节点向上拉(赋值为自身父亲的值),更新答案。

    zky的40分代码(1,4,5,6):

    #include<cstdio>
    #include<iostream>
    #include<vector>
    #include<cstring> 
    using namespace std;
    const int maxn = 1000005;
    int n, m, k, rt, ans, flag, from, to;
    int f[maxn], val[maxn];
    int deep[maxn];
    inline int read()
    {
        int t=0, f=0; char c;
        while(!isdigit(c=getchar())) f|=(c=='-');
        do t=(t<<3)+(t<<1)+c-'0';
        while(isdigit(c=getchar()));
        return f? -t:t;
    }
    void deal(int x, int y) {
        int t = deep[x] > deep[y] ? x : y, s = x == t ? y : x;
        while(deep[t] > deep[s]) ans = max(ans, val[t]), t = f[t];
        while(s != t) ans = max(ans, max(val[t], val[s])), t = f[t], s = f[s];
    }
    int main(void) {
    
        n=read(), m=read(), k=read();
        rt=read(), rt=read();
        deep[rt] = 1;
        rt=read(), rt=read();
        for(int i = 2; i <= k; ++i) {
            int b=read();
            for(int j = 1; j <= b; ++j) {
                int x=read();
                f[x]=read();
                val[x]=read();
                deep[x] = i;
            }
        }
        while(m--) {
            from=read(), to=read();
            ans = 0;
            deal(from, to);
            printf("%d\n", ans);
        }
    }
  • 正解:树上倍增,仿照LCA的倍增求法,fa[i][j]代表i的2^j辈祖先,zd[i][j]则代表i到它的2^j辈祖先路径上最长边的边权,则有 $$ fa[x][i]=fa[fa[x][i-1]][i-1] $$ $$ zd[x][i]=max(zd[x][i-1], zd[fa[x][i-1]][i-1]); $$

正解代码:

  #include<cmath>
  #include<cstdio>
  #include<iostream>
  #include<algorithm>
  using namespace std;
  const int N=1000005, INF=0x3f3f3f3f;
  int dep[N], fa[N][25], zd[N][25], t;
  inline int read()
  {
      int t=0, f=0; char c;
      while(!isdigit(c=getchar())) f|=(c=='-');
      do t=(t<<3)+(t<<1)+c-'0';
      while(isdigit(c=getchar()));
      return f? -t:t;
  }
  int Solve(int x, int y)
  {
      if(x==y) return 0;
      if(dep[x]<dep[y]) swap(x, y);
      int ans=0;
      for(int i=t; i>=0; i--) if(dep[fa[x][i]]>=dep[y])
          ans=max(ans, zd[x][i]), x=fa[x][i];
      if(x==y) return ans;
      for(int i=t; i>=0; i--) if(fa[x][i]!=fa[y][i])
          ans=max(ans, max(zd[x][i], zd[y][i])), x=fa[x][i], y=fa[y][i];
      return max(ans, max(zd[x][0], zd[y][0]));
  }
  int main()
  {
      int n=read(), m=read(), k=read(), x, y;
      t=log(n)/log(2);
      while(k--) if(y=read())
          while(y--)
          {
              x=read(), fa[x][0]=read(), zd[x][0]=read();
              dep[x]=dep[fa[x][0]]+1;
              for(int i=1; i<=t; i++)
                  fa[x][i]=fa[fa[x][i-1]][i-1],
                  zd[x][i]=max(zd[x][i-1], zd[fa[x][i-1]][i-1]);
          }
      while(m--) printf("%d\n", Solve(read(), read()));
      return 0;
  }

指针大法好!

2018-08-27 09:33:44 By lris

指针方便快捷,逻辑清晰,写代码没有累赘的[],多棒啊qwq

#126已修改并重测

2018-08-23 20:19:45 By lris

数据有锅,才一个点,输出精度大概有点问题,已修改并重测

然而只有kb和cyx写对了

共 19 篇博客