回到目录

教育工作者被我们刷历年真题,

其一意义为什么要描绘吗,因为在前头做了一个前端的页面效果,使用JS写的,感觉格外烦,真的,对于一个文本框长度动态统计,你要写blur,press,down什么的风波,太辛苦了,这时,我想开了knockoutjs,这东西好,为什么,是盖它们够简单,够强大,这半沾于程序员来说,就是好!

下一场漫不经心的游说了一样句子:“你们就算先举行做noip2016
day1 吧”

先来拘禁一下页面的效益

统计 1

 

统计 2

当字数达到某个值经常,如10独字,这时文本框将未允许你再输入,这下了subscribe,而长和文框关的涉及应用了computed(dependentObservable依赖监视器也是可的),而何时去接触事件采取了valueUpdate属性afterkeydown属性值表示当键盘被据下经常触发.

。。。。。。

脚看一下实现的原代码

HTML代码

  <input type="text" data-bind="value:count,valueUpdate: 'afterkeydown'" />
  /10

JS代码

        /*computed valueUpdate等属性的学习*/
        self.count = ko.observable().extend({
            maxLength: { params: 10, message: "最大长度为10" },
            required: {
                params: true,
                message: "请输入字符..."
            }
        });
        self.count.subscribe(function (o) {//实现当大于某个长度时,只绑定指定长度的字符
            if (o.length > 10)
                self.count(o.substr(0, 10));
        });

        self.countLen = ko.computed(function () {
            return self.count() ? self.count().trim().length : 0;
        });

 

归来目录

 

自身还会说啊,,,,,老师你当时是明摆着伤害我们什么2333333333

 

 

预计分数:100+25+24

骨子里分数:100+25+12

 

 

T1:玩具谜题

题目叙述

小南生同样仿照可爱之玩意儿小人, 它们各有不同的生意。

来一致龙, 这些玩具小人把小南底眼镜藏了四起。
小南意识玩具小人们围成了一个环绕,它们有的面朝圈内,有的面朝圈外。如下图:

统计 3

这会儿singer告诉小南一个谜題:
“眼镜藏于自家左数第3只玩具小人之右数第1独玩具小人的左数第2个玩具小人那里。

小南意识, 这个谜题中玩具小人之朝向非常主要,
因为朝内和朝外的玩具小人之左右主旋律是相反的: 面朝圈内之玩意儿小人,
它的左手是顺时针方向, 右边是逆时针方向; 而面向圈外的玩意儿小人,
它的左手是逆时针方向, 右边是顺时针方向。

小南一边艰难地辨别着玩具小人, 一边数在:

singer朝内, 左数第3个是archer。

archer朝外,右数第1个是thinker。

thinker朝外, 左数第2个是writer。

用眼镜藏于writer这里!

尽管打响找回了眼镜, 但小南并没有放心。
如果生浅发生重新多的玩具小人藏他的镜子, 或是谜題的尺寸还增长,
他恐怕就无法找到眼镜了 。 所以小南望您写程序救助他解决类似之谜題。
这样的谜題具体可以描述为:

来 n独玩具小人围成一缠,
已解其的事情和通往。现在第1单玩具小人告诉小南一个饱含 m漫长指令的谜題,
其中第 z条指令形如“左数/右数第 s,个玩具小人”。
你得输出依次数了这些指令后,到达的玩意儿小人之职业。

输入输出格式

输入格式:

 

输入的第一执行包含两只刚刚整数 n,m, 表示玩具小人的个数与指令的条数。

连下 n行, 每行包含一个整数和一个字符串,
以逆时针为各个为闹每个玩具小人的向和职业。其中0表示为为围内,
1表示于为圈外。保证不会见现出其他的勤。字符串长度不超过10都仅由小写字母构成,
字符串不也空, 并且字符串两点儿勿与。 整数和字符串之问用一个空格隔开。

连下去 m行,其中第 z行包含两只整数 a,,s,,表示第 z条指令。若 a,=
0,表示为左数 s,个人;若a,= 1 ,表示于右数 s,个人。保证a,不会见产出其它的往往,
1≤ s,<n 。

 

出口格式:

 

输出一个字符串, 表示于第一只读入的小人开始, 依次数完
m条指令后到的小人的生意。

 

