10.28闲话

闲话
960 words

10.28 闲话

摆了两天，没写闲话，今天决定续更。

日寄板块删除，因为觉得比较流水，没啥好记的，想看机房精神状态可查看 超级无敌旋风暴龙战士的日记。作为补偿，从今开始结尾放图（本人皱皮，故皱图较多）。

但是有些抽象的东西还是要记的，于是：

每日抽象

今日某同学网络鉴宝怒赚两万亿上头后挖宝翻车首付变首负。

评价：南柯一梦

发现了宝脏网站：七岁儿童智商测试，我在其中获得了 77 分，临近正常，可喜可贺。

想知道孩子的智商？快去测测吧！

顺带附上并不存在的满分评语：

智商：高智商 恭喜你，你的宝贝智商很高。但智商高的人会有些奇怪的表现，因为你的思维跳跃的太块了，比如大家在看跳水比赛，每个人都在谈论这个运动员的分数，但是你会突然就冒出一句：李宁的运动服真烂。因为你看到跳水运动员的泳裤是李宁的了，大家会觉得你很2，觉得你是个很古怪的人。

李宁怎么你了？

今天不想口胡题解了。

所以直接上图！

都看到这里了，我不放个题解过分了。

口胡题解

P7485 枫

预处理出每个长度的答案，对每次询问回答。

正难则反，考虑反向递推，发现每次都是隔 k 个插入一个数，所以我们可以从最内层向外扩展，每次反转区间，插入数，记录新答案位置。

上个代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
int const N=1000005;
int t,q,m,n,lst,ans[N],rev[N];
inline int rd()
{
    int x=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void wt(int x)
{
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
void solve(int k)
{
    q=rd(),m=rd(),lst=0;
    for(int i=1;++i<=m;)
    {
        if((i-1)%(k+1)!=0) ++lst;
        ans[i]=rev[lst]/k+rev[lst]+2;
        rev[i]=i-ans[i];
    }
    while(q--) n=rd(),wt(ans[n]),putchar(' ');
    putchar('\n');
}
signed main()
{
    t=rd(),ans[1]=1;
    for(int i=0;++i<=t;) solve(i);
    return 0;
}

CF979D Kuro and GCD and XOR and SUM

建立 \(\sqrt n\) 个 01 Trie，对于每个待插入的数，在其因数编号的 Trie 里插入，只用插小于 \(\sqrt n\) 的。插入同时统计结点子树内最小值便于询问。

对于询问，若 \(k\leq \sqrt n\) 查询第 \(k\) 棵 01 Trie，贪心选取，使最高位尽量与 \(x\) 不同，但若某一步时要进入的子树的最小值大于限制 （\(s-x\)）则不能进入。\(k>\sqrt n\) 暴力即可。

附上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
int const inf=0x3f3f3f3f;
int const N=100005,M=400,S=40000000;
int n,x,k,s,op,tot,rt[M],tr[S][2],mn[S];
bitset<N> vis;
void insert(int u,int x)
{
    mn[u]=min(mn[u],x);
    for(int i=20;~i;i--)
    {
        if(!tr[u][(x>>i)&1])
            tr[u][(x>>i)&1]=++tot,mn[tot]=inf;
        u=tr[u][(x>>i)&1],mn[u]=min(mn[u],x);
    }
}
int query(int u,int x,int lim)
{
    if(mn[u]>lim) return -1;
    int ret=0;
    for(int i=1<<20;i;i>>=1)
        if(x&i)
            if(mn[tr[u][0]]<=lim) u=tr[u][0];
            else u=tr[u][1],ret|=i;
        else
            if(mn[tr[u][1]]>lim) u=tr[u][0];
            else u=tr[u][1],ret|=i;
    return ret;
}
void sol1()
{
    cin>>x,vis[x]=1;
    for(int i=1;i<M&&i*i<=x;i++)
    {
        if(x%i) continue;
        insert(rt[i],x);
        if(x/i<M) insert(rt[x/i],x);
    }
}
void sol2()
{
    cin>>x>>k>>s;
    if(x%k) return cout<<-1<<endl,void();
    if(k<M) return cout<<query(rt[k],x,s-x)<<endl,void();
    int ret=-1;
    for(int i=k;i<=s-x;i+=k) if(vis[i])
        if(ret<0||(i^x)>(ret^x)) ret=i;
    return cout<<ret<<endl,void();
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n,tot=M-1;
    for(int i=0;i<M;i++)
        rt[i]=i,mn[i]=inf;
    while(n--)
        cin>>op,op==1?sol1():sol2();
    return 0;
}
Comments