投稿
  1. 高性能架构探索首页
  2. C/C++

第三周总结报告

admin • • C/C++ • 阅读 139

第三周总结报告

SMU Winter 2023 Round #5 (Div.2)

总结: 本次模拟赛本来是在洛谷举行 , 但因为有 bug 换到了 codeforces 上 , 本场比赛我做出来了 A, B, C, D 四道题 , E 题测试时超时其他题基本没思路 , 还是多做算法题。

比赛题解:

A: Lucky?

难度: 入门

题意:

​ 给定一个长度为 6 的数字字符串 , 求前三位和是否等于后三位和 , 相等输出 "YES" , 不相等输出 "NO"。

思路:

无

#include <bits/stdc++.h>
using namespace std;

int t;

int main(void)
{
    cin >> t;

    while (t--)
    {
        string s;
        cin >> s;

        int num1 = (s[0] - '0') + (s[1] - '0') + (s[2] - '0');
        int num2 = (s[3] - '0') + (s[4] - '0') + (s[5] - '0');

        if (num1 == num2) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

B: Equal Candies

难度: 入门

题意:

​ 给定一个数组 , 求数组中的最小数和其他所有元素差值的和。

思路:

找到最小的数并将与其他元素的差相加。

#include <bits/stdc++.h>
using namespace std;

const int N = 50 + 10;

int t, n, min1, ans;
int arr[N];

// 归并排序
int merge_sort(int l, int r)
{
    if (l >= r) return arr[l];
    
    int mid = l + r >> 1;
    
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    
    int k = 0, i = l, j = mid + 1, temp[N];
    while (i <= mid && j <= r)
    {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    
    for (int i = l, j = 0; i <= r; i++, j++) arr[i] = temp[j];
    
    return arr[0];
}

int main(void)
{
    cin >> t;
    
    while (t--)
    {
        ans = 0;
        
        cin >> n;
      	for (int i = 0; i < n; i++) cin >> arr[i];
        
       	min1 = merge_sort(0, n - 1);	// 升序排序并返回最小值
        
        for (int i = 0; i < n; i++) if (arr[i] > min1) ans += arr[i] - min1;
                    
		cout << ans << endl;
    }
    
    return 0;
}

C: Most Similar Words

难度: 入门

题意:

​ 给定多个相等长度的字符串 , 求出两个字符串对应位置的字母差值和的最小值。

​ 两个字符串对应位置的字母是这样的 , 如: bese 和 cost , b 和 c 对应 , e 和 o 对应 , s 和 s对应 , e 和 t 对 应。

​ 差值指的是对应位置的字母在英文字母排列顺序 ( 也就是 a, b, c, d, ..., z ) 上差的绝对值。如: a 和 b 的差值为 1, a 和 z 的差值为 25。

注: 差值必须在 26 个英文字母的范围内计算 , 如 a 和 y 的差值是 24 , 而不是 2。

思路:

对应位置上的字母排列顺序靠后的减去排列靠前的 , 再求和 , 以此类推将所有的字符串都相互求一边 , 最后输出最小值。

#include <bits/stdc++.h>
using namespace std;

vector<string> ve;
int t;

int main(void)
{
    cin >> t;
    
    while (t--)
    {
        int min1 = INT_MIN;	// 使最小值最初为 int 的最小值
        cin >> n >> m;
        
        for (int i = 0; i < n; i++)
        {
            string a;
            cin >> a;
            ve.push_back(a);
        }
        
        for (int i = 0; i < n - 1; i++)
            for (int j = i + 1; j < n; j++)
            {
                int sum = 0;
            	for (int k = 0; k < m; k++)
                {
                    if (ve[i][k] >= ve[j][k])
                    	sum += ve[i][k] - ve[j][k];
                    else
                        sum += ve[j][k] - ve[i][k];
                }
                if (sum < min1) min1 = sum;
            }
		cout << min1 << endl;
        ve.clear();
    }
    
    return 0;
}

D: X-Sum

难度: 普及

题意:

​ 给定一个二维数组 a , 每个元素都有相应的值 $0 le a_{ij} le 10^6 $ , 现在把一个国际象棋中的棋子 "主教" 放在这个二维数组上把棋子能走的所有位置的值加起来 ( 包括棋子所在的位置的值也加起来 ) , 求棋子在什么位置加起来的值最大。

​ 国际象棋中的 "主教" 是在的对角线上走 ( 也就是右上方, 右下方, 左下方, 左上方), 如图:

第三周总结报告
思路:

先选定一个位置然后按一定的顺序朝一个方向加 , 比如右上方, 右下方, 左下方, 左上方, 以此类推算出棋子在每个位置值的总和, 最后输出最大值。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 200 + 10;

int arr[N][N];
int t;
int d_x[4] = {-1, 1, 1, -1};	// 求总和时行的搜索方向
int d_y[4] = {1, 1, -1, -1};	// 求总和时列的搜索方向

LL solve(int x, int y, int n, int m)
{
    if (x == n - 1 || y == m - 1) return arr[x][y];
    
    LL sum = arr[x][y];
    for (int k = 0; k < 4; k++)
    {
        int sx = x + d_x[k];
        int sy = y + d_y[k];
        while ((sx >= 0 && sx < n) && (sy >= 0 && sy < m))
        {
            sum += arr[sx][sy];
            sx += d_x[k];
            sy += d_y[k];
        }
    }
    
    return sum;
}

int main(void)
{
    cin >> t;
    
    while (t--)
    {
        cin >> n >> m;
        
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                cin >> arr[i][j];
        
        LL sum = 0, max = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
            {
                sum = solve(i, j, n, m);
                if (sum > max) max = sum;
            }
        cout << max << endl;
    }
    
    return 0;
}

SMU Winter 2023 Round #6 (Div.2)

总结: 本次比赛只做出来了 C 题和 I 题 , I 题简单 , C 题第一次提交超时了 , 因为用到是暴力运算 , 然后我把排序的部分换成了快速排序 , 查找换成了二分查找然后就过了 , 还是比较有成就的 , 但其他题都没做出来 , F 题超时了 , J 题测试时 WA , 其他题没思路 , 算法基础学习不能停。

比赛题解

C: Add 9 Zeros

难度:简单

题意:

​ 给定一个数组 a 有 n 个元素 , 对 a 中的每个元素加 9 并将其放到新数组 b 中 , 现在问 b 中有多少个元素与 a 中不同。

思路:

用快速排序对数组 a 进行升序排序 , 再用二分查找判断数组 b 中有多少个元素与 a 数组不同。

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;

int n, ans;
int a[N], b[N];

void quick_sort(int l, int r)
{
	if (l >= r) return;
	
	int x = a[l + r + 1 >> 1], i = l - 1, j = r + 1;
	while (i < j)
	{
		do i++; while (a[i] < x);
		do j--; while (a[j] > x);
		if (i < j) swap(a[i], a[j]);
	}
	
	quick_sort(l, i - 1);
	quick_sort(i, r);
}

int b_search(int n, int x)
{
	int l = 0, r = n - 1;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (a[mid] >= x) r = mid;
		else l = mid + 1;
	}
	if (a[l] != x) return 0;
	else return a[l];
}

int main(void)
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
		b[i] = a[i] + 9;
	}
	
	quick_sort(0, n - 1);	// 快速排序
	
	// 二分查找
	for (int i = 0; i < n; i++)
		if (!b_search(n, b[i]))
			ans++;
			
	cout << ans << endl;
	
	return 0;
}

