冯志远0914

问题 A: 组合数问题

时间限制: 1 Sec  内存限制: 512 MB
提交: -  解决: -
[提交][讨论版]

题目描述

组合数C(n,m)表示的是从n个物品中选出m个物品的方案数。举个例子,从(1, 2, 3)三个物品中选择两个物品可以有(1, 2),(1, 3),(2, 3)这三种选择方法。根据组合数的定义,我们可以给出计算组合数C(n,m)的一般公式:

C(n,m)=n!/(m!(n-m)!)图片 1

 

其中n!= 1×2×···×n。

 

小葱想知道如果给定n,mk,对于所有的0≤in,0≤j≤min(i,m)有多少对

 

i
 

(i,j)满足C(i,j)是k的倍数。

 

输入

第一行有两个整数t,k,其中t代表该测试点总共有多少组测试数据,k的意义见【问题描述】。

 

接下来t行每行两个整数n,m,其中n,m的意义见【问题描述】。

 

输出

t行,每行一个整数代表所有的0≤in,0≤j≤min(i,m)中有多少对(i,j)满足C(i,j)是k的倍数。

 

样例输入

1 2 3 3 2 5 4 5 6 7

样例输出

1 0 7

提示

 

【样例 1 说明】

 

在所有可能的情况中,只有C(2,1)=2 是2的倍数。

【子任务】

蚯蚓

时间限制: 1 Sec  内存限制: 512 MB
提交: -  解决: -
[提交][讨论版]

题目描述

本题中,我们将用符号LcJ表示对c向下取整,例如:L3.0J=L3.1J=L3.9J=3。

 

蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

 

蛐蛐国里现在共有n只蚯蚓(n为正整数)。每只蚯蚓拥有长度,我们设第i只蚯蚓的长度为ai(i=1,2,...,n),并保证所有的长度都是非负整数(即:可能存在长度为0的蚯蚓)。

 

每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半。神刀手切开蚯蚓的位置由常数(是满足0<p<1的有理数)决定,设这只蚯蚓长度为x,神刀手会将其切成两只长度分别为[px]和x−[px]的蚯蚓([]表示下取整)。特殊地,如果这两个数的其中一个等于0,则这个长度为0的蚯蚓也会被保留。此 外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加q(是一个非负整常数)。

 

蛐蛐国王知道这样不是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物,但是救兵还需要m秒才能到来......(m为非负整数)蛐蛐国王希望知道这m秒内的战况。

 

具体来说,他希望知道:

 

lm秒内,每一秒被切断的蚯蚓被切断前的长度(有m个数);

 

lm秒后,所有蚯蚓的长度(有n+m个数)。

 

蛐蛐国王当然知道怎么做啦!但是他想考考你......

 

输入

第一行包含六个整数n,m,q,u,v,t,其中:n,m,q的意义见【问题描述】;u,v,t均 为正整数;你需要自己计算p=u/v(保证0<uv);t是输出参数,其含义将会在【输出格式】中解释。

 

第二行包含n个非负整数,为a1,a2,...,an ,即初始时n只蚯蚓的长度。

 

同一行中相邻的两个数之间,恰好用一个空格隔开。

 

保证1≤n≤105,0≤m≤ 7×106 ,0<u<v≤109 ,0≤q≤200,1≤t≤71 ,

 

0≤ai≤108 。

 

输出

第一行输出[m/t] 个整数,按时间顺序,依次输出第t秒,第2t秒,第3t秒,......被切断蚯蚓(在被切断前)的长度。

第二行输出[(n+m)/t]个整数,输出m秒后蚯蚓的长度:需要按从大到小的顺序,依次输出排名第t,第2t,第3t,......的长度。

 

同一行中相邻的两个数之间,恰好用一个空格隔开。即使某一行没有任何数需要输出,你也应输出一个空行。

 

  请阅读样例来更好地理解这个格式。

 

样例输入

3 7 1 1 3 1 3 3 2 3 7 1 1 3 2 3 3 2 3 7 1 1 3 9 3 3 2

