![content]( "content")
div class="article-list-left detail-content-wrap content"p class="sycode" p昨天一觉起来都5点半了。。没来的及玩，补的题。。/p pA题：http://codeforcesp p/p p class="sycode" p class="sycode" Ap p class="sycode" p class="sycode" time limit per test /p 1 second /p p class="sycode" p class="sycode" memory limit per test /p 256 megaytes /p p class="sycode" p class="sycode" input /p standard input /p p class="sycode" p class="sycode" output /p standard output /p /p p class="sycode" p Student Valera is an undergraduate student at the Universityp p According to the schedule, a student can take the exam for the i-th suject on the day numer ai? p Valera elieves that it would e rather strange if the entries in the record ook did not go in the order of non-decreasing datep /p p class="sycode" p class="sycode" Input /p p The first line contains a single positive integer n (1?≤?n?≤?5000) ? the numer of exams Valera will takep Each of the next n lines contains two positive space-separated integers ai and i (1?≤?i??ai?≤?109) ? the date of the exam in the schedule and the early date of passing the i-th exam, correspondinglyp p class="sycode" p class="sycode" Output /p p Print a single integer ? the minimum possile numer of the day when Valera can take the last exam if he takes all the exams so that all the records in his record ook go in the order of non-decreasing datep p class="sycode" p class="sycode" Sample test(s) /p p class="sycode" p class="sycode" p class="sycode" input /p div class="code" style="position:relative; padding:0px; margin:0px;"pre style="代码" class="precsshei"35 23 1 2/prediv class="contentsignin"登录后复制/div/div /p p class="sycode" p class="sycode" output /p /p p class="sycode" p class="sycode" input /p div class="code" style="position:relative; padding:0px; margin:0px;"pre style="代码" class="precsshei"36 15 3/prediv class="contentsignin"登录后复制/div/div /p p class="sycode" p class="sycode" output /p /p /p /p p class="sycode" p class="sycode" Note /p p In the first sample Valera first takes an exam in the second suject on the first day (the teacher writes down the schedule date that is 3)p p In the second sample Valera first takes an exam in the third suject on the fourth dayp /p r / p/p p简单贪心。。按a第一关键字，第二关键字降序排序下就好。肯定先选满足的。。/p p/p div class="code" style="position:relative; padding:0px; margin:0px;"pre name="code" class="sycode"/** * @author neko01 *///#pragma comment(linker, "/STACK:1000000,1000000")#include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;#define min3(a,,c) min(a,min(,c))#define max3(a,,c) max(a,max(,c))#define p push_ack#define mp(a,) make_pair(a,)#define clr(a) memset(a,0,sizeof a)#define clr1(a) memset(a,-1,sizeof a)#define dg(a) printf("%d\n",a)typedef pair pp;const doule eps=1e-9;const doule pi=acos(-1a;int main(){ int n,x,y; scanf("%d",&n); for(int i=0;i=ans) ans=a[i]prediv class="contentsignin"登录后复制/div/div r / ： http://codeforcesr / p/p p/p p class="sycode" p class="sycode" p p class="sycode" p class="sycode" time limit per test /p 1 second /p p class="sycode" p class="sycode" memory limit per test /p 256 megaytes /p p class="sycode" p class="sycode" input /p standard input /p p class="sycode" p class="sycode" output /p standard output /p /p p class="sycode" p Valery is a PE teacher at a school in erlandp p However, there is no reason for disappointment, as Valery has found another ruler, its length is l centimetersp p Valery elieves that with a ruler he can measure the distance of d centimeters, if there is a pair of integers i and j (1?≤?i?≤?j?≤?n), such that the distance etween the i-th and the j-th mark is exactly equal to d (in other words, aj?-?ai?=?d)p Under the rules, the girls should e ale to jump at least x centimeters, and the oys should e ale to jump at least y (x?? p Your task is to determine what is the minimum numer of additional marks you need to add on the ruler so that they can e used to measure the distances x and yp /p p class="sycode" p class="sycode" Input /p p The first line contains four positive space-separated integers n, l, x, y (2?≤?n?≤?105, 2?≤?l?≤?109, 1?≤?x??y?≤?l) ? the numer of marks, the length of the ruler and the jump norms for girls and oys, correspondinglyp The second line contains a sequence of n integers a1,?a2,??a2???an?=?l), where ai shows the distance from the i-th mark to the originp p class="sycode" p class="sycode" Output /p p In the first line print a single non-negative integer v ? the minimum numer of marks that you need to add on the rulerp In the second line print v space-separated integers p1,?p2,?p /p p class="sycode" p class="sycode" Sample test(s) /p p class="sycode" p class="sycode" p class="sycode" input /p div class="code" style="position:relative; padding:0px; margin:0px;"pre style="代码" class="precsshei"3 250 185 2300 185 250/prediv class="contentsignin"登录后复制/div/div /p p class="sycode" p class="sycode" output /p div class="code" style="position:relative; padding:0px; margin:0px;"pre style="代码" class="precsshei"1230/prediv class="contentsignin"登录后复制/div/div /p p class="sycode" p class="sycode" input /p div class="code" style="position:relative; padding:0px; margin:0px;"pre style="代码" class="precsshei" 250 185 2300 20 185 250/prediv class="contentsignin"登录后复制/div/div /p p class="sycode" p class="sycode" output /p /p p class="sycode" p class="sycode" input /p div class="code" style="position:relative; padding:0px; margin:0px;"pre style="代码" class="precsshei"2 300 185 2300 300/prediv class="contentsignin"登录后复制/div/div /p p class="sycode" p class="sycode" output /p div class="code" style="position:relative; padding:0px; margin:0px;"pre style="代码" class="precsshei"2185 230/prediv class="contentsignin"登录后复制/div/div /p /p /p p class="sycode" p class="sycode" Note /p p In the first sample it is impossile to initially measure the distance of 230 centimetersp p In the second sample you already can use the ruler to measure the distances of 185 and 230 centimeters, so you don't have to add new marksp In the third sample the ruler only contains the initial and the final marksp /p p/p p有意思的题。/p p题意：有一个长为L的尺子，n个刻度，为了测出x和y的长度，问最少要添加几个刻度。/p p可以用一个set或者二分查找每一个刻度+x，+y是否存在。如果都不存在，那么判断两个刻度之间有没有x+y,y-x的长度，如果有那么只需添加一个就行。代码有点丑233p p/p div class="code" style="position:relative; padding:0px; margin:0px;"pre name="code" class="sycode"/** * @author neko01 *///#pragma comment(linker, "/STACK:1000000,1000000")#include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;#define min3(a,,c) min(a,min(,c))#define max3(a,,c) max(a,max(,c))#define p push_ack#define mp(a,) make_pair(a,)#define clr(a) memset(a,0,sizeof a)#define clr1(a) memset(a,-1,sizeof a)#define dg(a) printf("%d\n",a)typedef pair pp;const doule eps=1e-9;const doule pi=acos(-1=0&&inary_search(a,a+i,a[i]+x-div class="contentsignin"登录后复制/div/div r / C题： http://codeforcesp/p p/p p class="sycode" p class="sycode" Cp p class="sycode" p class="sycode" time limit per test /p 2 seconds /p p class="sycode" p class="sycode" memory limit per test /p 256 megaytes /p p class="sycode" p class="sycode" input /p standard input /p p class="sycode" p class="sycode" output /p standard output /p /p p class="sycode" p Imagine that you are in a uilding that has exactly n floorsp p Let us suppose that at the moment you are on the floor numer x (initially, you were on floor a)?|x?-?|p p Your task is to find the numer of distinct numer sequences that you could have written in the noteook as the result of k trips in the liftp /p p class="sycode" p class="sycode" Input /p p The first line of the input contains four space-separated integers n, a, , k (2?≤?n?≤?5000, 1?≤?k?≤?5000, 1?≤?a,??≤?n, a?≠?)p p class="sycode" p class="sycode" Output /p p Print a single integer ? the remainder after dividing the sought numer of sequences y 1000000007 (109?+?7)p p class="sycode" p class="sycode" Sample test(s) /p p class="sycode" p class="sycode" p class="sycode" input /p div class="code" style="position:relative; padding:0px; margin:0px;"pre style="代码" class="precsshei"5 2 1/prediv class="contentsignin"登录后复制/div/div /p p class="sycode" p class="sycode" output /p /p p class="sycode" p class="sycode" input /p div class="code" style="position:relative; padding:0px; margin:0px;"pre style="代码" class="precsshei"5 2 2/prediv class="contentsignin"登录后复制/div/div /p p class="sycode" p class="sycode" output /p /p p class="sycode" p class="sycode" input /p div class="code" style="position:relative; padding:0px; margin:0px;"pre style="代码" class="precsshei"5 3 1/prediv class="contentsignin"登录后复制/div/div /p p class="sycode" p class="sycode" output /p /p /p /p p class="sycode" p class="sycode" Note /p p Two sequences p1,?p2,?p p Notes to the samples:/p ol li In the first sample after the first trip you are either on floor 1, or on floor 3, ecause |1?-?2|??|2?-?| and |3?-?2|??|2?-?|li In the second sample there are two possile sequences: (1,?2); (1,?3)li li In the third sample there are no sought sequences, ecause you cannot choose the floor for the first tripol /p p/p p题意：一个人在电梯里面初始位置a层，只能上下|a|的位置，也不能停在该楼层，问这样走k次后不同的方案有多少种。/p p分析：dp方程很好写,dp[i][j]表示第走i次时在第j层有多少种方案，但是直接转移O(k*n*n)的复杂度肯定超时。/p p注意转移时比如第i次到第j层(设j)，那么它可以由第i-1从1到第(j+-1)/2转移过来(减去第j层的)，所以我们只要算一个前缀和就可以实现转移了！复杂度O(k*n)/p p/p div class="code" style="position:relative; padding:0px; margin:0px;"pre name="code" class="sycode"/** * @author neko01 *///#pragma comment(linker, "/STACK:1000000,1000000")#include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;#define min3(a,,c) min(a,min(,c))#define max3(a,,c) max(a,max(,c))#define p push_ack#define mp(a,) make_pair(a,)#define clr(a) memset(a,0,sizeof a)#define clr1(a) memset(a,-1,sizeof a)#define dg(a) printf("%d\n",a)typedef pair pp;const doule eps=1e-9;const doule pi=acos(-1) a=n-a+1,=n+1; for(int i=a;i=n;i++) sum[i]=1; for(int i=1;i=k;i++) { for(int j=1;j;j++) dp[j]=(sum[(+j-1)/2]-(sum[j]-sum[j-1])+mod)%mod; for(int i=1;i=n;i++) sum[i]=(sum[i-1]+dp[i])%mod; } LL ans=0; for(int i=1;i;i++) { ans=ans+dp[i]; if(ans=mod) ans-=mod; } printf("%I6d\n",ans); return 0;}/prediv class="contentsignin"登录后复制/div/div r / r / p/p pr / /p pr / /p /p /div 09-14 02:34