[noip模拟赛2017.7.7]

时间:2022-12-20 12:33:02
题目名称 小猫爬山 Freda 的传呼机 Rainbow 的信号
程序文件名 catclimb communicate signal
输入文件名 catclimb.in communicate.in signal.in
输出文件名 catclimb.out communicate.out signal.out
每个测试点时限 1 秒 0.1 秒 1 秒
内存限制 128 MB 128 MB 128 MB
测试点数目 12 20 10
每个测试点分值 8.3333333333 5 10 (4+3+3)
是否有部分分
评测方式 Normal Normal Special Judge

评测环境: Intel(R) Core(TM) i3-370M CPU @2.40GHz 2.39GHz, 2.00GB RAM Cena 0.8.2 @ Windows 8 Release Preview x64 C++选手注意 Windows 7/8/Vista 可以使用 %lld 或%I64d 输入输出 64 位整数。 最终评测时,所有编译命令将打开-O2 优化开关。

小猫爬山 (catclimb.pas/c/cpp)

题目描述

Freda 和 rainbow 饲养了 N 只小猫,这天,小猫们要去爬山。经历了千辛万苦,小猫们 终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。 Freda 和 rainbow 只好花钱让它们坐索道下山。索道上的缆车最大承重量为 W,而 N 只 小猫的重量分别是 C1、C2……CN。当然,每辆缆车上的小猫的重量之和不能超过 W。每 租用一辆缆车,Freda 和 rainbow 就要付 1 美元,所以他们想知道,最少需要付多少美元才 能把这 N 只小猫都运送下山?

输入格式

第一行包含两个用空格隔开的整数,N 和 W。 接下来 N 行每行一个整数,其中第 i+1 行的整数表示第 i 只小猫的重量 C i。

输出格式

输出一个整数,最少需要多少美元,也就是最少需要多少辆缆车。

样例输入

5 1996

1

2

1994

12

29

样例输出

2

数据范围与约定

对于 100%的数据,1<=N<=18,1<=C i <=W<=10^8。

题解

考虑到猫的数量并不多,那么应该不存在多项式复杂度的算法,又桶的数量也不多,我们可以枚举桶的数量,并判断这么多桶能不能装下这么多猫,于是迭代加深搜索就出来啦,注意剪枝,比如要求第i个猫只能放在前i个桶中,下面放代码:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int n,Wt;
int w[20];
int c[20];
bool dfs(int ln,int k){
    if(ln<0)return true;
    for(int i=1;i<=k;i++){
        if(w[ln]+c[i]<=Wt){
            c[i]=c[i]+w[ln];
            if(dfs(ln-1,k))return true;
            c[i]=c[i]-w[ln];
        }
    }
    return false;
}
bool check(int k){
    memset(c,0,sizeof(c));
    return dfs(n,k);    
}
int work(){
    int l=1;
    while(!check(l)&&l<=n)l++;
    return l;
}
int main(){
    freopen("catclimb.in","r",stdin);
    freopen("catclimb.out","w",stdout);
    scanf("%d%d",&n,&Wt);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    sort(w+1,w+1+n);
    printf("%d",work());
}

Freda 的传呼机 (communicate.pas/c/cpp)

题目描述

为了随时与 rainbow 快速交流,Freda 制造了两部传呼机。Freda 和 rainbow 所在的地方 有 N 座房屋、M 条双向光缆。每条光缆连接两座房屋,传呼机发出的信号只能沿着光缆传 递,并且传呼机的信号从光缆的其中一端传递到另一端需要花费 t 单位时间。现在 Freda 要 进行 Q 次试验,每次选取两座房屋,并想知道传呼机的信号在这两座房屋之间传递至少需 要多长时间。Freda 和 rainbow 简直弱爆了有木有 T_T,请你帮帮他们吧…… N 座房屋通过光缆一定是连通的,并且这 M 条光缆有以下三类连接情况: A:光缆不形成环,也就是光缆仅有 N-1 条。 B:光缆只形成一个环,也就是光缆仅有 N 条。 C:每条光缆仅在一个环中。

输入格式

第一行包含三个用空格隔开的整数,N、M 和 Q。 接下来 M 行每行三个整数 x、y、t,表示房屋 x 和 y 之间有一条传递时间为t 的光缆。
最后 Q 行每行两个整数 x、y,表示 Freda 想知道在 x 和 y 之间传呼最少需要多长时间。

输出格式

输出 Q 行,每行一个整数,表示 Freda 每次试验的结果。

样例输入1

5 4 2

1 2 1

1 3 1

2 4 1

2 5 1

3 5

2 1

样例输出1

3

1

样例输入2

5 5 2

1 2 1

2 1 1

1 3 1

2 4 1

2 5 1

3 5

2 1

样例输出2

3

1

样例输入3

9 10 2

1 2 1

1 4 1

3 4 1

2 3 1

3 7 1

7 8 2

7 9 2

1 5 3

1 6 4

5 6 1

1 9

5 7

样例输出3

5

6

数据范围与约定

颂芬数据占 10%,2<=N<=1000,N-1<=M<=1200。 A类数据占 30%,M=N-1。 B类数据占 50%,M=N。 C 类数据占 10%,M>N。 对于 100%的数据,2<=N<=10000, N-1<=M<=12000,Q=10000,1<=x,y<=N,1<=t<32768。

题解

不会做。。。。

Rainbow 的信号 (signal.pas/c/cpp)

题目描述