样例输出

3 4 4 4 5 5 6 6 6 6 5 5 4 4 3 2 2 4 4 5 6 5 4 3 2 2

提示

 

【样例 1 说明】

 

在神刀手到来前:3只蚯蚓的长度为3,3,2。

 

1秒后:一只长度为3的蚯蚓被切成了两只长度分别为1和2的蚯蚓,其余蚯蚓的长度增加了1。最终 4只蚯蚓的长度分别为(1,2),4,3。括号表示这个位置刚刚有一只蚯蚓被切断。

 

2秒后:一只长度为4的蚯蚓被切成了1和3。5只蚯蚓的长度分别为:2,3,(1,3),4。

 

3秒后:一只长度为4的蚯蚓被切断。6只蚯蚓的长度分别为:3,4,2,4,(1,3)。

 

4秒后:一只长度为4的蚯蚓被切断。7只蚯蚓的长度分别为:4,(1,3),3,5,2,4。

 

5秒后:一只长度为5的蚯蚓被切断。8只蚯蚓的长度分别为:5,2,4,4,(1,4),3,5。

 

6秒后:一只长度为5的蚯蚓被切断。9只蚯蚓的长度分别为:(1,4),3,5,5,2,5,4,6。

 

7秒后:一只长度为6的蚯蚓被切断。10只蚯蚓的长度分别为:2,5,4,6,6,3,6,5,(2,4)。

 

所以,7秒内被切断的蚯蚓的长度依次为3,4,4,4,5,5,6。7秒后,所有蚯蚓长度从大到小排序为6,6,6,5,5,4,4,3,2,2。

【样例 2 说明】

这个数据中只有t=2与上个数据不同。只需在每行都改为每两个数输出一个数即可。

虽然第一行最后有一个6没有被输出,但是第二行仍然要重新从第二个数再开始输出。

 

【样例 3 说明】

这个数据中只有t=9与上个数据不同。注意第一行没有数要输出,但也要输出一个空行。

 

【子任务】

l 测试点1~3满足m=0。

l 测试点4~7满足n,≤1,000。

l 测试点8~14满足q=0,其中测试点8∼9还满足m≤105。

l 测试点15~18满足m≤3×105 。

l 测试点19~20没有特殊的约定,参见原始的数据范围。

l 测试点 1~12, 15~16还满足 v≤2,这意味着u,v的唯一可能的取值是u=1,v=2,即p=0.5。这可能会对解决问题有特殊的帮助。

每个测试点的详细数据范围见下表。

 

愤怒的小鸟

时间限制: 2 Sec  内存限制: 512 MB
提交: -  解决: -
[提交][讨论版]

题目描述

Kiana 最近沉迷于一款神奇的游戏无法自拔。

简单来说,这款游戏是在一个平面上进行的。

有一架弹弓位于 (0, 0) 处,每次 Kiana 可以用它向第一象限发射一只红色的小鸟,小鸟们的飞行轨迹均为形如 y = ax2 + bx 的曲线,其中 a, b 是 Kiana 指定的参数,且必须满足 a < 0。

当小鸟落回地面(即 x 轴)时,它就会瞬间消失。

在游戏的某个关卡里,平面的第一象限中有 n 只绿色的小猪,其中第 i 只小猪所在的坐标为 (xi, yi)。

如果某只小鸟的飞行轨迹经过了 (xi, yi) ,那么第 i 只小猪就会被消灭掉,同时小鸟将会沿着原先的轨迹继续飞行;

如果一只小鸟的飞行轨迹没有经过 (xi, yi) ,那么这只小鸟飞行的全过程就不会对第 i 只小猪产生任何影响。

例如,若两只小猪分别位于 (1, 3) 和 (3, 3) ,Kiana 可以选择发射一只飞行轨迹为 y =

−x2 + 4x 的小鸟,这样两只小猪就会被这只小鸟一起消灭。

而这个游戏的目的,就是通过发射小鸟消灭所有的小猪。

