上海源码网站建设公司,上海天华建筑设计有限公司合肥分公司,手机快速建站,服装品牌策划公司ACM第三次考核题解
题目序号难度题目编号题目考察知识点1签到题A这是一道很难的题#xff01;#xff01;#xff01;输出2迷之难度F神说要有光#xff0c;于是有了手电筒贪心3简单BThis is a real English problem#xff01;思维 英语4简单C玩具简单排序5简单I“近义词…ACM第三次考核题解
题目序号难度题目编号题目考察知识点1签到题A这是一道很难的题输出2迷之难度F神说要有光于是有了手电筒贪心3简单BThis is a real English problem思维 英语4简单C玩具简单排序5简单I“近义词”字符数组6一般G一起来运动二分搜索7一般E这糖保甜吗GCD 模拟8一般K卖教材模拟9一般D简单切割小游戏结构体运用10一般J简单截断前缀和11困难M马学长的小游戏博弈12困难H分提拉米苏二分答案13困难L算两次数学
A 这是一道很难的题
print(想看马学长跳舞)F 神说要有光于是有了手电筒
需要推出一个结论当最大的电池电量高于其他所有电池电量则可以把其他电池给消耗完如果不能其他电池可以相互搭配 11 1 1 11地消耗始终能够把所有的电池电量和 ÷ 2 ÷2 ÷2向下取整消耗完比如样例中 222 2 2 2 222 共 3 3 3个电池可以用第一个电池和第二个电池消耗 1 1 1的电量然后再和第三个电池消耗1的电量最后第二个和第三个一起消耗 1 1 1的电量。
#include iostream
using namespace std;
#define ll long long
int main() {ll sum 0, ans 0, n 0, a 0;cin n;for (int i 0; i n; i) {cin a;ans max(a, ans);sum a;}if (ans sum / 2) cout sum - ans;else cout sum / 2;return 0;
}B This is a real English problem
题意对于给定一个质数 n n n输出一个最小的质数 m m m使得 n m nm nm是合数。
这是一个很简单的题目可以证明答案不是 2 2 2就是 3 3 3。因为如果是奇数3之后一定为偶数一定为合数但需要考虑 2 2 2后是不是合数因为此题找的是最小的 m m m偶数 2 2 2仍然为偶数一定是合数。
#includebits/stdc.h
using namespace std;
int n;
bool check(int x){for(int i 2 ; i n ; i)if(x%i0) return true;return false;
}
int main()
{cin n;if(check(n2)) cout 2;else cout 3;return 0;
}C 玩具
/*
* 本题思路较为简单就是先排序然后从后往前取最大的那个就可以了
* 如果你觉得的冒泡太麻烦可以去学一下 C 用 C 的 algorithm 头文件里的 sort 函数进行排序
*/
#include stdio.h
#define N 1010int a[N];int main()
{int n, sum 0;scanf(%d, n);for (long long int i 1; i n; i )scanf(%d, a[i]);// 对数组进行排序for (int i 1; i n; i ) for (int j 1; j n - i; j ) if (a[j] a[j 1]) {int temp a[j];a[j] a[j 1];a[j 1] temp;}// 从后往前取两个两个取只把大的那个算入结果内for (long long int j n; j 1; j -- ) {sum a[j];j --; // 略过下一个}printf(%d\n, sum);return 0;
}
//-------------- 我是一个分割线 -----------------------
/*
* 如果你用 c 并使用 algorithm 这个头文件
* 第18行至第24行的排序算法可以替换成下面这行代码 sort(a 1, a 1 n);
*/
I “近义词”
看了题目大家应该都知道是直接遍历比较就可以最主要的是怎么存多个字母因为比较的字符串是在最后给出这里提供四个思路
1.用二维字符数组
2.用一维字符数组(但计算位置时需要退一下坐标)
3.用c的vector容器
4.用c的string数组
下面给出两种解法1和3的代码
#include stdio.h
int main()
{int n,m;int num0;int tem0;char a[1100][1100];scanf(%d%d,n,m);for(int i0;in;i){scanf(%s,a[i]);}for(int i0;in;i){for(int j0;jm;j){if(a[i][j]!a[n][j])tem;if(tem2)break;}if(tem2)num;tem0;}printf(%d,num);return 0;
}#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 2e5 10;
int n,m;
vectorstring v;
string s;
int ans;
int main()
{cin n m ;for(int i 1 ; i n ; i ){string s;cin s;v.push_back(s);}cin s;for(int i 0 ; i v.size() ; i ){int t 0;string ss v[i];for(int i 0 ; i ss.size() ; i){if(ss[i] ! s[i]) t;}if( t 2) ans ;//cout t endl;}cout ans;
}G 一起来运动
这题本意是靠二分但由于出题人疏忽数据没有捏好让你们 O ( n 3 ) O(n^3) O(n3)给过了气死了 #include iostream
#include cstring
#include algorithmusing namespace std;const int N 1100;
int a[N];
int n;int main() {cin n;for(int i 0; i n; i ) cin a[i];sort(a, a n);int ans 0;for(int i 0; i n; i ) {for(int j i 1; j n; j ) {int l lower_bound(a , a n, 2 * a[j] - a[i]) - a;int r upper_bound(a , a n, 3 * a[j] - 2 * a[i]) - a;ans r - l;}}cout ans endl;return 0;
}E 这糖保甜吗
#includestdio.h
#includemath.hint GCD(int m, int n)
{int tmp;m abs(m);n abs(n);// 保证后续m%n为较大数除以较小数if (mn){tmp m;m n;n tmp;}// 辗转相除的过程终止条件是余数为0while (m % n ! 0){tmp m;m n;n tmp % n;}// 返回除数较小数return n;
}int main() {int a, b, c, d;int gcd; // 最大公约数int den, num; // 分子num 分母denint op; // 操作数scanf(%d,op);scanf(%d %d %d %d,a,b,c,d);gcd GCD(b, d);// 以下是分数运算过程// 通分——分母最大den b * d / gcd;// den/b 为分母扩大了多少倍 分子也要相应扩大倍数if (op 1)num a * (den / b) c * (den / d); elsenum a * (den / b) - c * (den / d);// 以下是分数化到最简过程// 避免输出0/nif (num 0) {printf(0\n);} else if (num den) {printf(1\n);}else {gcd GCD(num, den); num num / gcd;den den / gcd;printf(%d/%d,num,den);}return 0;
}K 卖教材
根据题意模拟即可但需要注意的是当给20元找零的时候需要先使用 5 10 510 510如果没有再考虑 5 5 5 555 555
#include bits/stdc.h
using namespace std;
int num5,num10,num20;
int ans0;
int main()
{int n;scanf(%d,n);for(int i1;in;i){int x;scanf(%d,x);if(x5) {num5;ans;}else if(x10){if(num50){num5--;num10;ans;}else {break;}}else {if(num50num100){num5--;num10--;num20;ans;}else if(num53){num5-3;num20;ans;}else {break;}}}printf(%d,ans*5);return 0;
}D 简单切割小游戏
使用结构体存每一段排序之后贪心地从最后一个位置切割(这也是怎么排序的依据)
#include bits/stdc.h
#define ll long long
using namespace std;
const int N 1e55;
struct node{int a, b;
}s[N];
bool cmp(node x, node y){if(x.b y.b){return x.a y.a;}return x.b y.b;
}
void solve()
{int n, m;scanf(%d%d,n,m);for(int i 0;i m;i){scanf(%d%d,s[i].a,s[i].b);if(s[i].a s[i].b)swap(s[i].a,s[i].b);}sort(s,sm,cmp);int flag 0, ans 0;for(int i 0;i m;i){if(flag s[i].a){flag s[i].b;ans;}}printf(%d,ans);
}
int main()
{solve();return 0;
}J 简单截断
巧妙地运用了前缀和第一个切割点一定在所有数和的 1 3 \frac{1}{3} 31处而第二个切割点一定在所有数和的 2 3 \frac{2}{3} 32处
#includebits/stdc.h
using namespace std;
const int N 1e5 10;
int sum[N];
int n;
int main(){cin n;for(int i 1 ; i n ; i){int x;cin x;sum[i] sum[i-1] x;}if(sum[n]%3!0){cout 0;return 0;}long long cnt 0,ans 0;for(int i 1 ; i n - 2; i ){if(sum[i] sum[n]/3) cnt ;if(sum[i1] sum[n]/3*2) ans cnt;}cout ans;return 0;
}M 马学长的小游戏
#include iostream
using namespace std;
int main()
{int n 1;while(1) {cin n; if (n 0) break;if (n % 2 1) printf(maxuezhang win\n);else printf(xiaoJtongxue win\n);}return 0;
}H 分提拉米苏
#include bits/stdc.h
using namespace std;const int N 1e5 10;
int l[N], r[N];
int n, k;
bool check(int mid){int res 0;for(int i 0 ; i n ; i ){res (l[i]/mid)*(r[i]/mid);if(res k) return true;}return false;
}
int main()
{cin n k;for(int i 0 ; i n ; i ) cin l[i] r[i];int l 1 , r 10000;while(l r){int mid (l r 1) / 2;if(check(mid)) l mid;else r mid - 1;}cout l endl;return 0;
}L 算两次
#include bits/stdc.h
#define ll long long
#define N 100005
int f[N],p[N],nu1[N],nu2[N];
int num10,num20;
int ma0;
using namespace std;
int num0;
void init_p()
{f[1]1;num0;for(int i2;iN;i){if(f[N]0){p[num]i;}for(int j1;jnum;j){if(i*p[j]N) f[i*p[j]]1;if(i%p[j]0||i*p[j]N) break;}}
}
int main()
{init_p();int m;scanf(%d,m);for(int i1;im;i){int op,x;scanf(%d%d,op,x);if(x0){num1;x-1*x;}mamax(ma,x);if(op1){for(int i1;p[i]x;i){if(f[x]0){nu1[x];break;}while(1){if(x%p[i]0){nu1[p[i]];x/p[i];}else break;}}}else {for(int i1;p[i]x;i){if(f[x]0){nu1[x]--;break;}while(1){if(x%p[i]0){nu1[p[i]]--;x/p[i];}else break;}}}}scanf(%d,m);for(int i1;im;i){int op,x;scanf(%d%d,op,x);if(x0){num2;x-1*x;}mamax(ma,x);if(op1){for(int i1;p[i]x;i){if(f[x]0){nu2[x];break;}while(1){if(x%p[i]0){nu2[p[i]];x/p[i];}else break;}}}else {for(int i1;p[i]x;i){if(f[x]0){nu2[x]--;break;}while(1){if(x%p[i]0){nu2[p[i]]--;x/p[i];}else break;}}}}if(num1%2!num2%2){printf(NO);return 0;}for(int i1;p[i]ma;i){if(nu1[p[i]]!nu2[p[i]]){printf(NO);return 0;}}printf(YES);return 0;
}
