bzoj 前100题计划

时间:2022-09-18 23:37:21

bzoj前100题计划

xz布置的巨大的坑。。

有空填题解。。。


1002 轮状病毒

用python手动matrixtree打表。

#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
char biao[101][45]={"mmp","1","5","16","45","121","320","841","2205","5776","15125","39601","103680","271441","710645","1860496","4870845","12752041","33385280","87403801","228826125","599074576","1568397605","4106118241","10749957120","28143753121","73681302245","192900153616","505019158605","1322157322201","3461452808000","9062201101801","23725150497405","62113250390416","162614600673845","425730551631121","1114577054219520","2918000611027441","7639424778862805","20000273725560976","52361396397820125","137083915467899401","358890350005878080","939587134549734841","2459871053643326445","6440026026380244496","16860207025497407045","44140595050111976641","115561578124838522880","302544139324403592001","792070839848372253125","2073668380220713167376","5428934300813767249005","14213134522220588579641","37210469265847998489920","97418273275323406890121","255044350560122222180445","667714778405043259651216","1748099984655007556773205","4576585175559979410668401","11981655542024930675232000","31368381450514812615027601","82123488809519507169850805","215002084978043708894524816","562882766124611619513723645","1473646213395791149646646121","3858055874062761829426214720","10100521408792494338631998041","26443508352314721186469779405","69230003648151669220777340176","181246502592140286475862241125","474509504128269190206809383201","1242282009792667284144565908480","3252336525249732662226888342241","8514727565956530702536099118245","22291846172619859445381409012496","58360810951903047633608127919245","152790586683089283455442974745241","400010949097364802732720796316480","1047242260609005124742719414204201","2741715832729650571495437446296125","7177905237579946589743592924684176","18791999880010189197735341327756405","49198094402450621003462431058585041","128802283327341673812651951847998720","337208755579574400434493424485411121","882823983411381527490828321608234645","2311263194654570182037991540339292816","6050965600552329018623146299409643805","15841633607002416873831447357889638601","41473935220454921602871195774259272000","108580172054362347934782139964888177401","284266580942632122201475224120405260205","744219570773534018669643532396327603216","1948392131377969933807455373068577549445","5100956823360375782752722586809405045121","13354478338703157414450712387359637585920","34962478192749096460599414575269507712641","91532956239544131967347531338448885552005","239636390525883299441443179440077148943376","627376215338105766356982006981782561278125",};
int main(){
#ifndef ONLINE_JUDGE
freopen("1002.in","r",stdin);
freopen("1002.out","w",stdout);
#endif
printf("%s",biao[gi()]);
return 0;
}
from decimal import Decimal,getcontext
getcontext().prec=80
eps=Decimal("0."+"0"*50+"1")
for n in range(3,101):
A=[[Decimal('0') for i in range(0,n)]for i in range(0,n)]
for i in range(0,n):A[i][i]=Decimal('3')
for i in range(0,n):
for j in range(0,n):
if i!=j:A[i][j]=Decimal(str(-int(abs(i-j)==1 or abs(i-j)==n-1)))
for i in range(0,n):
for j in range(i+1,n):
if(abs(A[j][i])>abs(A[i][i])):
A[i],A[j]=A[j],A[i]
for j in range(i+1,n):
if abs(A[j][i]-Decimal('0'))<eps:continue
S=A[j][i]/A[i][i]
for k in range(i,n):
A[j][k]-=A[i][k]*S
ans=Decimal('1')
for i in range(0,n):ans*=A[i][i]
print("\""+str(int(ans))+"\"",end=',')

Decimal高精度真tm好


1004 cards

神仙Burnside。玄学求出所有洗牌法都没有不动点(除了单位元)

所以答案是不动点个数/(m+1),不动点个数是把Srgb组合一下


1005 明明的烦恼

怎么全是高精好烦啊

就是prufer序列上面d[i]!=-1的点会出现d[i]-1次,设前cnt个点d[i]!=-1,\(sum=\sum_{i=1}^{cnt}d[i]-1\)

所以这部分是\(\frac{sum!}{\Pi_{i=1}^{cnt} (d[i]-1)!}\)

剩下的点一共有\(n-cnt\)个,出现\(n-2-sum\)次,所以这部分是\((n-cnt)^{n-2-sum}\)

