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;
} 

---

明天着重复习后三道题