输入输出样例

输入样例#1:

7 3
0 singer
0 reader
0 mengbier 
1 thinker
1 archer
0 writer
1 mogician 
0 3
1 1
0 2

输出样例#1:

writer

输入样例#2:

10 10
1 C
0 r
0 P
1 d
1 e
1 m
1 t
1 y
1 u
0 V
1 7
1 1
1 4
0 5
0 3
0 1
1 6
1 2
0 8
0 4

出口样例#2:

y

说明

【样例1说明】

即组数就是是【题目叙述】 中提到的例子。

【子任务】

分任务会吃有部分测试数据的表征。 如果你当缓解题目中遇到了困难,
可以尝尝只解决部分测试数据。

每个测试点的数规模与特点如下表:

统计 4

中部分简写的排意义如下:

• 全往内: 若为“√”, 表示该测试点保证拥有的玩具小口且于为圈内;

全左数:若为“√”,表示该测试点保证有的通令都于左数,即针对随意的

1≤z≤m, ai=0;

s,= 1:若否“√”,表示该测试点保证拥有的一声令下都仅仅一再1单,即针对自由的

1≤z≤m, si=1;

事情长度也1 :若否“√”,表示该测试点保证拥有玩具小人之事一定是一个

长也1的字符串。

 

 

思路:纯模仿,可以为此数组,理论及呢得以就此双朝向链表(但是真正考场上发生号老佬炸了,只得了20.。。)。

     

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=100001;
 7 int n,m,how,step;
 8 struct node
 9 {
10     string name;
11     int to;
12 }a[MAXN];
13 int read(int &n)
14 {
15     char ch=' ';int q=0,w=1;
16     for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
17     if(ch=='-')w=-1,ch=getchar();
18     for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;
19     n=q*w;    return n;
20 }
21 int main()
22 {
23     //freopen("toya.in","r",stdin);
24     //freopen("toya.out","w",stdout);
25     read(n);read(m);
26     //scanf("%d%d",&n,&m);
27     //ios::sync_with_stdio(false);
28     for(int i=1;i<=n;++i)
29     {
30         read(a[i].to);
31         //scanf("%d",&a[i].to);
32         //cout<<a[i].to<<"*************"<<endl;
33         // 0朝向圈内  1朝向圈外 
34         cin>>a[i].name;
35     }
36     int where=1;
37     for(int i=1;i<=m;++i)
38     {
39         read(how);read(step);
40         //scanf("%d%d",&how,&step);
41         // 0向左数,1向右数
42         if(how==0)
43         {
44             if(a[where].to==0)// 向内
45             {
46                 where=where-step;
47                 if(where<=0)
48                 where=where+n;    
49             }
50             else if(a[where].to==1)// 向外 
51             {
52                 where=where+step;
53                 if(where>n)
54                 where=where-n;
55             }
56         }
57         else// 向右数 
58         {
59             if(a[where].to==0)
60             {
61                 where=where+step;
62                 if(where>n)
63                 where=where-n;
64             }
65             else
66             {
67                 where=where-step;
68                 if(where<=0)
69                 where=where+n;    
70             }
71         }
72     }
73     cout<<a[where].name;
74     return 0;
75 }

 

 

T2:天天爱跑步

题材叙述

小c同学觉得跑步非常有趣,于是决定打造一款名叫《天天好跑步》的玩耍。«天天好跑步»是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。

是玩的地形图可以看做一均等株包含 nn个结点和 n-1n−1条边的培育,
每条边连接两独结点,且随意两独结点存在一样漫漫途径互相可达。树上结点编号吧打11及nn的连续正整数。

今昔发mm个玩家,第ii单玩家的起点为 S_iS​i​​,终点为 T_iT​i​​ 。每天打卡任务开始经常,所有玩家在第00秒同时从自己的起点出发, 以每秒跑同长达边的快慢,
不停顿地沿着最缺乏路径向着好之顶峰跑去,
跑至终点后该玩家就成功了打卡任务。 (由于地图是一致棵树,
所以每个人之门路是唯一的)

小C想清楚打之活跃度, 所以在每个结点上还停了一个观察员。 在结点jj的观察员会选择在第W_jW​j​​秒观察玩家,
一个玩家会为此观察员观察到当且只当该玩家在第W_jW​j​​秒也理到达了结点 jj 。
小C想清楚每个观察员会观察到小人?

