世间情动，不过盛夏白瓷梅子汤，碎冰碰壁当啷响。

世间情劫，不过三九黑瓦黄连鲜，糖心低落苦作言。

世间执念，不过隆冬弱水千层冰，斧砸锹凿不能移。

世间情深，不过群星点点衬孤月，黑夜相随永相明。

世间温柔，不过是芳春柳摇染花香，槐序蝉鸣入深巷，白茂叶落醉故乡。

图片

牛客周赛 Round 14

A

直接开模，先判断首尾，再判断中间，如果已经一点都不能删除了，直接退出。

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
#include<bits/stdc++.h>
using namespace std;
vector<char>k;
int t,ans;
int main()
{
    int n;
    cin>>n;
    char a;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        k.push_back(a);
    }
    
    while(k.size()>1)
    {
        t=0;
        if(k[0]==k[k.size()-1]) 
    {
        t=1;
        k.erase(k.begin());
        k.pop_back();
        ans+=2;
    }
   else for(int i=1;i<k.size();i++)
    {
        if(k[i]==k[i-1])
        {
            t=1;
            k.erase(k.begin()+i);
            k.erase(k.begin()+i-1);
            ans+=2;
            break;
        }
    }
    if(t==0)  break;
    }
    cout<<ans;
    return 0;
}

B

大就要除，不能整除直接跳

小就要乘法，直接乘法

最后判断

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
#include <iostream>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int x, y;
        cin >> x >> y;
        int ans = 0;
        while (x != y) {
            if (x < y) {
                x *= 5;
                ans++;
            }
            else if (x > y && x % 6 == 0) {
                x /= 6;
                ans++;
            }
            else break;
        }
        if (x == y) {
            cout << ans << endl;
        }
        else {
            cout << -1 << endl;
        }
    }
}

当然也有一种相对来说比较暴力的

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
#include<bits/stdc++.h>
using namespace std;
int main()
{
    map<double,int>k;
    for(int i=0;i<=100;i++)
    for(int j=0;j<=100;j++)
    {
        k[double(pow(5,i)/(pow(6,j)*1.0))]=i+j;
    }
    int n;cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        if(a==b) cout<<"0"<<endl;
        else 
        {
            double c;
        c=double(b/(a*1.0));
        if(k[c]) cout<<k[c]<<endl;
        else cout<<"-1"<<endl;
        }
        
    }
}

C

前缀和+二分

前缀和体现在26的字母的统计上

实际上也满足了单调递增的关系，因此可以用二分枚举左端点求右边界

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
#include <bits/stdc++.h>
#define endl "\n"
#define int long long
 
using namespace std;
 
const int N = 200010;
 
int pre[N][30];
 
char s[N];
 
int n,l,r;
 
int ans;
 
int find(int sta,int t)
{
    int l = sta - 1,r = n;
    while(l < r){
        int mid = l + r + 1 >> 1;
        int cnt = 0;
        for(int i = 0;i < 26;i ++ ){
            if(pre[mid][i] - pre[sta - 1][i] > 0) cnt ++; 
        }
        if(cnt <= t) l = mid;
        else r = mid - 1;
    }
     
    return l;
}
 
signed main()
{
    cin >> n >> l >> r;
    cin >> s + 1;
    for(int i = 1;i <= n;i ++ ){
        for(int j = 0;j < 26;j ++ )
            pre[i][j] = pre[i - 1][j] + (j == (s[i] - 'a'));
    }
 
    for(int i = 1;i <= n;i ++ ){
        ans += find(i,r) - find(i,l - 1);
    }     
    cout << ans << endl;
     
    return 0;
}

双指针也可以

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n, l, r;
    string str;
    cin >> n >> l >> r >> str;
    auto get = [&](int k) {
        map<char, int> mp;
        int res = 0;
        for (int r = 0, l = 0; r < n; r ++) {
            mp[str[r]] ++;
            while (l <= r && mp.size() > k) {
                mp[str[l]] --;
                if (mp.count(str[l]) && !mp[str[l]]) {
                    mp.erase(str[l]);
                }
                l ++;
            }
            res += r - l + 1;
        }
        return res;
    };
    cout << get(r) - get(l - 1) << "\n";
}

D

看数据->数学题

一个字符串的权值为：长度为3的回文子串的数量

求长度为n的、仅由小写字母组成的所有字符串的权值之和。

从中不难看出，所求结果为：

$ = (n - 2) ^{(n - 1)} (10^9 + 7) $

通过模拟几组情况可以验证这一公式的正确性。

由于数据n的范围最大是\(10^{12}\)，用暴力的方法一定会超时，所以要采用快速幂算法进行幂运算

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e9+7;
void solve(LL n)
{   LL a=26;
    LL res=1;
    LL k=n-1;
    while(k)
    {
        if(k&1) res=(res*a)%N;
        k>>=1;
        a=(a*a)%N; 
    }
    res=res%N;
 cout<<((n-2)%N*res)%N<<endl;
}
int main()
{
    LL n;cin>>n;
    if(n<3) 
    {
        cout<<"0"<<endl;
        return 0;
    }
    solve(n);
    return 0;
}
img