首页 > 代码库 > Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)
Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)
C. Ray Tracing
There are k sensors located in the rectangular room of size n × m meters. The i-th sensor is located at point (xi, yi). All sensors are located at distinct points strictly inside the rectangle.
Opposite corners of the room are located at points (0, 0) and (n, m). Walls of the room are parallel to coordinate axes.
At the moment 0, from the point (0, 0) the laser ray is released in the direction of point (1, 1). The ray travels with a speed of 
meters per second. Thus, the ray will reach the point (1, 1) in exactly one second after the start.
When the ray meets the wall it‘s reflected by the rule that the angle of incidence is equal to the angle of reflection. If the ray reaches any of the four corners, it immediately stops.
For each sensor you have to determine the first moment of time when the ray will pass through the point where this sensor is located. If the ray will never pass through this point, print - 1 for such sensors.
The first line of the input contains three integers n, m and k (2 ≤ n, m ≤ 100 000, 1 ≤ k ≤ 100 000) — lengths of the room‘s walls and the number of sensors.
Each of the following k lines contains two integers xi and yi (1 ≤ xi ≤ n - 1, 1 ≤ yi ≤ m - 1) — coordinates of the sensors. It‘s guaranteed that no two sensors are located at the same point.
Print k integers. The i-th of them should be equal to the number of seconds when the ray first passes through the point where the i-th sensor is located, or - 1 if this will never happen.
3 3 4
1 1
1 2
2 1
2 2
1
-1
-1
2
3 4 6
1 1
2 1
1 2
2 2
1 3
2 3
1
-1
-1
2
5
-1
7 4 5
1 3
2 2
5 1
5 3
4 3
13
2
9
5
-1
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<stdlib.h> 5 #include<string.h> 6 #include<math.h> 7 #include<queue> 8 using namespace std; 9 typedef long long LL;10 pair<LL,LL>exgcd(LL n,LL m);11 LL solve(LL x, LL y,LL n,LL m,LL gc,LL ak);12 LL gcd(LL n,LL m);13 int main(void)14 {15 LL n,m,k;16 while(scanf("%lld %lld %lld",&n,&m,&k)!=EOF)17 { LL gc = gcd(2*n,2*m); pair<LL,LL>ak = exgcd(2*n,2*m);18 LL minn = min(solve(0,0,2*n,2*m,gc,ak.first),solve(n,m,2*n,2*m,gc,ak.first));19 minn = min(minn,solve(0,m,2*n,2*m,gc,ak.first));20 minn = min(solve(n,0,2*n,2*m,gc,ak.first),minn);//printf("%lld\n",minn);21 while(k--)22 {23 LL x,y;24 scanf("%lld %lld",&x,&y);25 LL akk = min(solve(x,y,2*n,2*m,gc,ak.first),solve(2*n-x,2*m-y,2*n,2*m,gc,ak.first));26 LL bk = min(solve(x,2*m-y,2*n,2*m,gc,ak.first),solve(2*n-x,y,2*n,2*m,gc,ak.first));27 akk = min(akk,bk);//printf("%lld\n",ak);28 if(akk==1e18||akk>minn)printf("-1\n");29 else printf("%lld\n",akk);30 }31 }32 return 0;33 }34 pair<LL,LL>exgcd(LL n,LL m)35 {36 if(m==0)37 return make_pair(1,0);38 else39 {40 pair<LL,LL>ak = exgcd(m,n%m);41 return make_pair(ak.second,ak.first-(n/m)*ak.second);42 }43 }44 LL solve(LL x, LL y,LL n,LL m,LL gc,LL ak)45 {46 LL cc = n;47 LL c = x-y;48 if(c%gc)return 1e18;49 else50 {51 c/=gc;52 n/=gc;53 m/=gc;54 LL x0 = (ak*c%m+m)%m;55 LL lcm = (LL)m*cc;56 x = x-cc*x0;57 x = x%lcm+lcm;58 x%=lcm;59 if(x==0)x+=lcm;60 return x;61 }62 }63 LL gcd(LL n,LL m)64 {65 if(m==0)return n;66 else return gcd(m,n%m);67 }
You are given a string s, consisting of lowercase English letters, and the integer m.
One should choose some symbols from the given string so that any contiguous subsegment of length m has at least one selected symbol. Note that here we choose positions of symbols, not the symbols themselves.
Then one uses the chosen symbols to form a new string. All symbols from the chosen position should be used, but we are allowed to rearrange them in any order.
Formally, we choose a subsequence of indices 1 ≤ i1 < i2 < ... < it ≤ |s|. The selected sequence must meet the following condition: for every j such that 1 ≤ j ≤ |s| - m + 1, there must be at least one selected index that belongs to the segment [j, j + m - 1], i.e. there should exist a k from 1 to t, such that j ≤ ik ≤ j + m - 1.
Then we take any permutation p of the selected indices and form a new string sip1sip2... sipt.
Find the lexicographically smallest string, that can be obtained using this procedure.
The first line of the input contains a single integer m (1 ≤ m ≤ 100 000).
The second line contains the string s consisting of lowercase English letters. It is guaranteed that this string is non-empty and its length doesn‘t exceed 100 000. It is also guaranteed that the number m doesn‘t exceed the length of the string s.
Print the single line containing the lexicographically smallest string, that can be obtained using the procedure described above.
3
cbabc
a
2
abcab
aab
3
bcabcbaccba
aaabb
In the first sample, one can choose the subsequence {3} and form a string "a".
In the second sample, one can choose the subsequence {1, 2, 4} (symbols on this positions are ‘a‘, ‘b‘ and ‘a‘) and rearrange the chosen symbols to form a string "aab".
题意：给出整数m和一个字符串，要求从所给的字符串中选出一些任意顺序组成一个字符串，要求新的字符串在所有符合条件的字符串中字典序最小，如果选择了第i个字符那么在下标在[i+1, i + 1+m]范围内的字符至少被选一个；
思路：贪心+单调队列；
我们贪心选取，第一个区间的最小值，区间长度为m那么接下来这个区间每次向右滑一个单位，然后我们只要看下当前区间的一个值是不是被前面区间的最小值，因为如果这个值被选了，无论是不是本区间的最小值，那么本区间就不必再选数了，如果不是，那么找当前区间的最小值选，并且这个最小值要靠后，因为前面的已经保证了，尽量往后选，才能使要选的更少，最小值用单调队列维护。然后最大值，前面所有比他小的都要补上，复杂度O（n）；
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<math.h> 6 #include<queue> 7 #include<stack> 8 #include<set> 9 using namespace std; 10 char str[100005]; 11 int cnt[26]; 12 int ask[100005]; 13 int quq[100005]; 14 set<int>vec; 15 set<int>::iterator it; 16 int main(void) 17 { 18 int n; 19 int i,j; 20 while(scanf("%d",&n)!=EOF) 21 { 22 vec.clear(); 23 scanf("%s",str+1); 24 int l =strlen(str+1); 25 memset(cnt,0,sizeof(cnt)); 26 for(i = 1; i <= l; i++) 27 { 28 cnt[str[i]-‘a‘]++; 29 } 30 int head = 1; 31 int rail = 0; 32 int cn = 0; 33 for(i = 1; i <= n; i++) 34 { 35 if(head > rail) 36 { 37 quq[++rail] = i; 38 } 39 else 40 { 41 while(true) 42 { 43 if(head > rail) 44 break; 45 int id = quq[rail]; 46 if(str[id] >= str[i]) 47 { 48 rail--; 49 } 50 else break; 51 } 52 quq[++rail] = i; 53 } 54 } 55 vec.insert(quq[head]); 56 for(i = n+1; i <= l; i++) 57 { 58 while(true) 59 { 60 if(head>rail) 61 break; 62 int id = quq[rail]; 63 if(str[id] >= str[i]&&!vec.count(id)) 64 { 65 rail--; 66 } 67 else break; 68 } 69 quq[++rail] = i; 70 int ic = quq[head]; 71 while(ic < i-n+1) 72 { 73 head++; 74 ic = quq[head]; 75 } 76 vec.insert(quq[head]); 77 } 78 for(it = vec.begin(); it!=vec.end(); it++) 79 { 80 ask[cn++] = str[*it]-‘a‘; 81 cnt[ask[cn-1]]--; 82 } 83 sort(ask,ask+cn); 84 int maxx = ask[cn-1]; 85 for(i = 0; i < 26; i++) 86 { 87 if(i < maxx) 88 { //printf("%d\n",cnt[i]); 89 while(cnt[i]) 90 { 91 ask[cn++] = i; 92 cnt[i]--; 93 } 94 } 95 } 96 sort(ask,ask+cn); 97 for(i = 0; i <cn; i++) 98 printf("%c",ask[i]+‘a‘); 99 printf("\n");100 }101 return 0;102 }
Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)