AGC 002E.Candy Piles(博弈论)
题目链接\(Description\)给定\(n\)堆糖，数量分别为\(a_i\)。Alice和Bob轮流操作。每次可以吃掉最多的一堆，也可以每堆各吃掉一个。无法操作的人输，求谁能赢。\(n\leq10^5,\ a_i\leq10^9\)。\(Solution\)画这图累死了= = 虽然确实有点丑假...
【AGC 005F】Many Easy Problems
DescriptionOne day, Takahashi was given the following problem from Aoki:You are given a tree with N vertices and an integer K. The vertices are number...
[agc008E]Next or Nextnext-[dp+思考题]
Description传送门Solution官方题解然后我谈下个人理解。由于我们的两个条件只要任意满足，则在p的图中i有两种连边法:i->p[i],i->p[p[i]]。我们考虑在a的图中i->a[i]。可得我们要把p图塞到a图里。具体分析看题解吧，题解图画的很清晰呀。然后。。就各...
AGC 016 F - Games on DAG(状压dp)
题意给你一个有\(n\)个点\(m\)条边DAG图，点的标号和拓扑序一致。现在有两个人进行博弈，有两个棋子分别在\(1,2\)号点上，需要不断移动到它指向的点上。如果当前两个点都无法移动，那么就视为当前操作的人失败。问有多少边集满足先手必胜。\(\displaystyle2\len\le15,m\l...
【AGC002E】Candy Piles 博弈论
题目大意有\(n\)堆糖果，第\(i\)堆有\(a_i\)个。两个人轮流决策，决策分为两种：1.选择糖果数最多的一堆糖果，并把这堆糖全吃了。2.在每堆非空的糖果堆里拿一颗糖吃掉。吃掉最后一颗糖的人输。问你先手必胜还是先手必败。\(n\leq100000\)题解又是一个打表结论题。先把\(a_i\)从...
agc015F - Kenus the Ancient Greek(结论题)
题意题目链接$Q$组询问，每次给出$[x,y]$，定义$f(x,y)$为计算$(x,y)$的最大公约数需要的步数，设$i\leqslantx,j\leqslanty$，求$max(f(i,j))$，以及$max(f(i,j))$不同的数对$(i,j)$的个数Sol结论题Orz设$f(x,y)$表示$...
AGC 030B.Tree Burning(贪心)
题目链接\(Description\)有一个长为\(L\)的环，上面有\(n\)棵树，坐标分别为\(a_i\)。初始时在原点。每次你可以选择顺时针或逆时针走到第一棵没有被烧掉的树，停在这个位置，然后烧掉这棵树。重复这一过程直到所有树都被烧掉。求走的总路程最多可以是多少。\(n\leq2\times1...
[agc011C]Squared Graph-[二分图]
Description传送门Solution我们以下考虑的情况都是原图中非孤立的点。题目要求新图的连通块个数。这个不好算，我们考虑计算新图的联通块内的特征点(x,y)，即无法通过移动找到(t,c)使得t<x，也无法找到点(x,a)满足a<y。（就是字典序最小吧）可知每个新图连通块内，都有...