国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

cf 759 A Pavel and barbecue

2019-11-11 01:46:32
字體:
來源:轉載
供稿:網友

題意:

給一個序列,序列值代表對應下標下一秒硬幣要移動到的下標,再給一個相同01序列,1代表在這個位置下一秒硬幣翻轉。問需要修改幾次這兩個序列使得每一枚硬幣經過若干秒后能以正面和反面的姿態都經過過每一個點。

解題思路:

之所以需要修改是硬幣的移動位置會形成循環,而這個循環有可能不是全局的,是分成幾堆硬幣內部循環,我們需要找出這樣硬幣的堆數,如果堆數是一那么正好不用改,如果大于一就需要把這幾堆硬幣串聯再一起,需要的修改數量就是堆數。

而翻轉的序列就很好考慮了,我們只考慮一枚硬幣,這枚硬幣經過其它所以點回到原來點后,如果翻轉次數是偶數,那么回來時的狀態和出發時的狀態是一樣的,這樣就會循環下去,那么肯定是不可以正反兩面都經過每一個點的,所以要求翻轉的次數是奇數。

代碼:

#include <bits/stdc++.h>using namespace std;const int maxn=2e5;int add[maxn];bool rev[maxn];bool vis[maxn];int main(){    int n;    scanf("%d", &n);    int i;    for(i=1; i<=n; i++)scanf("%d", &add[i]);    int cir=0;    for(i=1; i<=n; i++)    {        if(vis[i])continue;        cir++;        int t=i;        do        {            vis[t]=1;            t=add[t];        }while(i!=t);    }    int odd=0;    for(i=1; i<=n; i++){scanf("%d", &rev[i]);if(rev[i])odd++;}    int ans=0;//    PRintf("%d/n", ans);    if(odd%2==0)ans++;    printf("%d/n", ans+(cir>1?cir:0));    return 0;}


上一篇:poj1018

下一篇:poj1018

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 安平县| 祁连县| 安泽县| 水城县| 大洼县| 桃江县| 唐海县| 洛浦县| 大埔区| 韶关市| 司法| 黑山县| 腾冲县| 洞头县| 奉节县| 措勤县| 靖边县| 金秀| 镶黄旗| 开鲁县| 英吉沙县| 介休市| 察隅县| 海兴县| 桂阳县| 南投县| 南平市| 和平县| 涿州市| 名山县| 剑河县| 临猗县| 河津市| 崇仁县| 德庆县| 梨树县| 都江堰市| 黄山市| 邵阳县| 武安市| 塘沽区|