这款神奇游戏的每个关卡对 Kiana 来说都很难,所以 Kiana 还输入了一些神秘的指令,使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。

假设这款游戏一共有 T 个关卡,现在 Kiana 想知道,对于每一个关卡,至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算,所以希望由你告诉她。

输入

第一行包含一个正整数 ,表示游戏的关卡总数。

下面依次输入这 个关卡的信息。每个关卡第一行包含两个非负整数 n,分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。接下来的 行中,第 行包含两个正实数 xiyi ,表示第 只小猪坐标为 (xiyi) 。数据保证同一个关卡中不存在两只坐标完全相同的小猪。

如果m = 0 ,表示 Kiana 输入了一个没有任何作用的指令。

如果m = 1 ,则这个关卡将会满足:至多用「n/3 + 1¬只小鸟即可消灭所有小猪。

如果m = 2 ,则这个关卡将会满足:一定存在一种最优解,其中有一只小鸟消灭了至少Ln/3J 只小猪。

保证 1 ≤ ≤ 18 , 0 ≤ ≤ 2 , 0 < xiyi < 10 ,输入中的实数均保留到小数点后两 位。

 

 

上文中,符号 「c¬ 和 LcJ 分别表示对 向上取整和向下取整,例如: 「2.1¬ = 「2.9¬ =「3.0¬ = L3.0J = L3.1J = L3.9J = 3 。

输出

对每个关卡依次输出一行答案。

输出的每一行包含一个正整数,表示相应的关卡中,消灭所有小猪最少需要的小鸟数量。

样例输入

2 2 0 1.00 3.00 3.00 3.00 5 2 1.00 5.00 2.00 8.00 3.00 9.00 4.00 8.00 5.00 5.00 3 2 0 1.41 2.00 1.73 3.00 3 0 1.11 1.41 2.34 1.79 2.98 1.49 5 0 2.72 2.72 2.72 3.14 3.14 2.72 3.14 3.14 5.00 5.00 1 10 0 7.16 6.28 2.02 0.38 8.33 7.78 7.68 2.09 7.46 7.86 5.77 7.44 8.24 6.72 4.42 5.11 5.42 7.79 8.15 4.99

样例输出

1 1 2 2 3 6

提示

 

【样例 1 说明】

这组数据中一共有两个关卡。

第一个关卡与【问题描述】中的情形相同,2只小猪分别位于(1.00,3.00)和(3.00,3.00),只需发射一只飞行轨迹为y = −x2 + 4x的小鸟即可消灭它们。

  第二个关卡中有 5 只小猪,但经过观察我们可以发现它们的坐标都在抛物线y = −x2 + 6x上,故 Kiana 只需要发射一只小鸟即可消灭所有小猪。

 

【子任务】

数据的一些特殊规定如下表:

 

题意还是baidu吧,这三道题,均交了一次,都是得了预期的分数,第一题就是普通求一个二维前缀和,第二题用了c++stl貌似会超时,第三题就是裸的状压dp吧。

最后还是靠zyh的电脑跑的比较快,拿了285分,如果上次去考noip的话貌似还会挂的节奏,以当前水平200+285也是到不了500分的,而且我也打不了这个分数,

所以还需要多多努力。

问题 A 组合数问题

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<iostream>
 6 
 7 using namespace std;
 8 
 9 const int NN=2007;
10 
11 int cas,k;
12 long long f[NN][NN],c[NN][NN];
13 
14 void init()
15 {
16     for (int i=1;i<=2000;i++)
17     {
18         c[i][1]=i%k;
19         for (int j=2;j<=i;j++)
20             c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
21     }
22     for (int i=1;i<=2000;i++)
23         for (int j=i+1;j<=2000;j++)
24             c[i][j]=-1;
25     for (int i=1;i<=2000;i++)
26         for (int j=1;j<=2000;j++)
27         {
28             if (c[i][j]==0) f[i][j]=1;
29             f[i][j]=f[i][j]+f[i][j-1]+f[i-1][j]-f[i-1][j-1];
30         }
31     /*for (int i=1;i<=3;i++)
32     {
33         for (int j=1;j<=3;j++)
34             cout<<f[i][j]<<" ";
35         cout<<endl;        
36     }*/    
37 }
38 int main()
39 {
40     scanf("%d%d",&cas,&k);
41     init();
42     int x,y;
43     while (cas--)
44     {
45         scanf("%d%d",&x,&y);
46         printf("%lldn",f[x][min(x,y)]);
47     }
48 }

