清华冬令营的某题

By | 03月09日
Advertisement

问题背景

数字和数学规律主宰着这个世界。
机器的运转,
生命的消长,
宇宙的进程,
这些神秘而又美妙的过程无不可以用数学的语言展现出来。
这印证了一句古老的名言:
“学好数理化,走遍天下都不怕。”

问题描述

学渣小R被大学的数学课程虐得生活不能自理,微积分的成绩曾是他在教室里上的课的最低分。然而他的某位陈姓室友却能轻松地在数学考试中得到满分。为了提升自己的数学课成绩,有一天晚上(在他睡觉的时候),他来到了数学王国。

数学王国中,每个人的智商可以用一个属于[0,1]的实数表示。数学王国中有n个城市,编号从0到n−1,这些城市由若干座魔法桥连接。每个城市的中心都有一个魔法球,每个魔法球中藏有一道数学题。每个人在做完这道数学题之后都会得到一个在[0,1]区间内的分数。一道题可以用一个从[0,1]映射到[0,1]的函数f(x)表示。若一个人的智商为x,则他做完这道数学题之后会得到f(x)分。函数f有三种形式:

  1. 正弦函数sin(ax+b) (a∈[0,1],b∈[0,π],a+b∈[0,π])
  2. 指数函数eax+b (a∈[−1,1],b∈[−2,0],a+b∈[−2,0])
  3. 一次函数ax+b (a∈[−1,1],b∈[0,1],a+b∈[0,1])

数学王国中的魔法桥会发生变化,有时会有一座魔法桥消失,有时会有一座魔法桥出现。但在任意时刻,只存在至多一条连接任意两个城市的简单路径(即所有城市形成一个森林)。在初始情况下,数学王国中不存在任何的魔法桥。

数学王国的国王拉格朗日很乐意传授小R数学知识,但前提是小R要先回答国王的问题。这些问题具有相同的形式,即一个智商为x的人从城市u旅行到城市v(即经过u到v这条路径上的所有城市,包括u和v)且做了所有城市内的数学题后,他所有得分的总和是多少。

输入格式

第一行两个正整数 n,m和一个字符串type。表示数学王国中共有n座城市,发生了m个事件,该数据的类型为type。type字符串是为了能让大家更方便地获得部分分,你可能不需要用到这个输入。其具体含义在限制与约定中有解释。

接下来n行,第i行表示初始情况下编号为 i 的城市的魔法球中的函数。一个魔法用一个整数 f 表示函数的类型,两个实数 a,b 表示函数的参数,若

  1. f=1,则函数为f(x)=sin(ax+b)(a∈[0,1],b∈[0,π],a+b∈[0,π])
  2. f=2,则函数为f(x)=eax+b(a∈[−1,1],b∈[−2,0],a+b∈[−2,0])
  3. f=3,则函数为f(x)=ax+b(a∈[−1,1],b∈[0,1],a+b∈[0,1])

接下来 m 行,每行描述一个事件,事件分为四类。

  1. appear u v 表示数学王国中出现了一条连接u和v这两座城市的魔法桥(0≤u,v<n,u≠v) ,保证连接前u和v这两座城市不能互相到达。
  2. disappear u v 表示数学王国中连接u和v这两座城市的魔法桥消失了,保证这座魔法桥是存在的。
  3. magic c f a b 表示城市c的魔法球中的魔法变成了类型为f,参数为a,b的函数
  4. travel u v x 表示询问一个智商为x的人从城市u旅行到城市v(即经过u到v这条路径上的所有城市,包括u和v)后,他得分的总和是多少。若无法从u到达v,则输出一行一个字符串 unreachable

输出格式

对于每个询问,输出一行实数,表示得分的总和。

限制与约定

对于100%的数据,1≤n≤100000,1≤m≤200000 。
本题共有20个数据点,每个数据点5分。
时限:5s

数据类型的含义:
A:不存在 disappear 事件,且所有appear事件中的u=v−1
B:不存在 disappear 事件
C:所有的 travel 事件经过的城市总数 ≤5000000(不可到达的城市对不计入在内)
D:无限制
0:所有 travel 事件中,x=1(即所有人的智商均为1)
1:无限制

评分标准

如果你的答案与标准答案的相对误差在10−7以内或绝对误差在10−7以内,则被判定为正确。

