一共二十六道题,有几道题稍微有些难度,建议略过去,先看简单的(因为我自己做都要想一会儿,太菜了)。某些有难度的题我会标记出来。
我会将题目分为:非常简单、简单、中等、难、非常难五个级别。
每一道题我都会按照新生的标准讲解,十分详细的讲解,如果某个地方你看不懂了,说明这个地方很简单我不想赘述,那就请你自行百度或者问师哥也行。
还有请不要直接复制别人的代码,哪怕你自己照着别人的代码码一遍,我真的不太想回答";"跟";"是有区别的。
所有的题目我都会按照C++的代码编写,如果你看不惯cin、cout,还请尽快熟悉。(你是否会说我C还没学会呢,就学C++是不是不太好,我相信这个问题别的师哥/师姐也说过不止一遍,C++是C的扩充,所以学C++并不妨碍你使用你的C语言)
这里面有很多重复的内容,我并不会讲两遍,所以如果你不想遗漏任何知识点,请你从A题开始看。当然,也可以直接跳到你不会的那一道题,并不会有太大的妨碍。
好了,废话不多说,下面进行题目的解析:
A - A Trivial Problem
出题率:3/9
难度:难
大体题意:
给你一个数m,范围是:1~1e5(1e5:1*10^5,后面不会赘述),让你求阶乘后末尾0的个数为m的数,如果存在,先输出一共有几个,再按大小输出出来,否则输出0.
思路:
(1)首先讲一下阶乘,阶乘有一些简单的特性。
比如要对n的阶乘取模(设要取的模是mod),当n>=mod的话,最后的结果一定是0.
举一个简单的例子:
5!% 3 = (5 * 4 * 3 * 2 * 1)% 3 = 0
因为n是大于等于mod的,所以n的阶乘一定是mod的倍数,所以最后的结果一定是0
(这个特性跟这道题无关)
(2)这道题问的是末尾0的个数,很显然,阶乘中能组成的0的只有25能组成0,(10可以拆分为25,自己后面带0的肯定是由2*5转化来的)
在n的阶乘中,2的个数明显比5多,比如在1~10中,有2的为:2,4,6,8,10
有5的有5,10,所以这道题我们只需要考虑5的个数就可以了。有几个5,就可以组成几个0。
(3)末尾0的个数变化为5个一组,也就是说,0-4的阶乘,5-9的阶乘,10-14的阶乘~~末尾0的个数都是不一样的。
这个是很好理解的,因为每五个数肯定会出现一次5的倍数,而5的个数就是最后末尾0的个数,所以为5个一组。
(4)有些末尾0的个数是不存在的,比如说5.
在20~24内,末尾0的个数为4.
但是在25~29内,末尾0的个数为6.
因内25含有两个5(25=5*5)
所以末尾0的个数为5是不存在的。
具体代码如下:
//我这里有很多头文件,很多都用不到,可以不用管,看具体的代码就好。 #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; //这里是把long long 替换成 ll ,这样当你定义long long类型的变量的时候会码的快一点。 using namespace std; int main() { int n; cin >> n; //输入题目中要求输入的数(虽然题目中说的是m,但是我们把这个变量设成n是完全不会影响结果的。还有题目中让怎么输入的,一定完全按照题目中的来,别自己瞎加上一些输入。 int x=0; //用变量x记录‘5’的个数(‘5’的个数就是末尾0的个数) for (int i=5;i<=500000;i+5) //因为是找5的倍数,所以这里直接+5就可以,可以减少时间复杂度 { int y=i; //用y来代替i,统计当前的i含有多少个‘5’,用y来代替的用处是:防止i的值发生改变。 while(y) //如果y不为0 { if(y%5==0) //如果y是5的倍数,那么统计5的个数++,否则直接break掉就可以了。 { x++; y=y/5; } else break; } if(x>=n) //如果现在统计‘5’的个数>=n,那么进行接下来的判断 { if(x>n) //如果不是等于,那么说明不存在(就像思路(4)一样),直接输出0就可以了。 { cout << 0 << endl; break; } else //如果存在的话 { cout << "5" << endl; //因为是5个一组,所以只要存在,肯定是五个数 for (int j=i;j<=i+3;j++) //这四个数输出的后面带空格 { cout << j << " "; } cout << i+4 << endl; //最后一个数的后面带换行 //endl是换行的意思,不过推荐使用'\n',我写‘endl'主要是我自己写得顺手了. break; } } } return 0; }
B-Go to Jail
出题率:7/20
难度:简单
很简单的大水题,不明白为什么只有七个人做出来。
大体题意:
有两枚骰子,告诉你n次掷骰子的结果,如果存在连续三次(可有有更多次)两枚骰子掷出来的数是一样的,那么就是输出"Yes",反之,输出“No".
大体思路:
将第一个骰子掷出的数和第二个骰子掷出的数分别存放在两个数组中,用for循环进行查找,用一个变量记录结果相同的次数,如果相同,则++,如果不相同,则归零。
代码如下:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; int a[1000]; int b[1000]; int main() { int n; cin >> n; for (int i=1;i<=n;i++) //存放 { cin >> a[i] >> b[i]; } int sum=0; //记录连续几天 int flag=0; //标记是否有连续三次掷出相同点数,(0为否,1为是) for (int i=1;i<=n;i++) { if(a[i]==b[i]) //如果相同,则sum++ { sum++; if(sum>=3) //如果sum加到了3,那么flag=1,表明Yes,然后直接break掉就可以了 { flag=1; break; } } else { sum=0; } } if(flag==1) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
*C - A x B + C *
出题率:5/12
难度:中等
题意:
给你一个N,让你找三个正整数A ,B ,C,使得:A x B + C = N
(题目看起来很短,也很容易理解,但可能对于新生来说想出来、码出来还是稍微有些难度,当只要认真想想,码出来还是挺容易的)
大体思路:
用两个for循环遍历A和B,A就从1开始遍历到n结束,B就从1开始遍历到A-1结束,如果A*B的值比N小,说明存在C可以满足题目要求。
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> #include <fstream> typedef long long ll; using namespace std; int a[10000]; int main() { ll n; //这里的ll就是long long ,因为我在上面用了typedef ll sum=0; cin >> n; for (ll i=1;i<=n;i++) //i从1开始,到n结束 { for (ll j=1;j<i;j++) //j从1开始,到i-1结束 { if(i*j<n) sum+=2; //因为在i和j不相等的情况下,i和j是可以互换的,所以sum+=2,这也是为什么j到i-1就结束的原因 else break; } } for (ll i=1;i<=n;i++) //i和j相等的情况单独列出来计算一遍,因为两者相等,是无法互换的,所以sum++; { if(i*i<n) sum++; else break; } cout << sum << endl; }
D - Leaping Tak
出题率:0/2
难度:非常难
(这道题出给没学两天编程的人来说确实过于难想了,做不出来很正常,确实是有点难度了,想要提升自己的可以看看这里的解析,想先打好基础的可以直接看下一题)
题意:
在1~n的网格里,从第一格开始,在给的互不相交的区间中选出值来往前走,不可以超过网格,问总共有一种走法。(可以根据原题样例理解)
大体思路:
因为n是大于等于2,(当n=1的时候,也就是不用走,结果为1)
所以我们遍历的时候从2开始遍历就好了。
我们设dp[i]为走到i总共的方法数。
然后每一次遍历,我们要对每一个给出的区间进行判断。
设区间为[l,r],那么dp[i]=dp[i-l]+dp[i-l+1]+~~+dp[i-r-1]
我们可以设sum数组记录dp数组的前缀和,那么上述式子就可以写成:dp[i]=sum[i-l]-dp[i-r-1]
当然这道题的数据比较大,要取模。
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; ll mod = 998244353; int L[200005]; int R[200005]; ll sum[200005]; //dp的前缀和 ll dp[200005]; int main() { int n,k; cin >> n >> k; for (int i=1;i<=k;i++) { cin >> L[i] >> R[i]; } dp[1]=1; sum[1]=1; for (int i=2;i<=n;i++) { for (int j=1;j<=k;j++) { int l=L[j],r=R[j]; dp[i] = (dp[i] + sum[max(0,i-l)] - sum[max(0,i-r-1)] + mod) % mod; //sum里面的max是害怕小于0的情况,自己可以举个例子试试 } sum[i]=(sum[i-1]+dp[i])%mod; //更新dp数组的前缀和 } cout << dp[n] << endl; return 0; }
*E - Not *
出题率:34/50
难度:非常简单
题目:0输出1,1输出0
思路:按照题目的来
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> #include <fstream> typedef long long ll; using namespace std; int main() { int x; cin >> x; if(x==1) cout << "0" << endl; else cout << "1" << endl; }
F - Product Max
出题率:3/37
难度:中等
(个人感觉这道题出题数有点少,明明很水的一道题)
题目:给出两个区间,让你在两个区间各取一个数,让相乘为最大值
思路:肯定是取端点呀,不管是负数、正数还是0,最终答案肯定是端点相乘。
唯一想不到的可能就是会爆int,int的范围就到1e9,所以要用long long,这可能是唯一的绊脚石了。
下面给出AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; int main() { long long a,b,c,d; cin >> a >> b >> c >> d; cout << max(max(a*c,a*d),max(b*c,b*d)) << endl; return 0; }
*G - Ubiquity *
出题率:1/3
难度:非常难
(A出这道题的是咱们18级师哥,可以忽略不计,也就是这道题AC率为0)
(这道题确实有点难度,求排列组合还用到了逆元,不建议新生现在做这道题)
题目:给你n位数,你可以选择0~9中的任意一个数填进去
最后保证至少有一个0,至少有一个9的方法数是多少。
思路:
(1)所有的情况为:10^n
(2)没有0也没有9的情况:8^n
(3)只有0或者只有9:C(n,i)8^(n-i) -> i属于1~n(因为只有0或者只有9是一样道理的,所以这里要2)
(4)最后的结果就是(1)-(2)-(3)
下面给出AC代码:(我也是从网上找的)
里面还有一个知识点:快速幂,就是求a^n,可以降低时间复杂度。
想了解快速幂的可以从百度了解一下,这个知识点应该很快会讲到。
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> //typedef long long ll; using namespace std; typedef long long LL; const int N = 1e6+10; const int mod = 1e9+7; LL f[N]; /* 求组合数的时候要乘以逆元 在设计减法的时候要加上mod x的逆元:x^(mod-2) 预处理,提前求阶层 */ LL qpow(LL x,LL k) { LL res = 1; while(k) { if(k&1) res=res*x%mod; k>>=1; x = x*x%mod; } return res; } LL C(LL n,LL m) { return f[n]*(qpow(f[m]*f[n-m]%mod,mod-2)) % mod; } int main() { LL n; f[0] = 1; //注意预处理一下,f[n]代表n的阶层 for(int i=1;i<N;i++) { f[i] = f[i-1] * i % mod; } cin >> n; if(n<2) { cout << 0 << endl; return 0; } LL ans = (qpow(10,n) - qpow(8,n)+mod) % mod; LL tmp = 0; for(LL i=1;i<=n;i++) { tmp = (tmp + C(n,i)%mod*qpow(8,n-i)%mod)%mod; } tmp = tmp%mod*2%mod; ans = (ans - tmp + mod)%mod; cout<<ans<<endl; return 0; }
*H - Takoyaki *
出题率:26/41
难度:非常简单
题意:
每T分钟可以做X个甜点,问做N个甜点至少需要多少时间(这里的T分钟是不可以拆的)
思路:
如果可以整除的话,直接整除就好了,再T
如果不可以的话,那就所需时间的个数+1,然后再T
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> #include <fstream> typedef long long ll; using namespace std; int main() { int N,X,T; cin >> N >> X >> T; if(N%X==0) cout << N/X*T << endl; else cout << (N/X+1)*T << endl; }
I - Multiple of 9
出题率:3/20
难度:中等
(这道题可能有个知识点没有讲到,也可能讲到了你不会用,总之还是很简单的一道题)
题意:
给你一个整数(很大,很明显要用字符数组或者字符串输入),问你,这个整数各个位加起来的和是不是9的倍数。
思路:
(1)
这道题我是用字符串(string)来做的,简单讲一下字符串是什么东西:
字符串是C++独有的,C中并没有,C中要表示一串字符可以用char数组,而C++则可以用字符串。
正如他的名字一样,字符串是一串字符,地址从0开始,求一个字符数组的长度可以用.strlen()来求,而求字符串的长度则可以用.length()来求。
大体上字符串的基本知识就这些吧,当然字符串还有很多用处,这里就不说了。
(2)这道题还有一个知识点就是怎么把字符0~9转化成数字0~9
很简单:-‘0’就可以了。
好了,下面看具体的代码吧:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; int main() { string s; cin >> s; ll ans=0; for (int i=0;i<s.length();i++) { ans=ans+s[i]-'0'; //转成数字 } if(ans%9==0) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
*J - Step *
出题率:2/3
难度:简单
(不知道为什么这道水题A的人这么少,是没读懂题意吗?)
题意:给你n个数,在不交换这些数顺序的情况下,通过给一些数加上一些值,让他们成为非递减数列(就是后一个数大于等于前一个数)。
思路:
可以全部输进数组中,然后进行判断,如果后一个比前一个小,那么最后的结果ans就+=(前一个-后一个)
当然,也可以在输入的过程中直接进行判断。
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; ll a[200005]; //难道又是因为数组的原因导致不会做这道题? int main() { int n; cin >> n; for (int i=1;i<=n;i++) { cin >> a[i]; } ll ans=0; for (int i=2;i<=n;i++) { if(a[i]<a[i-1]) { ans+=a[i-1]-a[i]; a[i]=a[i-1]; } } cout << ans << endl; return 0; }
K - Rainy Season
出题率:17/34
难度:中等
不知道为啥这道题A的人又这么多,奇奇怪怪。
题意:
给你三个字符,问你最多几天连续下雨?
思路:
一共就三天,我连想都没想,直接暴力,不就是考虑那几种情况嘛,三天全是R,前两天是R,后两天是R,有一天是R这几种情况嘛。
很简单的想法,下面直接附上AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> #include <fstream> typedef long long ll; using namespace std; int main() { string s; cin >> s; if(s[0]==s[1]&&s[1]==s[2]&&s[0]=='R')cout << "3" << endl; else if((s[0]==s[1]&&s[0]=='R')||(s[1]==s[2]&&s[1]=='R')) cout << "2" << endl; else if(s[0]=='R'||s[1]=='R'||s[2]=='R') cout << "1" << endl; else cout << "0" << endl; }
*L - Making Triangle *
出题率:2/2
难度:中等
(这道题不是很难,主要是判断三角形)
题意:
给你n个数,选三个数,可以组成三角形,并且这三个数是不同的。
思路:
(1)因为N的最大范围是100,所以完全可以进行三次for循环,(很快就讲到时间复杂度了,等讲完时间复杂度你们再看这句话就会更好理解了)。
(2)判断三角形:两条小边之和大于第三边
给出AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; long long mod = 1e9+7; ll a[200005]; ll panduan(ll x,ll y,ll z) //判断三角形函数 { if(x>y) swap(x, y); if(y>z) swap(y, z); //首先把z换成最长的那一条边 if(x+y>z) return 1; else return 0; } int main() { int n; cin >> n; for (int i=1;i<=n;i++) { cin >> a[i]; } ll ans=0; for (int i=1;i<=n-2;i++) { for (int j=i+1;j<=n-1;j++) { for (int k=j+1;k<=n;k++) { if(a[i]==a[j]||a[i]==a[k]||a[j]==a[k]) continue; ans += panduan(a[i],a[j],a[k]); } } } cout << ans << endl; return 0; }
M - Walking Takahashi
出题率:0/0
难度:难
(这道题居然连交的都没有?虽然有点难,但到还不至于一个人都做不出来,就是一个思维题)
题意:
给你初始坐标X,运动次数K,每次运动的步数D
思路:
(1)首先X、K、D的范围很大,要用long long
(2)教大家一个求绝对值函数abs();
(3)这道题的大体思路:
如果可以走到离0点最近的距离,还剩下偶数步,那么结果就是最近距离的绝对值(偶数步的话走过去再走回来就好了)
如果还剩下奇数步,那么再走一步,然后求结果就跟求偶数步一样了,因为奇数步走完一步之后还剩偶数步。
如果不可以走到离0点最近的距离,那更简单了,直接朝着原点走,因为不可以走到离0点最近的距离,所以离0点一定越来越近。最后的结果就很好求了。
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; long long mod = 1e9+7; int main() { ll x,k,d; cin >> x >> k >> d; ll a = abs(x/d); //次数 (看看走到离0点最近的距离要用几次) if(a>=k) //如果走不到,分x正负输出就好 { if(x>=0) cout << abs(x-k*d) << endl; else cout << abs(x+k*d) << endl; return 0; //这里的return 0 ,说明程序直接结束,也就是如果这里运行了,下面的程序都不用运行了。 } //下面就是可以走到离0点最近的距离,也是分x正负 if(x>=0) x=x-a*d; else x=x+a*d; if((k-a)%2==0) //如果还剩下偶数步 { cout << abs(x) << endl; } else //如果还剩下奇数步 { if(x>=0) cout << abs(x-d) << endl; else cout << abs(x+d) << endl; } return 0; }
*N - Air Conditioner *
出题率:33/47
难度:非常简单
题意:大于等于30,输出Yes,否则输出No
思路:看题意
实在是太简单了,直接看AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; int main() { int n; cin >> n; if(n>=30) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
O - Distance
出题率:4/12
难度:中等
(非常简单的一道题,十分想要评简单)
题意:
跟你一个N和D以及N组样例
如果这N组样例中,有到原点的距离小于等于D的,结果就++
思路:看题意
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; long long mod = 1e9+7; int main() { double n,d; cin >> n >> d; int ans=0; for (int i=1;i<=n;i++) { double x,y; cin >> x >> y; if((x*x+y*y)<=d*d) ans++; //距离的判断 } cout << ans << endl; return 0; }
*P - Repsept *
出题率:0/0
难度:(非常难)
(好吧,这道题如果没有想法的话,很难做出来,对你们来说是有点难了)
题意:给你一个整数,让你求 能整除这个数的 由全部是7组成的数 的位数。
思路:
(1)如果n是偶数或者是5的倍数,可以得出不可能组成
证明:因为n是偶数,那么n任何数都是偶数,所以最后一位不可能是7
如果n是5的倍数,那么n任何数最后一位都是0或者5,不可能是7
(2)具体情况看代码吧,下面是AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; //样例101的例子如下: //1.7%101=7 //2.7*10+7=77,77%101=77 //3.77*10+7=777,777%101=70 //4.70*10+7=707,707%101=0 int main() { int k,cnt,a; scanf("%d",&k); if(k%2==0||k%10==5) { printf("-1\n"); return 0; } a=7; cnt=1; //cnt统计7出现的个数 while(1) //每进行一次就在最高位加一个1,这样cnt++,最后输出cnt就可以了 { if(a%k==0) break; a%=k; a=a*10+7; cnt++; } cout << cnt << endl; return 0; }
Q - Payment
出题率:28/71
难度:非常简单
题意:你有很多1000日元的钞票,给你一件商品的价格,问你最少买下它最少找你多少钱?
思路:
如果可以直接买下(是1000的倍数),则输出0
如果不可以直接买下,就以最少的1000日元买下,然后减掉价格就可以了
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> #include <fstream> typedef long long ll; using namespace std; int a[10000]; int main() { int n; cin >> n; if(n%1000==0) cout << "0" << endl; else { cout << (n/1000+1)*1000-n << endl; } }
*R - Judge Status Summary *
出题率:5/7
难度:简单
题意:
储存AC、TLE、WA、RE的次数
思路:直接看代码吧,很简单。
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; long long mod = 1e9+7; int main() { int n; cin >> n; string s; int sum1=0,sum2=0,sum3=0,sum4=0; for (int i=1;i<=n;i++) { cin >> s; if(s=="AC") sum1++; else if(s=="WA") sum2++; else if(s=="TLE") sum3++; else sum4++; } cout << "AC x " << sum1 << endl; cout << "WA x " << sum2 << endl; cout << "TLE x " << sum3 << endl; cout << "RE x " << sum4 << endl; return 0; }
S - Chat in a Circle
出题率:0/0
难度:难
(又是没有一个人做的题,话说出这么多题到底是干嘛~~~)
题意:
给你n个人,让你依次将人组成一个圆圈,当一个人插入圆圈的时候,舒适度等于左右两个人的最小的那个。
求最大的舒适度
思路:
先排序,依次将最大的输入圆圈中,可以得到,除了最大的那个值计算一次,剩下的就按照第二大、第三大~~依次计算2次
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; long long mod = 1e9+7; ll a[200005]; int main() { int n; cin >> n; for (int i=1;i<=n;i++) { cin >> a[i]; } sort(a+1, a+1+n); //这里是sort排序,很好用,想学的,可以问师哥或者百度(这里是直接将a数组从小到大排序) ll ans=0; ans += a[n]; //最大值计算一次 ll x=n-1; ll y=0; for (int i=1;i<=n-2;i++) //剩下的n-2次,从第二大开始依次计算两次 { ans += a[x]; y++; if(y==2) { y=0; x--; } } cout << ans << endl; return 0; }
T - Calc
出题率:33/34
难度:非常简单
题意&&思路:输出a+aa+aa*a
这道题非常简单,直接看AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> #include <fstream> typedef long long ll; using namespace std; int main() { int x; cin >> x; cout << x+x*x+x*x*x << endl; }
*U - Minor Change *
出题率:4/10
难度:中等
题意:
将一个字符串转化成另一个字符串
思路:按照前面说的,这种题用string或者char数组都可以。
(我这种题一般都用字符串,习惯了)
一位一位比较,如果不相等那么结果就++
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; int main() { string s1,s2; cin >> s1 >> s2; int ans=0; for (int i=0;i<s1.length();i++) { if(s1[i]!=s2[i]) ans++; } cout << ans << endl; return 0; }
V - Tsundoku
出题率:0/0
难度:非常难
(对你们这种小白来说这个题还是不太好理解,哎,又是一道0AC题)
题意:
给你一个最大容量,从两摞书中尽可能选择多的书。
思路:
(1)用前缀和数组储存两摞书的前缀和
(2)用for循环一摞书,另一摞书用二分的方法找到选择最大书的坐标
(这里的二分直接用upper_bound(),想学的同学可以从网上找找关于upper_bound()和lower_bound()的知识点。
(3)大体思路就是这样,具体还是看代码,这个题比较难,就不细致讲了,主要还是知识上的欠缺。
如果想要深入了解可以自行百度或者现场问各位师哥。
AC代码
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; ll a[200005]; ll sum1[200005]; ll b[200005]; ll sum2[200005]; int main() { ll n,m,t; cin >> n >> m >> t; for (int i=1;i<=n;i++) { cin >> a[i]; sum1[i]=sum1[i-1]+a[i]; } for (int i=1;i<=m;i++) { cin >> b[i]; sum2[i]=sum2[i-1]+b[i]; } ll ans=0; for (int i=0;i<=n;i++) { if(t<sum1[i]) break; ll x=upper_bound(sum2+1, sum2+1+m, t-sum1[i])-sum2; ans = max(ans,i+x-1); } cout << ans << endl; return 0; }
*W - αlphabet *
出题率:28/38
难度:非常简单
题意&&思路:大写字母输出A,小写字母输出a
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> #include <fstream> typedef long long ll; using namespace std; int main() { char x; cin >> x; if(x<='Z'&&x>='A') cout << "A" << endl; else cout << "a" << endl; }
*X - Mix Juice *
出题率:7/13
难度:中等
题意&&思路:
给你一个N和K以及N个数,让你找出这N个数中的K个数,使得和最小
这个题就是一个排序题,上面有提到过sort排序,如果你会sort排序的话,这道题就会很简单。
直接上AC代码
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> #include <fstream> typedef long long ll; using namespace std; int a[10000]; int main() { int n,m; cin >> n >> m; for (int i=1;i<=n;i++) { cin >> a[i]; } sort(a+1, a+1+n); int ans=0; for (int i=1;i<=m;i++){ ans+=a[i]; } cout << ans << endl; }
Y - One Quadrillion and One Dalmatians
出题率:0/1
难度:难
题意:十进制转化成二十六进制的题。
思路:
用while循环对要转化的数进行遍历,如果这个数!=0就不终止。
这个题就跟十进制转化成二进制一样,如果这个题的AC代码看不懂的话,建议先搞懂十进制转化为二进制。
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; int main() { ll n; cin >> n; string s; while(n) { n--; ll x=n%26; char c=x+'a'; s=s+c; n=n/26; } for (int i=s.length()-1;i>=0;i--) { cout << s[i] ; } cout << endl; return 0; }
*Z - Puzzle *
出题率:0/0
难度:非常难
(这道题应该是防止AK的题吧,我自己做都做了好久,如果不是这道题,从昨天晚上开始写解题报告的我应该会早很多写完吧)
题意:给你5*5的方格,里面有一个空格,然后给你一个字符串,按照上下左右的操作步骤进行操作,让你输出最终的结果。
这是一个多组样例输入的题,如果碰到‘Z’结束。
思路:别看我说题意很简单,实现还是很难的,如果对输入字符,有没有换行符,空格什么的不熟悉的同学,并且还要有一定基础,我强烈建议做一下这道题。
有兴趣欢迎讨论。
我直接给出AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; char c[10][10]; void jiaohuan(int x1,int x2,int y) { c[x1][y]=c[x2][y]; c[x2][y]=' '; } void jiaohuan2(int h,int y1,int y2) { c[h][y1]=c[h][y2]; c[h][y2]=' '; } int main() { int cnt=0; int x=0,y=0; char s; while(1) { for (int i=1;i<=5;i++){ for (int j=1;j<=5;j++){ c[i][j]=getchar(); if(c[1][1]=='Z') return 0; if(c[i][j]==' '){ x=i; y=j; } } getchar(); } int flag=1; while((s=getchar())!='0') { if(s=='A'&&x-1>=1) { jiaohuan(x,x-1,y); //空格,不是空格,列数 x=x-1; } else if(s=='B'&&x+1<=5) { jiaohuan(x,x+1,y); //空格,不是空格,列数 x=x+1; } else if(s=='L'&&y-1>=1) //跟左面的换 { jiaohuan2(x,y,y-1); //行 y=y-1; } else if(s=='R'&&y+1<=5) { jiaohuan2(x,y,y+1); y=y+1; } else if(isspace(s))continue; else flag=0; } getchar(); if(cnt!=0) cout << endl; printf("Puzzle #%d:\n", ++cnt); if(flag==1){ for (int i=1;i<=5;i++){ for (int j=1;j<=5;j++){ cout << c[i][j] ; if(j<5) cout << " "; } cout << endl; } } else printf("This puzzle has no final configuration.\n") ; } return 0; }
终于写完了,这简直是一场噩梦,如果下次还有这么多题,我绝对不写题解了,本来里面有很多小知识我想写一下,但我实在是太懒了、写不动了,就自动忽略了我认为很简单的问题。(好久没有连续这么长时间注意力高度集中了)
我的代码肯定是正确的,因为我都AC了一遍。
我的代码可能不是最精确的,可能不是最短的,可能是繁杂的,这是肯定的,有很多可以剪枝的方法我看出来了都没用,因为这些大水题完全没有必要。
因为写的太过匆忙,我也不知道写了多少字了,里面肯定有错别字,还希望大家谅解,二十六个题,不多不少,欢迎大家在群里或在评论区里讨论。