Chonu

Posted on In , Valine:

G Shift and Reverse

Topic

Bobo has a sequence $a_1,a_2,\dots,a_n$. He can rearrange the sequence using the following operation any number of times:

+ Select an integer i ($1 \le i \le n$) and change the sequence to $a_i, a_{i-1}, \dots, a_1, a_n, a_{n-1}, \dots, a_{i+1}$.

Bobo would like to know the number of different sequences can be obtained modulo $(10^9+7)$.

波波有一个序列$a_1,a_2,\dots,a_n$。他可以使用以下操作任意次数重新排列序列:

选择整数i($1 \le i \le n$)并将序列更改为$a_i, a_{i-1}, \dots, a_1, a_n, a_{n-1}, \dots, a_{i+1}$。

Bobo想知道有多少个不同的序列对$(10^9+7)$取模。

Analyse

遇到题目没思路就先模拟一下

一个新的数组a,标号从a1-an,假定选择k进行反转操作，执行操作后的序列为$a_{k},a_{k-1}…a_{k+2},a_{k+1},$

Posted on Edited on In , Valine:

A Intelligent Warehouse

Topic

In MI Intelligent Warehouse, there are $n_{}$ products, where the $i_{}$-th product is of size $a_i$. We always need to box producsts into all kinds of containers, and it will be safer and more cost efficient(效率高的) if for any two sizes of products, one is the other’s multiple, since(因为) there won’t be any residual(残余的) room in one container. So for each boxing we need to choose some products that for any two chosen products, either $a_i$ is multiple of $a_j$ or $a_j$ is multiple of $a_i$. Print the maximum number of products that can be chosen in one boxing.

在mi智能仓库中，有$n_{}$个产品，其中$i_{}$个产品的尺寸为$a_i$。我们总是需要把产品装进各种各样的容器中，如果任意两个尺寸的产品，一个是另一个的倍数，这样会更安全且成本效益更高，因为一个容器里不会有剩余的空间。因此，对于每次装箱，我们需要选择一些产品，对于任意两个选择的产品，要么是$a_i$是$a_j$的倍数，要么是$a_j$是$a_i$的倍数。打印出在一次装箱中选择的产品的最大数量。

Analyse

目的是选择若干个数字，其中任意两个数均成倍数关系

考虑最终选定的序列，将其排序后，每个数都必然是最大数的约数，所以其实存在一种递推关系，当$ai$是某个数列的最大数时，将$ai$的倍数加进来，整个数列必然也满足条件

考虑dp，dp[i]表示以i结尾的最长序列，dp关系式也如上文所说

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
constexpr int N=1e7;
int dp[N+10],mp[N+10];
void solve() {
    int n;cin>>n;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        mp[x]++;
    }
    int ans=0;
    for(int i=1;i<=N;i++){
        if(mp[i]){
            dp[i]+=mp[i];
            for(int j=i*2;j<=N;j+=i){
                dp[j]=max(dp[i],dp[j]);
            }
            ans=max(ans,dp[i]);
        }
    }
    cout<<ans;
}

B Intelligent Robot

C Smart Browser

Topic

In some social platforms(社交平台), there are some netizen(平台) who like to post “www“. Since the string is like the grass(草), which contains plenty of “/\“ shapes, so there are also some netizen who post “grass“.

As a fast, smart, and convenient browser, MI Browser can recognize this kind of text and show some special effects. Specifically(具体来说), given a string, MI Browser will determine(确定) the number of “/\“ shapes made by character “w“, where “w“ itself and the gap(间隙) between two adjacent(相邻的) “w“s both give one `/\` shape. If still not clear, please turn to sample input/output for more details.

As a MI fan, you want to detect(探究) the relationship between the special effects and the number of “/\“ shapes, so the thing you should do first is to determine the number of “/\“ shapes by yourself.

在一些社交平台上，有些网民喜欢发布“www”。由于这个字符串看起来很像草，其中包含了许多“/\”的形状，因此也有一些网民发布“grass”。

作为一款快速、智能且便捷的浏览器，MI浏览器能够识别这种文本并展示一些特殊效果。具体来说，给定一个字符串，MI浏览器会确定由字符“w”构成的“/\”形状的数量，其中“w”本身以及两个相邻“w”之间的间隙都构成一个“/\”形状。如果仍然不清楚，请参考示例输入输出以获取更多详情。

作为MI浏览器的粉丝，你想要探究这些特殊效果与“/\”形状数量之间的关系，因此你首先要做的就是自己确定“/\”形状的数量。

Analyse

双指针判断以v分隔开的w的字符数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve() {
    string s;cin>>s;
    int ans=0;
    for(int i=0;i<s.length();i++){
        if(s[i]=='w'){
            int cnt=1;
            while(s[i+1]=='w'&&i+1<s.length()){
                i++;cnt++;
            }
            ans+=2*cnt-1;
        }
    }
    cout<<ans<<endl;
}