然后还要乘一个\(C_{n-2}^{sum}\)

所以最后答案就是\(C_{n-2}^{sum} \times \frac{sum!}{\Pi_{i=1}^{cnt} (d[i]-1)!}\times (n-cnt)^{n-2-sum}\)

还能约个分$ \frac{(n-2)!(n-cnt){n-2-sum}}{(n-2-sum)!\Pi_{i=1}{cnt} (d[i]-1)!}$

这个诡异的东西,高精求就行了。。。


1037 [ZJOI2008]生日聚会Party

f[i][j][k][l] 表示选i个♂的j个♀的,右边每一段最多男比女多k女比男多l的方案数


1038 瞭望塔

每条直线的上半平面求个交。答案一定在原来折线的交点或上凸壳的顶点上。

#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
double x[301],y[301];
struct line{double k,b;bool del;}l[301],s[301],b[301];
int n,top;
il bool operator <(const line&a,const line&b){
if(a.del)return 0;if(b.del)return 1;
if(fabs(a.k-b.k)>1e-9)return a.k<b.k;
return a.b>b.b;
}
il double jx(const line&a,const line&b){return(a.b-b.b)/(b.k-a.k);}
il double jy(const line&a,const line&b){return(a.k*b.b-a.b*b.k)/(a.k-b.k);}
il double solve(double X,line*s,int N){
for(int i=1;i<N;++i)if(X-1e-9<=jx(s[i],s[i+1]))return s[i].k*X+s[i].b;
return s[N].k*X+s[N].b;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1038.in","r",stdin);
freopen("1038.out","w",stdout);
#endif
n=gi();
for(int i=1;i<=n;++i)scanf("%lf",&x[i]);
for(int i=1;i<=n;++i)scanf("%lf",&y[i]);
int m=n-1;
for(int i=1;i<=m;++i){
l[i].k=b[i].k=(y[i]-y[i+1])/(x[i]-x[i+1]);
l[i].b=b[i].b=y[i]-l[i].k*x[i];
l[i].del=0;
}
std::sort(l+1,l+m+1);
for(int i=1;i<=m;++i)if(fabs(l[i].k-l[i-1].k)<1e-7)l[i].del=1;
std::sort(l+1,l+m+1);
l[m+1].del=1;m=0;while(!l[m+1].del)++m;
top=0;
s[++top]=l[1];
for(int i=2;i<=m;++i){
while(top>1&&jx(s[top],l[i])<=jx(s[top-1],l[i])-1e-9)--top;
s[++top]=l[i];
}
double ans=1e18;
ans=std::min(ans,solve(x[1],s,top)-solve(x[1],b,n-1));
ans=std::min(ans,solve(x[n],s,top)-solve(x[n],b,n-1));
for(int i=1;i<n;++i){
double p=jx(b[i],b[i+1]);
ans=std::min(ans,solve(p,s,top)-solve(p,b,n-1));
}
for(int i=1;i<top;++i){
double p=jx(s[i],s[i+1]);
if(p+1e-9>=x[1]&&p<=x[n]+1e-9)ans=std::min(ans,solve(p,s,top)-solve(p,b,n-1));
}
if(ans<0)ans=0;
printf("%.3lf\n",ans);
return 0;
}

