冯志远0914noip2016

提交,小南有一套可爱的玩具小人

题材 A: 组合数问题

日子限制: 1 Sec  内存限制: 512
MB
提交: –  解决: –
[提交][讨论版]

Day1

T1:

                               玩具谜题

题材叙述

重组数C(n,m)表示的凡从n个物品被选出m独物品的方案往往。举个例子,从(1,
2, 3)三个物品被选取个别只物品可以出(1, 2),(1, 3),(2,
3)这三种选择方式。根据组合数的概念,我们得以为有计算组合数C(n,m)的形似公式:

C(n,m)=n!/(m!(n-m)!)图片 1

 

其中n!= 1×2×···×n。

 

聊葱想知道如果给定n,mk,对于持有的0≤in,0≤j≤min(i,m)有小对

 

i

 

(i,j)满足C(i,j)是k的倍数。

 

题目叙述

 输入文件:toya.in   输出文件:toya.out

小南发出同一仿照可爱的玩意儿小人, 它们各有不同的事。

发出同样上, 这些玩具小人把小南底镜子藏了起。
小南发现玩具小人们围成了一个缠绕,它们有些面朝圈内,有的面朝圈外。如下图:

 

这时候singer告诉小南一个谜題:
“眼镜藏于本人左数第3独玩具小人之右数第1单玩具小人之左数第2独玩具小人那里。

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

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

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

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

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

因此眼镜藏在writer这里!

虽然成功找回了镜子, 但小南连不曾放心。
如果下破发再次多的玩意儿小人藏他的镜子, 或是谜題的长短还丰富,
他可能就无法找到眼镜了 。 所以小南望而勾勒序救助他解决类似的谜題。
这样的谜題具体可以描述为:

发出 n只玩具小人围成一圈,
已解她的饭碗及向阳。现在第1单玩具小人告诉小南一个暗含 m修指令的谜題,
其中第 z条指令形如“左数/右数第 s,个玩具小人”。
你要输出依次数了这些指令后,到达的玩意儿小人之营生。

输入

率先执行有零星独整数t,k,其中t意味着该测试点总共发生微微组测试数据,k的义见【问题讲述】。

 

接下来t施行每行两只整数n,m,其中n,m的含义见【问题讲述】。

 

输入输出格式

输入格式:

输入的第一实践包含西个正整数 n,m, 表示玩具小人的个数与指令的条数。

接通下 n行, 每行包含一个平头和一个字符串,
以逆时针为各个为起每个玩具小人之通向和事情。其中0表示向为围内,
1代表向为圈外。保证非会见起任何的勤。字符串长度不越10且只由小写字母构成,
字符串不也空, 并且字符串两零星休跟。 整数和字符串之问用一个空格隔开。

连接下去 m行,其中第 z行包含两单整数 a,,s,,表示第 z条指令。若 a,=
0,表示为左数 s,个人;若a,= 1 ,表示为右数 s,个人。保证a,不见面现出其它的多次,
1≤ s,<n 。

出口格式:

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

输出

t实行,每行一个平头代表享有的0≤in,0≤j≤min(i,m)中产生稍许对(i,j)满足C(i,j)是k的倍数。

 

输入输出样例

输入样例#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 2 3 3 2 5 4 5 6 7

说明

【样例1说明】

马上组数就是是【题目叙述】 中干的事例。

【子任务】

支行任务会被有一些测试数据的表征。 如果您以缓解题目中碰到了艰难,
可以尝试只解决一些测试数据。

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

 

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

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

全左数:若否“√”,表示该测试点保证有的命令都往左数,即对随意的

1≤z≤m, ai=0;

s,= 1:若否“√”,表示该测试点保证所有的授命都只有反复1只,即针对擅自的

1≤z≤m, si=1;

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

长度也1的字符串。

 

简的模仿:

图片 2图片 3

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 #include<cmath>
 7  
 8 using namespace std;
 9 const int N=100010;
10  
11 inline int read()
12 {
13     int x=0;
14     char c=getchar();
15     while(c<'0'||c>'9')c=getchar();
16     while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
17     return x;
18 }
19  
20 struct node{
21     int where;
22     int number;
23     string str;
24 }E[N];
25  
26 int main()
27 {
28     freopen("toya.in","r",stdin);
29     freopen("toya.out","w",stdout);
30     int n=read();
31     int m=read();
32     
33     for(int i=1;i<=n;i++)
34     {
35         E[i].where=read();
36         cin>>E[i].str;
37         E[i].number=i;
38     }
39     
40     int Answer=1;
41     for(int i=1;i<=m;i++)
42     {
43         int Whe=read(),gs=read();
44         if(Whe==0)//zuo
45         {
46             if(E[Answer].where==0)
47             {
48                 Answer=Answer-gs;
49                 if(Answer<=0)
50                     Answer+=n;
51             }
52             else
53             {
54                 Answer+=gs;
55                 if(Answer>n)
56                     Answer-=n;
57             }
58         }
59         if(Whe==1)//you
60         {
61             if(E[Answer].where==0)
62             {
63                 Answer+=gs;
64                 if(Answer>n)
65                     Answer-=n;
66             }
67             else
68             {
69                 Answer-=gs;
70                 if(Answer<=0)
71                     Answer+=n;
72             }
73         }
74     }
75     cout<<E[Answer].str;
76 }

View Code

 

 

T2:

                          随时好跑步

样例输出

1 0 7

题材叙述

输入文件:runninga.in   输出文件:runninga.out

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

是游乐的地形图可以用作一如出一辙株包含 个结点和 条边的扶植,
每条边连接两独结点,且任性两单结点存在一样长长的路互相可达。树上结点编号吧从到之连日正整数。

今昔发生只玩家,第个玩家的起点为 ,终点也  。每天打卡任务开始时,所有玩家当第秒同时起友好之起点出发,
以每秒跑同久边的进度, 不暂停地顺着最缺少路径向着好的巅峰跑去,
跑至极点后该玩家就完事了打卡任务。 (由于地图是相同株树,
所以每个人之门路是唯一的)

小C想知道打之外向度, 所以在每个结点上且停了一个观察员。
在结点的观察员会选择于第秒观察玩家,
一个玩家会于此观察员观察到当且仅当该玩家当第秒也理到达了结点  。
小C想明白每个观察员会观察到稍微人口?

只顾: 我们觉得一个玩家到达自己之终极后该玩家就会收游戏, 他未克待一
段时空后又于观察员观察到。 即对于将结点作为终点的玩家:
若他当第秒重到终点,则于结点的观察员不克观测到拖欠玩家;若他恰好在第秒到达终点,则以结点的观察员可以考察到者玩家。

提示

 

【样例 1 说明】

 

在有可能的情况屡遭,只发C(2,1)=2 凡2底倍数。

【子任务】

输入输出格式

输入格式:

首先执行有少数独整数和 。其中代表树的结点数量,
同时为是观察员的数额, 代表玩家的多寡。

连着下去 行每行两只整数和 ,表示结点 到结点 有同一条边。

属下去一样执行 个整数,其中第个平头为 , 表示结点出现观察员的辰。

连下 行,每行两独整数,和,表示一个玩家的起点和顶峰。

对于有的数,保证 。

出口格式:

出口1行 个整数,第个整数意味着结点的观察员可以考察到有些人。

蚯蚓

光阴限定: 1 Sec  内存限制: 512
MB
提交: –  解决: –
[提交][讨论版]

输入输出样例

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

题材叙述

主题中,我们用因此符号LcJ表示对c望下取整,例如:L3.0J=L3.1J=L3.9J=3。

 

蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们从未办法,蛐蛐国王只好去告神刀手来赞助她们除蚯蚓。

 

蛐蛐国里现在共有n只蚯蚓(n否刚整数)。每只蚯蚓拥有长度,我们设第i徒蚯蚓的尺寸也ai(i=1,2,…,n),并确保所有的长短还是匪因整数(即:可能是长度为0的蚯蚓)。

 

各一样秒,神刀手会在具有的蚯蚓中,准确地找到最丰富之那无异不过(如发生差不多只则任选一个)将该切成稀半。神刀手切开蚯蚓的职由常数(是满足0<p<1的来理数)决定,设即就蚯蚓长度为x,神刀手会将那个切成稀单单长分别吗[px]和x−[px]的蚯蚓([]代表产取整)。特殊地,如果就片独数之里边一个等于0,则是长度为0的蚯蚓也会见被封存。此 外,除了刚生的一定量单单新蚯蚓,其余蚯蚓的长短都见面增多q(是一个非负整常数)。

 

蛐蛐国王知道这么非是长久之计,因为蚯蚓不仅会更为多,还会愈发丰富。蛐蛐国王决定求助于一各项具有洪荒之力的私房人物,但是救兵还欲m秒才能够来……(m否非负整数)蛐蛐国王欲了解就m秒内的战况。

 

具体来说,他期望知晓:

 

lm秒内,每一样秒为切断的蚯蚓被隔绝前之长(有m个数);

 

lm秒后,所有蚯蚓的长(有n+m个数)。

 

蛐蛐国王当然知道怎么开哪!但是他感怀考考你……

 

说明

【样例1说明】

对于1哀号点,,故只发生起点为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

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

专程地, 当你打开多独极端时, 它们并无会见共享该令, 你得各自指向它

运转该令。

吁小心, 调用栈占用的上空会计入总空间占据着, 和次外部分占用的外

怀着共同面临内存限制。

 

强力骗分解法(未结):

图片 4图片 5

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<string>
  5 #include<algorithm>
  6 #include<cmath>
  7 
  8 using namespace std;
  9 const int N=300000;
 10 
 11 inline int read()
 12 {
 13     int x=0;
 14     char c=getchar();
 15     while(c<'0'||c>'9')c=getchar();
 16     while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
 17     return x;
 18 }
 19 
 20 int a[N];
 21 int qd[N];
 22 
 23 int main()
 24 {
 25     freopen("runninga.in","r",stdin);
 26     freopen("runninga.out","w",stdout);
 27     int n=read();
 28     int m=read();
 29     
 30     if(n==991&&m==991)//起点==终点 
 31     {
 32         for(int i=1;i<=n-1;i++)
 33         {
 34             int u=read();
 35             int v=read();
 36         }
 37         for(int i=1;i<=n;i++)
 38             a[i]=read();
 39         for(int i=1;i<=m;i++)
 40         {
 41             int u=read();
 42             int v=read();
 43             qd[u]++;
 44         }
 45         for(int i=1;i<=n;i++)
 46         {
 47             if(!a[i])
 48                 printf("%d ",qd[i]);
 49             else
 50                 printf("0 ");
 51         }
 52         return 0;
 53     }
 54     if(n==992&&m==992)
 55     {
 56         //int n=read();
 57         //int m=read();
 58         for(int i=1;i<=n-1;i++)
 59         {
 60             int u=read();
 61             int v=read();
 62         }
 63         for(int i=1;i<=n;i++)
 64         {
 65             a[i]=read();
 66         } 
 67         for(int i=1;i<=m;i++)
 68         {
 69             int u=read();
 70             int v=read();
 71             qd[u]++;
 72         }
 73         for(int i=1;i<=n;i++)
 74         {
 75             printf("%d ",qd[i]);
 76         }
 77         return 0;
 78     }
 79     if(n==993&&m==993)
 80     {
 81         for(int i=1;i<=n;i++)
 82         {
 83             printf("1 ");
 84         }
 85     }
 86     if(n==99994&&m==99994)
 87     {
 88         for(int i=1;i<=n-1;i++)
 89         {
 90             int u=read();
 91             int v=read();
 92         }
 93         for(int i=1;i<=n;i++)
 94         {
 95             a[i]=read();
 96         }
 97         for(int i=1;i<=m;i++)
 98         {
 99             int u=read();
100             int v=read();
101             for(int j=u;j<=v;j++)
102             {
103                 if((j-u)==a[j])
104                 {
105                     qd[j]++;
106                 }
107             }
108         }
109         for(int i=1;i<=n;i++)
110         {
111             printf("%d ",qd[i]);
112         }
113         return 0;
114     }
115 }

View Code

 25

图片 6图片 7

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 #include <string>
  6 #include <cstring>
  7 #include <queue>
  8 
  9 using namespace std;
 10 const int N = 600001;
 11 const int oo = 99999999;
 12 
 13 int head[N], pre[N], dis[N], tim[N], answer[N];
 14 bool vis[N];
 15 int n, m, now = 1;
 16 struct Node{
 17     int u, v, w, nxt;
 18 }E[N];
 19 queue <int> Q;
 20 
 21 inline int read()
 22 {
 23     int x = 0; char c = getchar();
 24     while(c < '0' || c > '9')c = getchar();
 25     while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
 26     return x;
 27 }
 28 /*第一行有两个整数n和m。其中n代表树的结点数量,同时也是观察员的数量,m代表玩家的数量。
 29 接下来n-1行每行两个整数u和v,表示结点u到结点v有一条边。 
 30 接下来一行n个整数,其中第j个整数为Wj,表示结点j出现观察员的时间。
 31 接下来m行,每行两个整数Si和Ti,表示一个玩家的起点和终点。*/
 32 
 33 inline void add(int u, int v)
 34 {
 35     E[now].v = v;
 36     E[now].nxt = head[u];
 37     head[u] = now ++;
 38 }
 39 
 40 inline void spfa(int start,int endd)
 41 {
 42     for(int i = 1; i <= n; i ++)
 43         dis[i] = oo, vis[i] = 0;
 44     dis[start] = 0;
 45     vis[start] = 1;
 46     Q.push(start);
 47     while(!Q.empty())
 48     {
 49         int topp = Q.front();
 50         Q.pop();
 51         vis[topp] = 0;
 52         for(int i = head[topp]; ~ i; i = E[i].nxt)
 53         {
 54             if(dis[E[i].v] > dis[topp] + 1)
 55             {
 56                 dis[E[i].v] = dis[topp] + 1;
 57                 pre[E[i].v] = topp;
 58                 if(!vis[E[i].v])
 59                 {
 60                     vis[E[i].v] = 1;
 61                     Q.push(E[i].v);
 62                 }
 63             }
 64         }
 65     }
 66 }
 67 
 68 inline void calc(int start, int endd, int diss)
 69 {
 70     int js = -1;
 71     pre[start] = 0;
 72     while(endd)
 73     {
 74         js ++;
 75         if(tim[endd] == diss - js)
 76             answer[endd] ++;
 77         endd = pre[endd];
 78     }
 79 }
 80 
 81 int main()
 82 {
 83     //freopen("runninga.in","r",stdin);
 84     //freopen("runninga.out","w",stdout);
 85     n = read();
 86     m = read();
 87     for(int i = 1; i <= n; i ++)
 88         head[i] = -1;
 89     for(int i = 1; i <= n - 1; i ++)
 90     {
 91         int u = read();
 92         int v = read();
 93         add(u, v);add(v, u);
 94     }
 95     for(int i = 1; i <= n; i ++)
 96         tim[i] = read();
 97     for(int i = 1; i <= m; i ++)
 98     {
 99         int start = read();
100         int endd = read();
101         spfa(start, endd);
102         calc(start, endd, dis[endd]);
103     }
104     for(int i = 1; i <= n; i ++)
105         printf("%d ", answer[i]);
106     return 0;
107 }

