Codeforces Round #383 (Div. 2) C. Arpa's loud Owf and Mehrdad's evil plan(dfs+数学思想)

时间:2022-09-17 14:14:51

题目链接:http://codeforces.com/contest/742/problem/C

题意:题目比较难理解,起码我是理解了好久,就是给你n个位置每个位置标着一个数表示这个位置下一步能到哪个位置,然后要求

求一个数t,保证经过t步x能到达y,而且y经过t步能到x,而且是所有点都要满足。

这题只有一种情况是无法得到结果的,那就是有两个以上的点通向同一个位置。其实题目中也略微有点提示。

然后剩下的就差不多靠暴力解决,但还是有点技巧的。

注意要满足题目中要求其实就是找单向联通块,如果联通数为偶数那么就可以折半,否则就为循环到自己。

然后求各个联通块的gcd即可。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int M = 110;
int gcd(int a , int b) {
return b ? gcd(b , a % b) : a;
}
int vis[M] , Next[M] , have[M];
int dfs(int pos) {
if(vis[Next[pos]])
return 0;
vis[Next[pos]] = 1;
return 1 + dfs(Next[pos]);
}
int main() {
int n;
scanf("%d" , &n);
int flag = 0;
for(int i = 1 ; i <= n ; i++) {
scanf("%d" , &Next[i]);
have[Next[i]]++;
if(have[Next[i]] > 1)
flag = 1;
}
if(flag == 1) {
printf("-1\n");
}
else {
int ans = 1;
for(int i = 1 ; i <= n ; i++)
vis[i] = 0;
for(int i = 1 ; i <= n ; i++) {
if(vis[i])
continue;
int l = dfs(i);
if(l % 2 == 0)
l /= 2;
ans = (ans * l) / gcd(ans , l);
}
printf("%d\n" , ans);
}
return 0;
}

Codeforces Round #383 (Div. 2) C. Arpa's loud Owf and Mehrdad's evil plan(dfs+数学思想)的更多相关文章

  1. Codeforces Round &num;383 &lpar;Div&period; 2&rpar; C&period; Arpa&&num;39&semi;s loud Owf and Mehrdad&&num;39&semi;s evil plan —— DFS找环

    题目链接:http://codeforces.com/contest/742/problem/C C. Arpa's loud Owf and Mehrdad's evil plan time lim ...

  2. Codeforces Round &num;383 &lpar;Div&period; 2&rpar;C&period; Arpa&&num;39&semi;s loud Owf and Mehrdad&&num;39&semi;s evil plan

    C. Arpa's loud Owf and Mehrdad's evil plan time limit per test 1 second memory limit per test 256 me ...

  3. C&period; Arpa&&num;39&semi;s loud Owf and Mehrdad&&num;39&semi;s evil plan DFS &plus; LCM

    http://codeforces.com/contest/742/problem/C 首先把图建起来. 对于每个a[i],那么就在i --- a[i]建一条边,单向的. 如果有一个点的入度是0或者是 ...

  4. code forces 383 Arpa&&num;39&semi;s loud Owf and Mehrdad&&num;39&semi;s evil plan&lpar;有向图最小环&rpar;

    Arpa's loud Owf and Mehrdad's evil plan time limit per test 1 second memory limit per test 256 megab ...

  5. Arpa&&num;39&semi;s loud Owf and Mehrdad&&num;39&semi;s evil plan

    Arpa's loud Owf and Mehrdad's evil plan time limit per test 1 second memory limit per test 256 megab ...

  6. C&period; Arpa&&num;39&semi;s loud Owf and Mehrdad&&num;39&semi;s evil plan

    C. Arpa's loud Owf and Mehrdad's evil plan time limit per test 1 second memory limit per test 256 me ...

  7. Codeforces Round &num;383 &lpar;Div&period; 2&rpar; D&period; Arpa&&num;39&semi;s weak amphitheater and Mehrdad&&num;39&semi;s valuable Hoses —— DP(01背包)

    题目链接:http://codeforces.com/contest/742/problem/D D. Arpa's weak amphitheater and Mehrdad's valuable ...

  8. Codeforces Round &num;383 &lpar;Div&period; 2&rpar; B&period; Arpa’s obvious problem and Mehrdad’s terrible solution —— 异或

    题目链接:http://codeforces.com/contest/742/problem/B B. Arpa's obvious problem and Mehrdad's terrible so ...

  9. Codeforces Round &num;383 &lpar;Div&period; 2&rpar; D&period; Arpa&&num;39&semi;s weak amphitheater and Mehrdad&&num;39&semi;s valuable Hoses&lpar;分组背包&plus;dsu&rpar;

    D. Arpa's weak amphitheater and Mehrdad's valuable Hoses Problem Description: Mehrdad wants to invit ...

随机推荐

  1. openlayers

    很久没有写东西了,最近突然想看看地图,就翻看了下,用了2-3周时间看看网页,学习做了下:先看做的效果:

  2. Windows API 文件处理

    CloseHandle 关闭一个内核对象.其中包括文件.文件映射.进程.线程.安全和同步对象等 CompareFileTime 对比两个文件的时间 CopyFile 复制文件 CreateDirect ...

  3. HDU 2852 KiKi&&num;39&semi;s K-Number(树状数组&plus;二分搜索)

    题意:给出三种操作 0 e:将e放入容器中 1 e:将e从容器中删除,若不存在,则输出No Elment! 2 a k:搜索容器中比a大的第k个数,若不存在,则输出Not Find! 思路:树状数组+ ...

  4. SPRING IN ACTION 第4版笔记-第九章Securing web applications-010-拦截请求

    一. What if you wanted to restrict access to certain roles only on Tuesday? Using the access() method ...

  5. Ormlite or&lpar;&rpar;的使用

    如题,由于不熟悉这个框架的API,所以用的时候出错了,直接上代码 public List<Type> getAllBetweenDate(String start, String end) ...

  6. java 操作格子问题(线段树)

    很久之前做过线段树的问题(操作格子),时间长了之后再次接触到,发现当初理解的不是很透彻,然后代码冗长,再遇到的时候发现自己甚至不能独立地完成这个问题. 所以算法这个东西啊, 第一,是要经常练习(我个人 ...

  7. DSAPI Wifi热点的扫描与连接

    使用DSAPI扫描和连接Wifi热点,支持连接隐藏的SSID. 效果演示: 代码如下: Private Wifi As New DSAPI.网络.Wifi Private Sub Button1_Cl ...

  8. miniui中可以设置是否让页面进行分页 &lt&semi;div id&equals;&quot&semi;datagrid1&quot&semi; class&equals;&quot&semi;mini-datagrid&quot&semi; style&equals;&quot&semi;width&colon;100&percnt;&quot&semi; allowAlternating&equals;&quot&semi;true&quot&semi; showpager&equals;&quot&semi;true&quot&semi;&sol;&gt&semi; 就是设置showpager属性为true

    <div id="datagrid1" class="mini-datagrid" style="width:100%" allowA ...

  9. echarts设置toolTip大小和样式问题

    最近研究echarts,发现提示框太大,位置不合适问题, 用jq,css选中div的tooltip设置大小有时候不管用: 查了官网文档 http://echarts.baidu.com/option. ...

  10. C错误异常处理&comma;异常处理

    预处理器标识#error的目的是什么啊? 指令 用途 # 空指令,无任何效果 #include 包含一个源代码文件 #define 定义宏 #undef 取消已定义的宏 #if 如果给定条件为真,则编 ...