bzoj 前100题计划的更多相关文章

  1. 【总结】 BZOJ前100题总结

    前言 最近发现自己trl,所以要多做题目但是Tham布置的题目一道都不会,只能来写BZOJ HA(蛤)OI 1041 复数可以分解成两个点,所以直接把\(R^2\)质因数分解一下就可以了,注意计算每一 ...

  2. LeetCode前100题(EASY难度)

    1 Two Sum Given an array of integers, return indices of the two numbers such that they add up to a s ...

  3. 纪念,BZOJ AC 100题!

    虽然说有将近50+是usaco,然后还有很多水题T_T 看来我还是刷水题.... 看来我还是那么弱. T_T 但是好歹也要留个纪念..

  4. BZOJ第一页刷题计划

    BZOJ第一页刷题计划 已完成:67 / 90 [BZOJ1000]A+B Problem:A+B: [BZOJ1001][BeiJing2006]狼抓兔子:最小割: [BZOJ1002][FJOI2 ...

  5. bzoj 3208 花神的秒题计划I

    bzoj 3208 花神的秒题计划I Description 背景[backboard]: Memphis等一群蒟蒻出题中,花神凑过来秒题-- 描述[discribe]: 花花山峰峦起伏,峰顶常年被雪 ...

  6. csp退役前的做题计划1(真)

    csp退役前的做题计划1(真) 因为我太菜了,所以在第一次月考就会退役,还是记录一下每天做了什么题目吧. 任务计划 [ ] Z算法(Z Algorithm) 9.28 [x] ARC061C たくさん ...

  7. NOIP2018前的一些计划&amp&semi;记录&lpar;日更&rpar;

    先空着,等停课了再开始写. 诸位好,我是yyb.现在显然已经不再是高一的小蒟蒻了,已经升级为了高二的菜鸡了 现在已经不能再每天划划水切切题了,毕竟......已经高二了,所有的机会从高一的两倍全部除了 ...

  8. bzoj Usaco补完计划&lpar;优先级 Gold&gt&semi;Silver&gt&semi;资格赛&rpar;

    听说KPM初二暑假就补完了啊%%% 先刷Gold再刷Silver(因为目测没那么多时间刷Silver,方便以后TJ2333(雾 按AC数降序刷 ---------------------------- ...

  9. NOIP前的一些计划

    一些想法 距离NOIP2018只剩下一个星期的时间了,通过这几天在长郡的考试,渐渐感觉还有好多东西自己还不够熟练,也有些东西到现在还不会,现将NOIP前的一些计划列在这里,希望能在考前把他们全部完成吧 ...

随机推荐

  1. 配置Java开发IDE

    http://www.cnblogs.com/feichexia/archive/2012/11/07/Vim_JavaIDE.html

  2. html&sol;css基础篇——关于浏览器window、document、html、body高度的探究

    首先说明本人所理解的这几个元素的计算 window高度应当是文档所在窗口的可视高度(没有包括浏览器的滚动条),计算方法document.documentElement.clientHeight doc ...

  3. LINQ的高级应用

    ---恢复内容开始--- 本文不想罗列linq的通俗使用方法.因为很多博文都已经写得很详细了. 此处直接贴出源码,如果有需要的朋友可以参考,希望更多的朋友能够补充更多的linq的高级应用. 源码如下: ...

  4. js中document&period;documentElement 和document&period;body 以及其属性 clientWidth等

    在设计页面时可能经常会用到固定层的位置,这就需要获取一些html对象的坐标以更灵活的设置目标层的坐标,这里可能就会用到document .body.scrollTop等属性,但是此属性在xhtml标准 ...

  5. 【转】SQLServer内部原理

    原文地址:http://twb.iteye.com/blog/182083 在讲SQLSERVER内部原理的之前,我觉得非常有必要向大家介绍一下SQLSERVER的历史. 让我们站在1999年,看看计 ...

  6. android方向键被锁定的问题

    当虚拟机启动的时候,很多情况是旁边的方向键不能点击,处于一种被锁定的状态,解决办法如下: 找到   C:\Users\Administrator(你的用户名)\.android\avd\mm.adv( ...

  7. STM32之FreeRTOS

    STM32之FreeRTOS http://www.freertos.org/index.html http://www.freertos.org/a00090.html#ST http://www. ...

  8. Frame Interpolation

    对于视频网站.电视厂商以及进行视频压制的用户来说,改变视频的帧率算是一个比较常见的需求.视频网站改变帧率主要是为了向不同级别的网站用户提供差异化服务:电视厂商则是以提供更好的显示效果作为电视的卖点:对 ...

  9. spring cloud 配置文件application&period;yml和bootstrap&period;yml 的定位,区别和联系

    最近在启用springcloud配置中心server的东西,在整理属性资源的时候,突然发现:用了这么久的springboot,为什么会配置两个属性文件同时存在(application.yml/prop ...

  10. springboot深入学习&lpar;二&rpar;-----profile配置、运行原理、web开发

    一.profile配置 通常企业级应用都会区分开发环境.测试环境以及生产环境等等.spring提供了全局profile配置的方式,使得在不同环境下使用不同的applicaiton.properties ...