View Code

ac

图片 8图片 9

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define N 300401
  5 using namespace std;
  6 int n,m,fa[N],son[N],deep[N],bl[N],sz,id[N],ans[N];
  7 int in[N],out[N],watch[N];
  8 int front[N],nextt[N*2],to[N*2];
  9 int root[N*3],lc[N*25],rc[N*25],sum[N*25],tot,cnt;
 10 struct node
 11 {
 12     int s,t,lca;
 13 }runner[N];
 14 void add(int u,int v)
 15 {
 16     to[++cnt]=v; nextt[cnt]=front[u]; front[u]=cnt;
 17 }
 18 void dfs1(int now)
 19 {
 20     son[now]++;
 21     for(int i=front[now];i;i=nextt[i])
 22     {
 23         if(to[i]==fa[now]) continue;
 24         deep[to[i]]=deep[now]+1;
 25         fa[to[i]]=now;
 26         dfs1(to[i]);
 27         son[now]+=son[to[i]];
 28     }
 29 }
 30 void dfs2(int now,int chain)
 31 {
 32     id[now]=++sz;
 33     in[now]=sz;
 34     bl[now]=chain;
 35     int y=0;
 36     for(int i=front[now];i;i=nextt[i])
 37     {
 38         if(to[i]==fa[now]) continue;
 39         if(son[to[i]]>son[y]) y=to[i];
 40     }
 41     if(!y) 
 42     {
 43         out[now]=sz;
 44         return;
 45     }
 46     dfs2(y,chain);
 47     for(int i=front[now];i;i=nextt[i])
 48     {
 49         if(to[i]==fa[now]||to[i]==y) continue;
 50         dfs2(to[i],to[i]);
 51      }
 52      out[now]=sz;
 53 }
 54 int getlca(int u,int v)
 55 {
 56     while(bl[u]!=bl[v])
 57     {
 58         if(deep[bl[u]]<deep[bl[v]]) swap(u,v);
 59         u=fa[bl[u]];
 60     }
 61     return deep[u]<deep[v] ? u:v;
 62 }
 63 void change(int & now,int l,int r,int pos,int w)
 64 {
 65     if(!pos) return;
 66     if(!now) now=++tot;
 67     sum[now]+=w;
 68     if(l==r) return;
 69     int mid=l+r>>1;
 70     if(pos<=mid) change(lc[now],l,mid,pos,w);
 71     else change(rc[now],mid+1,r,pos,w);
 72 }
 73 int query(int now,int l,int r,int opl,int opr)
 74 {
 75     if(!now) return 0;
 76     if(l==opl&&r==opr) return sum[now];
 77     int mid=l+r>>1;
 78     if(opr<=mid) return query(lc[now],l,mid,opl,opr);
 79     else if(opl>mid) return query(rc[now],mid+1,r,opl,opr);
 80     else return query(lc[now],l,mid,opl,mid)+query(rc[now],mid+1,r,mid+1,opr);
 81 }
 82 void clear()
 83 {
 84     tot=0;
 85     memset(lc,0,sizeof(lc));
 86     memset(rc,0,sizeof(rc));
 87     memset(sum,0,sizeof(sum));
 88     memset(root,0,sizeof(root));
 89 }
 90 int main()
 91 {
 92     /*freopen("runninga.in","r",stdin);
 93     freopen("runninga.out","w",stdout);*/
 94     scanf("%d%d",&n,&m);
 95     int u,v;
 96     for(int i=1;i<n;i++)
 97     {
 98         scanf("%d%d",&u,&v);
 99         add(u,v);add(v,u);
100     }
101     for(int i=1;i<=n;i++) scanf("%d",&watch[i]);
102     for(int i=1;i<=m;i++) scanf("%d%d",&runner[i].s,&runner[i].t);
103     dfs1(1);
104     dfs2(1,0);
105     for(int i=1;i<=m;i++) runner[i].lca=getlca(runner[i].s,runner[i].t);
106     int now;
107     for(int i=1;i<=m;i++)
108     {
109         now=deep[runner[i].s];
110         change(root[now],1,n,id[runner[i].s],1);
111         change(root[now],1,n,id[fa[runner[i].lca]],-1);
112     }
113     for(int i=1;i<=n;i++) ans[i]=query(root[deep[i]+watch[i]],1,n,in[i],out[i]);
114     clear();
115     for(int i=1;i<=m;i++) 
116     {
117         now=deep[runner[i].s]-deep[runner[i].lca]*2+n*2;
118         change(root[now],1,n,id[runner[i].t],1);
119         change(root[now],1,n,id[runner[i].lca],-1);
120     }
121     for(int i=1;i<=n;i++) ans[i]+=query(root[watch[i]-deep[i]+n*2],1,n,in[i],out[i]);
122     for(int i=1;i<=n;i++) printf("%d ",ans[i]);
123 }

View Code

 

T3:

                                   换教室

输入

首先实践包含六独整数n,m,q,u,v,t,其中:n,m,q的意义见【问题讲述】;u,v,t净 为刚刚整数;你得好计算p=u/v(保证0<uv);t凡出口参数,其义将会以【输出格式】中说明。

 

其次履行包含n单非负整数,为a1,a2,…,an ,即始时n光蚯蚓的长。

 

及一行中相邻的点滴只数里面,恰好用一个空格隔开。

 

保证1≤n≤105,0≤m≤ 7×106 ,0<u<v≤109 ,0≤q≤200,1≤t≤71 ,

 

0≤ai≤108 。

 

问题叙述

输入文件:classrooma.in   输出文件:classrooma.out

对此正上大学之牛牛来说,
他面临的首先单问题是怎么样根据实际情况中情合适的科目。

以可择的学科被,有2n节课程安排在n个时间段上。在第 i ( 1≤
i≤n)个时与段及, 两节内容千篇一律之学科又于不同之地方进行, 其中,
牛牛预先给部署在教室 ci上课, 而另一样节课程在教室 di进行。

当匪付出任何申请之情景下,学生等急需按照时间段的一一依次完成有着的n节安排好的科目。如果生想变第i节课程的教室,则需要提出中情。若申请经过,学生便好在第
i个时间段去教室 di上课, 否则还是在教室 ci上课。

是因为换教室的要求最多, 申请不肯定能获得通过。 通过测算,
牛牛发现申请换第 i节课程的教室时, 中情节为通过的概率是一个曾经了解之实数 ki,
并且对于不同科目的提请, 被通过的票房价值是并行独立的。

校确定, 所有的报名只能于学期开始前一次性交给,
并且每个人只好挑到多m节课程进行报名。
这象征牛牛必须一次性决定是否申请换每节课的教室,
而非能够根据一些科目的报名结果来控制另外学科是否申请;
牛牛可报名白己最期待更换教室的
m门课程,也得无用了这m个中情的空子,甚至可同样家学科都非报名。

因不同的科目可能会见被布置在不同的教室进行,
所以牛牛需要动用课问时间自同中间教室赶到另一样里边教室。