J: Simple Game

难度: 简单

题意:

​ 给定一个数组 a , 现在把数组里下标为偶数的元素的和减去下标为奇数的元素的和 , 若差为奇数输出 "Alice" , 否则输出 "Bob"。

思路:

用两个变量分别存储数组下标为偶数的元素的和和下标为奇数元素的和。

代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int n;
int a[N];

int main(void)
{
	scanf("%d", n);
	int num1 = 0, num2 = 0;
	for (int i = 0; i < n; i++) 
	{
		scanf("%d", &a[i]);
		if (i % 2 == 0) num1 += a[i];
		else num2 += a[i];
	}
	
	if ((num1 - num2) % 2 == 0) cout << "Bob" << endl;
	else cout << "Alice" << endl;
	
	return 0;
}

SMU Winter 2023 Round #7 (Div.2)

总结: 今天的比赛做出来了 6 道题都是通过人数过百的题 , K 题是水题 , 做出来的其他题也比较简单 , 后面想攻克一下 B 题和 F 题 , 但 B 题没想出来 , F 题思路彻底错了。

比赛题解:

A: 解开束缚缠丝Ⅱ

难度: 简单

题意:

​ 给定若干个单个大写或小写的英文字母 , 求由这些英文字母组成的回文字符串的长度最长为多少?

