A. Maximum in Table
题意：给定一个表格，它的第一行全为1，第一列全为1，另外的数满足a[i][j]=a[i-1][j]+a[i][j-1]，求这个表格中的最大的数
a[n][n]即为最大的数
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[12][12],n;
int main()
{
int i,j,max;
scanf("%d",&n);
memset(a,0,sizeof(a));
for(j=1;j<=n;j++)
a[1][j]=1;
for(i=1;i<=n;i++)
a[i][1]=1;
for(i=2;i<=n;i++)
for(j=2;j<=n;j++)
{
a[i][j]=a[i-1][j]+a[i][j-1];
}
printf("%d
",a[n][n]);
}
B. Painting Pebbles
题意：给定n堆卵石，以及k种颜色，现在给它们上色，要求任意两堆石头的颜色为c的石头个数相差小于等于1
首先将这n堆石头排序，如果k<max-min，那么肯定不能满足 如果k>max-min,那么一定是每一堆石头重复的颜色越少，越能够满足这个条件，所以对每一堆石头，就从第一种颜色开始涂色，依次涂上1 2 3 ---如果石头的个数超过了颜色的种类，则当前涂到第j个石头，用j对k取余，即为该石头的颜色。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int b[305][305];
struct node
{
int num;
int order;
} a[305];
bool cmp(node n1,node n2)
{
return n1.num<n2.num;
}
bool cmp0(node n1,node n2)
{
return n1.order<n2.order;
}
int main()
{
int n,k,i,j,ans;
scanf("%d %d",&n,&k);
memset(b,0,sizeof(b));
for(i=1;i<=n;i++)
{
scanf("%d",&a[i].num);
a[i].order=i;
}
sort(a+1,a+1+n,cmp);
if(k<a[n].num-a[1].num)
printf("NO
");
else
{
for(i=1;i<=n;i++)
{
for(j=1;j<=a[i].num;j++)
{
b[a[i].order][j]=j%k;
if(j%k==0)
b[a[i].order][j]=k;
}
}
printf("YES
");
sort(a+1,a+n+1,cmp0);
for(i=1;i<=n;i++)
{
for(j=1;j<=a[i].num;j++)
printf("%d ",b[a[i].order][j]);
printf("
");
}
}
}
E. Pretty Song
题意：给出一串字符串，规定如果字母是A,E,I,O,U,Y，它的值为1，否则其值为0， w=该子串中元音字母的个数（即有多少个1）/ 该子串的长度
我们要计算的就是所有w的和
下面的思路是借鉴别人的思路---
可以令sum[i]为以第i个字母结尾有多少个元音字母，
当子串的长度为1的时候，每个字符都被计算了一次 tmp+=sum[len]-sum[1]
当子串的长度为2的时候，每个字符除了第一个字符和最后一个字符计算一次，其余的都被计算了两次，所以tmp+=sum[len-1]-sum[2]
以样例 Y I S V O W E L为例
长度为1的子串 Y,I,S,V,O,W,E,L 每个字符都被计算了1次 tmp+=sum[len]-sum[0];
长度为2的子串 YI,IS,SV,VO,OW,WE,EL 所以可以看到除了首字母和最后一个字母都被计算了两次--
剩下的就可以以此类推----
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long sum[1000010],l,r,len,tmp;
char s[1000010];
int main()
{
int i;
double ans=0;
scanf("%s",s+1);
len=strlen(s+1);
memset(sum,0,sizeof(sum));
for(i=1;i<=len;i++)
sum[i]=sum[i-1]+1*(s[i]=='A'||s[i]=='E'||s[i]=='I'||s[i]=='O'||s[i]=='U'||s[i]=='Y');
l=0;
r=len;
for(i=1;i<=len;i++)
{
tmp+=sum[r]-sum[l];
ans+=tmp*1.0/i;
r--;l++;
}
printf("%.7lf
",ans);
}