如果你的所有答案均为正确,则得满分,否则得0分。

请注意输出格式:每行输出一个答案,答案只能为 unreachable 或者一个实数(建议使用科学计数法表示)。每行的长度不得超过50。错误输出格式会被判定为0分。

小R教你学数学

若函数f(x)的n阶导数在[a,b]区间内连续,则对f(x)在x0(x0∈[a,b])处使用n次拉格朗日中值定理可以得到带拉格朗日余项的泰勒展开式

f(x)=f(x0)+f′(x0)(x−x0)1!+f″(x0)(x−x0)22!+⋯+f(n−1)(x0)(x−x0)n−1(n−1)!+f(n)(ξ)(x−x0)nn!,x∈[a,b]

其中,当x>x0时,ξ∈[x0,x]。当x<x0时,ξ∈[x,x0]。

f(n)表示函数f的n阶导数

Solution

数据可以私信我……
LCT的题目,比较裸。关键是怎么维护函数的性质。
考虑题目后面告诉我们的数学知识,我们可以把函数转换成k次多项式系数表示的方式,这三个函数的k阶导数都比较好求,为了好算我们取公式中的x0为0,然后只需要保存下来每个节点函数的k次项系数。本人亲测k要取10以上才能保证精度。这样的话维护系数很方便。为了提高精度我们还可以把式子中的阶乘项在统计答案的时候再除(不过好像没必要)。
然后就是普通的LCT操作了……

代码:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

inline int read(){
    int xx=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())xx=xx*10+ch-'0';
    return xx*f;
}

const int maxn=100010,max0=10;
struct node{
    int fa,ch[2];
    double sum[max0+1],data[max0+1];
    bool is_root,reverse;
}T[maxn];
int n,m,num;
char type[maxn];

int getson(int x){
    return (x==T[T[x].fa].ch[1]);
}
void pushreverse(int x){
    if(!x)return;
    swap(T[x].ch[0],T[x].ch[1]);
    T[x].reverse^=1;
}
void pushdown(int x){
    if(T[x].reverse){
        pushreverse(T[x].ch[0]);
        pushreverse(T[x].ch[1]);
        T[x].reverse=false;
    }
}
void update(int x){
    memset(T[x].sum,0,sizeof T[x].sum);
    for(int i=0;i<=max0;i++)T[x].sum[i]+=T[x].data[i];
    if(T[x].ch[0]){
        for(int i=0;i<=max0;i++)T[x].sum[i]+=T[T[x].ch[0]].sum[i];
    }
    if(T[x].ch[1]){
        for(int i=0;i<=max0;i++)T[x].sum[i]+=T[T[x].ch[1]].sum[i];
    }
}
void rotate(int x){
    if(T[x].is_root)return;
    int k=getson(x),fa=T[x].fa,fafa=T[fa].fa;
    pushdown(fa);pushdown(x);
    T[fa].ch[k]=T[x].ch[k^1];
    if(T[x].ch[k^1])T[T[x].ch[k^1]].fa=fa;
    T[x].ch[k^1]=fa;T[fa].fa=x;
    T[x].fa=fafa;
    if(!T[fa].is_root)T[fafa].ch[fa==T[fafa].ch[1]]=x;
    else T[x].is_root=true,T[fa].is_root=false;
    update(fa);update(x);
}
void push(int x){
    if(!T[x].is_root)push(T[x].fa);
    pushdown(x);
}
void Splay(int x){
    push(x);
    for(int fa;!T[x].is_root;rotate(x)){
        if(!T[fa=T[x].fa].is_root){
            rotate((getson(x)==getson(fa))?fa:x);
        }
    }
}
void access(int x){
    int y=0;
    do{
        Splay(x);pushdown(x);
        T[T[x].ch[1]].is_root=true;
        T[T[x].ch[1]=y].is_root=false;
        update(x);x=T[y=x].fa;
    }while(x);
}
void mroot(int x){
    access(x);Splay(x);pushreverse(x);
}
void link(int u,int v){
    mroot(u);T[u].fa=v;
}
void cut(int u,int v){
    mroot(u);
    Splay(v);
    T[T[v].ch[0]].fa=T[v].fa;
    T[T[v].ch[0]].is_root=true;
    update(T[v].ch[0]);
    T[v].fa=0;T[v].ch[0]=0;
}
bool judge(int u,int v){
    while(T[u].fa)u=T[u].fa;
    while(T[v].fa)v=T[v].fa;
    return u==v;
}
void get_sin(int x,double a,double b){
    T[x].data[0]=sin(b);
    double f=1,temp=a;
    for(int i=1;i<=max0;i++,temp*=a){
        if(!(i&1)){
            f*=-1;
            T[x].data[i]=f*temp*sin(b);
        }
        else T[x].data[i]=f*temp*cos(b);
    }
}
void get_pow(int x,double a,double b){
    double temp=1;
    for(int i=0;i<=max0;i++,temp*=a){
        T[x].data[i]=temp*exp(b);
    }
}
void get_funtion(int x,double a,double b){
    T[x].data[0]=b;T[x].data[1]=a;
    for(int i=2;i<=max0;i++)T[x].data[i]=0;
}

