注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

0327选拔赛(上午)  

2016-04-01 13:28:05|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
第一题:
                                               组题(pro 1s) 
题目描述】 GDOI2016 将于 4 月 30 日至 5 月 3 日在四会中学举行,为了准备这次比赛, 评委们正忙着出题。题目难度分为“简单题”、“中等题”、“难题”三个等级。评 委们已经出好了 E 道简单题, M 道中等题, H 道难题。然后评委们又出了 EM 道“简中”题和 MH 道“中难”题。所谓的“简中题”是指该类型的题既可以 归类为“简单题”也可以归类为“中等题”。所谓的“中难题”是指该类型的题 既可以归类为“中等题”也可以归类为“难题”。 评委们规定:一场比赛必须包含 3 道题,其中 1 题是“简单题”, 1 题是“中 等题”, 1 题是“难题”。每道题目至多只能出现在一场比赛中。问题是:评委们 最多可以组织多少场比赛? 
【输入格式】 pro.in
多组测试数据。
第一行,一个整数 R,表示有 R 组测试数据。
每组测试数据格式如下:
一行, 5 个整数: E、 EM、 M、 MH、 H。 0 <= E、 EM、 M、 MH、 H<=100000。

分析:
    这道题,就是一个分配问题,把EM分配给E和M,把MH分配给M和H,使得最小值最大(又是这样-_-)。
    首先,我先把EM都分给E,MH都分配给H。这样就变成把E和H分配给M的问题,这样会相对容易想,当然不这样也行。
    接下来,神犇用神之if(考试时就这样挂了^_^)或二份答案,
    而像我这样的小牛,就直接用for枚举。

程序:

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdio>

using namespace std;

int main()
{
freopen("pro.in","r",stdin);
freopen("pro.out","w",stdout);

int r; cin>>r;
for (int i=0; i<r; i++)
{
int E,EM,M,MH,H;
scanf("%d%d%d%d%d",&E,&EM,&M,&MH,&H);

E+=EM; H+=MH;

for (int i=300000; i>=0; i--)
{
if (E<i) continue;
if (H<i) continue;

if ( M+min((E-i),EM)+min((H-i),MH)<i ) continue;

//这里需小心最多也是分配EM个或MH,所以要用min

cout<<i; break;
}

cout<<endl;
}

return 0;
}

==============================================================
第二题:
                                                 K 叉树( ktree 1s) 
【题目描述】 有一个巨大的 K 叉树,从上到下,从左到右编了 N 个号,这 N 个点就是一个 K 叉完全树。例如 K=3, N=9: 你需要回答 Q 个问题:从 x 节点到 y 节点最少要经过几条边? 
【输入格式】 第 1 行输入整数 N ( 1 ≤ N ≤ 10^15(表示有 15 个 0)), K ( 1 ≤K ≤ 1,000), Q( 1 ≤ Q ≤ 100,000)。 下面 Q 行,每行两个整数 x 和 y( L ≤ x,y ≤ N , x≠y)。

分析:
    就是一个在树上找公共祖先的问题,由于数据不大,乱来都可以。(当K=1,时会超时!)
程序:

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdio>

using namespace std;

int K;

int main()
{
freopen("ktree.in","r",stdin);
freopen("ktree.out","w",stdout);

long long N;
int Q;
cin>>N>>K>>Q;

for (int i=0; i<Q; i++)
{
long long x,y;
scanf("%I64d%I64d",&x,&y);

if (K==1) { int t=abs(x-y); printf("%d\n",t); continue; }

x--; y--;

int sum=0;
for ( ; x!=y; )
{
if (x>y) x=(x-1)/K;
else y=(y-1)/K;

sum++;
}

printf("%d\n",sum);
}

return 0;
}

不过奇怪的是:把x=(x-1)/K写成子程序时,就超时了!!!!!!!*-*
更奇怪的是:清橙就不超时,lemon就爆了!!!
==============================================================
第三题:
                   最大值求和( summax 1s) 
【题目描述】
为了研究大奖赛的概率问题,数学家推出这样一个问题:
有编号是 1 到 N 的小球,每个小球上面有数字 ai。把从 N 个球选 K 个的所有方法都列出
来,每种取法都得到 K 个球上的 K 个数字,其中最大的作为这组数字的代表。
请计算这些代表的和。 
输入格式】
第 1 行: 2 个整数 N 和 K( 1 ≤ N ≤ 10,000, 1 ≤ K ≤ 50)。
第 2 行: N 个整数,第 i 个整数 ai, 表示编号 i 小球上的数字( 1 ≤ ai ≤ 1,000,000,000)。

分析:
    数据那么大,我们既不能傻傻的找一遍,不过我们可以枚举那个最大值0327选拔赛(上午) - 杨鸿飞 - 一个叫杨鸿飞的人的博客,就这么多了。

程序:

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdio>

using namespace std;

const int M=1000000007;

long long C[100010][55];
int a[100010];

int main()
{
freopen("summax.in","r",stdin);
freopen("summax.out","w",stdout);

int N,K; cin>>N>>K; K-=1;

for (int i=0; i<N; i++) scanf("%d",&a[i]);

sort(a+0,a+N);

for (int i=0;i<=N;i++) C[i][0]=1;
for (int i=1;i<=N;i++)
for (int j=1;j<=min(i,K);j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%M;

int ans=0;

for (int i=N-1; i>=K; i--) ans=(ans+(C[i][K]*a[i])%M)%M;

cout<<ans;

return 0;
}

注意:会有很多%,所以很容易爆,我就是这样挂的!!虽然我现在还没懂。
==============================================================
第四题:
        鬼畜的水了64分!!!至今未懂。



  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018