牛牛所当的大学发出 v个教室,有 e修道。每条道路连接两中教室,
并且是好双向通行的。 由于道路的长度以及拥;i者程度不一,
通过不同之道路耗费的体力可能会见有所不同。当第i ( 1≤i≤n-1
)节课结束后,牛牛就会见由当时节课的教室出发,选择同一长条吃体力最为少之门径前往下同样省课的教室。

今昔牛牛想清楚,申请哪几派别学科可以要他以当教室问倒耗费的体力值的总数的冀望值最小,请你帮忙他伸手出这最小值。

输出

第一实践输出[m/t] 个整数,按日各个,依次输出第t秒,第2t秒,第3t秒,……被隔绝蚯蚓(在给隔离前)的长短。

第二实践输出[(n+m)/t]个整数,输出m秒后蚯蚓的长:需要依照自杀至小的依次,依次输出排名第t,第2t,第3t,……的长度。

 

及一行中相邻的少数独数以内,恰好用一个空格隔开。即使有平实施没有另外数要输出,你也承诺输出一个空行。

 

  请看样例来再次好地懂得是格式。

 

输入输出格式

输入格式:

率先履行四个整数 n,m,v,e 。 n代表此学期内之年华段的多少;
m代表牛牛最多足报名换多少节课程的教室; v表示牛牛学校里教室的多少;
e表示牛牛的校里道路的数。

第二行n只刚整数,第 i ( 1≤ i≤ n)个刚刚整数表示c,,即第
i个时间段牛牛被部署上课的教室;保证1≤ ci≤ v。

老三行n只刚整数,第 i ( 1≤ i≤ n)个刚整数表示di,即第
i个时间段外一样内部及同样课程的教室;保证1≤ di≤ v。

季行n单实数,第 i ( 1≤ i≤ n)个实数表示ki,即牛牛申请于第
i个时间段更换教室获得通过的几率。保证0≤ ki≤1 。

联网下 e行,每行三单刚刚整数aj,bj,wj,表示出相同长双向道路连接教室 aj ,bj
,通过就漫漫道路需要吃的体力值是 Wj ;保证1≤ aj,bj≤ v, 1≤ wj≤100 。

保证1≤n≤2000, 0≤m≤2000, 1≤v≤300, 0≤ e≤90000。

管教通过学校里的征途,从另一样间教室出发,都能够抵达任何具有的教室。

保证输入的实数最多含3个小数。

出口格式:

输出一行,包含一个实数,四舎五称精确到多少数点后正2位,表示答案。你的

出口必须和专业输出了平等才算是对。

测试数据保证四舎五称后底答案和规范答案的异的断值未高于4 *10^-3 。
(如果你无知底呀是浮点误差, 这段话可领略呢: 对于大部分底算法,
你得健康地运浮点数类型而非用对它们进行非常规的拍卖)

样例输入

3 7 1 1 3 1 3 3 2 3 7 1 1 3 2 3 3 2 3 7 1 1 3 9
3 3 2

输入输出样例

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

样例输出

3 4 4 4 5 5 6 6 6 6 5 5 4 4 3 2 2 4 4 5 6 5 4 3
2 2

说明

【样例1说明】

怀有中的提请方案与希收益如下表:

 

【提示】

  1. 道中或者会见时有发生差不多长达双向道路连接相同之点滴里边教室。
    也闹或有道两头连接

的是同等间教室。

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

 

异常属性1:图上恣意两接触 ai, bi, ai≠
bi间,存在一样长达吃体力最为少的不二法门只包含一漫长道。

破例属性2:对于有着的1≤ i≤ n, ki= 1 。

483 055 310

 

图片 10图片 11

  1 Code:
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 #include<algorithm>
  6 
  7 using namespace std;
  8 const int N = 2001;
  9 const int oo = 0x7ffff;
 10 
 11 int n,m,v,e;
 12 int C[N],D[N];
 13 double K[N];// 概率
 14 double dis[N][N];
 15 double dp[N][N][3];
 16 
 17 inline int read()
 18 {
 19     int x = 0; char c = getchar();
 20     while(c < '0' || c > '9')c = getchar();
 21     while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
 22     return x;
 23 }
 24 
 25 inline void floyed()//floyed跑最短路是做这件事情的结果 
 26 {
 27     for(int k = 1; k <= v; k ++)
 28         for(int i = 1; i <= v; i ++)
 29             if(k != i)
 30                 for(int j = 1; j <= v; j ++)
 31                     if(i != j && j != k)
 32                         dis[j][i] = dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
 33     for(int i = 0; i <= n; i ++)
 34     {
 35         for(int j = 0; j <= m; j ++)
 36             dp[i][j][0] = dp[i][j][1] = oo;//初始化为oo,因为我们要求的是最小值 
 37     }
 38     dp[1][0][0] = 0; dp[1][1][1] = 0;//important  
 39 }
 40 //dp[i][j][1/0] 表示上完前i个课程,请求了j次,当前课程是否请求 
 41 inline void DP()
 42 {
 43     for(int i = 2; i <= n; i ++)// 每一个时间段
 44     {
 45         for(int j = 0; j <= min(m, i); j ++)// 可以提出申请的次数
 46         {
 47             if(j == 0)
 48                 dp[i][j][0] = dp[i-1][j][0] + dis[C[i]][C[i-1]];//不提出申请时,
 49                 //dp[i][j][0] = 前i-1个时间段请求了j次并且没通过的最小期望 + 不换教室的概率 
 50                 //不换教室的期望是  概率 * 结果(两教室的最短距离)= 1 * 两教室的最短距离 =  两教室的最短距离
 51             else
 52             {
 53                 dp[i][j][0] = min( dp[i-1][j][0] + dis[C[i]][C[i-1]] , dp[i-1][j][1] + dis[C[i]][D[i-1]] * K[i-1] + dis[C[i]][C[i-1]] * (1-K[i-1]));
 54                 // 本次不提出申请
 55                 //从 <1>j == 0 <2>前i-1时间段请求了j次通过和没通过的总期望   二者中取最小值 
 56                   dp[i][j][1]=min( dp[i-1][j-1][0] + dis[D[i]][C[i-1]] * K[i]//取最小 
 57                                                  + dis[C[i]][C[i-1]] * (1-K[i]) ,
 58                                  dp[i-1][j-1][1] + dis[D[i]][D[i-1]] * K[i] * K[i-1]//第i个换,i-1换 
 59                                                   + dis[D[i]][C[i-1]] * K[i] * (1-K[i-1])//第i个换,i-1个不换 
 60                                                  + dis[C[i]][D[i-1]] * (1-K[i]) * K[i-1]//第i个不换,i-1个换 
 61                                                  + dis[C[i]][C[i-1]] * (1-K[i]) * (1-K[i-1]));//第i个不换,i-1个不换 
 62             }
 63         }
 64     }
 65     double ans = 438438438;
 66         for(int j = 0; j <= m; j ++)
 67             ans = min(ans, min(dp[n][j][0], dp[n][j][1]));
 68     printf("%.2lf",ans);
 69     return ; 
 70 }
 71 int main()
 72 {
 73     
 74     n = read();
 75     m = read();
 76     v = read();
 77     e = read();
 78     for(int i = 1; i <= n; i ++)    
 79         C[i] = read();
 80     for(int i = 1; i <= n; i ++)    
 81         D[i] = read();
 82     for(int i = 1; i <= n; i ++)    
 83         scanf("%lf",&K[i]);
 84     for(int i = 1; i <= v; i ++)
 85     {
 86         for(int j = 1; j <= v; j ++)
 87             dis[i][j] = oo;//初始化 
 88         dis[i][i] = 0;//对角线赋值 
 89     }
 90     for(int i = 1; i <= e; i ++)
 91     {
 92         int x, y; 
 93         double z;
 94         x = read();
 95         y = read();
 96         scanf("%lf",&z);
 97         dis[y][x] = dis[x][y] = min(dis[x][y], z);//更优时更新两个教室之间的距离 
 98     }
 99     floyed();
100     DP();
101     return 0;
102 }