Freda 发明了传呼机之后,rainbow 进一步改进了传呼机发送信息所使用的信号。由于 现在是数字、信息时代,rainbow 发明的信号用 N 个自然数表示。为了避免两个人的对话被 大坏蛋 VariantF 偷听 T_T,rainbow 把对话分成 A、B、C 三部分,分别用 a、b、c 三个密码 加密。现在 Freda 接到了 rainbow 的信息,她的首要工作就是解密。Freda 了解到,这三部 分的密码计算方式如下: 在 1~N 这 N 个数中,等概率地选取两个数 l、r,如果 l>r,则交换 l、r。把信号中的第 l 个数到第 r 个数取出来,构成一个数列 P。 A部分对话的密码是数列 P 的 xor 和的数学期望值。xor 和就是数列 P 中各个数异或之
后得到的数; xor 和的期望就是对于所有可能选取的 l、 r,所得到的数列的 xor 和的平均数。

A部分对话占接收到的信息总量的40%,因此如果你计算出密码a,将获得该测试点 40% 的分数。

B部分对话的密码是数列 P 的 and 和的期望,定义类似于 xor 和,占信息总量的 30%。

C 部分对话的密码是数列 P 的 or 和的期望,定义类似于 xor 和,占信息总量的 30%。

输入格式

第一行一个正整数 N。 第二行 N 个自然数,表示 Freda 接到的信号。

输出格式

一行三个实数,分别表示 xor 和、and 和、or 和的期望,四舍五入保留3 位小数,相邻 两个实数之间用不少于一个空格隔开。三个实数分别占该测试点 40%、30%、30%的分数, 如果你的输出少于三个实数,或者你的输出不合法,将被判 0 分。

样例输入1

2

4 5

样例输出1

2.750 4.250 4.750

样例输入2

3

1 0 1

样例输出2

0.667 0.222 0.889

样例解释

样例 1 共包含四种可能的 l、r: l, r xor 和 and 和 or 和 1,1 4 4 4 1,2 1 4 5 2,1 1 4 5 2,2 5 5 5 以上每一对 l、r 出现的概率均相同,因此分别对 xor 和、and 和、or 和取平均数就是数 学期望值。

数据范围与约定

对于 20%的数据,1<=N<=100。

对于 40%的数据,1<=N<=1000。

对于另外 30%的数据,N 个数为 0 或 1。

对于 100%的数据,1<=N<=100000,N 个自然数均不超过 10^9。

题解

考虑那些另外的30%的数据,为什么只有0和1,我们试着做一下,发现好像非常好算,对于and运算,必须是全1的区间and值才为1,对于or运算,剔除全是0的区间,其他区间or值都为1,xor有点麻烦,我们分情况讨论:

用f[i]记录以i为右端点,与左边的某个点连成xor值为1的区间的个数,
当前是0的时候,显然,f[i]=f[i-1];
当前是1的时候,答案应该是f[i]=i-f[i-1],即对该位是0时的答案进行取反;

这样找出了每一位的答案,最终答案便是每一位上的答案的叠加,详情见代码:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
int n,msg[100100];
bool trs[31][100100];
double X,A,O;
int main(){
    //freopen("signal.in","r",stdin);
    //freopen("signal.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&msg[i]);
    for(int i=0;i<=30;i++){
        for(int j=1;j<=n;j++)
            trs[i][j]=(msg[j]&(1<<i));
        for(int j=1;j<=n;){
            int k=j;
            while(trs[i][k]&&k<=n)k++;
            A=A+(double)(k-j)*(k-j)*(1<<i);
            j=k+1;
        }
        double o=0;
        for(int j=1;j<=n;){
            int k=j;
            while(!trs[i][k]&&k<=n)k++;
            o=o+(double)(k-j)*(k-j);
            j=k+1;
        }
        O=O+(double(n)*n-o)*(1<<i);
        int lst=0;
        for(int j=1;j<=n;j++){
            lst=lst+trs[i][j-1];
            if(trs[i][j]){
                X=X+(double)((j-1-lst)*2+1)*(1<<i);
                lst=(j-1-lst);
            }
            else X=X+(double)(lst*2)*(1<<i);
        }
    }
    X=(X/n)/n;A=(A/n)/n;O=(O/n)/n;
    printf("%.3lf %.3lf %.3lf",X,A,O);
    return 0;
}

对于xor运算的另一种写法:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
int n,msg[100100];
bool trs[31][100100];
double X,A,O;
int main(){
    freopen("signal.in","r",stdin);
    freopen("signal.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&msg[i]);
    for(int i=0;i<=30;i++){
        for(int j=1;j<=n;j++)
            trs[i][j]=(msg[j]&(1<<i));
        for(int j=1;j<=n;){
            int k=j;
            while(trs[i][k]&&k<=n)k++;
            A=A+(double)(k-j)*(k-j)*(1<<i);
            j=k+1;
        }
        double o=0;
        for(int j=1;j<=n;){
            int k=j;
            while(!trs[i][k]&&k<=n)k++;
            o=o+(double)(k-j)*(k-j);
            j=k+1;
        }
        O=O+(double(n)*n-o)*(1<<i);
        int n01=0,n10=0,lst=0;
        for(int j=1;j<=n;j++){
            if(!trs[i][j]){
                X=X+(double)lst*(1<<i);
                n01++;
            }
            else {
                swap(n01,n10);
                lst=(1+n10*2);
                X=X+(double)lst*(1<<i);
                lst++;
                n10++;
            }
        }
    }
    X=(X/n)/n;A=(A/n)/n;O=(O/n)/n;
    printf("%.3lf %.3lf %.3lf",X,A,O);
    return 0;
}