img

牛客周赛 Round 32

小红的01背包

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

int main() 
{    
    int v, x, y;
    cin >> v >> x >> y;
    cout << v / x * y << '\n';

    return 0;
}

小红的dfs

暴力枚举即可（）

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
#include<bits/stdc++.h>
using namespace std;
char a[5][5];
int main()
{
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            cin>>a[i][j];
        }
    }
    int cnt=5;
    int ans=0x3f;
      for(int i=1;i<=3;i++)
      {  
          int cnt=3;
        if(a[i][1]=='d') cnt--;
       if(a[i][2]=='f') cnt--;
       if(a[i][3]=='s') cnt--;
       int q=2;
       if(i==1)
       {
           if(a[2][1]=='f')q--;
           if(a[3][1]=='s') q--;
           int w=cnt+q;
           ans=min(ans,w);
       }
       if(i==2)
       {
           if(a[1][2]=='d')q--;
           if(a[3][2]=='s') q--;
           int w=cnt+q;
           ans=min(ans,w);
       }
       if(i==3)
       {
           if(a[1][3]=='d')q--;
           if(a[2][3]=='f') q--;
           int w=cnt+q;
           ans=min(ans,w);
       }
      }
    
    cout<<ans<<endl;
}

小红的排列生成

排序之后减去即可，十分轻松写意

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n; cin >> n;
  vector<int> vp(n);
  for (auto &e: vp)
    cin >> e;
  sort(vp.begin(), vp.end());
  long long ans = 0;
  for (int i = 0; i < n; i ++)
    ans += abs(i + 1 - vp[i]);
  cout << ans << endl;
  return 0;
}

小红的二进制树

dfs再跑一遍dp就行

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
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],d[N];
vector<int>b[N];
int dfs(int x,int f)
{
    for(int i:b[x])
    {
        if(i==f)continue;
        d[x]+=dfs(i,x);
    }
    return d[x]+a[x];//子树其他节点贡献加上自己贡献
}
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        char t;
        cin>>t;
        a[i]=t-'0';
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        b[u].push_back(v);
        b[v].push_back(u);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)cout<<d[i]<<'\n';
}

小红的回文数

本题是很好的题

回文情况

如果长度是偶数，区间全部都是偶数

如果长度为奇数，那么区间内有且仅有一种字符数量是奇数

暴力枚举显然超时

官方题解

采取前缀和的思想

先找和当前相等的

再找和当前一位数不等的

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
map<vector<int>, int> m;
vector<int> temp(10);
int main()
{
    ios::sync_with_stdio(false);
    cin >> s;
    int len = (int)s.length();
    m[temp] ++;
    ll sum = 0;
    for(int i = 0; i < len; i ++)
    {
        temp[s[i] - '0'] ^= 1;
        //此数字多出现一次时，偶数变奇数，奇数变偶数
        //若出现的数字次数均为偶数时
        sum += m[temp];
        // 若此种奇偶情况之前出现过，则必然有合法区段，统计加入
        //若只有一个数字出现的次数为奇数，其他均为偶数时
        for(int j = 0; j < 10; j ++)
        {
            vector<int> tt = temp;
            tt[j] ^= 1;
            sum += m[tt];
        }
        //更新出现次数
        m[temp] ++;
    }
    cout << sum;
    return 0;
}

小红的矩阵修改

日后补罢（）