UOJ Logo lris的博客

博客

高一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;
  }

评论

NaCl
友链请挂 CSDN https://blog.csdn.net/qq_19982679
insilent
所以题三还可以在第二次循环中边跑边删(奇怪的做法)代码如下(跑的慢了呢): #include<cstdio> #define max(a,b) a>b?a:b #define umax 1000005 typedef long long ll; int a[umax],c[umax],c2[umax],maxn=-99999; int ask(int x) { ll ans=0; while(x) ans+=c[x],x-=x&-x; return ans; } void add(int p, int x) { while(p<=maxn) c[p]+=x,p+=p&-p; } int ask2(int x) { ll ans=0; while(x) ans+=c2[x],x-=x&-x; return ans; } void add2(int p, int x) { while(p<=maxn) c2[p]+=x,p+=p&-p; } int main() { int n=read(); ll ans=0; for(int i=1; i<=n; i++) { a[i]=read(); maxn=max(maxn,a[i]); } for(int i=1;i<=n;i++) add2(a[i],1); for(int i=n; i; i--) { ans+=ask(a[i]-1)*(ll)(ask2(maxn)-ask2(a[i])); add(a[i], 1); add2(a[i],-1); } printf("%lld", ans); return 0; }
z2512690268
来个预处理少一点而十分玄学的做法 #include<cstdio> #include<iostream> using namespace std; const int maxn = 1000010; inline int qread(){ register int x = 0, ch = getchar(), flag = 0; while(ch < '0' || ch > '9') flag = (ch == '-'), ch = getchar(); while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); return flag ? -x : x; } long long bitree[maxn][2], ans; inline void add(int x, const int& ind, const int& w){ for(; x <= 1000000; x += x & -x) bitree[x][ind] += w; } inline long long ask(int x, const int& ind){ long long cnt = 0; for(; x; x -= x & -x) cnt += bitree[x][ind]; return cnt; } int n; int main(void){ n = qread(); for(int i = 1; i <= n; ++i){ int x = qread(); add(x, 0, 1); add(x, 1, ask(1000000, 0) - ask(x, 0)); ans += ask(1000000, 1) - ask(x, 1); } printf("%lld\n", ans); }
pushinl
然而事实上这题只要开longlong暴力都有90分qwq

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。