在意: 我们以为一个玩家到达自己的极限后该玩家就会见结游戏, 他莫可知等一
段岁月晚重新叫观察员观察到。 即对于把结点jj作为终点的玩家: 若他在第W_jW​j​​秒重到终点,则当结点jj的观察员不能够体察到拖欠玩家;若他碰巧在第W_jW​j​​秒到达终点,则当结点jj的观察员可以考察到这玩家。

输入输出格式

输入格式:

 

第一尽有有限独整数nn和mm 。其中nn代表树的结点数量, 同时为是观察员的数, mm代表玩家的数。

通下 n- 1n−1行每行两个整数uu和 vv,表示结点 uu到结点 vv有平等长条边。

属下去一行 nn个整数,其中第jj个整数为W_jW​j​​ , 表示结点jj出现观察员的年月。

紧接下去 mm行,每行两独整数S_iS​i​​,和T_iT​i​​,表示一个玩家的起点和顶峰。

对有着的多少,保证1\leq
S_i,T_i\leq n, 0\leq W_j\leq n1≤S​i​​,T​i​​≤n,0≤W​j​​≤n 。

 

输出格式:

 

出口1行 nn个整数,第jj单整数表示结点jj的观察员可以洞察到有些人口。

 

输入输出样例

输入样例#1:

6 3
2 3
1 2 
1 4 
4 5 
4 6 
0 2 5 1 2 3 
1 5 
1 3 
2 6 

出口样例#1:

2 0 0 1 1 1 

输入样例#2:

5 3 
1 2 
2 3 
2 4 
1 5 
0 1 0 3 0 
3 1 
1 4
5 5 

出口样例#2:

1 2 1 0 1 

说明

【样例1说明】

对于1号点,W_i=0W​i​​=0,故只来起点为1声泪俱下点之玩家才会受考察到,所以玩家1跟玩家2被考察到,共有2人口叫考察到。

对2哀号点,没有玩家在第2秒时以这结点,共0人口深受考察到。

对3哀号点,没有玩家当第5秒时当是结点,共0丁吃考察到。

对于4号点,玩家1吃考察到,共1人口受观察到。

对此5如泣如诉点,玩家1受观察到,共1丁叫考察到。

于6声泪俱下点,玩家3叫考察到,共1人口吃观察到。

【子任务】

每个测试点的多寡规模及特点如下表所示。 提示:
数据范围之个位上的数字可以帮助判断是啦一样种多少类。

统计 5

【提示】

比方你的次用用较生之栈空问 (这一般意味着需要比生层数的递归),
请务必仔细翻阅选手日录下的文件当rumung:/stact.p″,
以了解在最后评测时栈空问的限定与当当前工作环境下调整栈空问限制的方式。

在结尾评测时,调用栈占用的空间尺寸不见面发出单独的限制,但以咱们的办事

条件遭到默认会起 8 MB 的范围。 这或会见招函数调用层数较多时, 程序发生

栈溢出崩溃。

咱俩可使有艺术修改调用栈的大大小小限制。 例如, 在极限中输入下列命

令 ulimit -s 1048576

是命令的义是,将调用栈的深浅限制修改为 1 GB。

诸如,在运动员目录建立如下 sample.cpp 或 sample.pas

统计 6

用上述源代码编译为可执行文件 sample 后,可以当极限中运作如下命令下

行该程序

./sample

若在尚未利用命令“ ulimit -s 1048576”的状下运行该次, sample

会晤因为栈溢出要夭折; 如果下了上述命令后运行该次,该次则无会见倒。

特意地, 当你打开多只终端时, 它们并无见面共享该令, 你要各自对它们

运作该令。

伸手小心, 调用栈占用的半空中会计入总空间占据着, 和次序外部分占用的外

存共同面临内存限制。

 

思路:感觉会骗好多丛分叉,但是本人或顶死了,写了25细分的暴力就从来不工夫了。。。

正解:
已超能力范围,怎么看还扣留不理解。。。。

援一下人家的:

25分

  考虑这统计 7n很粗,可以对各条路上暴力模拟,经过某个点时可以关押一下手上天天,是否以及经过的触发之统计 8w相等,如果当,则贡献加同。

 

45分

  注意到测试点统计 9统计 10统计 11统计 129−12时,保证统计 13m条路径的落脚点都是统计 141,那么我们可以设想要用统计 151作为树根,那么等同长条路怎样才能对于它经过的触发有贡献。

  不难看出对于一个触及统计 16i,只有在统计 17统计 18统计 19统计 20统计 21统计 22统计 23统计 24统计 25统计 26统计 27统计 28deep[i]=w[i],才发出或发贡献。

  我当考场上是一直用之链剖统计 29+线段树,因为这就改为模板题了,而且统计 30n不到统计 31统计 32统计 3310w,尽管复杂度偏大,但是对错。

  直接对每条路线经过的点在线段树上增加统计 341不良经过次数,显然只有统计 35统计 36统计 37统计 38deep与统计 39w相等的点才见面发生贡献。

  事实上对统计 40统计 41统计 42S=1的状态有线性的算法,正解会详细介绍,不再赘言。

 

60分

  注意到测试点统计 43统计 44统计 456−8时,题目保证培训退化成链。我们着眼一下对于链而言,有什么特别的地方。首先使显著,此时m条路径在链上肯定是要为左或为右侧,即统计 46统计 47统计 48统计 49S<=T或者统计 50统计 51统计 52S>T。

  先只考虑统计 53统计 54统计 55统计 56S<=T的情事,如果对统计 57S到统计 58T之间的点i,要产生贡献的口舌,肯定满足统计 59统计 60统计 61统计 62统计 63统计 64统计 65统计 66i−S=w[i],移项可得统计 67统计 68统计 69统计 70统计 71统计 72统计 73统计 74S=i−w[i]经常才得以满足要求。

  注意到等式右边只及统计 75i本身有关,不妨设为统计 76统计 77统计 78统计 79K[i],所以问题改成了查询统计 80S到统计 81T之间统计 82统计 83统计 84统计 85K[i]等于统计 86S的统计 87i的数量。

  因为问题就涉嫌到首暨尾,我们可非常轻联想到差分,即对统计 88S打上统计 89统计 90+1标记,统计 91T打上统计 92统计 93−1标记。

  根据上述思路,我们考虑具体做法:对于每个点统计 94i,我们很轻发现只有从一个特定的点出发才来或对统计 95i产生贡献。

  我们着想保护一个统计数组统计 96A,统计 97统计 98统计 99统计 100A[k]意味着的凡拍卖到目前的结点时,从统计 101k出发的门径(而且还没有挪动及终极)有多少条。

  这样对每个点统计 102i,我们如果查询一下所对应的统计 103统计 104统计 105统计 106统计 107统计 108统计 109A[K[i]]纵使足以了,根据上面的分析,这就是我们的答案了。

  有几许瞩目处理:处理一个触及统计 110i时,我们需要把为统计 111i为起点的门路在统计数组统计 112A,再计是结点的献,最后再次将以这结点为巅峰的不二法门从统计 113A中清除,具体可就此统计 114统计 115统计 116统计 117统计 118统计 119vector实现(上述处理顺序的必要性仔细琢磨就杀爱想接了)。

  而对于统计 120统计 121统计 122S>T的情景了类似,只是需要把统计 123统计 124统计 125统计 126K[i]定义为统计 127统计 128统计 129统计 130统计 131统计 132i+w[i],其余做法了类似。

      

