Codeforces Round #174 (Div. 1 + Div. 2)

A. Cows and Primitive Roots

• 暴力。

---

B. Cows and Poker Game

• 模拟。

---

C. Cows and Sequence

• 线段树维护。

---

D. Cow Program

• 除1的位置(a_x)都是固定的，也就说当前位置(x)最终的位置也是确定的。
• 只要判断最后(x)超出范围，或者在环中，或者走回1这三种情况。
• 当前信息需要记录位置(x)以及方向(d)，判断状态是否在环中可以使用时间戳，若在环中，显然时间戳应该是一样的。

---

E. Coin Troubles

• 题目保证(b_i)不相同，(c_i)不相同，即每个点最多出度为1，入度为1，所以要么点构成链要么构成环。
• 环的判断只要(O(n^3))DP即可，好写。或者跑一遍也可以。
• 假设有一条链为(i gt j gt k)，当k的个数加1时，(、、、i、j)也需要同时加1。因为题目要求(b_i)严格大于(c_i)，所以在之前需要统计每个点的最少个数（就是深度）。
• 只要构造(、、、、、、k+j+i、j +i、i)这些物品，问题转化成背包问

---

D. Cows and Cool Sequences

• 根据题意， ((x, y))表示(x=frac{(2a+1+y)y}{2})，转换成$$frac{2x}{y} =2a+1+y$$
• 显然需要满足(y|x)， 然后等式两边式子的奇偶性。
• 若(y)是奇数，则右边为偶数，左边也是偶数。
• 若(y)是偶数，则右边为奇数，若左边也要为奇数，则(y)的2的因子数要等于(x)的2的因子数+1。
• 记(f(x))表示数(x)的最大奇数因子，(v(x))表示2的因子数，则(x=f(x)v(x))。
• 根据上面的分析，((x,y))是合法的，当(f(y)|f(x))且(v(y)=0)或者(v(y)=v(x)+1)。
• 对于序列上的两个位置(i,j(i< j))，可以在同一序列的情况下，(f(a_j)|f(a_i))且(v(a_j)=v(a_i)+j-i || v(a_j)<j-i)
• 剩下的就类似于最长上升子序列的做法，找出可以在同一序列的最长长度即可。

---

E. Cow Tennis Tournament

• 假设tuple为((x, y, z))，且(x<y<z)。
• 显然不可能直接计算两两之间的大小关系，所以考虑用总方案数 - 不合法的方案数。
• 不合法的方案数只要考虑每个值是作(x,y,z)中的哪一个。
• 对于覆盖的区间，只要离线排序，插入线段树即可。