水题CF

发布时间:2016-12-8 10:05:59 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"水题CF",主要涉及到水题CF方面的内容,对于水题CF感兴趣的同学可以参考一下。

B. Xenia and Spies time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Xenia the vigorous detective faced n (n ≥ 2) foreign spies lined up in a row. We'll consider the spies numbered from 1 to n from left to right. Spy s has an important note. He has to pass the note to spy f. Xenia interrogates the spies in several steps. During one step the spy keeping the important note can pass the note to one of his neighbours in the row. In other words, if this spy's number is x, he can pass the note to another spy, either x - 1 or x + 1 (if x = 1 or x = n, then the spy has only one neighbour). Also during a step the spy can keep a note and not pass it to anyone. But nothing is that easy. During m steps Xenia watches some spies attentively. Specifically, during step ti (steps are numbered from 1) Xenia watches spies numbers li, li + 1, li + 2, ..., ri (1 ≤ li ≤ ri ≤ n). Of course, if during some step a spy is watched, he can't do anything: neither give the note nor take it from some other spy. Otherwise, Xenia reveals the spies' cunning plot. Nevertheless, if the spy at the current step keeps the note, Xenia sees nothing suspicious even if she watches him. You've got s and f. Also, you have the steps during which Xenia watches spies and which spies she is going to watch during each step. Find the best way the spies should act in order to pass the note from spy s to spy f as quickly as possible (in the minimum number of steps). Input The first line contains four integers n, m, s and f (1 ≤ n, m ≤ 105; 1 ≤ s, f ≤ n; s ≠ f; n ≥ 2). Each of the following m lines contains three integers ti, li, ri (1 ≤ ti ≤ 109, 1 ≤ li ≤ ri ≤ n). It is guaranteed that t1 < t2 < t3 < ... < tm. Output Print k characters in a line: the i-th character in the line must represent the spies' actions on step i. If on step i the spy with the note must pass the note to the spy with a lesser number, the i-th character should equal "L". If on step i the spy with the note must pass it to the spy with a larger number, the i-th character must equal "R". If the spy must keep the note at the i-th step, the i-th character must equal "X". As a result of applying the printed sequence of actions spy s must pass the note to spy f. The number of printed characters k must be as small as possible. Xenia must not catch the spies passing the note. If there are miltiple optimal solutions, you can print any of them. It is guaranteed that the answer exists. Sample test(s) input 3 5 1 3 1 1 2 2 2 3 3 3 3 4 1 1 10 1 3 output XXRR 一直for直到达到要求。。。。。 /* * Author: ******* * Created Time: 2013/9/7 16:11:08 * File Name: CF.cpp * solve: CF.cpp */ #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<string> #include<map> #include<stack> #include<set> #include<iostream> #include<vector> #include<queue> //ios_base::sync_with_stdio(false); //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define sz(v) ((int)(v).size()) #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define repf(i, a, b) for (int i = (a); i <= (b); ++i) #define repd(i, a, b) for (int i = (a); i >= (b); --i) #define clr(x) memset(x,0,sizeof(x)) #define clrs( x , y ) memset(x,y,sizeof(x)) #define out(x) printf(#x" %d\n", x) #define sqr(x) ((x) * (x)) typedef long long LL; const int INF = 1000000000; const double eps = 1e-8; const int maxn = 100000; int sgn(const double &x) { return (x > eps) - (x < -eps); } //vector<int> step[maxn]; vector<char> ans; int main() { //freopen("in.txt","r",stdin); int n,m,s,t; scanf("%d%d%d%d",&n,&m,&s,&t); int maxs = 0; map<int,vector<int> > step; repf(i,1,m) { int a,b,c; scanf("%d%d%d",&a,&b,&c); step[a].push_back(b); step[a].push_back(c); maxs = max(maxs,a); } ans.clear(); if(s == t) { cout<<"X"<<endl; }else if(s < t) { repf(i,1,INF) { if(step[i].size() == 0) { s++; ans.push_back('R'); if(s == t) break; }else { int L = step[i][0]; int R = step[i][1]; if((s+1>=L && s+1<=R) || (s>=L && s<=R)) ans.push_back('X'); else { s++; ans.push_back('R'); if(s == t) break; } } } rep(i,0,ans.size()) printf("%c",ans[i]); printf("\n"); }else { repf(i,1,INF) { if(step[i].size() == 0) { s--; ans.push_back('L'); if(s == t) break; }else { int L = step[i][0]; int R = step[i][1]; if((s-1<=R && s-1>=L)||(s <= R && s >= L)) ans.push_back('X'); else { s--; ans.push_back('L'); if(s == t) break; } } } rep(i,0,ans.size()) printf("%c",ans[i]); printf("\n"); } return 0; }

上一篇:linux内核中struct file_operations 结构体介绍
下一篇:三十分钟掌握STL

相关文章

关键词: 水题CF

相关评论