xjoi省选模拟赛_14

T1 发现 对于当前 投出 奇数次向上的概率为 p 那么 若加入一个 pi=0.5 的骰子

发现  p奇 +1=p奇 * 0.5+p * 0.5 = p偶+1  也就是说 只要方案中存在一个 p=0.5 的骰子

这个方案必然合法  :

 1 #include <bits/stdc++.h>
 2 #define N 100
 3 #define eps 1e-7
 4 using namespace std;
 5 typedef long double ldb;
 6 int t,n;
 7 ldb A[N];
 8 int main()
 9 {
10     scanf("%d",&t);
11     while(t--)
12     {
13         scanf("%d",&n);
14         for(int i=1;i<=n;i++)
15             scanf("%Lf",&A[i]);
16         int tot1=0;
17         for(int i=1;i<=n;i++)
18             if(fabs(A[i]-0.5)>eps) tot1++;
19         printf("%lld\n",(1ll<<n)-(1ll<<tot1));
20     }
21     return 0;
22 }

三分 次数 贪心 天数 || 二分天数 三分次数判断是否合法

我选择前者 但是我并不会证 求大爷带带我

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 inline ll read()
 5 {
 6     ll x=0,f=1;char ch=getchar();
 7     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
 8     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
 9     return x*f;
10 }
11 struct food
12 {
13     ll p,s;
14 }a[500],b[500];
15 ll t,n,m,f;
16 int tot;
17 inline bool cmp1(const food&a,const food&b)
18 {
19     return (a.s==b.s)? a.p<b.p:a.s<b.s;
20 }
21 inline bool cmp2(const food&a,const food&b)
22 {
23     return a.p<b.p;
24 }
25 ll get(ll x)
26 {
27     ll left=m-x*f,ans=0,tmp,now=0;
28     if(left<0) return 0;
29     for(int i=1;i<=tot;i++)
30     {
31         ll s=b[i].s,p=b[i].p;
32         if(now<=s) tmp=min(s-now+1,left/(p*x)),ans+=tmp*x,left-=p*x*tmp,now+=tmp;
33         if(now<=s) tmp=min(x,left/p),ans+=tmp,left-=p*tmp,now++;
34     }
35     return ans;
36 }
37 int main()
38 {
39     m=read();f=read();n=read();
40     for(int i=1;i<=n;i++)
41         a[i].p=read(),a[i].s=read();
42     sort(a+1,a+1+n,cmp1);b[1]=a[1];tot=1;
43     for(int i=1;i<=n;i++)
44         if(a[i].s>b[tot].s) b[++tot]=a[i];
45     sort(b+1,b+1+tot,cmp2);
46     if(f+a[1].p>m)
47     {
48         printf("0\n");
49         return 0;
50     }
51     ll l=1,r=m/(b[1].p+f),ans=max(get(l),get(r));
52     while(l+20<r)
53     {
54         ll tot=(r-l+1);
55         ll ansl=get(l+tot/3),ansr=get(l+2*tot/3);
56         if(ansl<ansr) ans=max(ansl,ans),l=l+tot/3+1;
57         else ans=max(ansr,ans),r=l+tot*2/3-1;
58     }
59     for(int i=l;i<=r;i++)
60         ans=max(ans,get(i));
61     printf("%lld\n",ans);
62     return 0;
63 }

模拟退火(进水?????)  Awd 大爷写了 禁忌搜索(全机房 我指507 就他一个人会)

 1 #include <bits/stdc++.h>
 2
 3 using namespace std;
 4 typedef double ldb;
 5 int n,A[55][55],vis[55],last,cnt;
 6 ldb ans;
 7 ldb dd(int x)
 8 {
 9     int g[55];g[0]=0;
10     ldb tmp=0;
11     for(int i=0;i<n;i++) if(x&(1<<i)) g[++g[0]]=i+1;
12     for(int i=1;i<=g[0];i++)
13         for(int j=i+1;j<=g[0];j++)
14             tmp+=(ldb)A[g[i]][g[j]];
15     return tmp/(ldb)(g[0]*(200-g[0]));
16 }
17 void solve()
18 {
19     double t=1.0;
20     while(t>0.00000001)
21     {
22         int p=rand()%2;
23         if(!p)
24         {
25             if(!cnt) continue;
26             int x=rand()%n+1;
27             if(!vis[x]) continue; int rel=0;
28             for(int i=1;i<=n;i++) if(vis[i]) rel+=A[x][i];
29             double tmp=last-rel;
30             if(ans<tmp/double(cnt-1)/double(201-cnt)||double(rand()%10000)/10000.0<t)
31                 last=tmp,ans=tmp/double(cnt-1)/double(201-cnt),cnt--,vis[x]=0;
32         }
33         else
34         {
35             int x=rand()%n+1;
36             if(vis[x]) continue;int rel=0;
37             for(int i=1;i<=n;i++) if(vis[i]) rel+=A[x][i];
38             double tmp=last+rel;
39             if(ans<tmp/double(cnt+1)/double(199-cnt)||double(rand()%10000/10000.0<t))
40                 last=tmp,ans=tmp/double(cnt+1)/double(199-cnt),cnt++,vis[x]=1;
41         }
42         t*=0.99999;
43     }
44     printf("%.5lf\n",ans);
45 }
46 int main()
47 {
48     srand(time(0));
49     scanf("%d",&n);
50     for(int i=1;i<=n;i++)
51         for(int j=1;j<=n;j++)
52             scanf("%d",&A[i][j]);
53     if(n<=15)
54     {
55         for(int i=0;i<(1<<15);i++)
56             ans=max(ans,dd(i));
57         printf("%.5lf\n",ans);
58     }
59     else solve();
60     return 0;
61 }
时间: 01-12

