题解
- A题
- B题
- C题
- D题
- E题
- F题
- G题
- H题
- I题
- J题
- K题
-
- 题外话
A题
题目链接
时间限制：C/C 1秒，其他语言2秒 空间限制：C/C 262144K，其他语言524288K 64bit IO Format: %lld
对于大多数编程语言，写一个可以输出的 “Hello World!” 的程序往往是最基本、最简单的。 因此，这个程序常常作为一个初学者接触一门新的编程语言所写的第一个程序，也经常用来测试开发、编译环境是否能够正常工作。 陈末也为大家准备了这样一个问题，现在你可以写一个输出 “Hello World!” 通过这个问题的程序~ Froshine : 也许，梦开始的地方也是最后无人问津的地方吧？~”
无
Hello World!
输入：
输出： Hello World!
无
1.C 解法
#include<bits/stdc .h> using namespace std; int main() {
cout<<"Hello World!"; return 0; } 2.PHP解法
Hello World! //PHP是最好的语言() B题
题目链接
时间限制：C/C 1秒，其他语言2秒 空间限制：C/C 262144K，其他语言524288K 64bit IO Format: %lld
众所周知，陈末的数学很差。 陈末连简单的函数解析都处理不了，所以他想请你帮他处理。 定义 f ( x ) = { 1 x = 0 2 x = 1 3 x = 2 4 x = 3 f ( x ? 1 ) f ( x ? 3 ) x > 3 f(x) = \left\{ \begin{array}{lr} 1 && x = 0\\ 2 && x = 1\\ 3 && x = 2\\ 4 && x = 3\\ f(x-1) f(x-3) && x > 3\\ \end{array} \right. f(x)=??????⎪⎪⎪⎪⎧1234f(x−1)+f(x−3)x=0x=1x=2x=3x>3 对于给定的 x ，输出对应 f(x) 的值。 由于最后答案可能很大，请输出将答案对 109 + 7 取模的结果。
一行，一个数 x (1 ≤ x ≤ 105)
输出对应 f(x) 的值
输入： 0 输出： 1
输入： 2 输出： 3
输入： 6666 输出： 193444274
刚上手用的递归，结果爆T了，因为递归栈溢出 链接:递归太深会导致栈溢出 换成递推过了
1.递归解法（TLE错误解法）
#include<bits/stdc++.h>
using namespace std;
int x;
const int mod = 1e9+7;
int fun(int x){
if(x==0) return 1;
else if(x==1) return 2;
else if(x==2) return 3;
else if(x==3) return 4;
else return(fun(x-1)+fun(x-3))%mod;
}
int main(){
cin>>x;
cout<<fun(x);
return 0;
}
2.递推解法
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
ll f[maxn];
int main(){
f[0] = 1, f[1] = 2, f[2] = 3, f[3] = 4;
for(int i = 4; i <= 1e5; ++i){
f[i] = (f[i - 1] + f[i - 3]) % mod; //每次取mod防止f[i]爆数据范围
}
ll x;
cin >> x;
cout << f[x];
return 0;
}
C题
题目链接
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld
因为陈末英雄联盟玩的太菜，青钢影就对陈末使用了大招 “海克斯最后通牒” ，将陈末困了起来，不让他继续祸害其他队友。 陈末向青钢影求饶，青钢影就给了陈末一个不等式 2n > n2 。 并要求他回答出当 n 为一些值的时候，等式是否成立。 只有陈末能正确回答，青钢影才会放他出来。 陈末数学太烂了，所以他请到了聪明的你来帮帮他。
第一行一个整数 n(1 ≤ n ≤ 109) ，代表 n 的值。
如果等式成立输出 “YES”（不包括双引号） ，否则输出 “NO”（不包括双引号）。
输入： 2 输出： NO 说明： 此时两边相等
输入： 5 输出： YES
直接判断，或者输出几个n找规律
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin>>n;
if(pow(2,n)>n*n) cout<<"YES";
else cout<<"NO";
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
if(n == 1 || n >= 5)puts("YES");
else puts("NO");
return 0;
}
D题
题目链接
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld
AK是每个acmer在每场比赛中的最大追求。 （AK：指在一次比赛中把全部题目都写出来了） 周波廷学长正在整理自己的训练成绩。 我们将训练赛的名字的简化成为一个个的字符串。 给定 n 个字符串。如果一个字符串的结尾是 “AK” ，那么这次训练的成绩就是AK。请你输出哪次比赛会AK。 如果有多个次AK，输出最靠前的一个。 数据保证一定有解。
第一行一个数整数 n(1 ≤ n ≤ 1 × 102) ，表示字符串的数量。 接下来 n 行，一行一个字符串 ，保证每个字符串大小不超过100。
输出一个字符串(比赛的名字)，表示这次比赛AK了且最靠前（不包含"AK"）。
输入： 3 acmer ICPCAK CCPCAK 输出： ICPC 说明： 周波廷学长在ICPC与CCPC都AK了，但是ICPC排名更靠前
输入： 2 atcoder codeforcesAK 输出： codeforces 说明： 周波廷学长只在codeforcesAK了
用字符串数组存入，遍历字符串，如果最后两个字符是“AK”就输出该字符串前length-2位，并提前结束
#include<bits/stdc++.h>
using namespace std;
int n;
string s[110];
int main(){
cin>>n;
for(int i = 0;i<n;i++) cin>>s[i];
for(int i = 0;i<n;i++){
int len = s[i].length();
if(s[i][len-2]=='A'&&s[i][len-1]=='K') {
for(int j = 0;j<len-2;j++) cout<<s[i][j];
return 0;
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
string a[maxn];
int main(){
int n ;
cin >> n ;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i){
int len = a[i].size() ;
if (len >= 2){
string tp = a[i].substr(len - 2, 2) ; //截取str的后两位字符
if (tp == "AK"){
for (int j = 0; j < len - 2; ++j)
cout << a[i][j];
cout << endl;
return 0;
}
}
}
return 0;
}
E题
题目链接
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld
众所周知，陈末是个英雄联盟菜鸟，又菜又爱玩。 陈末特别喜欢用派克来秀他下饭的操作，每次都能把自己秀死。 涌泉之恨是派克的大招，能在一定情况下，直接斩杀敌人。 此时陈末操作的派克在一个 N行 ，M 列 的二维空间中。 我们将问题简化，让派克的大招能直接斩杀一个十字形的区域内的敌人（这很码头菩萨），并且能触发连斩机制。 例如: 当派克斩杀的敌人坐标在 (i, j) ，那么(i, j) , (i+1, j) , (i, j+1) , (i-1, j) , (i, j-1)这些位置上的敌人都会被斩杀，并且除位置在 (i, j) 外的敌人 如果被斩杀就会触发连斩机制，将这个位置变成新的 (i, j)，并斩杀十字区域的敌人，以此类推。 陈末可以操纵派克选择二维空间中的任何一个敌人使用涌泉之恨。 陈末想借用科技的力量操作一次，请你来帮他计算出一次最多能斩杀出多少敌人。
第一行两个数 n(1 ≤ n ≤ 102) ，m(1 ≤ n ≤ 102) ，分别二维空间的行数和列数。 下面有 n 行 ，每行 m 个字符，代表二维空间的敌人分布情况。 *代表这个位置有一个敌人， # 代表这个位置没有敌人。
输出一次最多能斩杀出多少敌人。
输入： 4 4 # * # # * * * # # # * # # * # # 输出： 5 说明： 选择坐标(1, 2),(2, 1),(2, 2),(2, 3),(3, 3)中的任意一个敌人斩杀将触发连斩机制，进而斩杀5个敌人。
输入： 3 3 # * # * * # * # * 输出： 4 说明： 选择坐标(1, 2),(2, 1),(2, 2),(3,1)中的任意一个敌人斩杀将触发连斩机制，进而斩杀4个敌人。
选中一个存在敌人的点斩杀，如果该点的上下左右也有敌人那么也会被斩杀，直到每个点的上下左右都没有敌人时停止，求一次最多斩杀敌人数量。 也就是可以理解为求最大连通块的数量
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 3, M = 1e2 + 3;
int fx[] = {
0, 0, -1, 1};
int fy[] = {
-1, 1, 0, 0};
char a[N][M];
int vis[N][M];
int sum, ans;
int n, m;
void dfs(int x, int y){
vis[x][y] = 1; //1为搜索过
sum++; //sum 当前连通块数量
for(int i = 0; i < 4; ++i){
//搜索十字方向的点
int xx = x + fx[i], yy = y + fy[i];
if(xx < 1 || xx > n || yy < 1 || yy > m)continue; //越界
if(a[xx][yy] == '#')continue; //没有敌人
if(vis[xx][yy])continue; //已经搜过
dfs(xx, yy);
}
}
int main(){
scanf("%d %d\n", &n, &m);
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
scanf("%c", &a[i][j]);
}
getchar();
}
int ans = 0;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(a[i][j] == '*' && !vis[i][j]){
//有敌人&&是新的连通块
sum = 0;
dfs(i, j);
ans = max(ans, sum);
}
}
}
cout << ans << endl;
return 0;
}
F题
题目链接
时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld
一天，贺志飞学长收到了一封信，信里有 n 个序列。 每个序列长度为 S 。 每个序列中有 W1 ，W2 ，W3……Ws。 来信的人让贺志飞学长对这些序列中完全相同的序列进行去重操作(删除其他相同的，只保留一个)。 如果去重能正确完成，贺志飞学长将得到一笔丰厚的报酬。 为了得到报酬，贺志飞学长请到了聪明的你来帮忙。
第一行一个整数 n(1 ≤ n ≤ 2 ×105) ，代表有N个数组。 下面 n 行，每行包含一个整数 S，表示数组的元素个数，以及 S 个整数W1 ，W2 ，W3……Ws ，Wi(1 ≤ Wi ≤ 109)，代表数组的元素。 保证 n 个数组的元素个数总和不超过 2 ×105。
要求输出去重后的数组有多少个。
输入： 4 2 1 3 2 1 1 2 3 1 2 1 3 输出： 3 说明： 第1个数组与第4个数组完全相同，所以去重后只有3个数组了。
输入： 1 1 2 输出： 1
题目要求是数组去重，利用set集合中每个元素的值唯一的特点即可
#include <bits/stdc++.h>
using namespace std;
int main(){
int T;
scanf("%d", &T);
set<vector<int>> s; //数组set
while(T--){
//T个数组
int n;
scanf("%d", &n);
vector<int> tmp;
for(int i = 1; i <= n; ++i){
int x;
scanf("%d", &x);
tmp.push_back(x);
}
s.insert(tmp); //数组插入set
}
cout << s.size() << endl;
return 0;
}
G题
题目链接
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld
王梦涵学长，有着 n 个迷弟。每个迷弟有着自己的力量值。 为了让迷弟们和自己一样强大，王梦涵学长学习了一种增幅魔法，每次使用魔法可以让一位迷弟的力量值加 1 。 例如，王梦涵学长有3个迷弟，力量分别为[1，2，3]，王梦涵学长使用一次魔法使得1号迷弟的力量加1，变成[2，2，3]。 但是魔法不能无限使用，王梦涵学长最多只能使用 k 次魔法。 王梦涵学长十分关照力量值比较低的迷弟。所以他想在使用不超过 k 次魔法后，使得全部迷弟中力量值最低的迷弟，力量值最大。 请你帮帮王梦涵学长计算在上方的原则下，力量值最低的迷弟的力量值。
第一行两个数整数 n(1 ≤ n ≤ 2 ×105) ，k(1 ≤ k ≤ 2 ×105)，表示迷弟的人数以及使用魔法的最大次数。 接下来一行 n 个数 ai(1 ≤ ai ≤ 2 ×105) ，表示第i个迷弟的力量值。
输出一个数，表示在使用不超过 k 次魔法后，迷弟中，力量值最低的迷弟的最大力量值。
输入： 5 3 1 1 3 3 4 输出： 2 说明： 一种方法为从[1,1,3,3,4]加到[3,2,3,3,4]，此时最小力量值为2。
最大化最小值问题，用二分搜索求结果。 先假定一个答案x，再不断缩小答案范围，最终得到解。 因为x是最大的最小值，所以x-1也满足条件，但不是最大的，x+1不满足条件，所以单调性
#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 2e5 + 10; int a[maxn]; int n, k; bool judge(int x){ ll sum = 0; for(int i = 1; i <= n; ++i){ if(a[i] < x)sum += x - a[i]; //if(sum>k) return false; } return sum <= k; } int main(){ scanf("%d %d", &n, &k); for(int i = 1; i <= n; ++i){ scanf("%d", &a[i]); } int L = 1, R = 1e6; int ans; while(L <= R){ int mid = L + R >> 1; if(judge(mid))L = mid + 1 标签：继电器aqw215a