A. Turtle Puzzle: Rearrange and Negate

题目链接

题意

有一数组$a$，你可以进行如下操作若干次:

  • 选择$l$和$r$满足$(1 \leq l \leq r \leq n)$
  • 将$a_l,a_{l+1}, \dots a_{r}$变为原来的相反数
    最后求$\sum_{i=1}^n a_{i}$

分析

假设$a_{i}$是负数我们可以选择$l=r=i$，所以结果就是$$\sum_{i=1}^n abs(a_{i})$$

代码

1
2
3
4
5
6
7
8
9
10
11
void solve(){
    int n;
    cin>>n;
    int ans=0;
    for(int i=0;i<n;i++){
        int y;
        cin>>y;
        ans+=abs(y);
    }
    cout<<ans<<endl;
}

B. Turtle and Piggy Are Playing a Game

题目链接

题意

输入$l$和$r$且$(2 \cdot l \leq r)$，选择一个数$x(l \leq x \leq r)$，初始得分为0，进行以下操作直到x等于1:

  • 选择$x$的一个因数$q$
  • 将$x$变成$\frac{x}{q}$，得分加1
    求最高得分

分析

考虑$l$和$r$的二进制数，因为$2 \cdot l \leq r$所以$r$的二进制位数肯定至少比$l$的二进制位数多一位，并且为了让分数最大，肯定要让$x$的质因数越多，观察到2的幂次的数肯定是质因数最多的，所以我们可以选择二进制位数和$r$一样的并且是2的幂次的数作为$x$，其结果就是$r$的二进制位数-1

代码

1
2
3
4
5
6
7
8
9
10
void solve(){
    int l,r;
    cin>>l>>r;
    int ans=0;
    while(r){
        ans++;
        r=r/2;
    }
    cout<<ans-1<<endl;
}

C. Turtle Fingers: Count the Values of k

题目链接

题意

输入三个整数$a，b，l$求满足以下条件的k的数量: $l = k \cdot a^x \cdot b^y$

分析

看数据范围发现完全可暴力找k，我们枚举$x$和$y$找$k$即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve(){
    int a,b,l;
    cin>>a>>b>>l;
    int aa=1;
    int bb=1;
    int ans=0;
    set<int>st;
    for(;aa<=l;aa=aa*a){
        for(bb=1;aa*bb<=l;bb=bb*b){
            if(l%(aa*bb)==0){
                st.insert(l/aa/bb);
            }
        }
    }
    cout<<st.size()<<endl;
}

D. Turtle and an Infinite Sequence

题目链接

题意

有一个无限长的序列$a$，初始时$a_{i}=i(0 \leq i)$，每一秒钟$a_i$会变成$a_{i-1} | a_i | a_{i+1}$特别的$a_{0}$会变成$a_{0} | a_{1}$，求$m$秒过后$a_n$的值

分析

本质上就是求$a_{max(0,n-m)}$到$a_{n+m}$的或和，我们设$L=max(0,n-m)，R=n+m$，我们把$L$和$R$看成二进制数，从高位开始比较，
观察到在某一位不同时，无论怎么样这一位以及接下来的位都可以置1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve(){
    ll n, m;
    cin >> n >> m;
    ll l = max(0ll, n - m);
    ll r = n + m;
    ll cnt = 0;
    while(l != r){
        l >>= 1;
        r >>= 1;
        cnt++;
    }
    ll ans = (l << cnt) | ((1ll << cnt) - 1);
    cout << ans << endl;
}

E. Turtle vs. Rabbit Race: Optimal Trainings

题目链接

题意

有一个长度位$n$的数组$a$，和$q$次询问，每次询问会给一个$l$和$u$，要选择一个最小的$r$，使得$\frac{(u+u+1- \sum_{i=l}^{r} a_{i}) \cdot \sum_{i=l}^{r} a_{i} }{2}$最大

分析

我们设$v=\sum_{i=l}^{r} a_{i}$，可以得到如下推导式
$$
\begin{aligned}
原式 &= \frac{(2 \cdot u + 1 - v) \cdot v}{2}
&= \frac{1}{2} \cdot [-v^2+(2u+1)\cdot v]
\end{aligned}
$$
观察到等式是个关于$v$的开口向下的二次函数，其最大值为$\frac{2u+1}{2}$，所以我们只需要找在$u$附近的两个数就行了，至于如何求$v$，我们可以把$a$做个前缀和数组$sum$，这样$v$就是$sum_r-sum_{l-1}$，我们要找$u$附近的数就可以用二分在$sum$数组里寻找$sum_{l-1}+u$因为$lower_bound$是寻找第一个大于等于$sum_{l-1}+u$的数，所以还要和它之前的一个数比较

代码

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
void solve(){
    int n;
    cin>>n;
    vector<int>vt(n+1),sum(n+1);
    for(int i=1;i<=n;i++){
        cin>>vt[i];
    }
    for(int i=1;i<=n;i++){
        sum[i]=vt[i]+sum[i-1];
    }
    int q;
    cin>>q;
    while(q--){
        int l,u;
        cin>>l>>u;
        int it=lower_bound(sum.begin()+1,sum.end(),sum[l-1]+u)-sum.begin();
        if(it==n+1){
            cout<<n<<" ";
            continue;
        }
        if(it==l){
            cout<<l<<" ";
            continue;
        }
        int k1=sum[it-1]-sum[l-1];
        int k2=sum[it]-sum[l-1];
        if(abs((k1-u)*1.0-0.5)<=abs((k2-u)*1.0-0.5)){
            cout<<it-1<<" ";
        }
        else{
            cout<<it<<" ";
        }

    }
    cout<<endl;
}