【AtCoder】ARC079

电玩女神 2021-11-01 13:40 204阅读 0赞

# ARC079题解 #

### **C - Cat Snuke and a Voyage** ###

### **D - Decrease (Contestant ver.)** ###

由于发现一个1,2,3,4,5,6,7....N的序列一次操作后可以变成

2,3,4,5,6,7...N,0的序列，这样N次过后，总会得到所有数-1的序列

也就是，我可以进行那么多次，序列可以构造成\\(K / N\\)开始加1到N的序列，就是可以进行\\(\\lfloor \\frac\{K\}\{N\} \\rfloor N\\)那么多次了

剩下的就从头开始逆着往回加即可

### **E - Decrease (Judge ver.)** ###

进行一次操作我们直接把最大的扣到N以下，暴力进行几次复杂度不会太大

### **F - Namori Grundy** ###

若连通还每个点就一个入度，那这是一个有向的基环外向树

把环上挂着的数给dp完，相当于每次对于儿子取一个未出现过的最小值一样的操作

然后环上的点要么取自己未出现过的最小值，要么取把这个最小值填上之后下一个没出现过的

也就是环上前一个点如果选择下一个点的第一选项，下一个点必须选择第二选项

把环上每个点拆成两个点，按照这种关系连边，出现大小恰好为原来环点数的环时合法，如果无环或有一个二倍点数的环就不合法

#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define pdi pair<db,int> #define mp make_pair #define pb push_back #define enter putchar('\n') #define space putchar(' ') #define eps 1e-8 #define mo 974711 #define MAXN 200005 //#define ivorysi using namespace std; typedef long long int64; typedef double db; template<class T> void read(T &res) { res = 0;char c = getchar();T f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f; } template<class T> void out(T x) { if(x < 0) {x = -x;putchar('-');} if(x >= 10) { out(x / 10); } putchar('0' + x % 10); } int N,p[MAXN],deg[MAXN],val[MAXN]; int id[MAXN][2],tot,cir; vector<int> t[MAXN],to[MAXN * 2]; vector<int> son[MAXN]; queue<int> q; int dfn[MAXN * 2],low[MAXN * 2],sta[MAXN * 2],instack[MAXN * 2],idx,top; bool flag = 0; void Tarjan(int u) { dfn[u] = low[u] = ++idx; sta[++top] = u;instack[u] = 1; for(auto v : to[u]) { if(!dfn[v]) {Tarjan(v);low[u] = min(low[v],low[u]);} else if(instack[u] == 1){ low[u] = min(low[u],dfn[v]); } } if(low[u] == dfn[u]) { int k = 0; while(1) { int x = sta[top--]; ++k; instack[x] = 2; if(x == u) break; } if(k == cir) flag = 1; } } void Solve() { read(N); for(int i = 1 ; i <= N ; ++i) { read(p[i]); deg[p[i]]++; } for(int i = 1 ; i <= N ; ++i) { if(!deg[i]) q.push(i); } while(!q.empty()) { int u = q.front();q.pop(); sort(son[u].begin(),son[u].end()); son[u].erase(unique(son[u].begin(),son[u].end()),son[u].end()); int m = 0; while(m < son[u].size()) { if(son[u][m] != m) break; ++m; } son[p[u]].pb(m); if(!--deg[p[u]]) { q.push(p[u]); } } for(int i = 1 ; i <= N ; ++i) { if(deg[i]) { sort(son[i].begin(),son[i].end()); son[i].erase(unique(son[i].begin(),son[i].end()),son[i].end()); int m = 0,pos = 0; while(1) { if(pos >= son[i].size() || son[i][pos] != m) { t[i].pb(m); if(t[i].size() < 2) {++m;} else break; } else {pos++;++m;} } id[i][0] = ++tot;id[i][1] = ++tot; ++cir; } } for(int i = 1 ; i <= N ; ++i) { if(deg[i]) { int f = p[i]; to[id[f][0]].pb(id[i][t[f][0] == t[i][0]]); to[id[f][1]].pb(id[i][t[f][1] == t[i][0]]); } } for(int i = 1 ; i <= tot ; ++i) { if(!dfn[i]) Tarjan(i); } if(flag) puts("POSSIBLE"); else puts("IMPOSSIBLE"); } int main() { #ifdef ivorysi freopen("f1.in","r",stdin); #endif Solve(); return 0; }

转载于:https://www.cnblogs.com/ivorysi/p/10883706.html