int main(){
    freopen("math.in","r",stdin);
    freopen("math.out","w",stdout);
    n=read();m=read();scanf("%*s");
    for(int i=1;i<=n;i++)T[i].is_root=true;
    for(int i=1,opt;i<=n;i++){
        double a,b;
        opt=read();scanf("%lf%lf",&a,&b);
        if(opt==1)get_sin(i,a,b);
        else if(opt==2)get_pow(i,a,b);
        else get_funtion(i,a,b);
        update(i);
    }
    while(m--){
        int u,v,f;
        double a,b,x;
        scanf("%s",type);
        if(type[0]=='a'){
            u=read();v=read();
            link(++u,++v);
        }
        else if(type[0]=='d'){
            u=read();v=read();
            cut(++u,++v);
        }
        else if(type[0]=='m'){
            u=read();f=read();scanf("%lf%lf",&a,&b);
            Splay(++u);
            if(f==1)get_sin(u,a,b);
            else if(f==2)get_pow(u,a,b);
            else get_funtion(u,a,b);
            update(u);
        }
        else{
            u=read();v=read();scanf("%lf",&x);
            if(judge(++u,++v)){
                mroot(u);access(v);Splay(u);
                double ans=0,temp=1,jie=1;
                for(int i=0;i<=max0;jie*=(++i),temp*=x){
                    ans+=T[u].sum[i]*temp/jie;
                }
                printf("%.10lf\n",ans);
            }
            else puts("unreachable");
        }
    }
    return 0;
}

