新版C语言NOJ（持续更新中）
引言
第一篇博客，欢迎大佬们批评指正，期待更好的算法和更优化的代码。
本篇内容仅供交流学习，读者因其他用途造成的一切后果与本人无关。
Hello world
#includeint main()
{//注意大小写和空格printf("Hello World");return 0;
} A+B
#includeint main()
{int a,b;scanf("%d %d",&a,&b);printf("%d",a + b);return 0;
} 数据类型大小及范围
#include
#includeint main()
{int a;scanf("%d",&a);//注意数值和输出类型匹配if( a == 1 ) printf("%d,%d,%d",sizeof(char),CHAR_MIN,CHAR_MAX);if( a == 2 ) printf("%d,0,%u",sizeof(unsigned char),UCHAR_MAX);if( a == 3 ) printf("%d,%d,%d",sizeof(short),SHRT_MIN,SHRT_MAX);if( a == 4 ) printf("%d,0,%u",sizeof(unsigned short),USHRT_MAX);if( a == 5 ) printf("%d,%d,%d",sizeof(int),INT_MIN,INT_MAX);if( a == 6 ) printf("%d,0,%u",sizeof(unsigned int),UINT_MAX);if( a == 7 ) printf("%d,%ld,%ld",sizeof(long),LONG_MIN,LONG_MAX);if( a == 8 ) printf("%d,0,%lu",sizeof(unsigned long),ULONG_MAX);if( a == 9 ) printf("%d,%lld,%lld",sizeof(long long),LLONG_MIN,LLONG_MAX);if( a == 10 ) printf("%d,0,%llu",sizeof(unsigned long long),ULLONG_MAX);return 0;
} 平均值
#includeint main()
{//选择范围较大的数据类型long long a,b;scanf("%lld %lld",&a,&b);printf("%lld",(a + b)/2);return 0;
} 进制转换
#includeint main()
{long long a;scanf("%lld",&a);//X为大写printf("%X,%o",a,a);return 0;
} 浮点数输出
#includeint main()
{double a;scanf("%lf",&a);printf("%.6lf,%.2lf,%.8lf",a,a,a);return 0;
} 动态宽度输出
#includeint main()
{long long m,n,a;int w = 0;scanf("%lld %lld",&m,&n);a = m;//获得m的位数while(a != 0){w++;a = a/10;}if(n > w){for(int i = 1;i <= (n - w);i++){printf("0");}printf("%lld",m);}else printf("%lld",m);return 0;
} 计算地球上两点之间的距离
#include
#include#define PI 3.14159265358979323846
#define R 6371int main()
{//latitude纬度 longitude经度double longi1,lati1,longi2,lati2,dlongi,dlati;double a,d;scanf("%lf %lf\n%lf %lf",&lati1,&longi1,&lati2,&longi2);//注意将角度转化为弧度再进行计算longi1 = longi1 * (PI /180.0);lati1 = lati1 * (PI / 180.0);longi2 = longi2 * ( PI /180.0);lati2 = lati2 * (PI / 180.0);dlongi = longi2 - longi1;dlati = lati2 - lati1;a = pow(sin(dlati / 2),2) + cos(lati1) * cos(lati2) * pow(sin(dlongi / 2),2);d = 2 * R * asin(sqrt(a));printf("%.4lfkm",d);return 0;
}
风寒指数
%g表示自动舍去小数后不必要的0，整数则直接输出整数
#include
#includeint main()
{double ws,at,wc;double a,b,c;scanf("%lf %lf",&ws,&at);a = 0.6215 * at;b = 11.37 * pow(ws,0.16);c = 0.3965 * at * pow(ws,0.16);wc = 13.12 + a - b + c;wc = round(wc);printf("%g",wc);return 0;
} 颜色模型转换
#include
#includeint main()
{unsigned int R,G,B;double r,g,b,maxi,mini,d;double H,S,V;scanf("%u %u %u",&R,&G,&B);//应先将R，G，B范围转化为（0，1）//转化关系可上网自行搜索，即/255r = R / 255.0;g = G / 255.0;b = B / 255.0;maxi = g;mini = g;if(r > maxi) maxi = r;if(b > maxi) maxi = b;if(r < mini) mini = r;if(b < mini) mini = b;d = maxi - mini;V = maxi;if(V != 0) S = d / maxi;//注意讨论V是否为0else S = 0;if(d != 0){//注意小数尽量不要直接比较（float不能比较，但double与long double型可以）//可以将两数差值与极小数进行比较，判定是否相等//1e-9表示1*10^-9if(maxi - r < 1e-9){H = (g - b) / d;}if(maxi - g < 1e-9){H = 2 + (b - r) / d;}if(maxi - b < 1e-9){H = 4 + (r - g) / d;}H = H * 60;if(H < 0){H += 360;}}//不要遗漏H可能为0的情况else H = 0;printf("%.4lf,%.4lf%%,%.4lf%%",H,S * 100,V * 100);return 0;
} 方阵
方法一：思路为以0为分割
左边递减输出，右边递增输出
# include int main(void)
{int i,n;scanf("%d",&n);for (i=0; i-1;j--){printf(" %d",j);}for(int g=1;g 方法二：利用绝对值! (思路来自“ 农农绝世无双”）
#include
#includeint main()
{int a;scanf("%d",&a);for(int i =0;i 对称数
此题解法很有意思，是对switch用法很好的诠释。
简单解释一下switch：
我们清楚switch(p)中p为预判定的式子，计算机将自动判断p与case后设定的东西是否相等，但我们需要理解的是case语句只是提供了一个执行switch内语句的接口，这里就涉及到了break的作用。
以此题为例：
若p=0，显然他与case 0相符合，那么这时这个case 0后的语句就将被依次执行，直到遇到了第一个break语句，那么此次switch语句框架结束，立刻退出switch执行 switch外的代码。
若p=6，那则从case 6后开始执行，到第一个break结束并退出switch。
从这篇文章里学习到的：c语言switch中break语句的作用
#includeint main()
{int n,p,bn,r = 0;scanf("%d",&n);bn = n;while(bn > 0){p = bn % 10;switch(p){//0，1，8，6，9才可能构成对称数，3，4，7显然不可能构成对称数//另外此题认为2，5，也无法构成case 0:case 1:case 8:r = r * 10 + p;break;//6，9旋转发生变化，因此单独考虑case 6:r = r * 10 + 9;break;case 9:r = r * 10 + 6;break;default:printf("No");return 0;//r = r * + ；的操作是在进行书的翻转//即最后一位变成第一位，倒数第二位变成第二位，以此类推}bn = bn / 10;}if(n == r) printf("Yes");else printf("No");return 0;
} 乘数模
直接相乘再mod可能会超出数据上限，可分别mod相乘再mod，可自行证明。
#includeint main()
{long long a,b,m;scanf("%lld %lld %lld",&a,&b,&m);printf("%lld",(a % m) * (b % m) % m);return 0;
} 比率
思路为把小数部分乘10^c变为整数后作为分子，再将分母设为10^c进行约分
#include
#includeint main()
{double n,g;long long fz,fm,d,c=0,b=0,x,tfz,tfm;scanf("%lf",&n);int k = 0;g = n;//求出小数位数cwhile(k != g){g *= 10;k = (int)g;c++;}fm =pow(10,c);fz = n * pow(10,c);tfz = fz;tfm = fm;//获得最大公约数x（‘分数的加减乘除法’中提供了另一种更为简单求法）while(tfz % 2 == 0&&tfm % 2 ==0){tfz /= 2;tfm /= 2;b++;}//更相减损术while(tfz != tfm){if(tfz > tfm) tfz -= tfm;else tfm -= tfz;}x = pow(2,b) * tfz;//进行约分fz /= x;fm /= x;printf("%d/%d",fz,fm);return 0;
} 分数的加减乘除法
利用递归求m,n的最大公约数(太强了qwq)
注意三点：
1.考虑结果为1时的输出
2.考虑减法分子为0时的输出
3.考虑减法结果为负的输出
#include
#include//辗转相除法，可自行代数检验
int gcd(int m,int n)
{if(n == 0) return m;else return gcd(n,m % n);
}
int main()
{long a,b,c,d;long m,n;long t;scanf("%ld/%ld\n%ld/%ld",&a,&b,&c,&d);//加法m = a * d + c * b;n = b * d;t = gcd(m,n);m /= t;n /= t;if(m == n) printf("(%ld/%ld)+(%ld/%ld)=1\n",a,b,c,d);else printf("(%ld/%ld)+(%ld/%ld)=%ld/%ld\n",a,b,c,d,m,n);//减法m = a * d - c * b;n = b * d;t = abs(gcd(m,n));//将最大公约数取绝对值保证结果为负数时，输出的正确性m /= t;n /= t;if(m == 0) printf("(%ld/%ld)-(%ld/%ld)=0\n",a,b,c,d);else if(m == n) printf("(%ld/%ld)-(%ld/%ld)=1\n",a,b,c,d);else printf("(%ld/%ld)-(%ld/%ld)=%ld/%ld\n",a,b,c,d,m,n);//乘法m = a * c;n = b * d;if(m == n) printf("(%ld/%ld)*(%ld/%ld)=1\n",a,b,c,d);else{t = gcd(m,n);m /= t;n /= t;printf("(%ld/%ld)*(%ld/%ld)=%ld/%ld\n",a,b,c,d,m,n);}//除法m = a * d;n = b * c;if(m == n) printf("(%ld/%ld)/(%ld/%ld)=1\n",a,b,c,d);else{t = gcd(m,n);m /= t;n /= t;printf("(%ld/%ld)/(%ld/%ld)=%ld/%ld\n",a,b,c,d,m,n);}return 0;
} 组合数
#includeint main()
{int n,c;scanf("%d",&n);for(int i=0;i<10;i++){for(int j=0;j<10;j++){for(int g=0;g<10;g++){for(int w=0;w<10;w++){if((i+j+g+w)==n) c++;}}}}printf("%d",c);return 0;
} 级数和
#includeint main()
{int n;double t,sum = 0;scanf("%d",&n);for(int i=1;i 倍数和
方法一：
注意去重，及既能被3整除又能被5整除的数（代码较长，速度较快）
#include//获得小于n的所有自然数中3和5的倍数之和
unsigned int sum(unsigned int a)
{long long h = 0,i=0,j=0,g=0;while((3*i) 方法二：
不用去重（代码较短，速度较长）
#includeint main()
{long long t;scanf("%lld",&t);unsigned int a[t];for(int i=0;i 幂数模
此题学到很多新东西，初步涉及了一点算法问题
为了避免对a全部幂运算再取模超出数值范围，采取快速模幂运算，用到了二进制指数法和分治算法的思想
以13为例进行简单的说明：
13的二进制表示为1101，正常情况下如果要计算a^13，需进行13次乘法，为了减少计算时间，我们对算法进行优化
13=1×2^3+1×2^2+0×2^1+1×2^0，假设最终结果为r，不难发现，当二进制位数为0时，我们可以先不将r乘2，而是让a自乘（即a=a×a，相当于a^2^n，n每次加1），同时进行向右按位位移1位的操作（即>>=1），那么若右移后的最低位为1，我们便将r乘此时的a，这样就能使得运算次数减少。
详细解释一下，欲求5^13
while(b != 0){//b&1：用来判断当前b的二进制最低位是否为1//若为1，则累乘if(b & 1) t = t * a;//否则，只是将a自乘，并不与最终结果t累乘a = (a * a);//将b向右按位位移1位b >>= 1;}
/*初始b=13=（1101）B=2^3+2^2+2^0=8+4+1，a=5，t=1
第一次
b&1=0001 为真
if条件成立 t=t*5=1*5
a=a*a=5^2
b=110第二次
b&1=000 为假
if不成立 t=1*5不变
a=a*a=5^2*5^2=5^4
b=11第三次
b&1=01 为真
if条件成立 t=t*a=1*5*5^4
a=a*a=5^4*5^4=5^8
b=1第四次
b&1=1 为真
if条件成立 t=t*a=1*5*5^4*5^8=5^（2^0+2^2+2^3）*/感觉本质就在于把指数分解为二进制
具体操作是通过b&1判断和b>>=1，使得a自乘后的指数和二进制表示中为1的位对应的数相一致
本题答案
#includeint main()
{long long a,b,m,t = 1;scanf("%lld %lld %lld",&a,&b,&m);while(b != 0){//b&1：用来判断当前b的二进制最低位是否为1//若为1，则累乘if(b & 1) t = (t * a) % m;//否则，只是将a自乘，并不与最终结果t累乘a = (a * a) % m;//将b向右按位位移1位b >>= 1;}printf("%lld",t);return 0;
} 操作数
另一种获得位数的巧妙方法
即 位数n=(int)log10(x) + 1
#include//获得各个位数之和
long long wsum(long long x)
{long long h = 0;while(x!=0){h = h + (x % 10);x = x / 10;}return h;
}int main()
{long long n,i=0;scanf("%lld",&n);while(n>0){n = n - wsum(n);i++;}printf("%lld",i);return 0;
} 俄罗斯农夫乘法
#includeint main()
{long long m,n,sum = 0;scanf("%lld %lld",&m,&n);while(m != 0){printf("%lld %lld\n",m,n);if((m%2) != 0) sum = sum + n;n = n * 2;m = m / 2;}printf("%lld",sum);return 0;
} 余数和
#includeint main()
{int n,k,sum = 0;scanf("%d %d",&n,&k);while(n != 0){sum = sum + k % n;n--;}printf("%d",sum);return 0;
} 方案数
我们先进行数学上的运算(x = 1,2,3,...)
两个连续正整数的和：x x+1 = 2x+1
三个连续正整数的和：x x+1 x+2 = 3x+3
四个连续正整数的和：x x+1 x+2 x+3= 4x+6
......
i个连续正整数的和：x x+1 ... x+i-2 x+i-1 =i*x+i*(i-1)/2
不难发现当(n-(i*(i-1))/2)%i == 0时，方案成立，则方案数c加1
另外需要注意的是，while循环需要停止条件t
#includeint main()
{int n,i = 1,c = 0,t;scanf("%d",&n);do{if((n-(i*(i-1))/2)%i == 0) c++;i++;t = (i*(i-1))/2;}while(t 竖式乘法
#include//获得位数（考虑x可能为0的情况）
int ws(int x)
{int n=0;if(x != 0){while(x>0){x /= 10;n++;}}else n = 1;return n;
}int main()
{int a,b,t,tb,wb,c,ca,cb=0;scanf("%d %d",&a,&b);int m[b+1];tb = b;t = a * b;//获得最终结果位数c = ws(t) + 1;//获得a的位数ca = ws(a);//获得b的位数及每一位数while(tb>0){wb = tb % 10;tb /= 10;++cb;m[cb] = wb;}//输出前三行for(int i = 1;i <= c - ca;i++) printf(" ");printf("%d\n",a);printf("x");for(int i = 2;i <= c - cb;i++) printf(" ");printf("%d\n",b);for(int i = 1;i <= c;i++) printf("-");printf("\n");//输出运算过程for(int i = 1;i <= cb;i++){int tr,wr;tr = a * m[i];wr = ws(tr);if(i != cb){for(int j = 1;j <= (c - wr - i + 1);j++) printf(" ");printf("%d",tr);for(int j = 1;j <= i - 1;j++) printf(" ");printf("\n");}else{printf("+%d",tr);for(int j = 1;j <= i - 1;j++) printf(" ");printf("\n");}}for(int i = 1;i <= c;i++) printf("-");//输出最终结果printf("\n %d",t);return 0;
} 好数字
数学上的排列组合
0~9中偶数有0，2，4，6，8共五个，素数有1，3，5，7共四个
同时为了避免累乘过程超出数据范围，我们每次乘4或5时都同时%mod
另：
使用mod进行取模的原因防止计算时出现溢出，相加时防止int类型溢出，相乘防止long类型溢出
同时当数值比mod小的时候，取余数，对结果不会有影响。
#includeint main()
{long long n,r=1,mod=1e9+7;scanf("%lld",&n);for(long long i=1;i<=n;++i){if(i%2 != 0) r = (r * 5) % mod;else r = (r * 4) % mod;}printf("%lld",r);return 0;
} 查找数列
为了减少循环次数，我们从a = sqrt(n)开始
因为：
√n*(√n+1)/2 = (n+√n）/ 2 < n
#include
#includeint main()
{double n;long long a;scanf("%lf",&n);a = sqrt(n);while(((a+1)*(a+2)/2) 最大数字
#includeint main()
{unsigned int n;scanf("%u",&n);for(unsigned int i=n;i>0;--i){unsigned int t=i,a,b,c=1;while(t>9){a = t % 10;t /= 10;b = t % 10;if(b < a) c = 1;else c = 0;}if(c){printf("%u",i);break;}}return 0;
} 阶乘倍数
找到正确写法啦
终于不超时了！！！
#include
#includeint main()
{long long k,s,y,a=1,c=1;scanf("%lld",&k);s = sqrt(k);for(long long i=2;i<=s;++i){if(k%i==0){k /= i;y = i;}if(k==1){printf("%lld",i);return 0;}}do{a=k*c;c++;}while(a<=y);printf("%lld",a);return 0;
} 倒水
分两种情况
一、先倒满小杯
二、先倒满大杯
我们参照题目给出例子写出详细过程后，仔细思考发现，下一步的最优操作是由本步两杯水的情况决定的，因此我们分别考虑不同的情况（存在规律），并给出下一步的运算方式
#includeint firtype(int m,int n,int d)
{int a=m,b=0,i=1;while(1){if(a!=0&&b==0){b=a;a=0;i++;if(a==d||b==d) break;}if(a==0&&b!=0){a=m;i++;if(a==d||b==d) break;}if(a==m&&b!=0){b=b+a;if(b>n){a=b-n;b=n;}else a=0;i++;if(a==d||b==d) break;}if(a!=0&&b==n){b=0;i++;if(a==d||b==d) break;}}return i;
}int sectype(int m,int n,int d)
{int a=0,b=n,i=1;while(1){if(b==n){b=b-(m-a);a=m;i++;if(a==d||b==d) break;}if(a==m&&b!=0){a=0;i++;if(a==d||b==d) break;}if(a==0&&b!=0){a=b;b=0;i++;if(a==d||b==d) break;}if(a!=0&&b==0){b=n;i++;if(a==d||b==d) break;}}return i;
}int mini(int a,int b)
{return a 毕达哥拉斯三元组
说在前面：
调试了好久，最后发现时数据类型定义小了，把long long换成unsighed long long就顺利AC了
思路：
主要是条件的预处理：
1.c的大致范围
由a+b+c=n，a
由c^2=a^2+b^2<(a+b)^2,我们可以得到c 2.a的大致范围 由a 由a 取min{c/√2 , (n-c)/2}#include本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