xjoi省选模拟赛_14的相关文章

@省选模拟赛03/16 - T3@ 超级树

目录 @description@ @solution@ @accepted code@ @details@ @description@ 一棵 k-超级树(k-SuperTree) 可按如下方法得到:取一棵深度为 k 的满二叉树,对每个节点向它的所有祖先连边(如果这条边不存在的话). 例如,下面是一个 4-超级树: 请统计一棵 k-超级树 中有多少条不同的简单有向路径,对 mod 取模. input 一行两整数 k, mod. output 一行一整数表示答案. example input1: 2

2018.3.10 省选模拟赛

从这里开始 概况 Problem A 三元组 Problem B 攻略 Problem C 迂回 概况 这是省选T1合集?还是欢乐AK赛? 全班一半以上的人三道题都会做qwq. Doggu还剩一小时时以为自己AK了,然后玩了一小时.虽然最终被卡了20分的常数. ZJC 1个半小时AK?Excuse me? 我这条大咸鱼到最后10分钟才敲完了T1,然后发现线段树要T掉. 发自内心鄙视垃圾出题人卡常数,本来的欢乐AK变成280. 教练给我们考4个小时的试,题面上也这么写的,看题解,woc,考试时间3

2018.2.12 省选模拟赛

题目大意 (题目很简洁了,不需要大意) 其实显而易见地可以发现,当被卡一次后后面的路程都是固定了的. 可以用类似动态规划的思想来进行预处理.现在的问题就是怎么知道在某个位置刚等完红灯然后出发会在哪个路口再次被卡. 尝试画一画图: 其中横轴表示位置,纵轴表示时间,长方体表示红灯时段.有用的部分长度只有$r + g$,所以在模意义下弄一下就可以减少很多重复和无用状态: 但是这样仍然不好处理上面提到的问题,考虑让线段横着走,第一个撞着的长方形就是答案.为了实现这个目标,就每个长方形向下移动一段(移动的

2018/3/9 省选模拟赛 0分

第二题模拟扫一遍就可以过,不能更划算了.q=1的30分写的比100分还麻烦,有趣哦. 破暴力40分也没什么可写了,日常辣鸡吃枣药丸. 原文地址:https://www.cnblogs.com/137shoebills/p/8533870.html

2018/3/29 省选模拟赛 80

我真是太菜了... T1 10分纯暴力没写,20分容斥也没写(人就是懒死的).还有30分矩乘不会 正解 <IOI2018 中国国家集训队第一阶段作业题解部分 - 杭州第二中学 吴瑾昭.pdf>最后一题 T2  以为自己能拿到50分,但是其实那个暴力算法只能过10分的点,n=2000的20分数据用n^3带剪枝过不了,所以拿了30分. 正解 <计数与期望问题选讲 CLJ.pdf>最后一题 我记得我以前好像看到过这个文档但是没读过..今天读一下 T3 依然是分情况50分,30分树归20分

2018/3/27 省选模拟赛 140分

T1 树归 100 T2 写的快速幂卷积 40,超时了,正解是矩阵乘法之类的. 正解 1 暴力(m<=5):将x的所有约数提出来矩阵乘法 2 3 定义乘法同构: 4 A=p[1]^a[1] * p[2]^a[2] * ... * p[n]^a[n] 5 B=q[1]^b[1] * q[2]^b[2] * ... * q[n]^b[n] 6 其中p[i]与q[i]皆为质数 7 将数组a与b降序排序后如果是完全相同的,那么称A与B是乘法同构的 8 如 2*2*2*2*3*3*5 与 7*11*11*

省选模拟赛20180416

上午 T1 提答送了40分拿了20. T2 费用流,不会 暴力骗分40 T3 dp变成四个方向的转移优化掉一个m^2 不会 暴力分都没拿全只有50 下午 T1 dp+扫描线,不会扫描线,60分暴力 T2  40分二分,100分要找规律不会找,二分写炸了只有20分. 原文地址:https://www.cnblogs.com/137shoebills/p/8858110.html

2018.6.29 省选模拟赛

*注意:这套题目应版权方要求,不得公示题面. 从这里开始 Problem A 小D与电梯 Problem B 小D与田野 Problem C 小D与函数 Problem A 小D与电梯 题目大意 假设电梯在0层,容量无限大.给定$n$个人的到达时间和要去的楼层.电梯上下一层楼花费的时间为1,电梯开关门.乘客上下的耗时不计,电梯可以停留在某一层楼.问将所有人送达到目的地,并让电梯回到0层的最少耗时. 先按到达时间将所有人排序.显然,每次电梯运输的人是一段连续的区间中的人. 用$f[i]$表示将前$

2018.2.23 省选模拟赛

从这里开始 Problem A cycle Problem B meal Problem C naive Problem A cycle 判断是否有经过一个点的负环,我们可以跑最短路.判断这个点到自己的最短路是否是负数. 于是可以二分环大小跑dfs版spfa. 于是可以分层图做时间复杂度四方的dp. (YYR给的数据水得吓人,这两个做法居然都跑过了.然后都被我和jmr卡掉了) 注意到如果一个点走不超过$k$条边回到自己的最短路的长度是负数,那么走不超过$k + 1$条边也是. 因此我们可以二分答