Similar Posts:

  • [转载]清华高材生的金玉良言:永远不要说你已经尽力了!

    这是一位清华高材生的讲座报告,原题为<刻苦拼搏 攀登人生理想的巅峰>.原文转发于此,并改为现在这个标题,是因为这句话深深地刻在了我的脑海里:永远不要说你已经尽力了--这句话,值得我们所有的人记取,并随时随地提醒自己,告诫自己. 读罢此文,我想起了这样几句话:花儿为什么这样红?钢铁是怎样炼成的?不经一番寒彻骨,怎得梅花扑鼻香--世上所有荣誉的桂冠,都是用荆棘编织而成的!不怕做不到,就怕不想做:思想有多远,我们就能走多远-- 林语堂先生说过:人生不能无梦,无梦则无望,无望则无成,世界上做大事业的人

  • 李开复万字长文科普人工智能:AI是什么 将带我们去哪儿?

    新浪科技李根 整理报道 人工智能正以前所未有的态势汹涌而来,一方面是风投和创业创新,都把人工智能当做了下一个尚未被开垦的宝地:另一方面是应用,比起概念盛行的阶段,现在的无人车.AlphaGo等已经把人工智能技术带到了“看得到摸得着”的境地. 那人工智能到底是什么?这个领域包含哪些要素?它将如何改变当今世界,又面临哪些问题和瓶颈?对于人工智能的应用和商业化,哪些领域会最快显现效果出来? 在清华大学“清华学堂计算机科学实验班”题为<人工智能的黄金时代>的演讲中,创新工场董事长兼CEO李开复对“人工

  • 九月的哈尔滨

    金秋九月,美丽的哈尔滨! 9.24号我们从宁波飞往了美丽的哈尔滨,因为是哈尔滨,我们准备好了冬天的衣服,因为订不到火车票,我们只能飞机去,第一次做飞机,有激动有害怕,飞机不是直达的,中途还在沈阳停顿了一下,这样下来,一来一去就相当于做了四次飞机… 安全倒是没什么问题,就是耳朵难受了点,当天下午四点到达哈尔滨太平机场,确实有点冷,立马把带来的衣服全穿上,然后打的去了HIT华德学院,这次比赛的场地,弄完手续之后来到住的地方,其实还好,我们三个住三人间,除了房间小了点,马桶破了点,电视模糊了点,床硬了

  • 2016 Multi-University Training Contest 2 题解(待续)

    Acperience Born Slippy Call It What You Want Differencia Eureka Its All In The Mind Keep On Movin La Vie en rose Acperience 公式题 考场贪心乱搞版本: #include<bits/stdc++.h> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(

  • 1月12日清华2003年题 查找学生信息 教训总结

    1 #include "stdio.h" 2 #include "stdlib.h" 3 #include "string.h" 4 #include "math.h" 5 typedef struct stu 6 { 7 char num[100];//尽量开大数组 8 char name[100]; 9 char sex[3]; 10 int age; 11 }stu; 12 int main() 13 { 14 int

  • 我的清华考研路--写给今后考研的学弟学妹们(转自山东大学学生之家论坛,我的家)

    转自山东大学学生之家论坛,我的家,05级学长. [url]http://bbs.oursdu.com/thread-179164-1-1.html[/url] 2009年参加硕士生入学考试已经结束了,我以初试数学129,英语63,政治70,计算机专业基础141,总成绩403的成绩,被清华大学计算机系网络研究所录取.我觉得考研最重要的是信心,计划和坚持!大致上把我考研过程中经历个各个阶段和感受写下来.留下点东西给后来考研的研友们(特别是计算机统考的同学),希望能够给一点你们帮助,少走一点弯路. 一

  • 看看一位清华计算机专业的学生怎么看LINUX与WINDOWS的

    本文是一位清华退学学生所写!他的名字叫王垠,人很出名,不信GOOGLE一下就知道! 我已经半年没有使用 Windows 的方式工作了.Linux 高效的完成了我所有的工作. GNU/Linux 不是每个人都想用的.如果你只需要处理一般的事务,打游戏,那么你 不需要了解下面这些了. 我不是一个狂热的自由软件份子,虽然我很喜欢自由软件.这篇文章也不是用来推 行自由软件运动的,虽然我觉得自由软件运动是非常好的. 这篇文章也不是用来比较 Linux 和 Windows 内核效率,文件系统,网络服务的.

  • 一位清华计算机专业的学生怎么看LINUX与WINDOWS(一)

    我已经半年没有使用 Windows 的方式工作了.Linux 高效的完成了我所有的工作. GNU/Linux 不是每个人都想用的.如果你只需要处理一般的事务,打游戏,那么你 不需要了解下面这些了. 我不是一个狂热的自由软件份子,虽然我很喜欢自由软件.这篇文章也不是用来推 行自由软件运动的,虽然我觉得自由软件运动是非常好的. 这篇文章也不是用来比较 Linux 和 Windows 内核效率,文件系统,网络服务的. 我现在是作为一个用户而不是一个开发者来说话的,我们的讨论是基于操作,应用 层面的.是

  • 清华梦的粉碎-写给清华大学的退学申请

    作者:王垠 清华梦的诞生 小时候,妈妈给我一个梦.她指着一个大哥哥的照片对我说,这是爸爸的学生,他考上了清华 大学,他是我们中学的骄傲.长大后,你也要进入清华大学读书,为我们家争光.我不知道清华是什么样子,但是我知道爱迪生和牛顿的故事.清华,大概就是可以把我造就成他们这种人的地方吧.我幼小的脑海里就想象出我能在清华做的事情--我的脸上浮现出笑容.我说我要实现这个"清华梦".这就是清华梦的诞生. 小小科学家 我相信每个人在小时候都跟我差不多,对这个世界充满了好奇. 鲁迅有他的百草园,我也

  • hdu 4082 Hou Yi's secret(亚洲赛北京赛区B题)

    Hou Yi's secret Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 375 Accepted Submission(s): 120 Problem Description Long long ago, in the time of Chinese emperor Yao, ten suns rose into the sky. T

Tags: