[数据结构与算法]Codeforces Round #790 (Div. 4)A-H2

Codeforces Round #790 (Div. 4)
比赛网址
难度 div4 适合刚学不久的算法小白来写，博主备战区域赛所以也在练手速

A .Lucky?

题目意思：
给你 t 个六位数，如果前三位数字之和等于后三位数字之和，输出YES，否则输出NO。

题解：
开俩个变量记录前三位以及后三位的数字之和就可以了。

ac代码如下：

//
// Created by YikN on 2022/5/12.
//
#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 100;
int T;
int n, m;
int a[N];

int main() {
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        int sum = 0, sum1 = 0;
        for (int i = 0; i < 3; i++) {
            sum += (s[i] - '0');
        }
        for (int i = 3; i < s.size(); i++) {
            sum1 += (s[i] - '0');
        }
        //cout << sum << sum1 << endl;
        if (sum == sum1)puts("YES");
        else puts("NO");
    }
    return 0;
}

B. Equal Candies

题目意思：
有n个盒子，盒子里有a[i]颗糖果，问你吃多少糖果才能让每个盒子里的糖果数目相等？
有多组样例。
题解：
找到所有n个盒子里糖果最小的值，算出所有盒子糖果数量与最小糖果数的盒子数之差的和。
ac代码如下：

//
// Created by YikN on 2022/5/12.
//

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 100;
int T;
int n, m;
int a[N];

int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            sum += a[i];
        }
        sort(a + 1, a + n + 1);
        int num = a[1];
        sum -= num * n;
        printf("%d\n", sum);
    }
    return 0;
}

C.Most Similar Words

题目意思：
给你 n 个等长 m 的单词，单词的字母都由小写字母组成，问你哪一对单词，使它们单词相同所需改的次数最少，输出最少的次数，修改的字母只能修改为字母。

题解：
暴力枚举每两个单词，然后依次枚举每一位，找到他们的绝对值差值然后再相加，取最小操作值。

ac代码如下：

//
// Created by YikN on 2022/5/12.
//
#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 100;
int T;
int n, m;
char a[60][10];

int main() {
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
            scanf("%s", a[i]);
            // cout << a[i] << endl;
        }
        int res = 0x3f3f3f3f;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int ans = 0;
                for (int k = 0; k < m; k++) {
                   // cout << a[i][k] << a[j][k] << endl;
                    ans += abs((a[i][k] - 'a') - (a[j][k] - 'a'));
                  //  cout << ans << endl;
                }
                res = min(res, ans);
            }
        }
        cout << res << endl;
    }
    return 0;
}

D .X-Sum

题目意思：
对于每个测试用例，给你 1 个 n 行 m 列的棋盘，棋盘的每个格子上都有一个值，给你一个棋子，棋子可以向两个45度对角线攻击，问你哪个个位置棋子可以获得最大的值，输出最大值。

题解：
把这个点的坐标看成（x,y）注意在写代码的时候横坐标和纵坐标的顺序我们需要求的是在（y=x+b）和（y=-x+b）上的所有数值之和，这两个的直线都经过（x,y）所以我们只需要枚举x或者是y即可，注意x和y都要在n和m的范围内，写两个函数即可。

ac代码如下：

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 100;
int T;
int n, m;
int a[260][210];

int trun1(int y, int x) {
    int b = y - x;
    int res = 0;
    for (int i = 1; i <= m; i++) {
        int yy = i + b;
        if (yy >= 1 && yy <= n)res += a[yy][i];
    }
    return res;
}

int trun2(int y, int x) {
    int b = y + x;
    int res = 0;
    for (int i = 1; i <= m; i++) {
        int yy = -i + b;
        if (yy >= 1 && yy <= n)res += a[yy][i];
    }
    return res;
}

int main() {
    cin >> T;
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        int res = -0x3f3f3f3f;
       // cout << trun1(4, 4) << trun2(4, 4) << endl;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int ans = 0;
                ans += trun1(i, j);
                ans += trun2(i, j);
                ans -= a[i][j];
                res = max(res, ans);
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

E - Eating Queries

题目意思：
给你 n 颗糖，每个糖果都有糖量，有 多个查询，问你最少吃多少颗糖，才能使总糖量大于查询值，输出最小糖数，如果达不到查询值，输出 -1 ，多组查询。

题解：
查询多少，采用前缀和的方式进行记录，查询大小可以采用二分法来查询正确答案，数组内置函数lower__pound

注意为了保险起见不被爆long long直接longlong 但是要注意函数内置的参数也要为longlong

ac代码如下：

#include<bits/stdc++.h>

using namespace std;
const int N = 3 * 1e5 + 100;
int T;
int n, m;
long long a[N], s[N];

bool cmp(long long aa, long long b) {
    return aa > b;
}

int main() {
    cin >> T;
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
        }
        sort(a + 1, a + n + 1, cmp);
        s[0] = 0;
        //memset(s, 0, sizeof s);
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + a[i];
        }
        //for (int i = 1; i <= n; i++)cout << s[i] << endl;
        while (m--) {
            long long x;    //x内置也要是longlong型
            scanf("%lld", &x);
            int l = lower_bound(s + 1, s + n + 1, x) - s;
            if (l == n + 1)l = -1;
            printf("%d\n", l);
        }
    }
    return 0;
}

F. Longest Strike

题目意思：
给你一组序列，让你找出一组l，r要求所有在lr之间的数的数量大于k

