topcoder srm 380 div1

时间:2022-09-06 15:18:45

problem1 link

分类讨论。高度没有太大关系。主要看长度。

problem2 link

二分答案$mid$。计算每种$card$不足的部分,加起来,小于等于$min(jokers,mid)$就是合法的。

problem3 link

为了方便说明,以下所说的$x,y,a$分别是菱形宽度一半的平方、高度一半的平方、边长的平方。所以有$x+y=a$

对于宽的来说,比如第一个,$y_{1}\leq x_{1}$,所以$0\leq y_{1}\leq \frac{a_{1}}{2}$

对于高的来说,比如第二个,$y_{2}\geq x_{2}$,所以$ \frac{a_{2}}{2}\leq y_{1}\leq a_{2}$,宽和内部的高的关系为$y_{1}=y_{2}$,所以有$\frac{a_{2}}{2} \leq y_{1} \leq a_{2}$

同理对于第三个来说,它是宽的,所以$\frac{a_{3}}{2}\leq x_{3}\leq a_{3}$,高和内部的宽的关系为$x_{2}=x_{3}$,所以$\frac{a_{3}}{2}\leq x_{3}=x_{2}=a_{2}-y_{2}=a_{2}-y_{1}\leq a_{3}$,所以$a_{2}-a_{3} \leq y_{1} \leq a_{2}-\frac{a_{3}}{2}$

按照这个推导下去,会得到$y_{1}$的若干个区间,所有区间求交即可得到$y_{1}$最后的区间。如果区间合法,最小值就是答案。

code for problem1

import java.util.*;
import java.math.*;
import static java.lang.Math.*; public class LameKnight { public int maxCells(int n,int m) {
if(n==1) {
return 1;
}
else if(n==2){
if(m>=7) {
return 4;
}
else if(m>=5) {
return 3;
}
else if(m>=3) {
return 2;
}
else {
return 1;
}
}
else {
if(m>=7) {
return 3+(m-5);
}
else {
int result=dfs(1,1,n,m);
if(result>4) {
result=4;
}
return result;
}
}
} int dfs(int x,int y,int n,int m) {
if(x<1||x>n||y<1||y>m) {
return 0;
}
int result=1;
result=Math.max(result,1+dfs(x+2,y+1,n,m));
result=Math.max(result,1+dfs(x+1,y+2,n,m));
result=Math.max(result,1+dfs(x-1,y+2,n,m));
result=Math.max(result,1+dfs(x-2,y+1,n,m));
return result;
}
}

  

code for problem2

import java.util.*;
import java.math.*;
import static java.lang.Math.*; public class CompilingDecksWithJokers { public int maxCompleteDecks(int[] cards, int jokers) {
int low=0,high=1000000000;
int result=low;
while(low<=high) {
int mid=(low+high)>>1;
if(check(mid,cards,jokers)) {
result=Math.max(result,mid);
low=mid+1;
}
else {
high=mid-1;
}
}
return result;
} boolean check(int mid,int[] cards,int jokers) {
long result=0;
for(int i=0;i<cards.length&&result<=jokers&&result<=mid;++i) {
if(cards[i]<mid) {
result+=mid-cards[i];
}
}
return result<=jokers&&result<=mid;
}
}

  

code for problem3

import java.util.*;
import java.math.*;
import static java.lang.Math.*; public class NestedDiamonds { public double minHeight(int[] sides) {
Arrays.sort(sides);
final int n=sides.length;
for(int i=1;i<n;++i) {
if(sides[i]==sides[i-1]) {
return -1;
}
}
long[] a=new long[n];
for(int i=0;i<n;++i) {
a[i]=(long)sides[n-1-i]*sides[n-1-i];
}
long low=0,high=a[0];
for(int i=1;i<n;++i) {
long newlow=0,newhigh=0;
int sign=1;
for(int j=1;j<i;++j) {
newlow+=sign*2*a[j];
newhigh+=sign*2*a[j];
sign*=-1;
}
if((i&1)==1) {
newlow+=a[i];
newhigh+=2*a[i];
}
else {
newlow-=2*a[i];
newhigh-=a[i];
}
low=Math.max(low,newlow);
high=Math.min(high,newhigh);
}
if(low>high) {
return -1;
}
return Math.sqrt(0.5*low)*2;
}
}

  