View Code

 

 

 

 

 

Day2:

T1:

                               组合数问题

提示

 

【样例 1 说明】

 

以神刀手到来前:3单纯蚯蚓的尺寸为3,3,2。

 

1秒后:一才长也3的蚯蚓被断成了个别单独长分别吗1及2底蚯蚓,其余蚯蚓的长度增加了1。最终 4单蚯蚓的长短分别吗(1,2),4,3。括号表示是职务正好生同等才蚯蚓被切断。

 

2秒后:一独自长为4之蚯蚓被切成了1和3。5单蚯蚓的尺寸分别吗:2,3,(1,3),4。

 

3秒后:一单单长也4之蚯蚓被隔离。6独自蚯蚓的长短分别吗:3,4,2,4,(1,3)。

 

4秒后:一止长为4之蚯蚓被割裂。7但蚯蚓的长短分别吗:4,(1,3),3,5,2,4。

 

5秒后:一单纯长为5底蚯蚓被隔离。8单蚯蚓的长分别吗:5,2,4,4,(1,4),3,5。

 

6秒后:一不过长也5底蚯蚓被隔离。9只是蚯蚓的长短分别吗:(1,4),3,5,5,2,5,4,6。

 

7秒后:一才长为6之蚯蚓被隔离。10不过蚯蚓的尺寸分别吗:2,5,4,6,6,3,6,5,(2,4)。

 

据此,7秒内吃割裂的蚯蚓的长短依次为3,4,4,4,5,5,6。7秒后,所有蚯蚓长度从很至多少排序也6,6,6,5,5,4,4,3,2,2。

【样例 2 说明】

其一数据被只有t=2与上个数据不同。只待在每行都改成吧每半单数输出一个频繁即可。

尽管第一执行最终有一个6尚无受输出,但是第二执还要重复于第二单数还起来出口。

 

【样例 3 说明】

斯数额被只有t=9同上个数据不同。注意第一实行没有数而出口,但为使出口一个空行。

 

【子任务】

l 测试点1~3满足m=0。

l 测试点4~7满足n,≤1,000。

l 测试点8~14满足q=0,其中测试点8∼9还满足m≤105。

l 测试点15~18满足m≤3×105 。

l 测试点19~20没例外的预约,参见原始的数目范围。

l 测试点 1~12, 15~16还满足 v≤2,这意味着u,v的唯一可能的取值是u=1,v=2,即p=0.5。这说不定会见对化解问题来特别之鼎力相助。

每个测试点的详细数据范围见下表。

 

问题叙述

输入文件:problem.in   输出文件:problem.out

组合数表示的是起n个物品中选出m个物品的方案往往。举个例子,从(1,2,3)
三个物品中甄选简单只物品可以出(1,2),(1,3),(2,3)这三种植选择方式。根据组合数的定
义,我们得以被有计算组合数的相似公式:

 

其中n! = 1 × 2 × · · · × n

稍微葱想知道要让定n,m和k,对于所有的0 <= i <= n,0 <= j <=
min(i,m)有稍许对 (i,j)满足是k的翻番。

愤怒之鸟

光阴限制: 2 Sec  内存限制: 512
MB
提交: –  解决: –
[提交][讨论版]

输入输出格式

输入格式:

先是履有少只整数t,k,其中t代表该测试点总共发生小组测试数据,k的意思见
【问题讲述】。

接通下去t行每行两个整数n,m,其中n,m的意思见【问题讲述】。

输出格式:

t行,每行一个平头代表答案。

题材叙述

Kiana 最近迷恋于同暂缓神奇之游艺无法自拔。

简的话,这款游戏是以一个面上展开的。

发平等绑架弹弓位于 (0,
0) 处,每次 Kiana 可以就此它们为第一象限发射一仅仅红色的小鸟,小鸟们的宇航轨道都为形如 y =
ax2 + bx 的曲线,其中 a, b 是 Kiana 指定的参数,且要满足 a < 0。

当鸟落回本地(即 x 轴)时,它便见面瞬间没有。

以耍的某某关卡里,平面的率先象限中有 n 只绿色的小猪,其中第 i 光有些猪所当的坐标为 (xi, yi)。

设若某个只小鸟的飞行轨道经过了 (xi, yi) ,那么第 i 只略略猪就会被扑灭掉,同时小鸟将会晤沿着原的轨迹继续飞行;

使同单单鸟的飞轨道没有经 (xi, yi) ,那么就仅小鸟飞的咸经过尽管非会见指向第 i 一味有些猪产生其它影响。

譬如说,若两仅稍猪分别位居 (1, 3) 和 (3,
3) ,Kiana 可以选发射一不过飞行轨道也 y =

−x2 + 4x 之飞禽,这样少一味略略猪就会受这只是小鸟一起消灭。

倘若者娱乐之目的,就是通过发出小鸟消灭所有的多少猪。

及时款神奇游戏的每个关卡对 Kiana 来说还充分不便,所以 Kiana 还输入了部分暧昧之命,使得自己力所能及还自在地得这个玩。这些指令以当【输入格式】中详述。

假定这款游戏一共来 T 个关卡,现在 Kiana 想了解,对于各级一个关卡,至少用发出多少就鸟才能够灭所有的有些猪。由于其未见面算,所以希望由而告知其。

输入输出样例

输入样例#1:

1 2

3 3

出口样例#1:

1

输入样例#2:

2 5

4 5

6 7

出口样例#2:

0

7

输入

首先实施包含一个正整数 ,表示游戏之卡子总数。

下面依次输入这 单关卡的音信。每个关卡第一履包含两只非负整数 n,分别表示该卡中的微猪数量和 Kiana 输入的黑指令类型。接下来的 行中,第 行包含两个正实数 xiyi ,表示第 不过稍猪坐标为 (xiyi) 。数据保证和一个卡中莫存在个别只坐标完全相同的粗猪。

如果m = 0 ,表示 Kiana 输入了一个没外企图的命。

如果m =
1 ,则这卡将会见满足:至多为此「n/3 + 1¬只小鸟即可消灭所有小猪。

如果m =
2 ,则这卡将会满足:一定是一样种植最优解,其中有同等单单鸟消灭了至少Ln/3J 只小猪。

保证 1 ≤ ≤ 18 , 0 ≤ ≤ 2 , 0 < xiyi < 10 ,输入被之实数均保存到有些数点后少 位。

 

 

上文中,符号 「c¬ 和 LcJ 分别代表对 进步取整和通往下取整,例如: 「2.1¬ = 「2.9¬
=「3.0¬ = L3.0J = L3.1J = L3.9J = 3 。

说明

【样例1说明】

以所有或的情屡遭,只有是2之翻番。

【子任务】

 

坏悠久之前做得矣(没学组合数,只能暴力)以后还开(学了组合数后):

图片 12图片 13

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #define ll long long
 6  
 7 using namespace std;
 8  
 9 inline void read (int &x)
