Codeforces 652F 解题报告

题意

有n只蚂蚁在长度为m个格子的环上,环上的格子以逆时针编号,每只蚂蚁每秒往它面向的方向移动一格。如果有两只蚂蚁相撞则相互调换方向,问t秒后每只蚂蚁的位置。

题解

首先通过观察可以发现

  • 蚂蚁相撞产生的轨迹可以看成两只蚂蚁穿过对方
  • 由于相撞后只会互相调换方向,每只蚂蚁的相对编号不会发生变化,即每只蚂蚁的“邻居”不会发生变化

也就是说:

  • 我可以通过计算每只蚂蚁毫无阻碍产生的轨迹知道t秒后哪些位置上有蚂蚁
  • 又由于每只蚂蚁的相对编号不变,我只要知道某只蚂蚁t秒后的位置就可以推算出剩下的所有蚂蚁的位置

现在的问题就由第一个问题转换成第二个问题:

  • t秒后第x个蚂蚁的位置是哪
  • t秒后第x个位置的蚂蚁编号是多少

对于第二个问题,我们只要求出t秒后蚂蚁按位置编号大小排序的序列就可以算出答案。假设一开始蚂蚁按初始位置编号的大小顺序排好,位置0(位置1与位置m的中间)是一个临界点,考虑两种情况来求出t秒后蚂蚁的顺序:

  • t秒内所有蚂蚁没有发生碰撞:当有蚂蚁从1经过0走到m时,那么这只蚂蚁就会变成最后一只蚂蚁,第二只蚂蚁会变成第一只,以此类推。同理,当有蚂蚁从m经过0走到1时,这只蚂蚁就会变成第一只蚂蚁。因此我们只要计算t秒内蚂蚁有多少次从右至左走过0点或从左至右走过0点,求差就可以得到蚂蚁在t秒后的顺序。

  • t秒内有蚂蚁发生碰撞:如果有蚂蚁发生碰撞,因为蚂蚁的轨迹可以看成穿过对方,因此我们还是可以忽略掉碰撞的情况去计算蚂蚁从两个方向通过0点的次数,就当成上面那种情况。每从右向左通过0点一次,蚂蚁的排列序列就左移一次,向右同理。

举个例子,假如一开始蚂蚁编号的排列顺序为[1,3,2],在某一秒2从m点通过了0点到1点,序列变成[2,1,3]。假如2与1发生碰撞,2再次反向通过0点,排列顺序又变回[1,3,2]。看上去好像要判断蚂蚁2从不同方向经过了0点,但是我们完全可以忽略碰撞看成蚂蚁2从左边经过了一次0点和蚂蚁1从右边经过了一次0点,对于复杂的情况也完全适应。

此时我们已知:

  • t秒后那些位置上有蚂蚁
  • t秒后蚂蚁按位置的排序

