算法竞赛入门【暑期速成计划】（一）
前言
为什么突然想学算法了？
> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言，是因为当下快到了考研和找工作的年纪(ಥ_ಥ)，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个暑假速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~
一、程序设计入门
（一）、变量及其输入
- 程序的三部曲：输入、计算、输出，其中，整数值用%d输出，实数用%f输出。
- 只有运算符两边都是整数，运算结果才会是整数，但需要注意： 整数之间的除法会向下取整，如8/5=1，而如果想要1.6，则应改为实数运算，即8.0/5.0。
- 运算符“/”，其实是“多面手”，它既可以做整数除法，又可以做浮点数除法。整数/整数=整数，浮点数/浮点数=浮点数，浮点数/整数=浮点数，整数/浮点数=浮点数。
- 在算法竞赛中，输入前不要打印其它提示信息。输出完毕后应立即终止程序，不要等待用户按键，因为输入输出过程都是自动的，没有人工干预。
- 在算法竞赛中不要使用头文件conio.h（控制台输入输出），包括getch()、clrscr()等。
- 尽量用关键字声明常数。
- math.h中定义的常量M_PI不是ANSIC标准的，不信可以试试gcc-ansi编译试试。
总结一下，算法竞赛的程序应当只做3件事：读入数据、计算结果、打印输出。不要打印提示信息，不要打印输出后“暂停程序”，更不要尝试画图、访问网络等与算法无关的任务。
（二）、结构程序设计
1. 三位数反转
输入一个三位数，分离出它的百位、十位和个位，反转后输出。
样例输入：
127
样例输出：
721
【分析】
首先将三位数读入变量n，然后进行分离。百位等于n/100（注意这里取的是商的整数部分），十位等于n/10%10（这里的%是取余数操作），个位等于n%10。程序如下：#include<stdio.h>
int main()
{
int n;
scanf("%d",&n);
printf("%d%d%d\n",n%10,n/10%10,n/100);
return 0;
}【疑问】
此题中有一个没有说清楚的细节，即：如果个位是0，反转后应该输出吗？例如，输入是520，输出是25还是025？如果是25，直接用%d格式输出即可，而025，则需将输出格式变为%03d进行输出。
2.变量交换
输入两个整数a和b，交换二者的值，然后输出。
样例输入：
824 16
样例输出：
16 824
【分析】
按照题目所说，先把输入存入变量a和b,然后交换。如何交换两个变量呢？最经典方法是三变量法：
#include<stdio.h>
int main()
{
int a,b,c;
scanf("%d%d",&a,&b);
t=a;
a=b;
b=t;
printf("%d %d\n",a, b);
return 0;
}法二：
#include<stdio.h>
int main()
{
int a,b;
scanf("%d%d",&a,&b);
a=a+b;
b=a-b;
a=a-b;
printf("%d %d\n",a, b);
return 0;
}法三：
#include<stdio.h>
int main()
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d %d\n",b, a);
return 0;
}总结一下，交换两个变量的三变量法使用范围广，推荐使用，而算法竞赛中更推荐使用法三，简单快捷，符合算法竞赛的要求——KISS(Keep It Simple and Stupid)。
二、习题训练（码题集）
1.程序设计入门
【AC代码】
#include<stdio.h>
int main()
{
printf("This is my first program!\n");
printf("Coding is fun!");
return 0;
}2.输入和输出整型数据
【AC代码】
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int x;
cin>>x;
printf("You entered:%d",x);
return 0;
}3.整数运算
【AC代码】
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int x,y;
scanf("%d,%d",&x,&y);
printf("%d+%d=%d\n",x,y,x+y);
printf("%d-%d=%d",x,y,x-y);
return 0;
}4. 求余
【AC代码】
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int x,y,z,w;
scanf("%d %d",&x,&y);
scanf("%d %d",&z,&w);
printf("%d%%%d=%d\n",x,y,x%y);
printf("%d%%%d=%d",z,w,z%w);
return 0;
}5. 输入和输出实型数据
【AC代码】
#include<bits/stdc++.h>
using namespace std;
int main( )
{
float x;
double y;
scanf("%f %lf",&x,&y);
printf("You entered:%.2f and %.3f",x,y);
return 0;
}6. 实型数运算
【AC代码】
#include<bits/stdc++.h>
using namespace std;
int main( )
{
double x,y;
scanf("%lf %lf",&x,&y);
printf("%.6f*%.6f=%.6f\n",x,y,x*y);
printf("%.6f/%.6f=%.6f",x,y,x/y);
return 0;
}7. 平均分
【AC代码】
#include<bits/stdc++.h>
using namespace std;
int main( )
{
double x,y,z;
scanf("%lf %lf %lf",&x,&y,&z);
printf("%.6f\n",x+y+z);
printf("%.6f",(x+y+z)/3);
return 0;
}8. 圆球等的相关计算
【AC代码】
#include<bits/stdc++.h>
using namespace std;
int main( )
{
double r,h;
double PI=3.1415926;
scanf("%lf %lf",&r,&h);
printf("%.2f\n",2*r*PI);
printf("%.2f\n",PI*r*r);
printf("%.2f\n",4*PI*r*r);
printf("%.2f\n",PI*r*r*r*4/3);
printf("%.2f\n",PI*r*r*h);
return 0;
}9. 公式计算
【AC代码】
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int x,a;
float y;
scanf("%d %d",&x,&a);
y=0.5*(a*x+(a+x)/(4.0*a));
printf("%.2f",y);
return 0;
}10. 输入和输出字符型数据
【AC代码】
#include<bits/stdc++.h>
using namespace std;
int main( )
{
char a,b;
scanf("%c,%c",&a,&b);
printf("The ASCII code of %c is %d\n",a,a);
printf("The ASCII code of %c is %d",b,b);
return 0;
}11. 硬币塔
【AC】代码
#include<stdio.h>
long long int counthang(int n)
{
if(n==0)
return 1;
else
return 2+n+2*counthang(n-1);
}
long long int count(int n)
{
if(n==0)
return 1;
else
return n+2*count(n-1);
}
void jilu(int n,long long int i,long long int *sum)
{
if(n == 0){
if( i > 0)
*sum += 1;
return;
}
long long int num=counthang(n);
long long int temp = counthang( n - 1);
if( i <= n){
*sum+=0;
}else if(i>=num-n)// 1 | k-1 | k | k-1 | 1
{
*sum+=count(n);
}
else if( i > (temp + n + 1) )
{
*sum+=count(n-1)+ n;
jilu(n-1,i-temp-n - 1,sum);
}
else if(i> temp + 1)
{
*sum+= count(n-1)+i - temp -1;
}
else if ( i > n)
{
jilu(n-1,i-1,sum);
}
}
int main()
{
long long int i,sum=0;
int n;
scanf("%d %lld",&n,&i);
jilu(n,i,&sum);
printf("%lld",sum);
return 0;
}
12. 判断三角形
【AC代码】
#include<stdio.h>
void number(int *a,int *b,int *c){
int temp;
if(*a>*b) temp=*a,*a=*b,*b=temp;
if(*b>*c) temp=*b,*b=*c,*c=temp;
if(*a>*b) temp=*a,*a=*b,*b=temp;
}
int main()
{
int a,b,c;
long sqrtsum;
scanf("%d %d %d",&a,&b,&c);
number(&a,&b,&c);
sqrtsum = a*a + b*b;
if((a+b)>c){
if(sqrtsum == c*c) printf("Right triangle\n");
if(sqrtsum > c*c) printf("Acute triangle\n");
if(sqrtsum < c*c) printf("Obtuse triangle\n");
if(a == b||b == c) printf("Isosceles triangle\n");
if(a == c) printf("Equilateral triangle\n");
}else{
printf("Not triangle\n");
}
return 0;
}
13. 星图
【AC代码】
#include<stdio.h>
#include<math.h>
int main()
{
int n,k,x,y,i,j;
double result,sum,distance,distance_sum;
int A[150],B[150];
scanf("%d %d",&n,&k);
for(j=0; j<n; j++){
scanf("%d %d",&x,&y);
A[j]=x;
B[j]=y;
}
for(j=0; j<n-1; j++){
distance = sqrt(pow((A[j+1]-A[j]),2)+pow((B[j+1]-B[j]),2));
distance_sum += distance;
}
sum = distance_sum*k;
result=sum/50;
printf("%.9f",result);
return 0;
}14. 非常大的N
【AC代码】
#include<stdio.h>
#include<math.h>
int main()
{
int n,b=1;
double sum=1,a;
scanf("%d",&n);
for(int i=2;i<=n;i++){
b*=-1;
a=sqrt(i)*b;
sum+=a;
}
printf("%6f",sum);
return 0;
}15. 两条线段
【AC代码】
#include<stdio.h>
#include<stdlib.h>
int judge(int Ax1,int Ay1,int Ax2,int Ay2,int Bx1,int By1,int Bx2,int By2);
int main()
{
int Ax1,Ay1,Ax2,Ay2;
int Bx1,By1,Bx2,By2;
scanf("(%d,%d) (%d,%d)",&Ax1,&Ay1,&Ax2,&Ay2);
scanf("(%d,%d) (%d,%d)",&Bx1,&By1,&Bx2,&By2);
if(judge(Ax1,Ay1,Ax2,Ay2,Bx1,By1,Bx2,By2))
printf("YES\n");
else
printf("NO");
return 0;
}
int max(int x, int y){
if(x>y) y=x;
return y;
}
int min(int x, int y){
if(x<y) y=x;
return y;
}
int judge(int Ax1,int Ay1,int Ax2,int Ay2,int Bx1,int By1,int Bx2,int By2)
{
if(
( max(Ax1,Ax2)>=min(Bx1,Bx2)&&min(Ax1,Ax2)<=max(Bx1,Bx2) )&& //判断x轴投影
( max(Ay1,Ay2)>=min(By1,By2)&&min(Ay1,Ay2)<=max(By1,By2) ) //判断y轴投影
)
{
if(
( (Bx1-Ax1)*(Ay2-Ay1)-(By1-Ay1)*(Ax2-Ax1) ) * //判断B是否跨过A
( (Bx2-Ax1)*(Ay2-Ay1)-(By2-Ay1)*(Ax2-Ax1) ) <=0 &&
( (Ax1-Bx1)*(By2-By1)-(Ay1-By1)*(Bx2-Bx1) ) * //判断A是否跨过B
( (Ax2-Bx1)*(By2-By1)-(Ay2-By1)*(Bx2-Bx1) ) <=0
)
{
return 1;
}
else
return 0;
}
else
return 0;
}
16. 均分糖果
【AC代码】
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define ll long long
const int N = 1000010;
int n;
ll a[N];
int main() {
cin >> n;
ll ave = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i + n] = a[i] ;
ave += a[i];
}
ave = ave / n;
ll an = 1e9;
for (int i = 1; i <= n; i++){
ll now = 0, ans = 0;
for (int j = i; j <= n + i - 1; j++){
ll t = now + a[j] ;
ans += abs(t - ave);
now = t - ave;
}
an = min (an, ans) ;
//cout << ans <<" " ;
}
cout << an ;
return 0;
}
17. excel的烦恼
【AC代码】
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
string str;
int n,len;
void trans(bool mode)
{
char apt[] = " ABCDEFGHIJKLMNOPQRSTUVWXYZ"; //alphabet 字母表
int col = 0,row = 0; //col为列号，row为行号;
if(mode) //mode 1: RXCY转Excel式
{
int R = str.find("R"),C = str.find("C"); //使用find()函数，找到R与C所在的位置;
for(int i = R + 1;i < C;i++) //从R的下一位开始遍历，下同;
row = row * 10 + str[i] - '0'; //字符串转十进制数字
for(int i = C + 1;i < len;i++)
col = col * 10 + str[i] - '0';
string ans;
while(col > 0)
{
int temp = col % 26; //除26取余，下同;
if(temp == 0) temp = 26,col -= 26; //当col对应字母为'Z' 时，需要进行特判;
ans += apt[temp]; //利用apt[]将数字重新转为对应字母,使用ans字符串储存答案;
col /= 26;
}
reverse(ans.begin(),ans.end());
//此时得到的ans是按从低位到高位存储的，
//我们需要将ans反转，使其按高位到低位存储，从而符合题目要求;
cout<<ans<<row<<endl;//直接输出即可;
/*（如果不对ans进行反转，则输出应改为：）
for(int i = ans.length() - 1;i >= 0;i--) cout<<ans[i];
cout<<row<<endl;
*/
}
else //mode 2: Excel式转为RXCY式;
{
for(int i = 0;i < len;i++) //遍历字符串
{
if(!isdigit(str[i]))
col = col * 26 + str[i] - 'A' + 1; //26进制字符串转十进制数字;
else row = row * 10 + str[i] - '0'; //同上;
}
printf("R%dC%d\n",row,col);
}
}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
cin>>str; //使用string类型,以便下面利用一些STL的特性;
bool flag = 0,mode = 0; //本题是多组数据，需要初始化;
len = str.length();
for(int i = 0;i < len;i++) //遍历整个字符串，利用两种表示方式的不同来判断;
{
if(isdigit(str[i])) flag = 1; //flag用来标记数字是否已经出现;
if(flag&&str[i] == 'C') //在RXCY表示法中一定会出现字母C，且C之前一定会有数字出现，
{ //而在另一种表示法中，数字的后面不可能存在字母;
mode = 1;
break; //一旦判断出相应的表示方式，直接跳出即可;
}
}
trans(mode);// mode = 1 或 0，区分两种不同的转换;
}
return 0;
}
18. 门票
【AC代码】
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
const int maxn=10000100;
int n,t;
int b[maxn],c[maxn];
const ll mod=1000000007;
ll ans=0;
int num[maxn];
void insert(ll x){
for(int i=x;i<=n+1;i+=i&-i)
num[i]++;
}
ll query(ll x){
ll s=0;
for(int i=x;i;i-=i&-i)
s+=num[i];
return s;
}
int main(){
scanf("%d%d",&n,&t);
for(int i=1;i<=n;i++){
scanf("%d",&c[i]);
c[i]-=t;
}
for(int i=1;i<=n;i++) c[i]+=c[i-1];
for(int i=1;i<=n;i++) b[i]=c[i];
sort(b+1,b+n+2);
for(int i=0;i<=n;i++)
c[i]=lower_bound(b+1,b+n+2,c[i])-b;
insert(c[0]);
for(int i=1;i<=n;i++){
ll x=query(c[i]);
ans+=x;
ans%=mod;
insert(c[i]);
}
printf("%lld\n",ans);
return 0;
}19. 矩形包含
【AC代码】
#include<stdio.h>
int main()
{
int x1, y1,x2,y2,a1,b1,a2,b2;
scanf("%d %d %d %d %d %d %d %d",&x1,&y1,&x2,&y2,&a1,&b1,&a2,&b2);
if(x1<a1&&y1>b1&&x2>a2&&y2<b2) printf("YES");
else if(x1>a1&&y1<b1&&x2<a2&&y2>b2) printf("YES");
else printf("NO");
return 0;
}20. 特殊整数
【AC代码】
#include<stdio.h>
#include<math.h>
int main()
{
int m,n;
scanf("%d %d",&m,&n);
int i,s=0;
for(i=pow(10,n-1);i<pow(10,n);i++){
if(count(i,m)%m!=0) s++;
}
printf("%d",s);
return 0;
}
int count(int x,int p){
int y=x;
while(x){
if(x%10==p) return y;
x=x/10;
}
return 0;
}总结
如上，为今日小结，题目内容很简单，还望各位算法大佬见谅，莫笑，从今日起，暂定一个小目标，暑假期间每周必发一篇算法博客笔记，争取达成暑期速成计划，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~