100分

  题目中设计之几个档次的有分其实暗示已特别明显了。

  链的做法去正解就无远了。

  而统计 133统计 134统计 135S=1和统计 136统计 137统计 138T=1凡以报我们什么吧?

  拆路径!

  很易察觉,一长达统计 139S到统计 140T的路子可以拆成一长条统计 141S到统计 142统计 143统计 144LCA的不二法门和统计 145统计 146统计 147LCA到统计 148T的路径,然后对当下片漫漫路径,一漫漫向上,一修向下,都好对应成链的处理方式了!

  考虑对于各条途径,先将该拆分成稀长条路(为了简化对统计 149统计 150统计 151LCA在片漫长路子中还冒出的各种气象,我们可以预先就为统计 152统计 153统计 154LCA出现个别次等,如果最终发现统计 155统计 156统计 157LCA是有贡献的,只待统计 158统计 159−1即可),同样,我们先行只考虑发展的不二法门。

  如果我们于统计 160S在统计数组统计 161A上打上统计 1621的标记,统计 163统计 164统计 165LCA于统计数组统计 166A上打上统计 167统计 168−1的记号,那么题目转化为求一个碰之子树和。

  考虑上述做法科学:因为只有统计 169S到统计 170统计 171统计 172LCA路径之间的点会产生贡献,而当这个点放在路径之间常,子树和见面有统计 1731的贡献,而在统计 174S的子树中还是统计 175统计 176统计 177LCA的头还非会见出贡献。

  具体实现啊?

  对于一个碰统计 178i,产生贡献的极是统计 179统计 180统计 181统计 182统计 183统计 184统计 185统计 186统计 187统计 188统计 189统计 190统计 191统计 192统计 193统计 194统计 195统计 196统计 197统计 198deep[S]−deep[i]=w[i],同样令统计 199统计 200统计 201统计 202统计 203统计 204统计 205统计 206统计 207统计 208统计 209统计 210统计 211统计 212统计 213统计 214统计 215K[i]=deep[i]+w[i],当我们统计 216统计 217统计 218dfs到统计 219i时查询统计 220统计 221统计 222统计 223统计 224统计 225统计 226A[k[i]]的值即为孝敬。

  为了保科学,我们想想统计答案的方法和顺序。

  首先我们自然是当拍卖完统计 227i的子树之后还来处理统计 228i(想想就清楚了),然后我们要重把为统计 229i出发的开拓进取的不二法门在统计数组,再开展询问,最后将为统计 230i为终端的门径所生的孝敬在统计数组统计 231A中革除即可。

  注意到我们地方维护的无非是一个碰之深,由于同一深度的点众多,所以我们询问的下会发觉会管非以同一子树的触发统计称答案,那怎么惩罚吧?我们着想对于一个触及而查询子树和,肯定是一旦单独地考虑这一个子树的孝敬,所以我们好记录进入统计 232i时统计 233统计 234统计 235统计 236统计 237统计 238统计 239A[k[i]]的值,再于访了统计 240i的子树之后统计答案时,看一下这时候新的统计 241统计 242统计 243统计 244统计 245统计 246统计 247A[k[i]]的值。

  容易觉察新的价值减掉进入时的,才是确实的统计 248i的子树中之统计 249统计 250统计 251统计 252统计 253统计 254统计 255A[k[i]]的值。

  这样我们不怕得避将别的子树的答案统计进来了。

  对于向下之接触做法类似,有好几繁杂的地方便等式变成了统计 256统计 257统计 258统计 259统计 260统计 261统计 262统计 263统计 264统计 265统计 266统计 267统计 268统计 269统计 270统计 271统计 272统计 273统计 274统计 275统计 276统计 277统计 278统计 279deep[T]−deep[i]=len−w[i](统计 280统计 281统计 282len为路径长度),发现只要如此做的语会出现负数,那么我们就算将统计数组向右侧平移统计 283统计 284统计 285统计 286统计 2873∗105位就是足以了。

  上述做法要下的凡倍增求统计 288统计 289统计 290LCA的话语,复杂度就是统计 291统计 292统计 293统计 294统计 295统计 296统计 297统计 298O(nlogn);

  如果用统计 299统计 300统计 301统计 302统计 303统计 304tarjan离线求统计 305统计 306统计 307LCA的语句,可以成功统计 308统计 309统计 310统计 311统计 312统计 313O(n+m)。

 

 