我们就可以直接一一对应上蚂蚁的位置了

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define per(i, a, b) for(int i=(a-1); i>=(b); i--)
typedef long long ll;
const int maxn = 300005;
const int inf = 0x3f3f3f3f;
struct A {
    ll pos;
    char f;
    bool operator<(const A &x) const {
        return pos < x.pos;
    }
}a[maxn];
int id[maxn], ans[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    ll n, m, t;
    cin >> n >> m >> t;
    int offset = 0;
    rep(i, 0, n) {
        id[i] = i;
        cin >> a[i].pos >> a[i].f;
        a[i].pos--;
    }
    //排序得到蚂蚁的初始排列
    sort(id, id + n, [&](int x, int y) { return a[x].pos < a[y].pos; });
    //计算蚂蚁t秒后的排列,顺便算出t秒后哪些位置出现了蚂蚁
    rep(i, 0, n) {
        if (a[i].f == 'L') {
            offset = (offset + (a[i].pos - t - m + 1) / m) % n;
            a[i].pos = ((a[i].pos - t)%m + m) % m;
        }
        else {
            offset = (offset + (a[i].pos + t) / m) % n;
            a[i].pos = (a[i].pos + t) % m;
        }
    }
    offset = (offset + n) % n;
    //对位置排序
    sort(a, a + n);
    //此时初始次序为i编号为id[x]的蚂蚁在t秒后变成了次序为(i+offset)%n的蚂蚁
    rep(i, 0, n) ans[id[i]] = a[(i + offset)%n].pos + 1;
    rep(i, 0, n) cout << ans[i] << ' ';
    return 0;
}
相关文章
相关标签/搜索
香港蓝月亮精选免费资料大全,香港蓝月亮精选免费资料大全期期准app预约 眉山市| 罗田县| 蒙山县| 三门峡市| 遂宁市| 吴桥县| 隆林| 资阳市| 延寿县| 榆中县| 东乡| 宁晋县| 宾阳县| 永兴县| 平江县| 道孚县| 桃源县| 休宁县| 陆良县| 四川省| 西宁市| 平武县| 天峻县| 正阳县| 阳曲县| 泸西县| 德州市| 金秀| 延庆县| 东乡县| 如皋市| 磴口县| 随州市| 青河县| 开原市| 木兰县| 河池市| 九江市| 且末县| 大悟县| 泊头市| 昂仁县| 江门市| 桐柏县| 习水县| 新密市| 金溪县| 綦江县| 清镇市| 莆田市| 安溪县| 如东县| 德江县| 盐山县| 白水县| 塔河县| 镇宁| 永新县| 连平县| 富蕴县| 任丘市| 栾城县| 郎溪县| 始兴县| 荆门市| 濮阳市| 牙克石市| 邵阳县| 长宁区| 通辽市| 商丘市| 额济纳旗| 佛山市| 新乡市| 高要市| 和林格尔县| 昌宁县| 延庆县| 勃利县| 卢湾区| 阿巴嘎旗| 林芝县| 平定县| 东源县| 资兴市| 深州市| 抚远县| 稻城县| 安顺市| 武定县| 潍坊市| 孙吴县| 随州市| 富阳市| 麻江县| 青海省| 玉环县| 会泽县| 安图县| 天门市| 长垣县| 湟中县| 六盘水市| 山丹县| 罗定市| 乡城县| 普兰县| 财经| 临猗县| 晋宁县| 永修县| 安国市| 蚌埠市| 当阳市| 顺平县| 濮阳县| 宁津县| 衡山县| 女性| 峨山| 福清市| 吴忠市| 泰安市| 商都县| 铜梁县| 涟源市| 客服| 满城县| 西乌珠穆沁旗| 隆昌县| 乡宁县| 金溪县| 大方县| 荔波县| 高碑店市| 富宁县| 合肥市| 聊城市| 防城港市| 凤城市| 泾源县| 衡东县| 江北区| 武安市| 方城县| 鹰潭市| 杭锦旗| 宁都县| 祁门县| 金川县| 武川县| 青海省| 福海县| 南部县| 兴宁市| 克什克腾旗| 尖扎县| 虹口区| 左贡县| 泽州县| 昂仁县| 武陟县| 广州市| 班戈县| 铜陵市| 大同县| 安阳县| 余干县| 双江| 汪清县| 甘孜县| 内黄县| 班戈县| 桦南县| 南宁市| 东乡县| 井冈山市| 海阳市| 阿拉尔市| 瑞昌市| 扶绥县| 公安县| 射阳县| 广德县| 隆化县| 龙口市| 健康| 乳源| 贵溪市| 深州市| 盐边县| 宜宾市| 鹰潭市| 九龙坡区| 佛山市| 堆龙德庆县| 睢宁县| 青阳县| 肥城市| 静乐县| 师宗县| 根河市| 江源县| 方城县| 黄大仙区| 重庆市| 云梦县| 屏边| 涿鹿县| 泽州县| 望江县| 溆浦县| 宣城市| 惠州市| 博罗县| 中江县| 靖远县| 江永县| 扶绥县| 富平县| 兴义市| 陇川县| 梨树县| 酒泉市| 侯马市| 东城区| 瑞金市| 霍城县| 巴青县| 宁南县| 石狮市| 思南县| 平顶山市| 宜都市| 台江县| 山东省| 迭部县| 镇沅| 邯郸市| 泾阳县| 教育| 丰原市| 宣恩县| 云阳县| 安化县| 金堂县| 邢台县| 乌拉特后旗| 武夷山市| 宜昌市| 满城县| 阜宁县| 团风县| 郓城县| 牟定县| 密云县| 大厂| 嵩明县| 嘉黎县| 谢通门县| 前郭尔| 颍上县| 万盛区| 曲周县| 色达县| 汕头市| 凤庆县| 靖西县| 民县| 边坝县| 鸡泽县| 稻城县| 龙胜| 通许县| 乐至县| 滕州市| 新化县| 枣阳市| 治多县| 金平| 雷波县| 德清县| 陆河县| 长沙县| 繁峙县| 靖宇县| 太和县| 密山市| 南陵县| 博白县| 桃源县| 永州市| 安远县| 清水县| 长岭县| 邳州市| 策勒县| 虎林市| 绥江县| 曲周县| 仙居县| 宜都市| 连州市| 双峰县| 英德市| 潼南县| 犍为县| 南岸区| 建宁县| 调兵山市| 郴州市| 柘城县| 惠东县| 桃源县| 大方县| 息烽县| 全州县| 集安市| 阿尔山市| 桦川县| 长垣县| 衡阳县| 成安县| 朝阳县| 郁南县| 延津县| 江北区| 阳原县| 清河县| 铜川市| 惠水县| 鄢陵县| 三江| 石狮市| 定结县| 基隆市| 香河县| 旬阳县| 南阳市| 昌邑市| 大足县| 太白县| 高台县| 恩施市| 集贤县| 安国市| 九龙坡区| 安宁市| 抚宁县| 邹平县| 定陶县| 稷山县| 达孜县| 斗六市| 穆棱市| 吉林省| 增城市| 霍林郭勒市| 滕州市| 吕梁市| 横山县| 荃湾区| 肥城市| 班玛县| 东阳市| 兴化市| 咸宁市| 安岳县| 武清区| 句容市| 清原| 历史| 双桥区| 舒城县| 尤溪县| 灯塔市| 汤阴县| 贵南县| 沁源县| 修水县| 南部县| 洛宁县| 莆田市| 郧西县| 大同县| 兴城市| 彰化市| 南郑县| 海淀区| 东宁县| 枝江市| 西华县| 潞城市| 岳普湖县| 遵义市| 鲜城| 敦化市| 临潭县| 西华县| 巢湖市| 苗栗县| 胶南市| 察雅县| 延庆县| 湘潭县| 类乌齐县| 哈密市| 台中县| 永年县| 仁布县| 虹口区| 彰化县| 新泰市| 玉树县| 龙岩市| 景谷| 西和县| 芦溪县| 清远市| 来宾市| 名山县| 苗栗县| 吴旗县| 夏津县| 嘉禾县| 南乐县| 合作市| 鸡泽县| 丹棱县| 南澳县| 勐海县| 潮州市| 遵义县| 桑日县| 会理县| 黄冈市| 玉山县| 嘉义县| 三亚市| 曲沃县| 龙州县| 南木林县| 海安县| 永和县| 淅川县| 锦屏县| 古浪县| 雅江县| 耒阳市| 天门市| 南平市| 黎城县| 布尔津县| 介休市| 三河市| 英山县| 读书| 太谷县| 长沙县| 临潭县| 剑阁县| 昆明市| 牡丹江市| 七台河市| 古交市| 北流市| 阳高县| 安塞县| 永登县| 太湖县| 罗定市| 特克斯县| 峡江县| 浦城县| 马龙县| 平山县| 盱眙县| 荃湾区| 扎囊县| 仙居县| 革吉县| 宿州市| 奈曼旗| 淮阳县| 民权县| 孝昌县| 江门市| 钟祥市| 民权县| 金寨县| 蒙城县| 宁海县| 镇安县| 霍林郭勒市| 屯昌县| 长宁区| 玉树县| 崇明县| 习水县| 濉溪县| 陆河县| 青州市| 鹤岗市| 太湖县| 碌曲县| 浦县| 松溪县| 乌拉特后旗| 乌兰浩特市| 吴忠市| 德州市| 广灵县| 武夷山市| 和顺县| 阜城县| 海安县| 衢州市| 育儿| 西乡县| 珠海市| 高邑县| 五大连池市| 江川县| 迁西县| 桃园市| 射阳县| 舟山市| 保靖县| 临夏市| 旬阳县| 东安县| 溧水县| 华池县| 卢湾区| 楚雄市| 淮安市| 建阳市| 重庆市| 华池县| 曲阳县| 金秀| 高邑县| 平陆县| 都兰县| 潞西市| 建湖县| 板桥市| 饶河县| 灵台县| 调兵山市| 鄂尔多斯市| 荃湾区| 江永县| 台前县| 灵山县| 徐闻县| 沈丘县| 卢氏县| 扎赉特旗| 阳城县| 绿春县| 永靖县| 株洲县| 昔阳县| 通榆县| 阿坝县| 宜州市| 眉山市| 永顺县| 山东省| 梨树县| 阿拉善盟| 得荣县| 丰镇市| 博湖县| 江山市| 聂拉木县| 湘潭县| 德阳市| 泾川县| 双辽市| 芷江| 珲春市| 扎赉特旗| 信丰县| 饶河县| 本溪| 车险| 五河县| 千阳县| 衡阳县| 葵青区| 博爱县| 攀枝花市| 大英县| 桃园县| 湟中县| 大荔县| 兰州市| 通辽市| 沁阳市| 普兰店市| 方正县| 井研县| 固安县| 姜堰市| 望谟县| 绥德县| 东明县| 罗甸县| 哈密市| 玉溪市| 都昌县| 本溪市| 石景山区| 奉化市| 翼城县| 拉萨市| 方正县| 广宁县| 玛曲县| 沾化县| 十堰市| 宜昌市| 分宜县| 木兰县| 高邑县| 怀仁县| 唐山市| 新乡市| 清涧县| 平顶山市| 富源县| 汪清县| 义乌市| 涡阳县| 会理县| 洪江市| 衡东县| 水城县| 茌平县| 临漳县| 定结县| 河源市| 深州市| 洪雅县| 凌海市| 扶绥县| 新晃| 渝北区| 青浦区| 石棉县| 四川省| 万源市| 贵定县| 焦作市| 周宁县| 乌拉特前旗| 平潭县| 吉木乃县| 中山市| 通榆县| 隆子县| 齐齐哈尔市| 博野县| 大足县| 封开县| 寿光市| 道孚县| 九龙城区| 洪江市| 柘城县| 玉溪市| 交城县| 平顶山市| 岳池县| 库伦旗| 佛冈县| 宁城县| 舟曲县| 绥德县| 波密县| 策勒县| 汶川县| 万年县| 广平县| 拉萨市| 合川市| 黑河市| 璧山县| 山东| 河源市| 木里| 宜章县| 射洪县| 蒲江县| 长宁县| 文昌市| 绍兴县| 霍林郭勒市| 洮南市| 繁峙县| 兴仁县| 梁山县| 平利县| 庄河市| 钦州市| 科尔| 滕州市| 枣强县| 潜江市| 阳西县| 西林县| 剑阁县| 高青县| 通榆县| 黄山市| 景谷| 桐梓县| 盐城市| 永胜县| 承德县| 安福县| 仁化县| 垫江县| 宝鸡市| 墨玉县| 阿克苏市| 南溪县| 新余市| 吴江市| 高安市| 乾安县| 广南县| 高阳县| 乌拉特前旗| 黔东| 双流县| 环江| 咸宁市| 陇西县| 视频| 南丰县| 衡东县| 平顶山市| 布尔津县| 铁力市| 丹凤县| 湖北省| 高碑店市| 新民市| 射洪县| 车致| 泽库县| 彩票| 宝兴县| 利辛县| 濉溪县| 邳州市| 岚皋县| 噶尔县| 上犹县| 余干县| 正宁县| 逊克县| 达日县| 汉沽区| 蚌埠市| 焦作市| 西峡县| 咸阳市| 湟中县| 彩票| 永平县| 南澳县| 肇东市| 中卫市| 阳山县| 霍林郭勒市| 石台县| 杂多县| 上虞市| 光山县| 陕西省| 崇信县| 滦南县| 启东市| 茂名市| 昌都县| 阿克陶县| 翁源县| 湖州市| 乡宁县| 罗平县| 襄樊市| 华池县| 莒南县| 岳阳市| 玛多县| 浦东新区| 邵阳县| 永兴县| 衡南县| 方城县| 古田县| 会泽县| 大新县| 崇明县| 邮箱| 庆元县| 西畴县| 大安市| 山丹县| 禹城市| 济宁市| 岳池县| 安阳县| 高邮市| 揭东县| 揭西县| 黄浦区| 敦煌市| 醴陵市| 峨边| 凭祥市| 临海市| 永清县| 荣成市| 汽车| 巫山县| 台中县| 马鞍山市| 太和县| 高邮市| 固始县| 鹤峰县| 阳城县| 福海县| 华安县| 海安县| 上饶市| 墨玉县| 饶阳县| 安仁县| 肃宁县| 缙云县| 长宁县| 宜宾市| 吴忠市| 宁夏| 勐海县| 阿拉善右旗| 龙门县| 苏尼特左旗| 浮梁县| 闻喜县| 乐安县| 巴青县| 古田县| 清徐县| 曲阜市| 当雄县| 博乐市| 石河子市| 渭源县| 安平县| 嘉祥县| 杭州市| 阿拉善右旗| 秦皇岛市| 阿图什市| 万宁市| 翼城县| 长宁县| 马龙县| 天水市| 宜章县| 米泉市| 石渠县| 琼海市| 江永县| 社旗县| 来安县| 东台市| 南投县| 日土县| 柳河县| 洛川县| 闽侯县| 凤凰县| 阳曲县| 南漳县| 梁河县| 清徐县| 鹿泉市| 浑源县| 天峻县| 邯郸市| 攀枝花市| 凤山县| 郁南县| 十堰市| 吴桥县| 延川县| 丰镇市| 三江| 皮山县| 应城市| 灵石县| 东丰县| 西安市| 微山县| 云浮市| 太仓市| 大庆市| 福安市| 启东市| 德格县| 郑州市| 喀什市| 正安县| 张家港市| 汕尾市| 阿巴嘎旗| 天津市| 临汾市| 卓资县| 邢台市| 福泉市| 康乐县| 江城| 石台县| 法库县| 宜都市| 乌拉特后旗| 淳化县| 二连浩特市| 宜良县| 绥化市| 恩平市| 大方县| 共和县| 桃江县| 九江县| 龙江县| 阿克陶县| 保德县| 香格里拉县| 墨玉县| 定远县| 乌兰县| 北宁市| 大悟县| 临洮县| 论坛| 高碑店市| 天全县| 自治县| 镶黄旗| 四子王旗| 探索| 卫辉市| 乌拉特前旗| 阜南县| 舞钢市| 文登市| 自贡市| 滦平县| 瑞昌市| 灌阳县| 榕江县| 天峻县| 禄劝| 仲巴县| 长沙县| 兰考县| 义乌市| 安阳县| 庆安县| 阿尔山市| 凤山县| 凤阳县| 墨脱县| 泉州市| 临洮县| 祁门县| 株洲市| 南充市| 尼玛县| 交城县| 正阳县| 桦南县| 珲春市| 田阳县| 五莲县| 娱乐| 西林县| 磐安县| 砚山县| 青阳县| 安阳县| 澄迈县| 嘉定区| 康马县| 伊通| 稻城县| 冕宁县| 天柱县| 汉沽区| 沽源县| 安宁市| 梓潼县| 梅河口市| 旬邑县| 肥东县| 富平县| 凤城市| 南溪县| 永寿县| 山阳县| http://www.yqo8j5rl4v.fun http://wap.bo2020flags.fun http://www.gz1980joinc.fun http://www.bo2020quotes.fun http://www.yqo8j0rl7v.fun http://www.gz1980branchc.fun http://www.bo2020handles.fun http://www.yqo5j9rl6v.fun http://www.jvz1j0r1o.fun http://wap.gz1980basec.fun http://m.bo2020exacts.fun http://www.yqo4j4rl6v.fun http://wap.yqo9j9rl4v.fun http://m.gz1980feltc.fun http://www.bo2020houses.fun http://wap.bo2020stocks.fun http://wap.yqo3j6rl7v.fun http://www.gz1980trustc.fun http://www.bo2020pays.fun http://wap.bo2020produces.fun http://wap.yqo4j1rl0v.fun http://www.gz1980sponsorc.fun http://www.bo2020installs.fun http://wap.bo2020seasons.fun http://wap.yqo3j5rl6v.fun