题解：
看数据范围，序列的数据范围不高，但是所给数的范围较大，所以可以采用离散化
可以手写一个离散化然后再双指针算出最大的区间，也可以使用map，但是map可能会被卡，而且内置的auto遍历很多人不知道，所以小白还是手写一个离散化吧，先排序，然后再记忆所有不同的数，和记录数量，最后再双指针遍历即可

注意双指针需要注意一下边界，越界和重复计算也是要注意的

ac代码如下

#include<bits/stdc++.h>

using namespace std;
const int N = 3 * 1e5 + 100;
int T;
int n, m;
int a[N], s[N], num[N];

bool cmp(long long aa, long long b) {
    return aa > b;
}

int main() {
    cin >> T;
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        sort(a + 1, a + 1 + n);
        int idx = 0;
        for (int i = 1; i <= n; i++) {
            int j = i;
            while (a[j] == a[j + 1] && (j + 1 <= n))j++;
            s[++idx] = j - i + 1;
            num[idx] = a[i];
            i = j;
        }
        int l = -1, r = -1, len = -1;
        for (int i = 1; i <= idx; i++) {
            int j = i;
            while ((j + 1 <= idx) && s[j] >= m && s[j + 1] >= m && (num[j + 1] == num[j] + 1))j++;
            if ((l == -1 || num[j] - num[i] > len) && s[j] >= m) {
                l = i, r = j;
                len = num[j] - num[i];
            }
            i = j;
        }
        if (l != -1) {
            printf("%d %d\n", num[l], num[r]);
            // cout << num[l] << num[r] << endl;
        } else printf("-1\n");
    }
    return 0;
}

G - White-Black Balanced Subtrees

题目大意：
给你一组树的数据，每一个树的节点上都有一个棋子，有黑白两种颜色，问有多少棵子树的黑白棋子数相同。

题解：
就是dfs一下树的每一个节点，然后回溯计算节点数量。因为需要计算节点的信息所以
还是要设置一下数据结构，记录一下三个数量，黑白和总和

注意多组输入所以要重置数据
The first line of input contains an integer t (1≤t≤104) — the number of test cases.
The first line of each test case contains an integer n (2≤n≤4000) — the number of vertices in the tree.
The second line of each test case contains n?1 integers a2,…,an (1≤ai<i) — the parents of the vertices 2,…,n.
The third line of each test case contains a string s of length n consisting of the characters B and W — the coloring of the tree.
It is guaranteed that the sum of the values n over all test cases does not exceed 2?105.
看数据范围
图的输入最好使用scanf函数不要用cin因为超过1e5的数据scanf会比cin快很多

ac代码如下:

#include<bits/stdc++.h>

using namespace std;
const int N = 2 * 1e4 + 100;
int T;
int n, m;
int e[N], ne[N], h[N], idx;
string s;
int res = 0;
typedef pair<pair<int, int>, int> pii;

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

pii dfs(int x) {

    int W = 0, B = 0;
    W += s[x - 1] == 'W' ? 1 : 0;
    B += s[x - 1] == 'B' ? 1 : 0;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int j = e[i];
        pii P = dfs(j);
        W += P.first.first;
        B += P.first.second;
    }
    if (W == B && W != 0) {
        res++;
        //cout << x << endl;;
    }

    pii p = {{W, B}, res};
    return p;
}

int main() {
    cin >> T;
    while (T--) {
        res = 0;
        idx = 0;
        memset(h, -1, sizeof h);
        scanf("%d", &n);
        for (int i = 2; i <= n; i++) {
            int x;
            scanf("%d", &x);
            add(x, i);
        }
        cin >> s;
        dfs(1);
        printf("%d\n", res);
    }
    return 0;
}

H1/2题acwing上有很相似的题目
简单如代码

#include <bits/stdc++.h>

using namespace __gnu_pbds;
using namespace std; 

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tt;cin>>tt;
	while(tt--){
		int n;cin>>n;
		vector<int>a(n);
		ordered_set f,s;
		multiset<int>fi,se;
		long long ans=0;
		for(int i=0;i<n;i++){
			cin>>a[i];
			ans+=(int)f.size()-f.order_of_key(a[i]);
			f.insert(a[i]);
			fi.insert(a[i]);

		}
		//for(int i:f)cout<<i<<"  ";cout<<"\n";
		for(int i=n-1;i>=0;i--){
			ans+=s.order_of_key(a[i])+se.count(a[i]);
			s.insert(a[i]);
			se.insert(a[i]);

		}
		cout<<ans/2<<"\n";

	}
}

#include <bits/stdc++.h>

typedef long long int ll;
typedef long double ld;
using namespace std;

using namespace std;  



ll binpowmod(ll a, ll b, ll m) {
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}




long long modInverse(unsigned long long n, 
                                            ll p)
{
    return binpowmod(n, p - 2, p);
}



int main() 
{
  IOS;
  #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

  ll j,k,i,f,h,l,r,t1,t2,x,ans,y,tc,p,c,t3,u,q,a,w,t,d,b,n,m;
  cin >> tc ;
  while(tc--)
  {
    cin >> n ;
    ans=0;
    ordered_set<pair<ll,ll>> s;
    rep(i,n)
    {
      cin >> x ;
      s.insert({x,i});
      auto it=s.order_of_key({x,-1});

      ans+=s.size()-it-1;
    }
    //ans/=2;
    cout << ans << endl ;

    
  }
  

  return 0 ;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