ex_Asbable

ex_Asbable's blog!

20220322校内考试 T1 最大数题解

2022-03-23

ex_Asbable

20220322校内考试 T1 最大数题解
- 题目描述
- 解法
- CODE

const mathBlocks = document.querySelectorAll(‘script[type^=”math/tex”]’); Array.from(mathBlocks).forEach((el) => { const tex = el.textContent.replace(“% <![CDATA[”, “”).replace(“%]]>”, “”); el.outerHTML = window.katex.renderToString(tex, { displayMode: el.type === “math/tex; mode=display”, }); });

20220322校内考试 T1 最大数题解

题目描述

现在请求你维护一个数列，要求提供查询和修改两种操作：

1.查询数列中最后 $L$ 个数的最大值

2.将数列末尾插入一个数， $(n+t)\ mod\ d$ ，t为最近一次查询操作的答案，强制在线

解法

单点修改，区间查询。

可以想到线段树。

首先建树，范围1到m，设一个数来记录当前数列长度，添加元素时在长度+1的地方增加那个数，并使长度+1；查询时直接区间查询即可。

CODE

const ll mn=2e5+10;
const ll mm=2e5+10;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const ll fni=0xc0c0c0c0;
ll n,d;
struct stree{
    ll l,r;
    ll add,dat;
    #define l(x) tr[x].l
    #define r(x) tr[x].r
    #define add(x) tr[x].add
    #define dat(x) tr[x].dat
}tr[mn<<2];
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
void build(ll now,ll l,ll r){
    l(now)=l;r(now)=r;
    if(l==r)return;
    ll mid=(l+r)>>1;
    build(lc(now),l,mid);
    build(rc(now),mid+1,r);
}
inline void spread(ll now){
    if(!add(now))return;
    dat(lc(now))=max(dat(lc(now)),add(now));
    dat(rc(now))=max(dat(rc(now)),add(now));
    add(lc(now))=max(add(lc(now)),add(now));
    add(rc(now))=max(add(rc(now)),add(now));
    add(now)=0;
}
void plu(ll now,ll l,ll r,ll o){
    if(l<=l(now) && r>=r(now)){
        dat(now)=max(dat(now),o);
        return;
    }
    spread(now);
    ll mid=(l(now)+r(now))>>1;
    if(l<=mid)plu(lc(now),l,r,o);
    if(r>mid)plu(rc(now),l,r,o);
    dat(now)=max(dat(lc(now)),dat(rc(now)));
}
ll ask(ll now,ll l,ll r){
    if(l<=l(now) && r>=r(now))return dat(now);
    spread(now);
    ll mid=(l(now)+r(now))>>1,ans=0;
    if(l<=mid)ans=max(ans,ask(lc(now),l,r));
    if(r>mid)ans=max(ans,ask(rc(now),l,r));
    return ans;
}
inline void read_init(){
    n=read<ll>();d=read<ll>();
    ll las=0,m=0;
    build(1,1,n);
    for(ll i=1;i<=n;i++){
        char s[5];
        scanf("%s",s+1);
        ll o=read<ll>();
        if(s[1]=='A')m++,plu(1,m,m,(o+las)%d);
        else las=ask(1,m-o+1,m),write(las,1);
    }
}
int main(){
    freopen("maxnumber.in","r",stdin);
    freopen("maxnumber.out","w",stdout);
    read_init();
    
    return 0;
}

Read All

20220320校内考试 T2 string 题解

2022-03-20

ex_Asbable
- 20220320校内考试 T2 string 题解
  - 题目描述
  - 解法
  - CODE
20220320校内考试 T2 string 题解

题目描述

给出 n 以及 n 个单词（仅包含小写字母）形成一个句子，现打乱这个句子，但是对于任意单词，在原句子和乱序句子中第 i 次出现的位置不会相差超过1。

求有多少个这样的乱序句子，对1000000007取模。

$n\le100000$

解法

首先，由“在原句子和乱序句子中第 i 次出现的位置不会相差超过1”中，就可以知道，只用在原序列中判断是否交换相邻两数就好了。

既然如此，发现前 i 个单词的合法乱序个数不会受到后面单词的影响，故无后效性。

所以自然而然想到 dp 。

怎么设计状态？

很简单，设 dp[i] 表示前 i 个单词的合法乱序句子个数对1000000007取模的值。

故若当前单词与上一个单词不同的话（交换会使序列改变），则dp[i]=dp[i-1]+dp[i-2]

反之，若相同，则dp[i]=dp[i-1]（因为此时交换不影响结果，不需更新）

总结一下：

dp[i]=dp[i-1]+dp[i-2]（a[i]!=a[i-1]）

dp[i]=dp[i-1]（a[i]==a[i-1]）

别忘了取模

CODE
```
const ll mn=1e5+10;
const ll mm=1e5+10;
const ll mod=1000000007;
const ll inf=0x3f3f3f3f;
const ll fni=0xc0c0c0c0;
ll n,dp[mn];string s[mn];
inline void read_init(){
    n=read<ll>();
    for(ll i=1;i<=n;i++)
        cin>>s[i];
}
int main(){
//    freopen("string17.in","r",stdin);
//     freopen("string.out","w",stdout);
    read_init();
    dp[0]=1;
    for(ll i=1;i<=n;i++)
        dp[i]=(dp[i-1]+(s[i]==s[i-1]?0:dp[i-2]))%mod;
    write(dp[n]%mod,1);
    return 0;
}
```
Read All
20220320校内考试 T1 hat 题解

2022-03-20

ex_Asbable
- 20220320校内考试 T1 hat 题解
  - 题目描述
  - 解法
  - CODE
\[u\]
20220320校内考试 T1 hat 题解

题目描述

给出一个正偶数 $n$ ，有 $n$ 个整数 $a_i$ ，并定义数组 b ，使 $b_i=$ 除 $a_i$ 外的所有数 $\in a$ 的异或和。

给出数组 b ，求 a 。

解法

由数组 b 的定义可知，设 B 为数组 b 的异或和，所以 B 就等于每一个 $a_i$ 的异或和（因为每个 $a_i$ 都异或了 n-1 次，且 n 是偶数， $a_i\oplus a_i=0$ ）。那么 $\forall b_i=B\oplus a_i$ ，所以 $A\oplus b_i=A\oplus (A\oplus a_i)$ ，由于异或满足结合律，则 $A\oplus b_i=a_i$ ，我们要求的 $a_i$ 它自己就冒出来了。（有点像小学数学的异或版）

所以只需要求出异或和 B，然后一个一个地异或输出就好了。

CODE
```
const int mn=2e5+10;
const int mm=2e5+10;
const int mod=1e9+7;
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll fni=0xc0c0c0c0c0c0c0c0;
ll n,xor_sum,b[mn];
inline void read_init(){
    n=read<ll>();
    for(ll i=1;i<=n;i++)
        b[i]=read<ll>();
}
int main(){
    // freopen("hat.in","r",stdin);
    // freopen("hat.out","w",stdout);
    read_init();
    for(ll i=1;i<=n;i++)
        xor_sum^=b[i];
    for(ll i=1;i<=n;i++)
        write(xor_sum^b[i],2);
    puts("");
    return 0;
}
```
Read All