Codeforces Round #790 A-E 题解
- A. Lucky?
- B. Equal Candies
- C. Most Similar Words
- D. X-Sum
- E. Eating Queries
A. Lucky?
A. Lucky?
题意
给你 t 个六位数(可能含前导0),对于每个六位数,如果前三位数字之和等于后三位数字之和,输出YES,否则输出NO
解法
一位一位读数字即可
AC代码
#define _CRT_SECURE_NO_DEPRECATE
#include <bits/stdc++.h>
using namespace std;#define FOR(i, a, b) for (register int i = a; i <= b; i++)int n,a,b;int main()
{cin>>n;while(n--){a=b=0;int tmp=0;FOR(i,1,3){scanf("%1d",&tmp);a+=tmp;}tmp=0;FOR(i,1,3){scanf("%1d",&tmp);b+=tmp;}if(a==b)printf("YES\n");else printf("NO\n");}return 0;
}
B. Equal Candies
B. Equal Candies
题意
对于每个测试用例,有n个盒子,盒子里有ai颗糖果,问你必须吃多少糖果才能让每个盒子里的糖果数目相等?
解法
找到所有n个盒子里糖果最小的值,算出所有盒子糖果数量与最小值之差的和
AC代码
#define _CRT_SECURE_NO_DEPRECATE
#include <bits/stdc++.h>
using namespace std;#define FOR(i, a, b) for (register int i = a; i <= b; i++)const int INF = 0x3f3f3f3f;
const int N=1000;
int a[N],n,t;int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);int mini=INF,ans=0;FOR(i,1,n){scanf("%d",&a[i]);if(a[i]<mini)mini=a[i];}FOR(i,1,n){ans+=(a[i]-mini);}printf("%d\n",ans);}return 0;
}
C. Most Similar Words
C. Most Similar Words
题意
对于每个测试用例,给你 n 个等长 m 的单词,单词的字母都由小写拉丁字母组成,你可以按字母顺序更改字母(比如 e 可以改为 d 或 f ),但 a 与 z 不能互改。问你哪一对单词,使它们单词相同所需改的次数最少,输出最少的次数
解法
枚举每一对单词,求出使它们单词相同所需改的次数,输出最小值
AC代码
#define _CRT_SECURE_NO_DEPRECATE
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;#define FOR(i, a, b) for (register int i = a; i <= b; i++)const int INF = 0x3f3f3f3f;
const int N=100;
int t,n,m;
string x[N];
int s[N][N];int main()
{scanf("%d",&t);while(t--){scanf("%d %d",&n,&m);FOR(i,1,n){cin>>x[i];FOR(j,1,m){s[i][j]=(int)(x[i][j-1]-'a'+1);}}int mini=INF,miniab,tmp;FOR(a,1,n){FOR(b,a+1,n){miniab=INF;FOR(k,1,26){tmp=0;FOR(j,1,m){tmp+=abs(s[a][j]-s[b][j]);}if(tmp<miniab)miniab=tmp;}if(miniab<mini)mini=miniab;}}printf("%d\n",mini);}return 0;
}
D. X-Sum
D. X-Sum
题意
对于每个测试用例,给你 1 个 n 行 m 列的棋盘,棋盘的每个格子上都有一个值,给你一个棋子,棋子可以斜向四面八方攻击,问你怎么摆放棋子可以获得最大的值,输出最大值。
解法
对于每一个格子,它的值都等于两条斜线值的和减去当前格子的值。
因此可以先存储两条斜线值的值,再来计算某一格子的值,这样可以简化计算量。
AC代码
#define _CRT_SECURE_NO_DEPRECATE
#include <bits/stdc++.h>
using namespace std;#define FOR(i, a, b) for (register int i = a; i <= b; i++)const int N=210,B=210;
int s[N+B][N],si[N+B],sj[N+B];
int t,n,m;int main()
{scanf("%d",&t);while(t--){memset(s,0,sizeof(s));memset(si,0,sizeof(si));memset(sj,0,sizeof(sj));scanf("%d %d",&n,&m);FOR(i,1,n){FOR(j,1,m){scanf("%d",&s[i][j]);}}FOR(k,1,n+m-1){for(int i=k,j=1;i>=1&&j<=m;i--,j++){si[k]+=s[i][j];}}FOR(k,1,n+m-1){for(int i=k,j=m;i>=1&&j>=1;i--,j--){sj[k]+=s[i][j];}}int maxi=0,tmp;FOR(i,1,n){FOR(j,1,m){tmp=(si[i+j-1]+sj[i+m-j]-s[i][j]);if(tmp>maxi)maxi=tmp;}}printf("%d\n",maxi);}return 0;
}
E. Eating Queries
E. Eating Queries
题意
对于每个测试用例,给你 n 颗糖,每个糖果都有糖量,有 q 个查询,问你最少吃多少颗糖,才能使总糖量大于查询值,输出最小糖数,如果达不到查询值,输出 -1 。
解法
使用排序+前缀和+二分查找。
先排序,使糖量大的排前面,再通过前缀和存储总糖量,最后使用二分查找找出最小糖数。
AC代码
#define _CRT_SECURE_NO_DEPRECATE
#include <bits/stdc++.h>
using namespace std;#define FOR(i, a, b) for (register int i = a; i <= b; i++)const int N=1e6;
int t,n,q;
int a[N];int f(int s,int e,int q)
{if(a[e]<q)return -1;int i=s+e>>1;while(s!=e){if(a[i]<q){s=i+1;}else{e=i;}i=s+e>>1;}return i;
}bool cmp(int a,int b)
{return a>b;
}int main()
{scanf("%d",&t);while(t--){scanf("%d %d",&n,&q);FOR(i,1,n)scanf("%d",&a[i]);sort(a+1,a+n+1,cmp);FOR(i,1,n)a[i]+=a[i-1];int k;FOR(x,1,q){scanf("%d",&k);printf("%d\n",f(1,n,k));}}return 0;
}