概述
第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京）
- F题
- 题面
- 思路
- 源码
- H题
- 题面
- 思路
- 源码
F题
tag:数学 公式推导 二分 三分
题面
题目描述
Kotori is practicing making fireworks for the upcoming hanabi taikai1. It takes her nn minutes to make a single firework, and as she is not really proficient in making fireworks, each firework only has a probability of p×10−4 to be perfect.
After she finishes making a firework, she can just start making the next firework, or take m minutes to light all the remaining fireworks finished before. If there is at least one perfect firework among the lit ones, she will be happy and go to rest. Otherwise, she will continue practicing. Can you tell her the minimum expected practicing time before she goes to rest if she takes the optimal strategy?
Notice that no matter how many fireworks remain, it always takes mm minutes to light them all.
(1Hanabi taikai: Romaji of the Japanese word “花火大會”, which means the firework… err… party?)
输入
There are multiple test cases. The first line of the input contains an integer T (1≤T≤104 ) indicating the number of test cases. For each test case:The first and only line contains three integers n, m and p (1≤n,m≤109,1≤p≤104).
输出
For each test case, output one line containing one number indicating the minimum expected practicing time.
Your answer will be considered correct if and only if the absolute or relative error does not exceed10−4.
样例输入
3
1 1 5000
1 1 1
1 2 10000
样例输出
4.0000000000
10141.5852891136
3.0000000000
思路
求期望，进行公式推导，设制作x（x为整数）个烟花后进行点燃，推导出关于x的期望公式。
当可求导且导数比较简单时，可采取令导数=0，二分的方式（小数的二分，用整数二分会由于精度等原因出错）进行求解，带入期望公式可得最小期望。
通解是采取三分的方法：三分是专门用于求解函数极值的一种方法（具体算法见代码）。
公式推导如下：
源码
//二分代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(int argc, char** argv) {
ll t,n,m,pp,l,r,temp;
double p,px,ans,ans1,ans2,ans3,lnp,ex,ex1,mid;
scanf("%lld",&t);
while(t--){
scanf("%lld%lld%lld",&n,&m,&pp);
if(pp==10000) {ans=n+m;printf("%.6fn",ans);continue;}
p=1-pp/10000.0;
lnp=log(p);
ans=(n+m)/(1-p);
if(n*(1-p)+p*lnp*(n+m)>=0) {
printf("%.6fn",ans);continue;
}
l=1;r=1000000000;
while(true){
mid=(l+r)/2.0;
ex=n*(1-pow(p,mid))+pow(p,mid)*lnp*(n*mid+m);
ex1=n*(1-pow(p,mid+1))+pow(p,mid+1)*lnp*(n*mid+m+n);
if(ex<=0 && ex1>=0) break;
if(ex>0) r=mid;
else l=mid;
}
temp=(int)mid;
ans1=(n*temp+m)/(1-pow(p,temp));
ans2=(n*temp+n+m)/(1-pow(p,temp+1));
if(ans1<ans) ans=ans1;if(ans2<ans) ans=ans2;
printf("%.6fn",ans);
}
return 0;
}
//三分代码
//三分法求函数极值
#include <bits/stdc++.h>
using namespace std;
double p;
int n,m;
double f(int k)//函数 ，k为自变量
{
return ((double)k * n + m) / (1.0 - pow(p, k));
}
int main()
{
int t,pp,l,r;
double ans;
scanf("%d", &t);
while (t--)
{
scanf("%d%d%d", &n, &m, &pp);
if(pp==1e4) {
ans=n+m/1.0;
printf("%.6f",ans);
continue;
}
p = 1.0-pp / 10000.0;
l=1;r=1e9;
ans=min(f(l),f(r));
while(l+2<r){
int m1=l+(r-l)/3;
int m2=l+(r-l)/3*2;
double ans1=f(m1),ans2=f(m2);
if(ans1>=ans2) l=m1;
else r=m2;
}
for(int i=l;i<=r;i++) ans=min(ans,f(i));
printf("%.6fn", ans);
}
return 0;
}
H题
tag:思维 深搜 打表
题面
题目描述
A vertex-colored rectangle is a rectangle whose four vertices are all painted with colors. For a vertex-colored rectangle, it’s harmonious if and only if we can find two adjacent vertices with the same color, while the other two vertices also have the same color with each other.
For example,
is not (same number for same color, and different numbers for different colors).
For each point in {(x,y)∣1≤x≤n,1≤y≤m,x,y∈Z}, where Z is the set of all integers, Kotori wants to paint it into one of the three colors: red, blue, yellow. She wonders the number of different ways to color them so that there exists at least one harmonious rectangle formed by the points, whose edges are all parallel to the xx- or yy-axis. That is to say, there exists1≤x1 <x2 ≤n and1≤y1<y2 ≤m such that
or
where color(x,y) is the color of point (x,y).
Two coloring plans are considered different if there exists a point having different colors in the two coloring plans.
输入
There are multiple test cases. The first line of the input contains an integer T (1≤T≤104 ) indicating the number of test cases. For each test case:
The first and only line contains three integers n, m(1≤n,m≤2×103).
输出
For each test case output one line containing one integer indicating the number of different ways of coloring modulo (109 + 7).
样例输入
3
1 4
2 2
3 3
样例输出
0
15
16485
思路
题意为：不能找到任意两行或两列的2*2矩阵平行。以行为例进行说明：以1 2 3代表三种颜色，假如某行有两个元素同为1（或2或3）那么只要存在另外一行对应列的元素也相同即可，列与之同理。因此可以发现：当m或n为1时，必定不存在，输出0；当m或n大于9时，必定存在，证明如下：当m或n大于9时，必定有4个或以上元素1（or 2 or 3），那么因为只有三种颜色，则必定会有两个元素相同，因此必定符合题意，输出3(m*n)。对于其他一般情况，通过深搜分别计算结果并保存，打表判断。
源码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int MOD=1e9+7;
ll quickm(ll x,ll n){
ll ans=1;
while(n!=0){
if(n&1) ans=(ans*x)%MOD;
x=(x*x)%MOD;
n>>=1;
}
return ans;
}
/* 打表
ll gcnt,m,n;
ll a[15][15];
void dfs(int xx, int yy) {
for(int color=0;color<3;color++){
int x2=xx,y2=yy;
a[y2][x2]=color;
bool flag=true;
for(int y1=0;y1<y2&&flag;y1++){
for(int x1=0;x1<x2&&flag;x1++){
if((a[y1][x1]==a[y2][x1]&&a[y1][x2]==a[y2][x2])||
(a[y1][x1]==a[y1][x2]&&a[y2][x1]==a[y2][x2])){
flag=false;
gcnt+=quickm(3,(n-1-y2)*m+(m-1-x2));
gcnt%=MOD;
//printf("%lldn",gcnt);
}
}
}
if(flag){
x2++;
if(x2>=m){
x2=0;
y2++;
if(y2>=n){
continue;
}
}dfs(x2,y2);
}
}
a[yy][xx]=-1;
}
ll solve_dfs(){
gcnt=0;
dfs(0,0);
return gcnt;
}*/
ll table[10][10]={
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,15,339,4761,52929,517761,4767849,43046721,387420489,
0,0,339,16485,518265,14321907,387406809,460338013,429534507,597431612,
0,0,4761,518265,43022385,486780060,429534507,792294829,175880701,246336683,
0,0,52929,14321907,486780060,288599194,130653412,748778899,953271190,644897553,
0,0,517761,387406809,429534507,130653412,246336683,579440654,412233812,518446848,
0,0,4767849,460338013,792294829,748778899,579440654,236701429,666021604,589237756,
0,0,43046721,429534507,175880701,953271190,412233812,666021604,767713261,966670169,
0,0,387420489,597431612,246336683,644897553,518446848,589237756,966670169,968803245
};
int main(int argc, char** argv) {
/*
for(n=2;n<=9;n++){
for(m=2;m<=9;m++){
memset(a,0,sizeof(a));
printf("%lld,",solve_dfs());
//printf("%lldn",quickm(m,n));
}
printf("n");
}*/
int t,m,n;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
if(n==1 || m==1) printf("0n");
else if(m>9 || n>9) printf("%lldn",quickm(3,m*n));
else{
printf("%lldn",table[n][m]);
}
}
return 0;
}
最后
以上就是喜悦服饰为你收集整理的12.31 icpc 南京站F题H题的全部内容，希望文章能够帮你解决12.31 icpc 南京站F题H题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复