25分代码:

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<algorithm>
  5 using namespace std;
  6 const int MAXN=600001;
  7 const int INF=0x7fffff;
  8 inline void read(int &n)
  9 {
 10     char c=getchar();n=0;bool flag=0;
 11     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
 12     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
 13 }
 14 struct node
 15 {
 16     int u,v,nxt;
 17 }edge[MAXN];
 18 int head[MAXN];
 19 int num=1;
 20 inline void add_edge(int x,int y)
 21 {
 22     edge[num].u=x;
 23     edge[num].v=y;
 24     edge[num].nxt=head[x];
 25     head[x]=num++;
 26 }
 27 int n,m;
 28 int W[MAXN];
 29 struct Player
 30 {
 31     int bg,ed;
 32 }player[MAXN];
 33 int dis[MAXN];
 34 int vis[MAXN];
 35 int PointPre[MAXN];
 36 int ans[MAXN];
 37 inline void SPFA(int S,int T)
 38 {
 39     for(int i=0;i<=n+1;i++)    dis[i]=INF,vis[i]=0,PointPre[i]=-1;
 40     queue<int>q;dis[S]=0;vis[S]=1;
 41     q.push(S);
 42     while(!q.empty())
 43     {
 44         int p=q.front();q.pop();
 45         vis[p]=0;
 46         for(int i=head[p];i!=-1;i=edge[i].nxt)
 47         {
 48             if(dis[edge[i].v]>dis[edge[i].u]+1)
 49             {
 50                 dis[edge[i].v]=dis[edge[i].u]+1;
 51                 PointPre[edge[i].v]=edge[i].u;
 52                 if(!vis[edge[i].v])
 53                     q.push(edge[i].v),vis[edge[i].v]=1;
 54             }
 55         }
 56     }    
 57 }
 58 void Calc(int S,int T)
 59 {
 60     int NowPoint=T,NowTime=0;
 61     while(PointPre[NowPoint]!=-1)
 62     {
 63         NowPoint=PointPre[NowPoint];
 64         NowTime++;
 65     }
 66     NowPoint=T;
 67     while(PointPre[NowPoint]!=-1)
 68     {
 69         if(W[NowPoint]==NowTime)
 70             ans[NowPoint]++;
 71         NowTime--;
 72         NowPoint=PointPre[NowPoint];
 73     }
 74     if(W[NowPoint]==NowTime)
 75         ans[NowPoint]++;
 76 }
 77 int main()
 78 {
 79     memset(head,-1,sizeof(head));
 80     read(n);read(m);
 81     for(int i=1;i<=n-1;i++)
 82     {int x,y;read(x);read(y);add_edge(x,y);add_edge(y,x);}
 83     for(int i=1;i<=n;i++)    read(W[i]);//观察员出现的时间 
 84     for(int i=1;i<=m;i++)
 85     {read(player[i].bg);read(player[i].ed);}
 86     
 87     if(n%10==4)
 88     {
 89         for(int i=1;i<=n;i++)
 90         {
 91             int nt=0;
 92             if(player[i].bg>player[i].ed)
 93             {
 94                 for(int j=player[i].bg;j>=player[i].ed;j--)
 95                     if(W[j]==nt)    ans[j]++;
 96                 nt++;
 97             }
 98             else
 99             {
100                 for(int j=player[i].bg;j<=player[i].ed;j++)
101                     if(W[j]==nt)    ans[j]++;
102                 nt++;
103             }
104         }
105         for(int i=1;i<=n;i++)
106             printf("%d ",ans[i]);
107     }
108     else
109     {
110         for(int i=1;i<=m;i++)
111         {SPFA(player[i].bg,player[i].ed);
112          Calc(player[i].bg,player[i].ed);}
113         
114         for(int i=1;i<=n;i++)
115             printf("%d ",ans[i]);    
116     }
117     
118     
119     return 0;
120 }

 

 

T3:换教室

 

题目叙述

对刚刚上大学的牛牛来说,他面临的率先只问题是怎么样根据实际状况申请当的课程。

在可以挑选的课被,有 2n2n 节课程安排在 nn 个日子段达到。在第 ii(1
\leq i \leq n1≤i≤n)个时间段达到,两节内容一致的教程又以不同之地点开展,其中,牛牛预先让部署在教室 c_ic​i​​ 上课,而别一样节省课程在教室 d_id​i​​ 进行。

每当未交任何申请之状态下,学生等要按照时间段的各个依次完成有着的 nn 节布置好的课程。如果生想变第 ii 节课程的教室,则要提出申请。若申请经过,学生便足以以第 ii 个时间段去教室 d_id​i​​ 上课,否则还是在教室 c_ic​i​​ 上课。

