20210807考试

封面来源

赏天灯-95640795

T1

前缀数组

我们定义一个字符串$S$ 的第$i(i≤|S|)$个前缀为其第一个字符至第$i$个字符依次连接形成的子串。一个字符串$S$ 的前缀数组的第$i$位为$j$，当且仅当在所有 $S$ 的前缀中，第$j$个前缀是字典序第$i$小的。换而言之，前缀数组中按照字典序记录了字符串所有前缀的编号。

现在小 X 想要知道，对于给定的字符串$S$,它的前缀数组是什么。

为了避免输出文件过大，你只需要输出前缀数组的每一位与其下标的乘积的和对$10^9+7$取模的结果即可。

输入

第一行一个整数 $Num$，表示测试点编号，以便选手方便地获得部分分，你可能不需要用到这则信息，样例中$ Num$ 的含义为数据范围与某个测试点相同。

接下来一行两个正整数 $N、M$，含义见题目描述。

接下来 $N$ 行，第 i 行两个整数 $Li、Ri$，含义见题目描述

solution.

其实就是求1-n的平方和…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include<bits/stdc++.h>
using namespace std;
#define int long long
int num;
string s;
const int mod=1e9+7;
signed main(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>num;
    cin>>s;
    int ans=0;
    for(int i=1;i<=s.size();i++){
        (ans+=i*i)%=mod;
    }
    cout<<ans<<endl;
    return 0;
}

T2

失意

小 X 是一个实力不强的 $OIer$，他一共在 $N$ 场比赛中失败过。

每一场比赛持续的时间可以用一个数轴上的区间$[Li,Ri]$来表示，同一时间可能会有多场比赛。

退役后，小 X 回忆起自己失败的 $OI$ 历程，他选择了 $M$ 场失败的比赛，定义这$M $场比赛持续时间的交集长度为这$M$场比赛的失败程度。

小 X 希望选出一组失败程度最高的 $M$ 场比赛。

solution

1.暴力.会TLE，会RE。

2.离散化后暴力. 会TLE

3.离散化后线段树. 会WA

4.贪心,在N个区间中找M个区间，使交集最大

 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


#include<bits/stdc++.h>
#define FOR(i,l,r) for(register int i=l;i<=r;++i)
using namespace std;
const int N = 1e6+7;
int num,n,m,ans,l,r;
priority_queue<int,vector<int>,greater<int> > q;
struct node{
    int l,r,id;
}nd[N];
bool cmp(const node &a,const node &b){
    return a.l<b.l;
}
signed main(){
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    scanf("%d%d%d",&num,&n,&m);
    FOR(i,1,n){
        scanf("%d%d",&nd[i].l,&nd[i].r);
        nd[i].id=i;
    }
    sort(nd+1,nd+n+1,cmp);
    FOR(i,1,n){
        // cout<<"asdasd"<<q.top()<<endl;
        q.push(nd[i].r);
        if(q.size()>m){
            q.pop();
        }
        if(q.size()==m&&q.top()-nd[i].l>ans){
            // cout<<i<<endl;
            ans=q.top()-nd[i].l;
            l=nd[i].l;
            r=q.top();
        }
    }
    printf("%d\n",ans);
    if(ans==0){
        FOR(i,1,m){
            printf("%d ",i);
        }
    }
    else{
        FOR(i,1,n){
            if(nd[i].l<=l&&nd[i].r>=r){
                printf("%d ",nd[i].id);
                m--;
                if(m==0){
                    return 0;
                }
            }
        }
    }
}

T3

小 X 是一个孤独的$ OIer$，退役后他发现他无法和其他人找到共同的话题。

好在小 X 有 $M$ 名同学，小 X 希望通过 $K$ 天的交流拉近与他们的关系这 $M$ 名同学可能感兴趣的话题共有 $N$ 种，我们用一个 $N$ 位的二进制数 $Ai$ 来表示一位同学对于各个话题是否感兴趣，例如，当 $N=3$，$Ai$=二进制数 110(即十进制数 66)，表示第$ i $位同学对第 1、第 2 个话题感兴趣，而对第 3 个话题不感兴趣。

每天，小 X 会选择一位同学，与其交流一个他感兴趣的话题。由于 $OIer$ 的记忆只有 7 秒，所以小 X 每天与同学交流的话题必须都一样。

现在，小 X 想要知道他有多少种不同的方式选择每天交流的同学，使得他能够找到至少一个话题，顺利地完成和他们的交流。两种选取方案不同，当且仅当在某一天小 X 选择的同学不同。

由于答案可能很大，输出其对 109+7109+7 取模的结果。

输入

第一行一个整数 $Num$，表示测试点编号，以便选手方便地获得部分分，你可能不需要用到这则信息，样例中$ Num$ 的含义为数据范围与某个测试点相同。

接下来一行三个整数 $N、M、K$，含义见题面描述接下来一行 $M $个整数 $Ai$，表示每名同学可能感兴趣的话题，以十进制的式给出

容斥原理，答案是$每个话题的方案数-两个话题的方案数+三个话题的方案数-四个话题的方案数\cdots$

代码

 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


#include<bits/stdc++.h>
#define int long long
#define FOR(i,l,r) for(register int i=l;i<=r;++i)
using namespace std;
const int M = 1e5+7;
const int mod = 1e9+7;
int num,n,m,k;
int ans;
inline int Qpow(register int a,register int b){
    register int ans =1;
    while(b){
        if(b&1){
            (ans*=a)%=mod;
        }
        b>>=1;
        (a*=a)%=mod;
    }
    return ans;
}
inline bool cal(register int x){
    register int res=0;
    while(x){
        res++;
        x-=(x&(-x));
    }
    if(res&1){
        return true;
    }
    return false;
}
int opt[1<<25];
int a[M];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>num>>n>>m>>k;
    FOR(i,1,m){
        // read(a[i]);
        cin>>a[i];
        for(int j=a[i];j;j=(j-1)&a[i]){
            opt[j]++;
        }
    }
    FOR(i,1,(1<<n)-1){
        if(!opt[i]){
            continue;
        }
        if(cal(i)){
            (ans+=Qpow(opt[i],k))%=mod;
        }
        else{
            ((ans-=Qpow(opt[i],k))+=mod)%=mod;
        }
    }
    cout<<ans<<endl;
}