校赛个人赛第六，七场总结
这两场比赛体现了英文水平的重要性
第六场的题目超长，用词还诡异，话了很长时间才看懂
这两场题目都比较有难度，第六场我只出了2题
A Grey Area
A题是很诡异的统计，是一道纯模拟就能过的题，其他的不多说了
代码：
#include<iostream>
using namespace std;
int pe[20];
int main()
{
int n,w;
while(cin>>n>>w, n || w)
{
int value;
int peNum = 0;
int Max = 0;
int valueMax = 0;
memset(pe,0,sizeof(pe));
while(n --)
{
scanf("%d",&value);
while(value >= Max)
{
peNum ++;
Max = peNum * w;
}
pe[value / w] ++;
if(pe[value / w] > valueMax)
valueMax = pe[value / w];
}
double output = 0.01;
for(int i = 0 ; i < peNum ; i ++)
output += ((double)pe[i] / (double)valueMax)
* ((double)(peNum - i - 1) / (double)(peNum - 1));
printf("%lf\n",output);
}
return 0;
}
B Expected Allowance
B题和A题类似，也是纯暴力
代码：
#include<iostream>
#include<cmath>
using namespace std;
long value[10000];
void cal(long now,int pos,int n,int m)
{
for(int i = 1 ; i <= m ; i ++)
if(pos == n)
value[now + i] ++;
else
cal(now + i,pos + 1,n,m);
}
int main()
{
long m,n,k;
while(scanf("%ld %ld %ld",&n,&m,&k), n || m || k )
{
memset(value,0,sizeof(value));
cal(0,1,n,m);
double output = 0.0;
double fm = pow((double)m,(double)n);
for(long i = n ; i <= n * m ; i ++)
if(i - k <= 0)
output += (double)value[i] / fm;
else
output += (double)value[i] / fm * (double)(i - k);
printf("%.8lf\n",output);
}
return 0;
}
第七场
第七场很多题目都有想法，可是很多都没能写出来
同样B和E是水题，直接暴力能过，不过就是要有耐性
B要注意一下判断的优先级.
代码如下：
#include<iostream>
#include<cstring>
using namespace std;
double bank[10][10000];
char cmd[20];
int isExist[10][10000];
int main()
{
int n = 1;
//freopen("b.in","r",stdin);
while(scanf("%d",&n),n)
{
memset(bank,0,sizeof(bank));
memset(isExist,0,sizeof(isExist));
while(n --)
{
int tmpInt1,tmpInt2;
double tmpMoney;
scanf("%d/%d %lf",&tmpInt1,&tmpInt2,&tmpMoney);
isExist[tmpInt2][tmpInt1] = 1;
bank[tmpInt2][tmpInt1] = tmpMoney;
}
while(scanf("%s",cmd) , strcmp(cmd,"end"))
{
if(!strcmp(cmd,"withdraw"))
{
int tmpInt1,tmpInt2;
double tmpMoney;
scanf("%d/%d %lf",&tmpInt1,&tmpInt2,&tmpMoney);
printf("withdraw %.2lf: ",tmpMoney);
if(isExist[tmpInt2][tmpInt1])
{
if(bank[tmpInt2][tmpInt1] < tmpMoney)
printf("insufficient funds\n");
else
{
printf("ok\n");
bank[tmpInt2][tmpInt1] -= tmpMoney;
}
}
else
printf("no such account\n");
}
else if(!strcmp(cmd,"deposit"))
{
int tmpInt1,tmpInt2;
double tmpMoney;
scanf("%d/%d %lf",&tmpInt1,&tmpInt2,&tmpMoney);
printf("deposit %.2lf: ",tmpMoney);
if(isExist[tmpInt2][tmpInt1])
{
printf("ok\n");
bank[tmpInt2][tmpInt1] += tmpMoney;
}
else
printf("no such account\n");
}
else if(!strcmp(cmd,"create"))
{
int tmpInt1,tmpInt2;
scanf("%d/%d",&tmpInt1,&tmpInt2);
printf("create: ");
if(isExist[tmpInt2][tmpInt1])
printf("already exists\n");
else
{
printf("ok\n");
isExist[tmpInt2][tmpInt1] = 1;
bank[tmpInt2][tmpInt1] = 0;
}
}
else if(!strcmp(cmd,"transfer"))
{
int tmpInt1,tmpInt2,tmpInt3,tmpInt4;
double tmpMoney;
scanf("%d/%d %d/%d %lf",&tmpInt1,&tmpInt2,&tmpInt3,&tmpInt4,&tmpMoney);
printf("transfer %.2lf: ",tmpMoney);
if(isExist[tmpInt2][tmpInt1] && isExist[tmpInt4][tmpInt3])
{
if(tmpInt2 == tmpInt4 && tmpInt1 == tmpInt3)
printf("same account\n");
else if(bank[tmpInt2][tmpInt1] < tmpMoney)
printf("insufficient funds\n");
else
{
if(tmpInt2 == tmpInt4)
printf("ok\n");
else
printf("interbank\n");
bank[tmpInt2][tmpInt1] -= tmpMoney;
bank[tmpInt4][tmpInt3] += tmpMoney;
}
}
else
printf("no such account\n");
}
}
printf("end\n\n");
}
printf("goodbye");
return 0;
}
E Stock Exchange
我这题TLE一次，原因是很郁闷的忘了把freopen函数给注释掉 -_-!!
我的代码如下:
#include<iostream>
#include<cstring>
using namespace std;
char Issuer[12];
struct Member
{
char name[30];
double money;
char type[10];
};
Member mem[1001];
int main()
{
int n;
//freopen("e.txt","r",stdin);
while(scanf("%d %s",&n,Issuer), strcmp(Issuer,"END") || n)
{
int i,j;
for(i = 0 ; i < n ; i ++)
scanf("%s %s %lf",mem[i].name,mem[i].type,&mem[i].money);
printf("%s\n",Issuer);
int num = 0;
for(i = 0 ; i < n ; i ++)
{
num = 0;
printf("%s:",mem[i].name);
for(j = 0 ; j < n ; j ++)
{
if(mem[i].type[0] == mem[j].type[0])
continue;
if(mem[i].type[0] == 'b'
&& mem[j].money <= mem[i].money)
printf(" %s",mem[j].name),num ++;
else if(mem[i].type[0] == 's'
&& mem[j].money >= mem[i].money)
printf(" %s",mem[j].name),num ++;
}
if(num)
putchar('\n');
else
printf(" NO-ONE\n");
}
}
return 0;
}
C题很烦，但是我觉得可以通过列出各种特殊情况出来死套。太烦了所以没写
D题我觉得可以通过DP+Hash来完成，按最长子序列的反向DP（不过我觉得等我想出来DP方案时间也到了，就没写）
F题我没什么思路
G题我认为可以DP，主要是算出三个子段的最小值，且三个子段的长度和为k-1，但是DP的话要写24种分支，我觉得这个方法并不好，所以也没写
以上各题希望大牛能分享思路，指点一二。