2019期末
癌细胞体积
#include <stdio.h>
double r;
int main(void) {
scanf("%lf",&r);
printf("%.3lf",4.0*3.14159*r*r*r/3);
return 0;
}
寻找三角形
#include <stdio.h>
/* C语言初始模板程序 */
int main(void) {
int a,b,n,ans=0;scanf("%d%d%d",&a,&b,&n);
if(a<b) {int tmp=a;a=b;b=tmp;}
for(int i=1;i<=n;++i)
{
int x;scanf("%d",&x);
if(a-b<x&&x<a+b) ++ans;
}
printf("%d\n",ans);
return 0;
}
凑数
#include <stdio.h>
int a[200];
int main(void) {
int n,k;scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
scanf("%d",&k);
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
{
if(a[i]+a[j]==k)
{
printf("%d %d\n",i-1,j-1);
return 0;
}
}
printf("-1 -1\n");
return 0;
}
考虑一下如果不是选两个数而是m个数应该怎么做？
美丽编号
#include <stdio.h>
int f(int x)
{
if(x==1) return 1;
if(x%2==0) return f(x/2);
if(x%3==0) return f(x/3);
if(x%5==0) return f(x/5);
return 0;
}
int main(void) {
int n,ans=0;scanf("%d",&n);
for(int i=1;i<=n;++i)
{
int x;scanf("%d",&x);
if(f(x)) ++ans;
}
printf("%d\n",ans);
return 0;
}
这里采用递归的写法每次递归除掉一个因子，原理是一个数是否美丽等价于他除以2，3，5的余数是否美丽。
最后一块石头
#include <stdio.h>
int a[200];
int main(void) {
int n,now=0;scanf("%d",&n);
for(int i=1;i<=n;++i)
{
int x;scanf("%d",&x);
if(now==0) now=x;
else now=now>x?now-x:x-now;
}
printf("%d\n",now);
return 0;
}
相似的名字
#include <stdio.h>
#include <string.h>
char a[400],b[400];
int n;
int main(void) {
scanf("%d\n",&n);
for(int m=1;m<=n;++m){
scanf("%s%s",a,b);int x=0;
int l1=strlen(a),l2=strlen(b);
if(l1!=l2)
{printf("NO\n");continue;}
for(int i=0;i<=l1-2;++i)
for(int j=i+1;j<l1;++j){
if(a[i]>a[j])
{char tmp=a[i];a[i]=a[j];a[j]=tmp;}
if(b[i]>b[j])
{char tmp=b[i];b[i]=b[j];b[j]=tmp;}}
for(int i=0;i<l1;++i)
if(a[i]!=b[i]) x=1;
if(x==0) printf("YES\n");
else printf("NO\n");
}
return 0;
}
排序，然后逐个比较
新年晚会
#include <stdio.h>
int a[2000],b[2000],c[2000];
int main(void) {
int n;scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d,%d",&a[i],&b[i]);c[i]=i;
}
for(int i=1;i<=n;++i)
{
for(int j=i+1;j<=n;++j)
{
if(a[i]>a[j]||(a[i]==a[j]&&b[i]>b[j]))
{
int tmp=a[i];a[i]=a[j];a[j]=tmp;
tmp=b[i];b[i]=b[j];b[j]=tmp;
tmp=c[i];c[i]=c[j];c[j]=tmp;
}
}
}
for(int i=1;i<=n;++i) printf("%d\n",c[i]);
return 0;
}
最长连号
#include <stdio.h>
int n,ans,a[20000],f[20000];
int main(void) {
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d\n",&a[i]);
if(a[i]==a[i-1]+1&&a[i]>1)
f[i]=f[i-1]+1;
if(ans<f[i]) ans=f[i];
}
printf("%d\n",ans+1);
return 0;
}
咱就说这道题是不是也算dp呢（逃
田忌赛马
#include <stdio.h>
int a[200],b[200];
int n,ans;
int main(void) {
scanf("%d",&n);int cnt=n;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
scanf("%d",&b[i]);
for(int i=n;i>=1;--i)
{
if(a[cnt]<b[i])
{
++ans;--cnt;
}
}
if(ans>n/2) printf("yes\n");
else printf("no\n");
return 0;
}
贪心算法，从头挨个比较
括号闭合问题
#include <stdio.h>
#include <string.h>
char c[2000],q[2000];
int n,cnt;
int main(void) {
gets(c);n=strlen(c);
if(c[0]!='('&&c[0]!='['&&c[0]!='{')
{
printf("no\n");
return 0;
}q[0]=c[0];
for(int i=1;i<n;++i)
{
if(c[i]-q[cnt]<=2&&c[i]-q[cnt]>0) {--cnt;continue;}
if(c[i]=='}'||c[i]==']'||c[i]==')') {printf("no\n");return 0;}
q[++cnt]=c[i];
}
if(cnt==-1) printf("yes\n");
else printf("no\n");
return 0;
}
括号匹配经典题，考察队列的应用，左括号入队，右括号匹配，匹配正确就让相应的左括号出队，详见代码
护林员盖房子
方法一：就本题的数据范围来讲，完全可以直接爆搜，但是可能代码量略大(?)
方法二：记录每个空地左边的空地个数，然后对于每一个格子扫描其在左下方的最大矩形，只需要\(n^3\)即可解决。
#include <stdio.h>
#include <string.h>
int a[100][100],b[100][100];
int main(void) {
int m,n,ans=0;scanf("%d%d",&m,&n);
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j){
scanf("%d",&a[i][j]);
if(a[i][j]==0)
b[i][j]=b[i][j-1]+1;
}
for(int j=1;j<=n;++j)
for(int k=1;k<=m;++k) {
int minx=1000000000,now=0;
for(int i=k;i<=m;++i) {
if(a[i][j]==1){
now=0;minx=1000000000;
continue;}
++now;
if(minx>b[i][j]) minx=b[i][j];
if(ans<minx*now) ans=minx*now;
}
}
printf("%d\n",ans);
return 0;
}