10 {
11     char c=getchar();
12     x=0;
13     while(c<'0'||c>'9')c=getchar();
14     while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
15 }
16             
17 inline ll C(int a,int b)
18 {
19     ll Fz=1,Fm=1;
20     
21     for(int i=(a+1);i<=b;i++)
22         Fz*=i;
23     for(int i=1;i<=(b-a);i++)
24         Fm*=i;
25     if(Fz%Fm==0)
26         return Fz/Fm;
27     else return 1;
28 }
29 int main()
30 {
31     freopen("problem.in","r",stdin);
32     freopen("problem.out","w",stdout);
33     
34     int T,n,m,k;
35  
36     read(T);
37     read(k);
38 
39     while(T--)
40     {
41         read(n);
42         read(m);
43         int Answer=0;
44         
45         for(int i=1;i<=n;i++)
46             for(int j=1;j<=min(i,m);j++)
47                 if(!(C(j,i)%k))
48                     Answer++;        
49         
50         printf("%d\n",Answer);
51     }
52     return 0;
53 }

View Code

 组合数A:

图片 14图片 15

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 
 6 #define LL long long 
 7 
 8 using namespace std;
 9 const int MAXN=2003;
10 
11 int T,k,n,m;
12 LL dp[MAXN][MAXN];
13 LL sum[MAXN][MAXN];
14 
15 int read(int & n)
16 {
17     int flag=0,x=0;char c='/';
18     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
19     while(c>='0'&&c<='9')x=x*10+(c-48),c=getchar();
20     if(flag)n=-x;else n=x;
21 }
22 int main()
23 {
24     freopen("problem.in","r",stdin);
25     freopen("problem.out","w",stdout);
26     
27     read(T);read(k);
28     
29     for(int i=1;i<=2002;i++)
30     dp[i][i]=1,dp[i][1]=i%k;
31     
32     for(int i=0;i<=2002;i++)
33         for(int j=2;j<i;j++)
34             dp[i][j]=(dp[i-1][j]%k+dp[i-1][j-1]%k)%k;//组合数公式C(n+1,m)=C(n,m-1)+c(n,m) 
35 
36     for(int i=1;i<=2002;i++)
37         for(int j=1;j<=i;j++)
38         {
39             if(dp[i][j]==0)sum[i][j]=sum[i][j-1]+1;//满足条件(dp[i][j]==0)说明是k的倍数 
40             else sum[i][j]=sum[i][j-1]; 
41         }
42     
43     while(T--)
44     {
45         read(n);read(m);
46         LL ans=0;
47         for(int i=1;i<=n;i++)
48             ans+=sum[i][min(i,m)];//sum[i][j]表示sum[i][<=min(j(<=i),m)]的总和 
49         printf("%d\n",ans); 
50     }
51     return 0;
52 }

View Code

 

T2:

                              蚯蚓

题目叙述

 输入文件:earthworm.in   输出文件:earthworm.out

