SMU Winter 2023 Round #5 (Div.2)
A题 Lucky？
题意：给一个六位数，如果前三位和后三位上的数字之和相等就输出yes否则输出no。
思路：将六位数转化成字符串，然后求前三个字符和后三个字符所对应的数字之和。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
const int N=110;
int main() {
IOS;
int t;
cin>>t;
while(t--) {
string s;
cin >> s;
int a, b;
a = (s[0] - '0') + (s[1] - '0') + (s[2] - '0');
b = (s[s.size() - 1] - '0') + (s[s.size() - 2] - '0') + (s[s.size() - 3] - '0');
if (a == b)cout << "Yes" << '\n';
else cout << "NO" << '\n';
}
return 0;
}
B题 EqualCandies
题意：给你n】个盒子，有a[i]个糖果，问最少拿多少块糖使盒子内的糖果相等。
思路：直接贪心，肯定要以最少的那个盒子为标准，因为不能添加，排序后一个一个减求和即可。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
const int N=110;
int a[N];
int main() {
IOS;
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int ans=0;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
for(int i=1;i<n;i++){
ans+=a[i]-a[0];
}
cout<<ans<<'\n';
}
return 0;
}
c题 Most Similar Words
题意：对于每个测试用例，给你 n 个等长 m 的单词，单词的字母都由小写拉丁字母组成，你可以按字母顺序更改字母（比如 e 可以改为 d 或 f ），但 a 与 z 不能互改。问你哪一对单词，使它们单词相同所需改的次数最少，输出最少的次数
思路：直接枚举每个字符串的所有情况求最小即可。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
const int N=110;
int a[N];
int main() {
IOS;
int t;
cin>>t;
while(t--){
int n,m;
int mn=INT_MAX;
cin>>n>>m;
string s[n+10];
for(int i=0;i<n;i++)cin>>s[i];
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
int ans=0;
for(int k=0;k<s[i].size();k++){
if(s[i][k]<=s[j][k])ans+=(s[j][k]-s[i][k]);
else ans+=(s[i][k]-s[j][k]);
}
mn=min(mn,ans);
}
}
cout<<mn<<'\n';
}
return 0;
}
D题 X—Sum
题意：对于每个测试用例，给你 1 个 n 行 m 列的棋盘，棋盘的每个格子上都有一个值，给你一个棋子，棋子可以斜向四面八方攻击，问你怎么摆放棋子可以获得最大的值，输出最大值。
思路：也是暴力求解，每个格子就求一下对角线的格子以及自己个内的数字之和，求对角线就是从1开始枚举到n和m的对大致，加个判断条件只有在边界内才加上，最后再求最大值，也事先可以先求每一条对角线的值，到哪一个再加，复杂度会降低。
#include<bits/stdc++.h>
using namespace std;
const int N=210;
int f[N];
int g[N][N];
int dx[]={-1,-1,1,1};
int dy[]={-1,1,-1,1};
int main()
{
int t ;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>g[i][j];
}
int sum=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int ans=0;
ans+=g[i][j];
for(int l=1;l<=max(n,m);l++)
{
for(int k=0;k<4;k++)
{
int a=l*dx[k]+i;
int b=l*dy[k]+j;
if(a>0&&a<=n&&b>0&&b<=m)
ans+=g[a][b];
}
}
sum=max(sum,ans);
}
cout<<sum<<endl;
}
return 0;
}
E题 Eating Queries
题意：给你 n 颗糖，每个糖果都有糖量，有 q 个查询，问你最少吃多少颗糖，才能使总糖量大于查询值，输出最小糖数，如果达不到查询值，输出 -1 。
思路：看到总量，可以想到前缀和，大于查询值，就是找值，可以用二分，所以这题就是前缀和+二分就可以过了。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
int x, y;
int a[N];
int b[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x >> y;
for (int j = 0; j < x; j++) {
cin >> a[j];
}
sort(a, a + x,greater<int>());
for (int j = 0; j <x ; j++) {
if (j == 0) {
b[j] = a[j];
}
else {
b[j] = b[j - 1] + a[j];
}
}
for (int j = 0; j < y; j++) {
int k;
cin >> k;
if (k > b[x-1]) {
cout << -1 << endl;
continue;
}
int l=0, r=x-1;
while (l < r)
{
int mid = l + r >> 1;
if (b[mid] >= k) r = mid;
else l = mid + 1;
}
if (k <= b[l]) cout << l+1 << "\n";
else cout << "-1\n";
}
}
}
F题 Longest Strike
题意：给你一组序列，让你找出一组l，r要求所有在lr之间的数的数量大于k
思路：看数据范围，序列的数据范围不高，但是所给数的范围较大，所以可以采用离散化,可以手写一个离散化然后再双指针算出最大的区间，先排序，然后再记忆所有不同的数，和记录数量，最后再双指针遍历即可
#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;
}
H题 Maximum Crossings (Easy Version)
题意：就是求逆序对
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
int a[N], n;
signed main()
{
int t; cin>>t;
while(t--)
{
cin>>n;
for(int i=1; i<=n; ++i) cin>>a[i];
int res = 0;
for(int i=1; i<n; ++i)
{
for(int j=i+1; j<=n; ++j)
{
if(a[i] >= a[j]) ++res;
}
}
cout<<res<<'\n';
}
return 0;
}
SMU Winter 2023 Round #7 (Div.2)
A题 解开束缚缠丝Ⅱ
题意：求给出的n个字符最长可以组成多长的回文串。
思路：就是统计字符出现的次数，要么全部是偶数全部可以构成回文串，如果有奇数，那么只有其中一个奇数的字符串可以放入回文串中，用map来做就可以了。
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
map <char,int> mp;
int ans=0;
for(int i=0;i<n;i++){
char ch;
cin>>ch;
mp[ch]++;
}
for(auto i:mp){
if(i.second%2!=0)ans++;
}
//cout<<ans<<' ';
cout<<n-ans+1<<endl;
}
return 0;
}
B题 7 的意志
题意：求有最多几个区间的和为7777
思路：先进行前缀和预处理，然后枚举每一个可能的区间和的左端点，寻找可行的右端点。一个左端点最多只有一个可行的右端点进行匹配
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, ans;
int a[100005], s[100005];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
ll t;
cin>>t;
while (t--) {
cin >> n;
s[0] = ans = 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
for (int i = 1; i <= n; ++i) {
ll tar = s[i - 1] + 7777;
ll x = lower_bound(s + 1, s + n + 1, tar) - s;
if (s[x] == tar) ans++;
}
cout << ans << '\n';
}
return 0;
}
F题 月光奏鸣曲
题意：给你两个正方形的数字矩阵，可以逆时针和顺时针转动，问最少转几次让两个矩阵相等。
思路：肯定只能往一个方向转，不然只要有一个向另外一个方向转了，就会抵消本方向的一次，相当于没有转，但是操作次数却多了两次，题目求最少，并且做多只有可能转三次，第四次就回原位置了，写四个转零次，一次，两次，三次的函数判断一下即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
int a[25][25], b[25][25];
bool check0() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (b[i][j] != a[i][j]) return false;
}
}
return true;
}
bool check1() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (b[i][j] != a[n - j + 1][i]) return false;
}
}
return true;
}
bool check2() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (b[i][j] != a[j][n - i + 1]) return false;
}
}
return true;
}
bool check3() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (b[i][j] != a[n - i + 1][n - j + 1]) return false;
}
}
return true;
}
void main2() {
cin >> n;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> a[i][j];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> b[i][j];
}
}
if (check0()) cout << 0 << '\n';
else if (check1()) cout << 1 << '\n';
else if (check2()) cout << 1 << '\n';
else if (check3()) cout << 2 << '\n';
else cout << -1 << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL _;
cin >> _;
// _ = 1;
while (_--) main2();
return 0;
}
H题 简单的 LRU 问题
就是根据题目所说模拟一下就可以了，但是有点复杂，要耐得住性子
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m, mx;
int a[105][10];
string hx = "0123456789abcdef";
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
mx = 0;
cout << "+------+";
for (int i = 0; i < n; ++i) {
cout << "--------+";
}
cout << '\n';
cout << "| |";
for (int i = 0; i < n; ++i) {
cout << " 0x";
int a = i / 16, b = i % 16;
cout << hx.substr(a, 1) << hx.substr(b, 1) << " |";
}
cout << '\n';
cout << "+------+";
for (int i = 0; i < n; ++i) {
cout << "--------+";
}
cout << '\n';
for (int i = 0; i < m; ++i) {
int x; cin >> x;
if (i == 0) a[0][0] = x;
else {
int have = 0;
for (int j = 0; j <= mx; ++j) {
if (a[i - 1][j] == x) {
have = 1; break;
}
}
if (have) {
int k = 0;
for (int j = 0; j <= mx; ++j) {
if (a[i - 1][j] == x) continue;
a[i][k++] = a[i - 1][j];
}
a[i][mx] = x;
}
else {
if (mx < n - 1) {
for (int j = 0; j <= mx; ++j) {
a[i][j] = a[i - 1][j];
}
a[i][++mx] = x;
}
else {
int k = 0;
for (int j = 1; j <= mx; ++j) {
a[i][k++] = a[i - 1][j];
}
a[i][mx] = x;
}
}
}
cout << "| 0x";
int A, B, C, D; A = i / 16; B = i % 16;
cout << hx.substr(A, 1) << hx.substr(B, 1) << " |";
for (int j = 0; j <= mx; ++j) {
cout << " 0x";
int tmp = a[i][j];
A = tmp / 4096; tmp -= A * 4096;
B = tmp / 256; tmp -= B * 256;
C = tmp / 16; tmp -= C * 16;
D = tmp;
cout << hx.substr(A, 1) << hx.substr(B, 1);
cout << hx.substr(C, 1) << hx.substr(D, 1) << " |";
}
for (int j = mx + 1; j < n; ++j) {
cout << " |";
}
cout << '\n';
cout << "+------+";
for (int i = 0; i < n; ++i) {
cout << "--------+";
}
cout << '\n';
}
return 0;
}
I题 好想听肆宝唱歌啊
题意：给你几首个的名字以及喜爱它的程度，数字越大喜爱程度越高，再给你个数字k，就是最爱的前k首歌曲已经点了，现在要点目前情况下最喜爱的歌曲，输出该歌曲的名字。
思路：使用一个结构体进行排序，如果输出k+1首歌曲的名字就可以了。
#include<bits/stdc++.
using namespace std;
typedef long long LL;
const int N=100010;
int n;
struct S {
int w;
string x;
}s[N];
bool cmp(S a,S b){
return a.w>b.w;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> s[i].w >> s[i].x;
sort(s + 1, s + n + 1, cmp);
int k;
cin >> k;
cout << s[k + 1].x;
return 0;
}
J 题 毁灭凤凰人
#include<bits/stdc++.h>
using namespace std;
int n, m;
int mxa = 0, a = 0, b = 0;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
int res, x;
cin >> res;
if (res == 0) {
cin >> x;
mxa = max(mxa, x);
} else if (res == 1) a = 1;
else b = 1;
}
if (m == 0 && mxa >= 2500 && a) {
cout << "haoye\n";
return 0;
} else if (m == 1 && mxa > 2100 && a) {
cout << "haoye\n";
return 0;
} else if (b && n > 1) {
cout << "haoye\n";
return 0;
} else cout << "QAQ\n";
return 0;
}
### K题 欢迎来到杭师大
题意：给你一个n，输出n个Welcome to HZNU，每个要换行
思路：先定义一个字符串，用个循环输出即可。
#include<bits/stdc++.h> #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) using namespace std; int main() { IOS; int n; cin>>n; string s="Welcome to HZNU"; while(n--){ cout<<s<<'\n'; } return 0; }
### L题 Ayanoto 变形记
题意：给n个点，每次条x步，问再其中一个位置，能不能跳回原来的位置
思路：我们可以知道，总共跳的步数就是两个数的最小公倍数，但两个不为零的数肯定有最小公倍数，所以只要跳的x不为零，都可以，为零就不行。
#include<bits/stdc++.h> #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define ll long long using namespace std; int main() { IOS; ll t; cin>>t; while(t--) { ll a, b; cin >> a >> b; if (b == 0)cout << "no" << '\n'; else cout << "yes" << '\n'; } return 0; }
### M题 龙学长的教诲
题意：给你一个字符串，他的顺序是1，3，5，6，4，2这样的顺序，但他正确的顺序是1，2，3，4，5，6，将正确的输出出来，标点符号在最后
思路：再读入的时候，当这个字符串的结尾有标点符号时就结束读入，将标点符号记下来，按顺序输出就可以了，记得最后加标点符号，再注意一下具体的格式。
#include<bits/stdc++.h> using namespace std; typedef long long LL;
int n; string x[1005]; char op;
void print(int id) { if (id != n) cout << x[id]; else { int len = x[id].length(); for (int i = 0; i < len - 1; ++i) { cout << x[id][i]; } } }
int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--){ n=0; while (cin >> x[++n]) { int len = x[n].length(); if (x[n][len - 1] == '.' || x[n][len - 1] == '!' || x[n][len - 1] == '?') { op = x[n][len - 1]; break; } } for (int i = 1; i <= n / 2; ++i) { print(i); cout << ' '; print(n - i + 1); if (i < n / 2 or n % 2 == 1)cout << ' '; } if (n % 2 == 1) { print(n / 2 + 1); } cout << op<< '\n'; } return 0; }
京公网安备 11010502036488号