topcoder srm 380 div1的更多相关文章

  1. Topcoder SRM 643 Div1 250&lt&semi;peter&lowbar;pan&gt&semi;

    Topcoder SRM 643 Div1 250 Problem 给一个整数N,再给一个vector<long long>v; N可以表示成若干个素数的乘积,N=p0*p1*p2*... ...

  2. Topcoder Srm 726 Div1 Hard

    Topcoder Srm 726 Div1 Hard 解题思路: 问题可以看做一个二分图,左边一个点向右边一段区间连边,匹配了左边一个点就能获得对应的权值,最大化所得到的权值的和. 然后可以证明一个结 ...

  3. topcoder srm 714 div1

    problem1 link 倒着想.每次添加一个右括号再添加一个左括号,直到还原.那么每次的右括号的选择范围为当前左括号后面的右括号减去后面已经使用的右括号. problem2 link 令$h(x) ...

  4. topcoder srm 738 div1 FindThePerfectTriangle&lpar;枚举&rpar;

    Problem Statement      You are given the ints perimeter and area. Your task is to find a triangle wi ...

  5. Topcoder SRM 602 div1题解

    打卡- Easy(250pts): 题目大意:rating2200及以上和2200以下的颜色是不一样的(我就是属于那个颜色比较菜的),有个人初始rating为X,然后每一场比赛他的rating如果增加 ...

  6. Topcoder SRM 627 div1 HappyLettersDiv1 &colon; 字符串

    Problem Statement      The Happy Letter game is played as follows: At the beginning, several players ...

  7. Topcoder SRM 584 DIV1 600

    思路太繁琐了 ,实在不想解释了 代码: #include<iostream> #include<cstdio> #include<string> #include& ...

  8. TopCoder SRM 605 DIV1

    604的题解还没有写出来呢.先上605的. 代码去practice房间找. 说思路. A: 贪心,对于每个类型的正值求和,如果没有正值就取最大值,按着求出的值排序,枚举选多少个类型. B: 很明显是d ...

  9. topcoder srm 575 div1

    problem1 link 如果$k$是先手必胜那么$f(k)=1$否则$f(k)=0$ 通过对前面小的数字的计算可以发现:(1)$f(2k+1)=0$,(2)$f(2^{2k+1})=0$,(3)其 ...

随机推荐

  1. 使用git pull文件时和本地文件冲突怎么办?

    同事在使用git pull代码时,经常会碰到有冲突的情况,提示如下信息: error: Your local changes to 'c/environ.c' would be overwritten ...

  2. 水晶报表&lpar;web&rpar;表格信息展示

    一.环境安装 开发工具使用VS2010+SAP Crystal Reports13_0+.NETformwork4.0 因为vs2010已经不再集成水晶报表,所以需要我们去找合适的版本下载http:/ ...

  3. org&period;springframework&period;dao&period;InvalidDataAccessApiUsageException&colon;The given object has a null identifi的解决方案

    异常信息: org.springframework.dao.InvalidDataAccessApiUsageException: The given object has a null identi ...

  4. iOS中UITableView的cell点击事件不触发didSelectRowAtIndexPath(汇总)

    iOS中UITableView的cell点击事件不触发didSelectRowAtIndexPath 首先分析有几种原因,以及相应的解决方法 1.UITableViewCell的userInterac ...

  5. mysql启动的四种方式

    mysql的四种启动方式: .mysqld 启动mysql服务器:./mysqld --defaults-file=/etc/my.cnf --user=root 客户端连接: mysql --def ...

  6. Spring MVC 学习总结(九)——Spring MVC实现RESTful与JSON(Spring MVC为前端提供服务)

    很多时候前端都需要调用后台服务实现交互功能,常见的数据交换格式多是JSON或XML,这里主要讲解Spring MVC为前端提供JSON格式的数据并实现与前台交互.RESTful则是一种软件架构风格.设 ...

  7. java基本语法特殊点

    一.关系运算符 instanceof(类型比较运算符) example:a instanceof hello // hello是一个class ==与!=可以用于引用相等运算符( 二.数组 (数组是对 ...

  8. hdu 4453 splay

    Looploop Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total S ...

  9. 如何通过免费开源ERP Odoo建立你的团队&comma; 销售过程和目标

    这种快速的一步一步的指南将引导您完成Odoo CRM, 帮助您轻松处理您的销售渠道, 时刻从线索到客户管理您的销售渠道. 配置 从 Odoo初始化后,生成你的数据库, 选择CRM 作为第一个app安装 ...

  10. lambda表达式——写多线程

    JDK1.8 中Lambda 表达式的出现,基本可以取替原来的匿名类实现多线程的方式.下面列举常用的常用的三种情况. 一.普通开启异步线程   new Thread(() -> System.o ...