问题 B 蚯蚓

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<queue>
 5 #include<cmath>
 6 #include<cstring>
 7 #define ll long long
 8 
 9 using namespace std;
10 
11 int n,m,q,u,v,t,cnt;
12 ll ans[8000007],x,pluss;
13 priority_queue<ll> stack;
14 
15 inline void make_out()
16 {
17     for (int i=1;i<cnt;i++)
18         cout<<ans[i]<<" ";
19     if (cnt!=0) cout<<ans[cnt]<<endl;
20     if (cnt==0) cout<<endl;
21     int num=0;
22     cnt=0;
23     while (!stack.empty())
24     {
25         num++;
26         x=stack.top();
27         stack.pop();
28         x+=pluss;
29         if (num%t==0) ans[++cnt]=x;
30     }
31     for (int i=1;i<cnt;i++)
32         cout<<ans[i]<<" ";
33     cout<<ans[cnt];    
34 }
35 int main()
36 {
37     scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
38     for (int i=1;i<=n;i++)
39     {
40         scanf("%lld",&x);
41         stack.push(x);
42     }
43     double p=(double)u*1.0/v;
44     for (int i=1;i<=m;i++)
45     {
46         x=stack.top();
47         x=x+pluss;
48         stack.pop();
49         if (i%t==0) ans[++cnt]=x;
50         ll y=(ll)(x*p+0.0000001),z=x-y;
51         y-=pluss,z-=pluss;
52         y-=q,z-=q;
53         stack.push(y),stack.push(z);
54         pluss=pluss+(ll)q;
55     }
56     
57     make_out();
58 }

问题 C 愤怒的小鸟

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<queue>
 7 #define NN 22
 8 #define INF 1e9+7
 9 
10 using namespace std;
11 
12 int n,m;
13 int dp[1<<NN],pre[NN][NN];
14 double x[NN],y[NN];
15 
16 int solve()
17 {
18     int up=(1<<n);
19     for (int i=1;i<=up;i++)
20         dp[i]=INF;
21     dp[0]=0;
22     for (int k=0;k<up;k++)
23     {
24         int i;
25         for (i=0;i<n;i++)
26             if (((1<<i)&k)==0) break;
27         dp[k|(1<<i)]=min(dp[k|(1<<i)],dp[k]+1);
28         for (int j=1;j<=n;j++)
29             dp[k|pre[i+1][j]]=min(dp[k|pre[i+1][j]],dp[k]+1);
30     }
31     return dp[up-1];
32 }
33 int main()
34 {
35     int Cas;
36     scanf("%d",&Cas);
37     while (Cas--)
38     {
39         scanf("%d%d",&n,&m);
40         for (int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
41         memset(pre,0,sizeof(pre));
42         for (int i=1;i<=n;i++)
43             for (int j=i+1;j<=n;j++)
44                {    
45                   double a=(y[j]*x[i]-y[i]*x[j])/((x[j]-x[i])*x[j]*x[i]);
46                   double b=(y[j]*x[i]*x[i]-y[i]*x[j]*x[j])/((x[i]-x[j])*x[i]*x[j]);
47                   if (a>=-0.0000001) continue;
48                   for (int k=1;k<=n;k++)
49                       if (fabs(a*x[k]*x[k]+b*x[k]-y[k])<=0.0000001)
50                         pre[i][j]|=1<<(k-1);
51                }
52         printf("%dn",solve());
53     }
54 }

 

本文由大发快三开奖结果发布于电脑,转载请注明出处:冯志远0914

TAG标签:
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。