考试时候可能没有VS,但codeblocks是必备的。
下面总结一些常用的快捷键。
- Ctrl+Enter:光标移至行尾
- Shift+Enter:光标跳到下一行
- Ctrl+D:直接复制粘贴当前行
- Ctrl+L:删除当前行
- F9:build+run。
- Ctrl+Shift+C:注释掉当前行
- Ctrl+Shift+X:解除当前行注释
- 文件路径最好不要含有中文,否则编译出错时无法定位!
下面也给出了csdn写博客的快捷键
ctrl+shift+
H:标题
O:有序列表
K:插入代码
1.阶乘-递归算法
本来没加long long 只有13组用例可以通过
-
#include <iostream> using namespace std; long long int function_(int n){ //本来没加long long 只有13组用例可以通过 if (n==0||n==1) return 1; else return n*function_(n-1); } int main() { int n; while (cin >> n) { // 注意 while 处理多个 case cout <<function_(n)<< endl; } }
- 2.特殊乘法--字符转为整数
- 写个算法,对2个小于1000000000的输入,求结果。 特殊乘法举例:123 * 45 = 1*4 +1*5 +2*4 +2*5 +3*4+3*5
- 将字符转换为数字的方法:
c - '0'
-
#include <iostream> using namespace std; long int function_(string a,string b) { long long res=0; for(int i=0;i<a.size();i++){ for(int j=0;j<b.size();j++) { res+=(a[i]-'0')*(b[j]-'0');//非常巧妙地将字符串转为数字来进行计算 } } return res; } int main() { string a, b; while (cin >> a >> b) { // 注意 while 处理多个 case cout << function_(a,b) << endl; } }
2.小白鼠排队——排序
按weight 降序排列
-
#include <algorithm> #include <iostream> using namespace std; struct rat{ int weight; string color; }; bool cmp(rat a,rat b) { return a.weight>b.weight; } int main() { int n; cin>>n; rat rats[n]; for(int i=0;i<n;i++) { cin>>rats[i].weight>>rats[i].color; } stable_sort(rats,rats+n,cmp); for(int i=0;i<n;i++) { cout<<rats[i].color<<endl; } }
-
3.简单加密--字符串
- 对给定的一个字符串,把其中从a-y,A-Y的字母用其后继字母替代,把z和Z用a和A替代,则可得到一个简单的加密字符串。
- 注意:字符串的输入有空格时,不能用cin,可用getline();
-
#include <iostream> using namespace std; int main() { string s; //cin>>s; 注意这里如果用cin输入的话碰到空格就会停止输入 while(getline(cin,s)){ int len=s.size(); for(int i=0;i<len;i++) { if(s[i]>='a'&&s[i]<='z')s[i]=(s[i]-'a'+1)%26+'a'; if(s[i]>='A'&&s[i]<='Z')s[i]=(s[i]-'A'+1)%26+'A'; } cout<<s; } }
-
4.质因数的个数
- 求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5,共有5个质因数。
- 注意空间的问题,空间太大就不能通过的。
-
//求质因子的时候没必要去判断一个因子是否为质数,因为一个数是质数,比如11,无论前面如何进行除法运算,一定有这个因子。 //只需要从2开始遍历,遍历到根号n即可。因为一个数字至多存在一个大于根号n的因子,如果存在大于根号n的因子,加一就好了。 #include <iostream> using namespace std; //第一次尝试用function_1,但是算法空间太大,所有下面用function_2进行改进 long long int function_1(long int a) { int sum=0;//用于计数 long int a_=a;//用于更新被除数,初值为a int i; for( i=2;i*i<=a;i++) { if(a_%i==0){ int s=0; while(a_%i==0) { s++; a_/=i; } sum+=s; } } if(a_>1) sum++;//如果有大于根号n的因子,最后结果加1; return sum; } long int function_2(long int x) { int sum=0;//用于计数 int i; for( i=2;i<=x/i;i++) { if(x%i==0){ int s=0; while(x%i==0) { s++; x/=i; } sum+=s; } } if(x>1) sum++;//如果有大于根号n的因子,最后结果加1; return sum; } int main() { long int x; cin>>x; cout<<function_2(x); }
5.整数的拆分
一个整数总可以拆分为2的幂的和,例如: 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。 再比如:4可以拆分成:4 = 4,4 = 1 + 1 + 1 + 1,4 = 2 + 2,4=1+1+2。 用f(n)表示n的不同拆分的种数,例如f(7)=6. 要求编写程序,读入n(不超过1000000),输出f(n)%1000000000。
//思路:动态规划
//每一个数都可以拆成2的次幂形式,2的次幂有(1,2,4,8...),其中只有一个奇数
//假定给一个数N
/*1.N是奇数,那么N的拆分一定有一个1,所以f(N)=f(N-1)
2.N是偶数,可以分两种情况:
a.N中拆分出1,之后和1.的情况一样
b.N中不拆分出1,即都是偶数。假如N的和为2m,那么除2之后就变成m,但是并不影响f(n)
两种情况的结果相加可以得到完整的结果。
也就是说N为偶数的结果就是f(N)=f(N-1)+f(N/2),好看一点就是f(2m)=f(2m-1)+f(m)
*/
#include <iostream>
using namespace std;
//这里写的f1输出结果是对的,但是提交到系统超时了,说是循环有问题或算法复杂。
int f1(int n)
{
if(n==1)return 1;
if(n%2!=0)//n为奇数
{
return f1(n-1);
}
else//n为偶数
{
return f1(n-1)+f1(n/2);
}
}
//基于上面的问题,用下面的方法
//不用递归函数,而是用一个数组来存储,直接求出前几项的结果,再用类似上面的函数
//f(N)=f(N-1)+f(N/2)
void f2(long int n){
long int c[1000001];
c[0]=1;
for(int i=1;i<=n;i++){
if(i%2==0) c[i]=(c[i-1]+c[i/2])%1000000000;//这里不是很懂为什么%1000000000
else c[i]=c[i-1]%1000000000;
}
cout<<c[n]<<endl;
}
//当成完全背包
/*
先介绍一下科学计数法的表示。如:
234 可以记为: 2.34e+2
0.0234 可以记为: 2.34e-2
所以1e6 //10的6次方1000000
*/
void f3(int n)
{
const int N=1e6+10,mod=1000000000;
int f[N];
f[0]=1;
for(int i=1;i<=n;i*=2)
{
for(int j=i;j<=n;++j)
{
f[j]=(f[j]+f[j-i])%mod;
}
}
cout<<f[n]<<endl;
}
int main() {
long int n;
cin>>n;
f3(n); //一共写了三种方法,个人觉得2比较好理解,可能是背包还不熟
return 0;
}
// 64 位输出请用 printf("%lld")
6.求球的半径和体积
#include <cmath>
#include <iostream>
#include<math.h>
using namespace std;
//已知球中心点和任意一点
//输出球的半径和体积,并且结果保留三位小数 为避免精度问题
//球的半径用两点之间的距离公式来求解,体积4/3(Π*R*R*R)
void f(int x0,int y0,int z0,int x,int y,int z)
{
double R;
R=sqrt((x0-x)*(x0-x)+(y0-y)*(y0-y)+(z0-z)*(z0-z));
double V;
V=(4*(M_PI*R*R*R))/3;
printf("%.3f ",R);
printf("%.3f",V);
}
int main() {
int x0,y0,z0;//中心点
int x,y,z; //任一点
while(cin>>x0>>y0>>z0>>x>>y>>z){
f(x0,y0,z0,x,y,z);
}
return 0;
}
// 64 位输出请用 printf("%lld")
7.二叉树的遍历
读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。
输入 abc##de#g##f###
输出 c b e g d f a
本题主要学习全局变量和递归算法遍历二叉树
//本题主要学习全局变量和递归算法遍历二叉树
#include <bitset>
#include <cstddef>
#include <iostream>
using namespace std;
typedef struct BiNode{//定义二叉树结点
char value;
BiNode * left,*right;
}BiNode,*BiTree;
int pos;
char s[100];
BiNode * first_create()
{
char c=s[pos++];
if(c=='#') //如果为空,返回上个节点
return NULL;
BiNode *root=new BiNode();//新建节点
root->value=c;
root->left=first_create();//创建左子树
root->right=first_create();//创建右子树
return root;
}
void middle_print(BiTree T)
{
//中序遍历左根右
if(T!=NULL)
{
middle_print(T->left);
cout<<T->value<<" ";
middle_print(T->right);
}
else return;
}
int main() {
BiTree T;
while (cin >> s ) { // 注意 while 处理多个 case
pos=0;
T=first_create(); //先序创建二叉树
middle_print(T); //二叉树的中序遍历
}
}
// 64 位输出请用 printf("%lld")
8.最大最小值
#include <iostream>
using namespace std;
//如果仅求最大最小值的话,不需要排序,输入时维护好最大最小值就好。不用把数存成一个数组
//也不用搞一个最大最小函数,搞复杂了点,但是复杂函数的时候要用这个模块化
int main() {
int n,temp;
while(cin>>n){
int MAX=-0x3f3f3f3f,MIN=0x3f3f3f3f;//初始的MAX值设置的很大,MIN值很小
for(int i=0;i<n;i++){
cin>>temp;
if(temp>MAX)MAX=temp;
if(temp<MIN)MIN=temp;
}
cout<<MAX<<" "<<MIN<<endl;
}
return 0;
}
// 64 位输出请用 printf("%lld")
9.特殊乘法
写个算法,对2个小于1000000000的输入,求结果。 特殊乘法举例:123 * 45 = 1*4 +1*5 +2*4 +2*5 +3*4+3*5
下面的方法具简单,但是前提是你已经发现里面的规律。不然还是老老实实的求解。
#include <iostream>
using namespace std;
//我的思路是一种是用整数来做,但是发现如果数过大的话会比较麻烦
//其实把两个数看为字符串,但好像步骤有点繁琐
//下面有一种其他大佬的思路
/*特殊乘法结果为x,y所有位和的乘积
如123 * 45 = 1*4 +1*5 +2*4 +2*5 +3*4+3*5
= 1(4+5)+2(4+5)+3(4+5)
= (1+2+3)*(4+5)
*/
int Sum(int num)//求十进制数所有位的和
{
int sum=0;
while(num>0)
{
sum+=num%10;
num/=10;
}
return sum;
}
// long int f(long int a,long int b){
// }
int main() {
long int a, b;
while (cin >> a >> b) { // 注意 while 处理多个 case
//cout << f(a,b) << endl;
cout<<Sum(a)*Sum(b);
}
}
下面是直接用字符串的方法。关键是如何将字符转为数字 用 c-'0' 就可以啦!
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s1, s2;
cin >> s1 >> s2;
long long res = 0;
for (int i = 0; i < s1.size(); ++i)
for (int j = 0; j < s2.size(); ++j)
res += (s1[i] - '0') * (s2[j] - '0');
cout << res << endl;
return 0;
}
10.今天是第几天
输入年、月、日,计算该天是本年的第几天。
包括三千个整数年(1<=Y<=3000)、月(1<=M<=12)、日(1<=D<=31)
本题学习一下平年润年的判断方法以及二维数组
#include <iostream>
using namespace std;
int dayTable[2][13]={
{0,31,28,31,30,31,30,31,31,30,31,30,31},//平年
{0,31,29,31,30,31,30,31,31,30,31,30,31}
};
bool isLeapYear(int year)
{
if((year%4==0&&year%100!=0)||year%400==0)
return true;//润年是1
return false;
}
int f(int year,int month,int day)
{
//求二维数组的行和
int number=0;
int row=isLeapYear(year);
for(int i=0;i<month;i++)
{
number+=dayTable[row][i];
}
number+=day;
return number;
}
int main() {
int year,month,day;
while (cin >>year>>month>>day) { // 注意 while 处理多个 case
cout <<f(year,month,day) << endl;
}
}
每日十题,今日任务完成!!!
11.完数和盈数
#include <iostream>
using namespace std;
/*
完数和盈数
*/
// 8 1 2 4 8
// 16 1 2 4 8 (16)
// 32 1 2 4 8 16 (32)
int main() {
int a[60];
int b[60];
int pos_a=0;//如果是完数保存到数组a
int sum_a=0;
int pos_b=0;
int sum_b=0;
for(int i=2;i<=60;i++){
int sum=0;
for(int j=1;j<i;j++)
{
if(i%j==0) sum+=j;
}
if(sum==i)
{
a[pos_a++]=i;
sum_a++;
}
if(sum>i)
{
b[pos_b++]=i;
sum_b++;
}
}
cout<<"E: ";
for(int i=0;i<sum_a;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"G: ";
for(int i=0;i<sum_b;i++)
{
cout<<b[i]<<" ";
}
}
12.递推数列
给定a0,a1,以及an=p*a(n-1) + q*a(n-2)中的p,q。这里n >= 2。 求第k个数对10000的模。
输入描述:
输入包括5个整数:a0、a1、p、q、k。
循环的时间复杂度低于递归。
使用cin会超时,使用scanf输入
#include <iostream>
using namespace std;
//这里用递归会显示程序超时
// int f(int a0,int a1,int p,int q,int k)
// {
// if(k==2) return p*a1+q*a0;
// return p*f(a0,a1,p,q,k-1)+q*f(a0,a1,p,q,k-2);
// }
//下面的 部分报错,显示段错误,咋也不知道是咋会儿事
// int a[1000];
// int f(int a0,int a1,int p,int q,int k)
// {
// return p*a1+q*a0;
// }
// int main() {
// int a0,a1,p,q,k;
// cin>>a0,a1,p,q,k;
// for(int i=2;i<=k;i++)
// {
// a[i]=f(a[i-1],a[i-2],p,q,i);
// }
// a[k]=a[k]%10000;
// cout<<a[k];
// }
//重新写吧
//家人们为什么下面这里还说我运行超时呀?
int main(){
int a0,a1,p,q,k;
scanf("%d %d %d %d %d",&a0,&a1,&p,&q,&k);
//家人们这里我用了cin会显示超时,变成scanf就成功运行了
int a[k+1];
a[0]=a0;
a[1]=a1;
int i;
for( i=2;i<=k;i++)
{
a[i]=(p*a[i-1]+q*a[i-2])%10000;
}
cout<<a[k];
return 0;
}
13.最大序列和--动态规划
给出一个整数序列S,其中有N个数,定义其中一个非空连续子序列T中所有数的和为T的“序列和”。 对于S的所有非空连续子序列T,求最大的序列和。 变量条件:N为正整数,N≤1000000,结果序列和在范围(-2^63,2^63-1)以内。
#include <algorithm>
#include <iostream>
#include <bits/stdc++.h>
#include<limits.h>
using namespace std;
//家人们这个哪里有问题我想说,提交不通过呀
// const int MAX=1e6+10;
// long long f[MAX],a[MAX];//用这个数组来存前i项的和
// int main() {
// int n;
// while(~ scanf("%d",&n)){
// for(int i=1;i<=n;i++) scanf("%d",&a[i]);
// f[1]=a[1];
// long long maxx=f[1];
// for(int i=2;i<=n;i++)
// {
// if(f[i-1]>0) {f[i]=f[i-1]+a[i];}
// else {f[i]=a[i];}
// maxx=max(f[i],maxx);//比较的两个数必须类型也是一样的,不然max函数会报错
// }
// printf("%d\n",maxx);
// }
// return 0;
// }
//下面和上面有什么不同呀,下面的可以通过
#include<iostream>
#include<limits.h>
using namespace std;
const int MAX=1e6+10;
typedef long long ll;
ll f[MAX],a[MAX];
int main(){
int n;
while(~scanf("%d",&n)){
for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
f[1]=a[1];
ll maxx=f[1];
for(int i=2;i<=n;++i){
if(f[i-1]>0) f[i]=f[i-1]+a[i];
else f[i]=a[i];
maxx=max(f[i],maxx);
}
printf("%lld\n",maxx);
}
return 0;
}