鉴于换教室的需要最多,申请免自然能获得通过。通过计算,牛牛发现申请换第 ii 节课程的教室时,申请被通过的几率是一个曾掌握之实数 k_ik​i​​,并且于不同科目的提请,被通过的票房价值是相独立的。

全校规定,所有的提请只能当学期起前一次性交给,并且每个人只能选择到多 mm 节课程进行报名。这代表牛牛必须一次性决定是否申请换每节课的教室,而不克因一些科目的提请结果来支配另外学科是否申请;牛牛可以申请自己无比盼望更换教室的 mm 门课程,也可不用完马上 mm 个申请之机会,甚至足以同样派系科目都无提请。

坐不同的教程或会见于安排在不同之教室进行,所以牛牛需要以课间日打平中教室赶到另一样间教室。

牛牛所当的高校有 vv 个教室,有 ee 条道路。每条道连接两里面教室,并且是可双向通行的。由于道路的长短和拥挤程度不一,通过不同之道耗费的体力可能会见迥然不同。
当第 ii(1 \leq i \leq n-11≤i≤n−1)节课结束后,牛牛就见面打立节课的教室出发,选择同一长长的吃体力最为少之不二法门前往下一致节省课的教室。

现牛牛想知道,申请哪几宗课程可以要他坐在教室中间活动耗费的体力值的总和的梦想值最小,请您拉他告出这极小价。

输入输出格式

输入格式:

 

首先履四单整数 n,m,v,en,m,v,e。nn 代表这学期内的流年段的多寡;mm 表示牛牛最多足报名换多少节课的教室;vv 表示牛牛学校里教室的数;ee表示牛牛的学校里道路的数码。

次实施 nn 个正整数,第 ii(1
\leq i \leq n1≤i≤n)个刚整数表示 c_ic​i​​,即第 ii 个时间段牛牛被部署上课的教室;保证 1 \le c_i \le v1≤c​i​​≤v。

其三实行 nn 个正整数,第 ii(1
\leq i \leq n1≤i≤n)个刚刚整数表示 d_id​i​​,即第 ii 个时间段外一样内部及平等课程的教室;保证 1 \le d_i \le v1≤d​i​​≤v。

第四行 nn 个实数,第 ii(1
\leq i \leq n1≤i≤n)个实数表示 k_ik​i​​,即牛牛申请当第 ii 个时间段更换教室获得通过的概率。保证 0 \le k_i \le 10≤k​i​​≤1。

搭下 ee 行,每行三独正整数 a_j, b_j, w_ja​j​​,b​j​​,w​j​​,表示来同一条双向道路连接教室 a_j, b_ja​j​​,b​j​​,通过就漫漫道需要消耗的体力值是 w_jw​j​​;保证 1 \le a_j, b_j \le v1≤a​j​​,b​j​​≤v, 1
\le w_j \le 1001≤w​j​​≤100。

保证 1 \leq n \leq
20001≤n≤2000,0 \leq m \leq 20000≤m≤2000,1 \leq v \leq 3001≤v≤300,0
\leq e \leq 900000≤e≤90000。

担保通过学校里之道,从外一样中间教室出发,都能抵达任何所有的教室。

管教输入的实数最多含 33 位小数。

 

输出格式:

 

输出一行,包含一个实数,四放弃五切精确到多少数点后刚好22号,表示答案。你的出口必须跟正式输出了一样才终于对。

测试数据保证四放弃五符合后底答案和标准答案的不等的绝对化值不浮 4 \times 10^{-3}4×10​−3​​。
(如果你免掌握呀是浮点误差,这段话可以知道呢:对于大多数之算法,你得健康地以浮点数类型而无用对她进行出格之处理)

 

输入输出样例

输入样例#1:

3 2 3 3
2 1 2
1 2 1
0.8 0.2 0.5 
1 2 5
1 3 3
2 3 1

输出样例#1:

2.80

说明

【样例1说明】

不无中的申请方案和希望收益如下表:

统计 314

【提示】

  1. 道路被或会见发出差不多修双向道路连接相同之鲜中间教室。
    也起或发道两端连接

的凡相同间教室。

2.请求注意区分n,m,v,e的义, n不是教室的数, m不是道路的数目。

统计 315

独特性质1:图上随便两触及 ai, bi, ai≠
bi间,存在同样久吃体力最为少的路线只包含一长达道。