​ 回文字符串: 对称的字符串 , 如: "AABB", "ccDaa", "level" 等。

**思路: **

​ 记录所有英文单词 ( 大写和小写都记录 ) 出现的次数 , 因为只要出现偶数次就能参与构成回文字符串 , 所以记录完所有字母出现的次数后某个字母整除 2 再乘 2 就能知道它为字符串贡献了多少长度, 如: a 出现了 5 次, $ 5 / 2 = 2 $ , (2 * 2 = 4) , a 使字符串长度增加 4 , 以此类推相加就能求出回文字符串的最长长度。

​ 当回文字符串长度为奇数时 , 最中间的字母就出现一次 , 如: "level" 中的 v , 所以为了保证长度最大当某个字母在输入中出现次数为奇数时字符串长度可以再加 1 ( 但只能加一次 )。

代码:

#include <bits/stdc++.h>
using namespace std;

int t, n;
int arr[52];	// 大小写英文字母加起来总共有 52 个

int main(void)
{
	scanf("%d", &t);
	
	while (t--)
	{
		int len = 0;
		scanf("%d", &n);
		cin.get();	// 回收按下的回车键
		while (n--)
		{
			char ch;
			scanf("%c", &ch);
			cin.get();	// 回收按下的空格
			
			if (ch <= 90) arr[ch - 65]++;	// 记录小写字母的出现次数, 在数组中的 0 ~ 25 的位置 
			else arr[ch - 71]++;	// 记录大写字母的出现次数, 在数组中的 26 ~ 51 的位置
		}
		
		int flag = 0;
		for (int i = 0; i < 52; i++)
		{
			if (flag == 0 && arr[i] % 2 != 0)
			{
				len++;
				flag = 1;
			}
			len += ((arr[i] / 2) * 2);
		}
		cout << len << endl;
		
		memset(arr, 0, sizeof(arr));	// 使数组的记录归零
	}
	
	return 0;
}

I: 好想听肆宝唱歌啊

难度: 简单

题意:

​ 输入一个数 n , 接下来 n 行每行有两个数据一个整数和一个字符串 , 在最后一行再输入一个整数 m , 输出n 个输入中字符串前面的整数大小为倒数第 m - 1 的字符串。

样例:

input

4
1 flos
3 Yellow
9 Starduster
1000000000 Kawakiwoameku
3

output

flos

思路:

创建一个结构体数组 , 结构体的成员是 n 个输入中的整数和字符串。

根据字符串前面的整数按升序排序结构体数组。

输出结构体数组中下标为第 m 的字符串。

代码:

#include <bits/stdc++.h>
using namespace std;

struct music
{
    int num;
    string s;
};

const int N = 1e5 + 10;

int n, m;

// 快速排序
void quick_sort(struct music arr[], int l, int r)
{
    if (l >= r) return;

    int x = arr[l + r + 1 >> 1].num, i = l - 1, j = r + 1;
    while (i < j)
    {
        do i++; while (arr[i].num > x);
        do j--; while (arr[j].num < x);
        if (i < j) swap(arr[i], arr[j]);
    }

    quick_sort(arr, l, i - 1);
    quick_sort(arr, i, r);

    return;
}

int main(void)
{
    struct music arr[N];

    cin >> n;

    for (int i = 0; i < n; i++) cin >> arr[i].num >> arr[i].s;
    cin >> m;

    quick_sort(arr, 0, n - 1);

    cout << arr[m].s << endl;

    return 0;
}

J: 毁灭凤凰人

难度: 简单

题意:

​ 有怪物有两个数值 atk: 2500 和 def: 2100 , 怪物打死了可以复活 , 现在有三种卡牌通过这些卡牌能真正打死怪物:

  • 0: 0 卡有自己的攻击力 , 若使用 0 卡 , 当怪物在攻击状态时 ( 0 表示攻击 , 1 表示防守 ) , 若这个卡的攻击力大于等于怪物的 atk ( 也就是大于等于 2500 ) 就能将怪物打死或当怪物在防守状态时 , 若这个卡的攻击力大于 def , 就能将怪物打死 ( 但怪物还是会复活 )。
  • 1: 若使用 1 卡 , 在把怪物打死的情况下怪物不能复活。
  • 2: 若使用 2 卡 , 在牺牲另一个卡牌的情况下可以将怪物打死并使怪物不能复活。

​ 现在给 n 个卡牌问能不能利用这些卡牌将怪物真正打死;

​ 真正打死怪物的方法: 在有要用的卡牌的情况下使用 0 卡 后使用 2 卡或在有大于 1 个卡牌的情况下使用 2 卡。

​ 若能真正打死输出 "haoye" , 否则输出 "QAQ" ( 不含引号 )。

思路:

在有 1 卡 的条件下判断是否有 0 卡并且这个 0 卡的攻击力能否打死怪物或在有 2 卡的条件下判断手中卡牌的总数是否大于 1 , 若能直接使用 2 卡即可。

代码:

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> ve;

int main(void)
{
	cin >> n >> m;
	
	int flag = 0;
	for (int i = 0; i < n; i++)
	{
		int card;
		cin >> card;
		if (card == 0)
		{
			int attack;
			cin >> attack;
			if ((attack >= 2500 && m == 0) || (attack > 2100 && m == 1)) flag = 1;
		}
		ve.push_back(card);
	}
	
	for (int i = 0; i < n; i++)
	{
		if (ve[i] == 1 && flag == 1)
		{
			cout << "haoye" << endl;
			return 0;
		}
		if (ve[i] == 2 && n > 1) 
		{
			cout << "haoye" << endl;
			return 0;
		}		
	}
	
	cout << "QAQ" << endl;
	
	return 0;
}

M: P 龙学长的教诲

难度: 中等

题意:

​ 输入一段字符串长度为 n , 每个单词可以用 $ a_1 , a_2, ..., a_n$ 表示 , 现在给定一段字符串它的表现形式是 ( a_1, a_3, a_5,...,a_6, a_4,a_2) , 现在把字符串以 (a_1 , a_2, ..., a_n) 的形式输出。

​ 确定字符串以 ' . ' , ' ! ' , ' ? ' 结束 , 每个单词之间只以空格隔开

思路:

用 vector 存储每个单词和结束符号 ' . ' , ' ! ' , ' ? '。

从输入的形式可以看出要以 (a_1 , a_2, ..., a_n) 的形式输出只要按前数第一个单词 , 倒数第一个单词 , 前数第二个单词 , 倒数第二个单词的形式输出 , 最后加上结束符即可。

代码:

#include <bits/stdc++.h>
using namespace std;

int t;
vector<string> ve;

int main(void)
{
	scanf("%d", &t);
	cin.get();
	
	string s, temp;
	while (t--)
	{
		getline(cin, s);
		
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] != ' ' && s[i] != '.' && s[i] != '!' && s[i] != '?') temp += s[i];
			else
			{
				ve.push_back(temp);
				temp.clear();
			}
		}
			
		if (ve.size() % 2 == 0)
		{
			for (int i = 0, j = ve.size() - 1; i < ve.size() / 2; i++, j--)
			{
				if (i < ve.size() / 2) cout << ve[i] << ' ';
				if (j > ve.size() / 2) cout << ve[j] << ' ';
				else cout << ve[j] << s[s.size() - 1] << endl;
			}
		}
		else
		{
			for (int i = 0, j = ve.size() - 1; i <= ve.size() / 2; i++, j--)
			{
				if (i < ve.size() / 2) cout << ve[i] << ' ';
				else if (i == ve.size() / 2) cout << ve[i] << s[s.size() - 1] << endl;
				if (j > ve.size() / 2) cout << ve[j] << ' ';
			}
		}
		ve.clear();
	}
	
	return 0;
}

原文链接: https://www.cnblogs.com/Ailicode/p/17057517.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

    第三周总结报告

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/313474

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年2月16日 下午12:53
下一篇 2023年2月16日 下午12:55

相关推荐