HN集训 day3

Author Avatar
ajcxsu 2018年06月22日
  • 160 次阅读

果然是一天比一天难
对菜鸡来说

上午

T1

30pts都不会系列
先去看了T2/3,再回来打
细节真多qwq

然后想了个好办(bao)法(li)
原本预想中1000保证过,1e5随机乱搞=30pts+?

结果测出来85pts???
错的还是前面的点....

T2

以为题面出错
0pts

T3

看上去很复杂的题
但我知道这是个人类智慧题

打表
好玄妙的函数...

噫某个项数组会爆很大
绝对有规律
打表
作差
分解因数...
又出现了这个性质??
玄妙啊

最后按着这个性质扩展
发现时间复杂度竟然比预想中的小不少?

打完预想50pts

测完10pts??
啊忘记取模了

改题

T1

环上不相交区间问题
使用倍增优化
std的思路实在是巧妙,非常简洁
我这个菜鸡基本上就只能对着题解打代码,不知道如何简单处理qwq

由于奇怪的std,自己程序里也出现了奇奇怪怪的下划线变量名

Code

// Code by ajcxsu
// Problem: circular

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10, OP=20;
struct Seg { int x, y; } s[N];
bool cmp(const Seg &a, const Seg &b) { return a.y<b.y; }
typedef pair<int, int> mpair;
mpair de[N<<1];
int nxt[N][OP];

template<typename T> inline void gn(T &x) {
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

int main() {
    ios::sync_with_stdio(false);
    int m,n;
    gn(m), gn(n);
    for(int i=1;i<=n;i++) {
        gn(s[i].x), gn(s[i].y);
        if(s[i].y<s[i].x) s[i].y+=m;
        s[n+i].x=s[i].x+m, s[n+i].y=s[i].y+m;
    }
    for(int i=1;i<=2*n;i++) {
        de[i]=mpair(s[i].y, i);
        de[i+2*n]=mpair(s[i].x, i+2*n);
    }
    sort(de+1, de+1+4*n);
    int lst=-1;
    for(int i=4*n, id; i>=1; i--) {
        id=de[i].second;
        if(id<=2*n) nxt[id][0]=lst;
        else {
            id-=2*n;
            if(lst<0 || s[lst].y>s[id].y) lst=id;
        }
    }
    for(int j=1;j<OP;j++)
        for(int i=1;i<=2*n;i++)
            nxt[i][j]=(nxt[i][j-1]==-1?-1:nxt[nxt[i][j-1]][j-1]);
    int ans=0, tot=0;
    for(int i=1;i<=2*n;i++) {
        int _j=i;
        tot=0;
        for(int j=OP-1;j>=0;j--)
            if(nxt[_j][j]>0 && s[nxt[_j][j]].y<=s[i].x+m)
                _j=nxt[_j][j], tot|=1<<j;
        ans=max(ans, tot+1);
    }
    printf("%d\n", ans);
    return 0;
}

T2

咕咕
突然又发现题面没问题了
不会FFT.jpg

T3

这题真的...
看不出来..
打算弃坑...


忽然发现每次都是开了坑不填系列....

谁雇的水军..

嘲讽菜鸡没意思...

本文链接:https://acxblog.site/archives/hn-day3.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。

    菜鸡1号
    菜鸡1号  2018-06-22, 17:07

    fAKe
    AK爷太假了

    菜鸡2号
    菜鸡2号  2018-06-22, 17:08

    fAKe
    AK爷太假了

    菜鸡3号
    菜鸡3号  2018-06-22, 17:10

    fAKe
    AK爷太假了

    菜鸡4号
    菜鸡4号  2018-06-22, 17:10

    fAKe
    AK爷太假了

    菜鸡5号
    菜鸡5号  2018-06-22, 17:11

    fAKe
    AK爷太假了

    菜鸡6号
    菜鸡6号  2018-06-22, 17:11

    fAKe
    AK爷太假了

    菜鸡7号
    菜鸡7号  2018-06-22, 17:12

    fAKe
    AK爷太假了

    菜鸡8号
    菜鸡8号  2018-06-22, 17:13

    fAKe
    AK爷太假了

    菜鸡⑨号
    菜鸡⑨号  2018-06-22, 17:14

    fAKe
    AK爷太假了

    菜鸡11号
    菜鸡11号  2018-06-22, 18:31

    你太菜了(五毛一条,记得删除)

    菜鸡12号
    菜鸡12号  2018-06-22, 18:32

    你太菜了()

    菜鸡13号
    菜鸡13号  2018-06-22, 18:35

    你太菜了(删除)

    菜鸡14号
    菜鸡14号  2018-06-22, 19:11

    我是第14个菜鸡,(博主的巨佬身份瞒不住了……随我们搞了qwq

    stO yzk Orz
    stO yzk Orz
    stO yzk Orz
    stO yzk Orz
    stO yzk Orz
    stO yzk Orz

      ajcxsu
      ajcxsu  2018-06-22, 19:14

      来嘲讽菜鸡了(哭)