题目链接: http://codeforces.com/problemset/problem/652/F
n ants are on a circle of length m. An ant travels one unit of distance per one unit of time. Initially, the ant number i is located at the position si and is facing in the direction di (which is either L or R). Positions are numbered in counterclockwise order starting from some point. Positions of the all ants are distinct.
- All the ants move simultaneously, and whenever two ants touch, they will both switch their directions. Note that it is possible for an ant to move in some direction for a half of a unit of time and in opposite direction for another half of a unit of time.
- Print the positions of the ants after t time units.
- Input
- The first line contains three integers n, m and t (2≤n≤3.105,2≤m≤109,0≤t≤1018) - the number of ants, the length of the circle and the number of time units.
- Each of the next n lines contains integer si and symbol di (1≤si≤m and di is either L or R) - the position and the direction of the i-th ant at the start. The directions L and R corresponds to the clockwise and counterclockwise directions, respectively.
It is guaranteed that all positions si are distinct.
- Output
- Print n integers xj - the position of the j-th ant after t units of time. The ants are numbered from 1 to n in order of their appearing in input.
- Examples
- Input
- 2 4 8
- 1 R
- 3 L
- Output
- 1 3
- Input
- 4 8 6
- 6 R
- 5 L
- 1 R
- 8 L
- Output
- 7 4 2 7
- Input
- 4 8 2
- 1 R
- 5 L
- 6 L
- 8 R
- Output
- 3 3 4 2
题目大意: 有 N 只蚂蚁, M 长度的圆 (可以看做一条直线, 到了终点 回到起点, 到了起点回到终点),T 时间
接下来每只蚂蚁有个初始位置, 往左或者往右, 两只蚂蚁相遇会往自己的反方向走, 问你 T 秒后, 每只蚂蚁在哪个位置
思路:
重要的点有两个:
1. 两只蚂蚁相遇, 虽然都是往反方向走, 但是可以用另一种方式来看, 其实就相当于两只蚂蚁换一下编号, 但是还是沿着初始的方向走, 例如:
1 R
3 L
可以看做 1 一直往右走, 只是相遇之后编号变为了 3
2. 根据 1 我们可以很简单的求出最后所有的蚂蚁的所有位置对吧, 但是问题是, 我们要的是每只蚂蚁对应的位置是啥, 我们仅仅知道所有位置是不够的
所以 2 就是用来求这个了
一个巧妙的思想:
蚂蚁的相对位置不变, 因为相对位置不变, 所以, 蚂蚁每向右穿过 0 线一次, 从 0 开始数第一个蚂蚁就向后顺移一位;
每向左穿过 0 线一次, 就正移一位. 所以只要统计每只蚂蚁穿过 0 线的次数即可, 十分神奇.
看代码:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- #include<vector>
- #include<map>
- #include<stack>
- #include<cstdlib>
- using namespace std;
- typedef long long LL;
- const LL mod=1e9+7;
- const LL INF=1e9+7;
- const int maxn=3e5+50;
- LL now[maxn],ans[maxn];
- struct Node
- {
- LL pos,dir,id;
- }a[maxn];
- bool cmp(const Node x,const Node y)
- {
- return x.pos<y.pos;
- }
- int main()
- {
- char op[5];
- LL N,M,T,v;scanf("%lld%lld%lld",&N,&M,&T);
- for(int i=0;i<N;i++)
- {
- scanf("%lld%s",&v,op);
- v--;// 方便处理 % 操作
- a[i].pos=v;
- // cout<<a[i].pos<<endl;
- if(op[0]=='L') a[i].dir=-1;
- else a[i].dir=1;
- a[i].id=i;
- }
- sort(a,a+N,cmp);// 按起点从小到大排序
- // for(int i=0;i<N;i++) cout<<a[i].id<<" ";cout<<endl;
- LL p=0;// 此时在第一个位置的是 a[0]
- // for(int i=0;i<N;i++) cout<<a[i].pos<<" ";cout<<endl;
- for(int i=0;i<N;i++)
- {
- if(a[i].dir==1)// 代表往右走
- {
- p=((p-((a[i].pos+T)/M)%N)+N)%N;
- }
- else
- {
- p=((p-((a[i].pos-T+1-M)/M)%N)+N)%N;
- }
- now[i]=(((a[i].pos+T*a[i].dir)%M)+M)%M+1;
- }
- // cout<<"p:"<<p<<endl;
- sort(now,now+N);
- // for(int i=0;i<N;i++) cout<<now[i]<<" ";cout<<endl;
- for(int i=0;i<N;i++)
- {
- ans[a[(i+p)%N].id]=now[i];
- }
- for(int i=0;i<N;i++) printf("%d",ans[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3286626.html