首页 > > 程序设计 > C/C++ >

Noip 2016 Day1 题解

2018-06-17 21:57:01来源：未知阅读 ()

老师让我们刷历年真题，

然后漫不经心的说了一句：“你们就先做做noip2016 day1 吧”

。。。。。。

我还能说什么，，，，，老师你这是明摆着伤害我们啊2333333333

预计分数：100+25+24

实际分数：100+25+12

T1：玩具谜题

题目描述

小南有一套可爱的玩具小人, 它们各有不同的职业。

有一天, 这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈,它们有的面朝圈内,有的面朝圈外。如下图:

这时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：

输出样例#2：

说明

【样例1说明】

这组数据就是【题目描述】中提到的例子。

【子任务】

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难, 可以尝试只解决一部分测试数据。

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

其中一些简写的列意义如下:

• 全朝内: 若为“√”, 表示该测试点保证所有的玩具小人都朝向圈内;

全左数:若为“√”,表示该测试点保证所有的指令都向左数,即对任意的

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同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。«天天爱跑步»是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。

这个游戏的地图可以看作一一棵包含

现在有 $S_iS?i??,终点为 T_iT?i?? 。每天打卡任务开始时,所有玩家在第00秒同时从自己的起点出发, 以每秒跑一条边的速度, 不间断地沿着最短路径向着自己的终点跑去, 跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树, 所以每个人的路径是唯一的)$

小C想知道游戏的活跃度, 所以在每个结点上都放置了一个观察员。在结点 $jj的观察员会选择在第W_jW?j??秒观察玩家, 一个玩家能被这个观察员观察到当且仅当该玩家在第W_jW?j??秒也理到达了结点 jj 。小C想知道每个观察员会观察到多少人?$

注意: 我们认为一个玩家到达自己的终点后该玩家就会结束游戏, 他不能等待一段时间后再被观察员观察到。即对于把结点 $若他在第W_jW?j??秒重到达终点,则在结点jj的观察员不能观察到该玩家;若他正好在第W_jW?j??秒到达终点,则在结点jj的观察员可以观察到这个玩家。$

输入输出格式

输入格式：

第一行有两个整数

接下来

接下来一行 $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行

输入输出样例

输入样例#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：

输出样例#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人被观察到。

【子任务】

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

【提示】

如果你的程序需要用到较大的栈空问 (这通常意味着需要较深层数的递归), 请务必仔细阅读选手日录下的文本当rumung:/stact.p″, 以了解在最终评测时栈空问的限制与在当前工作环境下调整栈空问限制的方法。

在最终评测时，调用栈占用的空间大小不会有单独的限制，但在我们的工作

环境中默认会有 8 MB 的限制。这可能会引起函数调用层数较多时，程序发生

栈溢出崩溃。

我们可以使用一些方法修改调用栈的大小限制。例如，在终端中输入下列命

令 ulimit -s 1048576

此命令的意义是，将调用栈的大小限制修改为 1 GB。

例如，在选手目录建立如下 sample.cpp 或 sample.pas

将上述源代码编译为可执行文件 sample 后，可以在终端中运行如下命令运

行该程序

./sample

如果在没有使用命令“ ulimit -s 1048576”的情况下运行该程序， sample

会因为栈溢出而崩溃；如果使用了上述命令后运行该程序，该程序则不会崩溃。

特别地，当你打开多个终端时，它们并不会共享该命令，你需要分别对它们

运行该命令。

请注意，调用栈占用的空间会计入总空间占用中，和程序其他部分占用的内

存共同受到内存限制。

思路：感觉能骗好多好多分，但是我还是太弱了，写完25分的暴力就没时间了。。。

正解：已超出能力范围，怎么看都看不懂。。。。

引用一下别人的：

25分

　　考虑此时

45分

　　注意到测试点

　　不难看出对于一个点

　　我在考场上是直接用的链剖

　　直接对于每条路径经过的点在线段树上增加

　　事实上对于

60分

　　注意到测试点

　　先只考虑

　　注意到等式右边只与

　　因为题目只涉及到首和尾，我们可以很容易联想到差分，即对于

　　根据上述思路，我们考虑具体做法：对于每个点

　　我们考虑维护一个统计数组

　　这样对于每个点

　　有一点注意处理：处理一个点

　　而对于

100分

　　题目中设计的几个档次的部分分其实暗示已经很明显了。

　　链的做法离正解就不远了。

　　而

　　拆路径！

　　很容易发现，一条

　　考虑对于每条路径，先将其拆分成两条路径（为了简化对

　　如果我们对于

　　考虑上述做法正确性：因为只有

　　具体实现呢？

　　对于一个点

　　为了保证正确性，我们思考统计答案的方式和顺序。

　　首先我们肯定是在处理完

　　注意到我们上面维护的仅仅是一个点的深度，由于同一深度的点很多，所以我们查询的时候会发现会把不在同一子树的点统计入答案，那怎么办呢？我们考虑对于一个点要查询子树和，肯定是只要单独地考虑这一个子树的贡献，所以我们可以记录进入，再在访问完

　　容易发现新的值减掉进入时的，才是真正的

　　这样我们就可以避免把别的子树的答案统计进来了。

　　对于向下的点做法类似，有一点复杂的地方就是等式变成了

　　上述做法如果采用的是倍增求

　　如果用

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：换教室

题目描述

对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中，有 $\leq i \leq n1≤i≤n）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 c_ic?i?? 上课，而另一节课程在教室 d_id?i?? 进行。$

在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 $d_id?i?? 上课，否则仍然在教室 c_ic?i?? 上课。$

由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 $k_ik?i??，并且对于不同课程的申请，被通过的概率是互相独立的。$

学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多

因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。

牛牛所在的大学有 $\leq i \leq n-11≤i≤n−1）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。$

现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。

输入输出格式

输入格式：

第一行四个整数

第二行 $\leq i \leq n1≤i≤n）个正整数表示 c_ic?i??，即第 ii 个时间段牛牛被安排上课的教室；保证 1 \le c_i \le v1≤c?i??≤v。$

第三行 $\leq i \leq n1≤i≤n）个正整数表示 d_id?i??，即第 ii 个时间段另一间上同样课程的教室；保证 1 \le d_i \le v1≤d?i??≤v。$

第四行 $\leq i \leq n1≤i≤n）个实数表示 k_ik?i??，即牛牛申请在第 ii 个时间段更换教室获得通过的概率。保证 0 \le k_i \le 10≤k?i??≤1。$

接下来 $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。$

保证 $\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。$

保证通过学校里的道路，从任何一间教室出发，都能到达其他所有的教室。

保证输入的实数最多包含

输出格式：

输出一行，包含一个实数，四舍五入精确到小数点后恰好

测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于 $\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说明】

所有可行的申请方案和期望收益如下表:

【提示】

道路中可能会有多条双向道路连接相同的两间教室。也有可能有道路两端连接

的是同一间教室。

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

特殊性质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 }