本文主要是介绍ACM实训冲刺第十八天，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
统计元音
代码
需要注意的是getchar()和gets(s)
#include<stdio.h>
#include<string.h>
int main(){//测试实例个数int n;scanf("%d",&n) ;char s[100];getchar();while(n--){gets(s);int cnta=0,cnte=0,cnti=0,cnto=0,cntu=0;for(int j=0;j<strlen(s);j++){if(s[j]=='a')cnta++;else if(s[j]=='e')cnte++;else if(s[j]=='i')cnti++;else if(s[j]=='o')cnto++;else if(s[j]=='u')cntu++;}printf("a:%d\n",cnta);printf("e:%d\n",cnte);printf("i:%d\n",cnti);printf("o:%d\n",cnto);printf("u:%d\n",cntu);}return 0;
}Let the Balloon Rise
代码
strcmp(str[i],str[j])需要注意
#include<stdio.h>
#include<string.h>
int main(){int n;char str[1001] [20];int cnt[1001];while(scanf("%d",&n)&&n!=0){for(int i=0;i<n;i++){scanf("%s",str[i]);}for(int i=0;i<n;i++) {cnt[i] =0;}//累加出现字符次数 for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(strcmp(str[i],str[j])==0){cnt[i]++;}}}//找到最大值 int max=0;int k=0;for(int i=0;i<n;i++) {if(cnt[i]>max){max=cnt[i];k=i;}}printf("%s\n",str[k]);}return 0;
}0-1 Knapsack Problem
代码
注意转换方程
#include<stdio.h>
int main(){int n,m;scanf("%d %d",&n,&m);int dp[10001]for(int i=0;i<=m;i++){dp[i]=0;}for(int i=0;i<n;i++){int w,d;scanf("%d %d",&w,&d);for(int j=m;j>=w;j--){if(dp[j-w]+d>dp[j])dp[j]=dp[j-w]+d;} }printf("%d\n",dp[m]);return 0;
}Election Time
奶牛这道题有点难，暂时先放弃，明天再记
代码
#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{int a,b,num;
} s[50010];
int cmpa(node a, node b)
{if (a.a == b.a) return a.b > b.b;return a.a > b.a;
}
int cmpb(node a, node b)
{if (a.b == b.b) return a.a > b.a;return a.b > b.b;
}
int main()
{int i,n,k;while (scanf("%d%d", &n, &k) != EOF){for (i = 0; i < n; ++i){scanf("%d%d", &s[i].a, &s[i].b);s[i].num = i + 1;}sort(s, s + n, cmpa);sort(s, s + k, cmpb);printf("%d\n", s[0].num);}return 0;
}Drying
代码
二分查找需要记住
#include<stdio.h>
#include<iostream>
using namespace std;
int main(){int n,k;scanf("%d",&n);int a[n];int ma=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);ma=max(ma,a[i]);}scanf("%d",&k);if(k==0){printf("%d\n",ma);return 0;}int l=0,r=ma,m;while(r>l){m=(l+r)/2;int sum=0;for(int i=0;i<n;i++){if(a[i]>m){sum=(a[i]-m)/(k-1)+((a[i]-m)%(k-1)!=0);}}if(sum>m){l=m+l;}else{r=m;}}printf("%d\n",l);return 0;
}N皇后问题
代码
深度算法这里也需要额外花时间记忆
#include<stdio.h>
#include<math.h>
int rank[20];
bool vis[20];
int n,cnt=0;
void dfs(int pos){if(pos==n+1){//递归边界条件 cnt++;return;}for(int i=1;i<=n;i++){//枚举每行 if(vis[i]==false){bool flag=true;for(int j=1;j<pos;j++){//枚举pos之前的皇后 if(abs(pos-j)==abs(i-rank[j])){flag=false;break;}}if(flag){rank[pos]=i;//pos列在i行 vis[i]=true;dfs(pos+1); vis[i]=false;}}}
}
int main(){scanf("%d",&n);dfs(1);printf("%d",cnt);return 0;
} 明天着重复习后三道题
这篇关于ACM实训冲刺第十八天的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
