正睿2018暑期集训CD班附加赛Round4暨贺爸探底纪念赛123民间题解
BY QYJ
T1:不知道什么鬼~
std:
#include<bits/stdc++.h>
using namespace std;
int t;
double x;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%lf",&x);
printf("%.10lf\n",(double)1/(1-x));
}
return 0;
}T2:大模拟
将数字分为4段（歪果仁都是三位一段的）
每一段内进行操作。
预处理出1~9，10~19，10，20，30，40，50，60，70，80，90，100
即可操作
std:
#include<bits/stdc++.h>
using namespace std;
int t;
string s[11]={"zero","one","two","three","four","five","six","seven","eight","nine"};
string p[11]={"ten","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"};
string Q="hundred";
string l[11]={"ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"};
void put(string s)
{
for(int i=0;i<s.size();i++)
printf("%c",s[i]);
return;
}
void print(int x)
{
if(x==0) return;
else if(x<10)
{
put(s[x]);
printf(" ");
return;
}
else if(x<20)
{
put(l[x-10]);
printf(" ");
return;
}
else if(x<100)
{
put(p[x/10-1]);
if(x%10!=0)
{
printf("-");
put(s[x%10]);
}
printf(" ");
return;
}
else if(x%100==0)
{
put(s[x/100]);
printf(" ");
put(Q);
printf(" ");
return;
}
else
{
put(s[x/100]);
printf(" ");
put(Q);
printf(" and ");
if((x/10)%10-1>0)
{
put(p[(x/10)%10-1]);
if(x%10!=0)
{
printf("-");
}
}
if(x%10!=0)
{
put(s[x%10]);
}
printf(" ");
return;
}
}
int main()
{
//外文数字：3位一断
//x and y-z xxx
//例如 one hundred and twenty-three million
//分3个档做：
//million
//thousand
//one
//打表暴力从0~999
//freopen("大样例-送温暖.out","w",stdout);
scanf("%d",&t);
while(t--)
{
int x;
scanf("%d",&x);
if(x==0)
{
printf("zero\n");
continue;
}
if(x>999999999)
{
put(s[x/1000000000]);
printf(" billion ");
}
if((x/1000000)%1000!=0)
{
print((x/1000000)%1000);
if(x>=1000000) printf("million ");
}
if((x/1000)%1000!=0)
{
print((x/1000)%1000);
if(x>=1000) printf("thousand ");
}
print(x%1000);
printf("\n");
}
return 0;
}T3:
13pts:
这题明显可以dp。
设f[i]表示在第i个点时最小消耗了几块钱。
dfs转移。
33~100pts:
将它看成有向图。
前后两个点连一条边。
u->v的边权即为v
haha
记得加上起始位置的点权！
你寇以用SPFA加上玄学优化
当然......
100pts:
dijstra+堆优化 才是正义的！
