支付宝 收费 网站开发,连云港建设部网站,怎么给QQ名片做网站,软件开发难度大吗ARC079F - Namori Grundy
Solution
首先这是一个NNN个点NNN条边的有向图#xff0c;所以它的基图是一棵基环树#xff0c;其次这个图的所有点入度为111#xff0c;因此这是一棵基环外向树。
然后对于aia_iai#xff0c;假设我们求出S{aj∣(i,j)∈E}S\{a_j|(i,j)\in E\…ARC079F - Namori Grundy
Solution
首先这是一个NNN个点NNN条边的有向图所以它的基图是一棵基环树其次这个图的所有点入度为111因此这是一棵基环外向树。
然后对于aia_iai假设我们求出S{aj∣(i,j)∈E}S\{a_j|(i,j)\in E\}S{aj∣(i,j)∈E}即iii的所有出边的aaa的集合那么显然aimexSa_imex\;SaimexSaia_iai的值是可以通过其出边唯一确定的。
我们先考虑一棵树的情况我们发现叶子结点必然为000因此每一个结点iii的aia_iai都可以从下到上通过其儿子结点递推得到。
现在考虑基环树对于环上一点我们可以通过它的子树唯一确定去掉环时它的aaa然后可以发现当且仅当环长为奇数且环上结点的aaa都相等时无解。
然后直接找到环递推求出每一个aaa判一判就行了。
时间复杂度O(n)O(n)O(n)。
Proof
现在我们可以把子树点都扔掉只考虑一个kkk元环。 我们设环上点依次为0,1,2...k−10,1,2...k-10,1,2...k−1(i1,i)∈E(i1,i)\in E(i1,i)∈E之后的下标都在模kkk意义下。
若ai1a_{i1}ai1要加111当且仅当ai1aia_{i1}a_iai1ai。因为环上点出度为111一个点最多加111。
首先我们不会让所有点都加111因为这和所有点不变一样所以若存在方案一定有一种有至少一个点ppp不动的方案。
如果我们知道ppp那么我们可以从ppp开始判断apa_pap是否等于ap1a_{p1}ap1若相等则ap11a_{p1}1ap11。
我们令一段连续的111的下标区间为[l1,r][l1,r][l1,r]显然有alal1,al11al2,al21al3...a_{l}a_{l1},a_{l1}1a_{l2},a_{l2}1a_{l3}...alal1,al11al2,al21al3...因此这段aaa一定是al,al,al1,al2...al(r−l−1)a_l,a_l,a_l1,a_l2...a_l(r-l-1)al,al,al1,al2...al(r−l−1)点lll不动且为其中的最小值。
所以我们有结论若能找到一个iii使得ai̸ai−1a_i\not a_{i-1}aiai−1且∀jai≤aj\forall_j a_i\leq a_j∀jai≤ajiii可以作为ppp方案存在。
那么最后还剩下找不到iii的环其上的点必然是所有aaa相等的这个就很容易考虑了因为所有点都等价所以可以任取一个作为ppp最后的序列一定长成ap,ap1,ap,ap1,ap,ap1...a_p,a_p1,a_p,a_p1,a_p,a_{p}1...ap,ap1,ap,ap1,ap,ap1...的形式。
这就相当于一个二分图染色只有当kkk为奇数时存在相邻两个aaa相等不合法当aaa为偶数时存在合法方案。
综上当且当且仅当环长为奇数且环上结点的aaa都相等时无解。
Code
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
vectorint e[MAXN];
int fa[MAXN],vis[MAXN],instk[MAXN],flag[MAXN],tag[MAXN],f[MAXN],n;
void dfs(int x)
{vis[x]1,instk[x]1;for (auto v:e[x]){if (instk[v]) {for (int px;p!v;pfa[p]) flag[p]1;flag[v]1;}else fa[v]x,dfs(v);}instk[x]0;
}void tree_dp(int x,int father)
{for (auto v:e[x]) if (v!father!flag[v]) tree_dp(v,x);for (auto v:e[x]) if (v!father!flag[v]) tag[f[v]]x;for (int i0;in;i) if (tag[i]!x) { f[x]i; return; }
}signed main()
{nread();for (int i1,x;in;i) xread(),e[x].PB(i);for (int i1;in;i) if (!vis[i]) dfs(i);int p0,num0;for (int i1;in;i) if (flag[i]) tree_dp(i,0),pf[i],num;if (!(num1)) { puts(POSSIBLE); return 0; } for (int i1;in;i)if (flag[i]p!f[i]) { puts(POSSIBLE); return 0; }puts(IMPOSSIBLE);return 0;
}
