img

牛客周赛Round31

小红小紫替换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

string s;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> s;
    cout << (s == "kou" ? "yukari" : s) << 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 endl "\n"
using namespace std;
typedef long long ll;
ll t,n,m,ans=0;
 
void solve() {
    cin>>n;
    for (int i=2;i<=n/i;i++){
        if (n%i==0){
            while(n%i==0) n/=i;
            ans++;
        }
    }
    cout<<ans+(n!=1);
} 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    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 endl "\n"
using namespace std;
typedef long long ll;
ll t,n,m,ans=0;
 
void solve() {
    char c;string s;
    cin>>n>>c;
    cin>>s;
    for (int i=0;i<n;i++)
    {
        if (s[i]==c) ans+=1+min((ll)i,n-i-1);
    }
    cout<<ans;
} 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

小红数组操作

链表和map模拟

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N=300010, M=998244353;
int n, m, k, q, a[N];
void solve() {
    cin>>n;
    list<int> q;
    map<int, list<int>::iterator> mp;
    for(int i=1; i<=n; ++i) {
        int op, x, y; cin>>op>>x;
        if(op==1) {
            cin>>y;
            if(y==0) {
                q.push_front(x);
                mp[x] = q.begin();
                //插入前面
            }else {
                auto it = mp[y];
                //记录编号
                q.insert(next(it), x);
                //下一个位置插入
                mp[x] =next(it);
                //下一个位置
            }
        }else {
            q.erase(mp[x]);
            //删除
            mp.erase(x);
        } 
    }
    cout<<q.size()<<'\n';
    for(auto x: q) {
        cout<<x<<' ';
    }
}
 
signed main(void) {
    ios::sync_with_stdio(0); cin.tie(0);
    int t=1;// cin>>t;
    while(t--) solve();
    return 0;
}

小红的子集取反

维护一个dp(i,j)，记录对于前i个元素，使数列元素和为j，最少需要的操作次数，对于每一个i，都遍历8e4个可能取值进行转移。

对于i,j，第i个元素为x，那么当前元素x可以选择保持初始符号，直接加进来，那么dp(i,j)从dp(i-1,j-x)转移过来，也可以选择取反再加，那么dp(i,j)从dp(i-1,j+x)+1转移过来，由于进行了取反操作，操作次数加一。

由于数组下标只能取正数，需要把它们映射到(0,8e4)上，映射后的4e4对应原来的0。最后检查dp(n,4e4)是否为初始值(inf)判断能否使元素和为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
27
#include <iostream>
#include <cstring>
using namespace std;
int n;
int a[210];
int f[210][80010];
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) 
    {
        cin >> a[i];
    }
    memset(f, 0x3f, sizeof(f));
    f[0][40000] = 0;
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 0; j <= 80000; j++) 
        {
             
            if (j + a[i] <= 80000 && j + a[j] >= 0) f[i][j] = min(f[i][j], f[i - 1][j - a[i]]);
            if (j - a[i] >= 0 && j - a[i] <= 80000) f[i][j] = min(f[i - 1][j + a[i]] + 1, f[i][j]);
        }
    }
    if (f[n][40000] <= n) cout << f[n][40000];
    else cout << -1;
    return 0;
}