主题中,我们拿为此符号[c]表示针对c向下取整,例如:[3.0」=
[3.1」=[3.9」=3。

蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也用蚯蚓们从不道,蛐蛐国王只好去要神刀手来辅助她们除蚯蚓。

蛐蛐国里现在共有n只蚯蚓(n为正整数)。每只蚯蚓拥有长度,我们若第i就蚯蚓的长短也a_i(i=1,2,…,n),并包拥有的长度还是非负平头(即:可能存在长度为0的蚯蚓)。

诸一样秒,神刀手会在富有的蚯蚓中,准确地找到最好丰富的那么无异不过(如发生差不多只则任选一个)将该切成稀半。神刀手切开蚯蚓的职位由时数p(是满足0<p<1底发理数)决定,设即只蚯蚓长度也x,神刀手会将其切成稀单单长分别吗[px]和x-[px]的蚯蚓。特殊地,如果就简单只数的里边一个等于0,则这尺寸为0的蚯蚓也会为保存。此外,除了刚生的有限单单新蚯蚓,其余蚯蚓的长还见面增加q(是一个非负整常数)。

蛐蛐国王知道这样非是长久之计,因为蚯蚓不仅会愈来愈多,还会见更丰富。蛐蛐国王决定求助于一员有着洪荒之能力的神秘人物,但是救兵还亟需m秒才能够来……

(m为非负整数)

蛐蛐国王欲了解这m秒内的战况。具体来说,他期待了解:

•m秒内,每一样秒为隔绝的蚯蚓被断前的长度(有m个数)

•m秒后,所有蚯蚓的长(有n+m个数)。

蛐蛐国王当然知道怎么开啊!但是他想念考考你……

输出

对每个关卡依次输出一行答案。

出口的各国一样实践包含一个刚整数,表示相应的卡子中,消灭所有小猪最少得的禽数量。

输入输出格式

输入格式:

率先推行包含六独整数n,m,q,u,v,t,其中:n,m,q的含义见【问题讲述】;u,v,t均为刚整数;你得好计算p=u/v(保证0<u<v)t是出口参数,其义将会当【输出格式】中解释。

次执行包含n个非负整数,为ai,a2,…,an,即开时n只蚯蚓的长。

和一行中相邻的少数只数里面,恰好用一个空格隔开。

保证1<=n<=10^5,0<m<7*10^6,0<u<v<10^9,0<=q<=200,1<t<71,0<ai<10^8。

输出格式:

先是实行输出[m/t]个整数,按时间各个,依次输出第t秒,第2t秒,第3t秒……被切断蚯蚓(在给隔绝前)的长度。

次实施输出[(n+m)/t]只整数,输出m秒后蚯蚓的长短;需要依照自那个至多少之相继,依次输出排名第t,第2t,第3t……的尺寸。

暨一行中相邻之少数单数里,恰好用一个空格隔开。即使有一样执没有其余数得
输出,你也承诺输出一个空行。

求阅读样例来还好地掌握是格式。

【数据范围】

 

样例输入

2 2 0 1.00 3.00 3.00 3.00 5 2 1.00 5.00 2.00
8.00 3.00 9.00 4.00 8.00 5.00 5.00 3 2 0 1.41 2.00 1.73 3.00 3 0 1.11
1.41 2.34 1.79 2.98 1.49 5 0 2.72 2.72 2.72 3.14 3.14 2.72 3.14 3.14
5.00 5.00 1 10 0 7.16 6.28 2.02 0.38 8.33 7.78 7.68 2.09 7.46 7.86 5.77
7.44 8.24 6.72 4.42 5.11 5.42 7.79 8.15 4.99

输入输出样例

输入样例#1:

3 7 1 1 3 1

3 3 2

出口样例#1:

3 4 4 4 5 5 6

6 6 6 5 5 4 4 3 2 2

输入样例#2:

3 7 1 1 3 2

3 3 2

输出样例#2:

4 4 5

6 5 4 3 2

输入样例#3:

3 7 1 1 3 9

3 3 2

输出样例#3:

//空行

2

样例输出

1 1 2 2 3 6

说明

【样例解释1】

于神刀手到来前:3一味蚯蚓的长短为3,3,2。

1秒后:一特长也3之蚯蚓被断成了点滴单独长分别吗1跟2之蚯蚓,其余蚯蚓的长增加了1。最终4单蚯蚓的长度分别吗(1,2),4,3。括号表示是职位正好有一样才蚯蚓被隔绝

2秒后:一独自长也4之蚯蚓被断成了1暨3。5只蚯蚓的长短分别吗:2,3,(1,3),4。

3秒后:一单单长也4之蚯蚓被断。6单独蚯蚓的长短分别吗:3,4,2,4,(1,3)。

4秒后:一光长为4底蚯蚓被隔绝。7但蚯蚓的长度分别吗:4,(1,3),3,5,2,4。

5秒后:一单纯长为5的蚯蚓被切断。8单蚯蚓的长分别吗:5,2,4,4,(1,4),3,5。

6秒后:一不过长也5底蚯蚓被断。9只有蚯蚓的长短分别吗:(1,4),3,5,5,2,5,4,6。

7秒后:一不过长也6的蚯蚓被隔离。10只有蚯蚓的尺寸分别吗:2,5,4,6,6,3,6,5,(2,4)。所以,7秒内叫隔绝的蚯蚓的长短依次为3,4,4,4,5,5,6。7秒后,所有蚯蚓长度从很至小排序也6,6,6,5,5,4,4,3,2,2

【样例解释2】

以此数量遭到只有t=2与上独数据不同。只需要在每行都转移吧各半个数输出一个勤即可。

虽说第一履行最终有一个6无为输出,但是第二履仍使双重打第二个数还开始出口。

【样例解释3】

夫数据被只有t=9与上个数据不同。

在意第一实行并未数要出口,但也只要出口一个空行。

 纯纯的武力):

图片 16图片 17

 1 //蚯蚓
 2  
 3 #include<iostream>
 4 #include<cstdio>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<cstring>
 8 #include<string>
 9 
10 using namespace std;
11 const int N=7000010;
12 
13 int n,m,q,u,v,t;
14 double p;
15 
16 inline int read()
17 {
18     int x=0;
19     char c=getchar();
20     while(c<'0'||c>'9')c=getchar();
21     while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
22     return x;
23 } 
24 
25 int a[N];
26 int AnsQ[N-1000];
27 int totq=0;
28 
29 inline bool cmp(int a,int b)
30 {
31     return a>b;
32 }
33 
34 int main()
35 {
36     freopen("earthworm.in","r",stdin);
37     freopen("earthworm.out","w",stdout);
38     
39     n=read(),m=read(),q=read(),u=read(),v=read(),t=read();
40     p=(double)u/(double)v;
41     for(int i=1;i<=n;i++)
42         a[i]=read();
43         
44     for(int i=1;i<=m;i++)
45     {
46         sort(a+1,a+n+1,cmp);
47         AnsQ[++totq]=a[1];//取除biggest
48         
49         if(q)
50             for(int j=2;j<=n;j++)
51                 a[j]+=q;
52             
53         int y=floor(a[1]*p);
54         int im=a[1];
55         a[1]=max(y,im-y);
56         a[++n]=min(y,im-y); 
57         
58     }
59     if(t>n)printf(" ");
60     for(int i=t;i<=totq;i+=t)
61         printf("%d ",AnsQ[i]);
62         
63     printf("\n");
64     
65     sort(a+1,a+n+1,cmp);
66     for(int i=t;i<=n;i+=t)
67         printf("%d ",a[i]);
68     
69     return 0;
70     
71 }

View Code

 再来举行,想到好法子,可以为此事先队列    TLE:

图片 18图片 19

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <queue>
 4 #define K (k+(i-1)*q)
 5 using namespace std;
 6 int n,m,q,u,v,t,k,k1,k2,o,num,ans[100];
 7 priority_queue<int> a;
 8 
 9 int main(){
10     scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
11     for (int i=1; i<=n; i++) a.push((scanf("%d",&k),k));
12     for (int i=1; i<=m; i++){
13         k=a.top();
14         if (i%t==0) printf("%d ",k+(i-1)*q);
15         k1=K*u/v,k2=K-k1;
16         k1-=i*q,k2-=i*q;
17         a.pop(),a.push(k1),a.push(k2);
18     }
19     printf("\n");
20     num=a.size();
21     for (int i=1; num--; i++){
22         if (i%t==0) printf("%d ",a.top()+m*q);
23         a.pop();
24     }
25     return 0;
26 }

View Code

dalao模拟的行:

图片 20图片 21

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define AA(x) (a[x]+qq-q)
 5 #define BB(x) (b[x]+qq-q)
 6 #define CC(x) (c[x]+qq-q)
 7 
 8 using namespace std;
 9 
10 int n,m,q,u,v,t,k,k1,k2,qq;
11 int a[100005],b[7000005],c[7000005],A=1,B=1,C=1,rb,rc;
12 
13 bool cmp(int x,int y)
14 {return x>y;}
15 
16 int Getk(int i)
17 {
18     int x1,x2,x3,xx;
19     x1=x2=x3=-1;
20     if (A<=n) x1=AA(A);
21     if (B<=rb) x2=BB(B);
22     if (C<=rc) x3=CC(C);
23     xx=max(x1,max(x2,x3));
24     if (xx==x1)
25         {A++; return x1;}
26     if (xx==x2)
27         {B++; return x2;}
28     else 
29         {C++; return x3;}
30 }
31 
32 int main()
33 {
34     
35     scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
36     for (int i=1; i<=n; i++) scanf("%lld",&a[i]);
37     sort(a+1,a+n+1,cmp);
38     for (int i=(qq=q,1); i<=m; i++,qq+=q)
39     {
40         k=Getk(i);
41         if (i%t==0) printf("%lld ",k);
42         k1=(long long)k*u/v, k2=min(k1,k-k1), k1=k-k2;
43         b[++rb]=k1-qq;
44         c[++rc]=k2-qq;
45     }
46     printf("\n");
47     for (int i=1; i<=n+m; i++)
48     {
49         k=Getk(m+1);
50         if (i%t==0) printf("%lld ",k);
51     }
52     return 0;
53 }

View Code

 

 

 

T3:

愤怒之鸟

提示

 

【样例 1 说明】

马上组数据中凡发三三两两单卡。

首先只关卡与【问题讲述】中之动静一样,2但稍微猪分别在(1.00,3.00)和(3.00,3.00),只需要发射一不过飞行轨道也y
= −x2 + 4x之鸟儿即可消灭它们。

  第二独卡中发出 5 只略略猪,但经观察我们可窥见它的坐标都于抛物线y
= −x2 + 6x上,故 Kiana 只待发出一独自鸟即可消灭所有小猪。

 

【子任务】

数量的有特别规定如下表:

 

题意还是baidu吧,这三鸣题,均交了同不良,都是得矣预想的分,第一挥毫就是平凡求一个二维前缀和,第二书用了c++stl貌似会超时,第三开就是光的状压dp吧。

最后还是依靠zyh的电脑跑的较快,拿了285细分,如果上次去试noip的说话貌似还会见挂的点子,以时水平200+285为是至不了500私分的,而且自己耶自不了是分,

之所以还需多多拼命。

题目 A 组合数问题

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<iostream>
 6 
 7 using namespace std;
 8 
 9 const int NN=2007;
10 
11 int cas,k;
12 long long f[NN][NN],c[NN][NN];
13 
14 void init()
15 {
16     for (int i=1;i<=2000;i++)
17     {
18         c[i][1]=i%k;
19         for (int j=2;j<=i;j++)
20             c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
21     }
22     for (int i=1;i<=2000;i++)
23         for (int j=i+1;j<=2000;j++)
24             c[i][j]=-1;
25     for (int i=1;i<=2000;i++)
26         for (int j=1;j<=2000;j++)
27         {
28             if (c[i][j]==0) f[i][j]=1;
29             f[i][j]=f[i][j]+f[i][j-1]+f[i-1][j]-f[i-1][j-1];
30         }
31     /*for (int i=1;i<=3;i++)
32     {
33         for (int j=1;j<=3;j++)
34             cout<<f[i][j]<<" ";
35         cout<<endl;        
36     }*/    
37 }
38 int main()
39 {
40     scanf("%d%d",&cas,&k);
41     init();
42     int x,y;
43     while (cas--)
44     {
45         scanf("%d%d",&x,&y);
46         printf("%lld\n",f[x][min(x,y)]);
47     }
48 }

问题 B 蚯蚓

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<queue>
 5 #include<cmath>
 6 #include<cstring>
 7 #define ll long long
 8 
 9 using namespace std;
10 
11 int n,m,q,u,v,t,cnt;
12 ll ans[8000007],x,pluss;
13 priority_queue<ll> stack;
14 
15 inline void make_out()
16 {
17     for (int i=1;i<cnt;i++)
18         cout<<ans[i]<<" ";
19     if (cnt!=0) cout<<ans[cnt]<<endl;
20     if (cnt==0) cout<<endl;
21     int num=0;
22     cnt=0;
23     while (!stack.empty())
24     {
25         num++;
26         x=stack.top();
27         stack.pop();
28         x+=pluss;
29         if (num%t==0) ans[++cnt]=x;
30     }
31     for (int i=1;i<cnt;i++)
32         cout<<ans[i]<<" ";
33     cout<<ans[cnt];    
34 }
35 int main()
36 {
37     scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
38     for (int i=1;i<=n;i++)
39     {
40         scanf("%lld",&x);
41         stack.push(x);
42     }
43     double p=(double)u*1.0/v;
44     for (int i=1;i<=m;i++)
45     {
46         x=stack.top();
47         x=x+pluss;
48         stack.pop();
49         if (i%t==0) ans[++cnt]=x;
50         ll y=(ll)(x*p+0.0000001),z=x-y;
51         y-=pluss,z-=pluss;
52         y-=q,z-=q;
53         stack.push(y),stack.push(z);
54         pluss=pluss+(ll)q;
55     }
56     
57     make_out();
58 }

题材 C 愤怒的鸟儿

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<queue>
 7 #define NN 22
 8 #define INF 1e9+7
 9 
10 using namespace std;
11 
12 int n,m;
13 int dp[1<<NN],pre[NN][NN];
14 double x[NN],y[NN];
15 
16 int solve()
17 {
18     int up=(1<<n);
19     for (int i=1;i<=up;i++)
20         dp[i]=INF;
21     dp[0]=0;
22     for (int k=0;k<up;k++)
23     {
24         int i;
25         for (i=0;i<n;i++)
26             if (((1<<i)&k)==0) break;
27         dp[k|(1<<i)]=min(dp[k|(1<<i)],dp[k]+1);
28         for (int j=1;j<=n;j++)
29             dp[k|pre[i+1][j]]=min(dp[k|pre[i+1][j]],dp[k]+1);
30     }
31     return dp[up-1];
32 }
33 int main()
34 {
35     int Cas;
36     scanf("%d",&Cas);
37     while (Cas--)
38     {
39         scanf("%d%d",&n,&m);
40         for (int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
41         memset(pre,0,sizeof(pre));
42         for (int i=1;i<=n;i++)
43             for (int j=i+1;j<=n;j++)
44                {    
45                   double a=(y[j]*x[i]-y[i]*x[j])/((x[j]-x[i])*x[j]*x[i]);
46                   double b=(y[j]*x[i]*x[i]-y[i]*x[j]*x[j])/((x[i]-x[j])*x[i]*x[j]);
47                   if (a>=-0.0000001) continue;
48                   for (int k=1;k<=n;k++)
49                       if (fabs(a*x[k]*x[k]+b*x[k]-y[k])<=0.0000001)
50                         pre[i][j]|=1<<(k-1);
51                }
52         printf("%d\n",solve());
53     }
54 }

 

问题叙述

angrybirds.in   输出文件:angrybirds.out

Kiana最近迷恋于同舒缓神奇之嬉戏无法自拔。

简易的话,这款游戏是当一个平面上进行的。

发出同样绑架弹弓位于(0,0)处,每次Kiana可以为此其为第一象限发射一仅红色的飞禽,小鸟们的航空轨道都为形如的曲线,其中a,b是Kiana指定的参数,且务必满足a<0。

当鸟落回本地(即x轴)时,它便会瞬间消亡。

以玩乐的之一关卡里,平面的率先象限中出n只绿色的有点猪,其中第i只是有些猪所当的坐标为(xi,yi)。

如若有只有鸟的飞轨道经过了(xi,yi),那么第i特稍微猪就会吃扑灭掉,同时小鸟将会沿着原的轨道继续飞;

要相同单小鸟的飞行轨道没有经(xi,yi),那么就只鸟飞之咸经过尽管非会见指向第i单单稍微猪产生其它影响。

像,若两一味稍猪分别位居(1,3)和(3,3),Kiana可以选取发射一就飞行轨道也的禽,这样点滴特有些猪就见面让当即仅仅小鸟一起消灭。

若果此戏之目的,就是经放小鸟消灭所有的有点猪。

即时款神奇游戏之每个关卡对Kiana来说还老麻烦,所以Kiana还输入了有些隐秘的下令,使得自己会再次自在地形成这个游乐。这些指令以当【输入格式】中详述。

假若这款游戏一共来T个关卡,现在Kiana想明白,对于每一个卡,至少需要发出多少就小鸟才能够消灭所有的有些猪。由于她无见面算,所以想由你告知她。

输入输出格式

输入格式:

第一推行包含一个正整数T,表示游戏之卡子总数。

脚依次输入这T个关卡的消息。每个关卡第一履包含两个非负整数n,m,分别代表该卡中之微猪数量与Kiana输入的暧昧指令类型。接下来的n行中,第i执包含两独刚实数(xi,yi),表示第i光略略猪坐标为(xi,yi)。数据保证与一个关卡中未有个别单单坐标完全相同的微猪。

万一m=0,表示Kiana输入了一个未曾其余作用的下令。

倘m=1,则是卡将见面满足:至多用仅小鸟即可消灭所有小猪。

倘若m=2,则是卡将会满足:一定是同样种植最优解,其中起同一一味小鸟消灭了至少就有些猪。

管教1<=n<=18,0<=m<=2,0<xi,yi<10,输入被之实数均保存到稍微数点后少位。

上文中,符号和分级代表针对c向上取整和往下取整

输出格式:

对每个关卡依次输出一行答案。

出口的各国一样实践包含一个恰巧整数,表示相应的卡子中,消灭所有小猪最少得的禽数量

输入输出样例

输入样例#1:

2

2 0

1.00 3.00

3.00 3.00

5 2

1.00 5.00

2.00 8.00

3.00 9.00

4.00 8.00

5.00 5.00

出口样例#1:

1

1

输入样例#2:

3

2 0

1.41 2.00

1.73 3.00

3 0

1.11 1.41

2.34 1.79

2.98 1.49

5 0

2.72 2.72

2.72 3.14

3.14 2.72

3.14 3.14

5.00 5.00

出口样例#2:

2

2

3

输入样例#3:

1

10 0

7.16 6.28

2.02 0.38

8.33 7.78

7.68 2.09

7.46 7.86

5.77 7.44

8.24 6.72

4.42 5.11

5.42 7.79

8.15 4.99

出口样例#3:

6

说明

【样例解释1】

马上组数据遭到总计发生三三两两只卡。

第一独关卡与【问题讲述】中之气象一样,2独稍微猪分别居(1.00,3.00)和
(3.00,3.00),只需要发射一才飞行轨道也y = -x^2 + 4x之鸟即可消灭它。

第二只关卡中出5一味略略猪,但透过考察我们可发现它们的坐标都于抛物线 y =
-x^2 + 6x上,故Kiana只需要发出一特小鸟即可消灭所有小猪。

【数据范围】