奇异属性2:对于持有的1≤ i≤ n, ki= 1 。

483 055 310

 

Noip历年以来的率先道概率题

自我同样开始想到了24分割的做法,就是m=0的状态,

再有平等栽80分叉的做法,暴力枚举换不更换。

100私分的做法是DP

用dp[i][j][0]意味着前i个时间段,已经转移了j个,第i单不移的图景,dp[i][j][1]意味着换的情况,

换方程需要考虑:

1.这次移不转换

2.上次换没换

3.对各一样种植情景的想望,

接下来因期望有线性的原理,

增长即可

注意在读入边的早晚要新鲜判断一下

 

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=2001;
 7 const int INF=0x7ffff;
 8 inline void read(int &n)
 9 {
10     char c=getchar();n=0;bool flag=0;
11     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
12     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
13 }
14 int n,m,v,e;
15 int C[MAXN],D[MAXN];
16 double K[MAXN];// 概率
17 double dis[MAXN][MAXN];
18 double dp[MAXN][MAXN][3];
19 inline void floyed()
20 {
21     /*for(int k=1;k<=v;k++)
22         for(int i=1;i<=v;i++)
23             for(int j=1;j<=v;j++)
24                 if(dis[i][j]>dis[i][k]+dis[k][j])    dis[i][j]=dis[i][k]+dis[k][j];*/
25     for(int k=1;k<=v;k++)
26         for(int i=1;i<=v;i++)
27             if(k!=i)
28                 for(int j=1;j<=v;j++)
29                     if(i!=j && j!=k)
30                         dis[j][i]=dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
31     for(int i=0;i<=n;i++)
32     {
33         for(int j=0;j<=m;j++)
34             dp[i][j][0]=dp[i][j][1]=INF;
35     }
36     dp[1][0][0]=0;dp[1][1][1]=0;
37 }
38 inline void DP()
39 {
40     for(int i=2;i<=n;i++)// 每一个时间段
41     {
42         for(int j=0;j<=m;j++)// 可以提出申请的次数
43         {
44             if(j==0)
45                 dp[i][j][0]=dp[i-1][j][0]+dis[C[i]][C[i-1]];
46             else
47             {
48                 dp[i][j][0]=min( dp[i-1][j][0] + dis[C[i]][C[i-1]] ,
49                                  dp[i-1][j][1] + dis[C[i]][D[i-1]] * K[i-1] +
50                                                   dis[C[i]][C[i-1]] * (1-K[i-1]));
51                 // 本次不提出申请
52                 dp[i][j][1]=min( dp[i-1][j-1][0] + dis[D[i]][C[i-1]] * K[i]
53                                                  + dis[C[i]][C[i-1]] * (1-K[i]) ,
54                                  dp[i-1][j-1][1] + dis[D[i]][D[i-1]] * K[i] * K[i-1]
55                                                   + dis[D[i]][C[i-1]] * K[i] * (1-K[i-1])
56                                                  + dis[C[i]][D[i-1]] * (1-K[i]) * K[i-1]
57                                                  + dis[C[i]][C[i-1]] * (1-K[i]) * (1-K[i-1]));           
58             }
59         }
60     }
61     double ans=438438438;
62         for(int j=0;j<=m;j++)
63             ans=min(ans,min(dp[n][j][0],dp[n][j][1]));
64     printf("%.2lf",ans);
65 }
66 int main()
67 {
68     //freopen("classrooma.in","r",stdin);
69     //freopen("classrooma.out","w",stdout);
70     read(n);read(m);read(v);read(e);
71     for(int i=1;i<=n;i++)    read(C[i]);
72     for(int i=1;i<=n;i++)    read(D[i]);
73     for(int i=1;i<=n;i++)    scanf("%lf",&K[i]);
74     for(int i=1;i<=v;i++)
75     {
76         for(int j=1;j<=v;j++)
77             dis[i][j]=INF;
78             dis[i][i]=0;
79     }
80     for(int i=1;i<=e;i++)
81     {
82  
83         int x,y;double z;
84         read(x);read(y);scanf("%lf",&z);
85         dis[y][x]=dis[x][y]=min(dis[x][y],z);
86     }
87     floyed();
88     DP();
89     return 0;
90 }