签到签慢了，四题中间的样子吧，然后难题也没有写出来，补了两题，好像02也能补，再说吧哈哈。
1004.Quel'Thalas（签到）
题意：给你一个$[0,n]\times [0,n]$的二维点，用一条直线去划，最少用多少条线通过区域内除了$(0,0)$的点。
思路：我的想法是划斜线，队友的想法是横竖，结果都是一样的——$2\times n$
1001.Theramore（思维+签到）
题意：给你一个01字符串，你可以选择一个奇数区间 $[l,r]$ 使得区间内的01反转过来，可以使用无限次，求最后的字典序最小的字符串。
思路：每次就交换长度为$3$的区间，这样每次就是将$1$往后移动（同样在奇数位上），所以只需要统计奇偶的1有多少个。
这个是什么意思呢？说明这些1可以放在后面开始放，但是同样也需要满足奇偶，奇数的1只能放在奇数上，偶数的1只能放在偶数上。
所以统计完之后从后往前放就好，如果当前还有则放。
代码：
inline void Case_Test()
{
int r[2];
r[0] = 0, r[1] = 0;
cin>>s;
n = s.size();
for (int i=0;i<n;i++)
{
if (s[i]=='0') continue;
r[i%2]++;
}
string ans(n,'0');
for (int i=n-1;i>=0;i--)
if (r[i%2]) ans[i] = '1', r[i%2]--;//往前放，如果还有那么就放
cout<<ans<<endl;
}
1011.Stormwind（签到）
题意：给你一个$n\times m$的纸片以及一个$k$，求最多能砍多少刀并且保证每一块的面积都需要大于等于$k$，注意：每一刀都需要保证是二维坐标的整数点，并且起点和终点都需要在边缘上（不能中间砍）
思路：枚举$a$，这个表示的是小长方形的横着的那条边，从1到n进行枚举，如果不能正好整除，多出来怎么办？例如下图：
右侧大于a，多出来一块
我本来想着是判断一下，结果把它看成左侧一样的，只不过它多出来一块就行，其实就是不管它，那么这样竖着首先能切n/a-1刀。
那么横着的也是同理，不过需要先要得到我小长方形的另外一条边长是多少，需要向上取整就是t=(k+a-1)/a，还是按照上面方法，加起来取Max就好。
代码：
inline void Case_Test()
{
cin>>n>>m>>k;
ans = 0;
for (int a=1;a<=n;a++)
{
int res = 0;
if (a*m<k) continue;
res = n/a-1;
int t = (k+a-1)/a;
res += m/t-1;
ans = Max(ans, res);
}
cout<<ans<<endl;
}
1008.Orgrimmar（树形DP）
题意：给你一颗树，求一个点集其中的点最多只与一个点相连的集合。求集合内点的最大个数。
思路：设置三种状态(用u表示当前点，用v表示子结点)
dp[u][0]：不删u点。u只与一个v相连，其他都不连。dp[u][1]：不删u点。u都不与任何v相连。dp[u][2]：删u点。
那么来看三种状态转移：
dp[u][0]：只能与一个v相连，说明要选择v未选择别人的（因为如果选了再连u就三个点连续了，不合题意），所以需要选择v的dp[v][1]，其他的点则都不能连，则选择dp[v][2]。那么如何选择这个v呢？很显然当dp[v][1]-dp[v][2]最大的时候，这个是最优的。dp[u][1]：都不连v，这个意思代表不删u，删v，所以只需要加上所有的dp[v][2]。dp[u][2]：需要删u，这个最自由，对于每一个v的三种状态选Max即可。
代码：
int dp[N][3];
inline void dfs(int x,int pre)
{
int r2 = 0, r0 = 0, r1 = 0, res = 0,p = 0,t = 0;
//debug2(x,pre);
for (int i=head[x];i;i=edge[i].next)
{
int y = edge[i].to;//注意一定写int y,保证在内部有效。
if (y==pre) continue;
dfs(y,x);
res += dp[y][2];
if (dp[y][1]-dp[y][2]>p) p = dp[y][1]-dp[y][2],t = y;
r2 += max({dp[y][0],dp[y][1],dp[y][2]});
}
dp[x][0] = 1 + Max(res - dp[t][2] + dp[t][1], res);
dp[x][1] = 1 + res;
dp[x][2] = r2;
}
inline void Case_Test()
{
for (int i=1;i<=n;i++) head[i] = dp[i][0] = dp[i][1] = dp[i][2] = 0;
cnt = 0;
cin>>n;
for (int i=1;i<n;i++)
{
cin>>x>>y;
add(x,y);
add(y,x);
}
int st=1;
dfs(st,0);
cout<<max({dp[st][0],dp[st][1],dp[st][2]})<<endl;
}
1007.Darnassus（思维+最小生成树）
题意：给你$n(1\leq n\leq 50000)$的点以及对应的$p[i]$，每个点之间的边权是$|(i-j)\times (p[i]-p[j])|$。求最小生成树。
思路：这个建完全图实在是不可能，无论从时间还是空间上来看。所以需要转化一下。
对于每个相邻的点($i,i+1$)之间的连边有：
$$
|(i+1-i)\times (p[i+1]-p[j])\ =\ |p[i+1]-p[i]| \leq n-1
$$
这$n-1$条边已经足够满足生成一颗生成树了，但是不一定是最小的，所以我们能得到什么信息呢？
如果一条边长度大于等于$n$则是不行的，所以我们只需要找到小于等于$n-1$的边即可。
那么如何枚举？从上面那个式子来看
$$
w=|(i-j)\times (p[i]-p[j])\leq n-1
$$
这是两个乘积，如果要满足小于$n$的话最特殊的情况是$\sqrt{n} \times \sqrt{n}$，所以只需要枚举$t=\sqrt{n}$的个数即可。
为什么呢？对于当前的$i$来说，我只需往后枚举$\sqrt{n}$个数则满足$(i-j)\leq \sqrt{n}$，这样有可能满足我们想要的条件。
那么还有其他情况吗？当然有可能，当$i-j\gt \sqrt{n}$的时候，但是我的$p[i]-p[j]\leq n$就可能满足条件。所以还需要对于$p$往后枚举$\sqrt{n}$次。
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n&&j<=i+t;j++)
{
m = Abs((i-j)*(p[i]-p[j]));//边权
if (m<=n-1) v[m].emplace_back(i,j);
m = Abs((pos[i]-pos[j])*(i-j));//pos[p[i]] = i
if (m<=n-1) v[m].emplace_back(pos[i],pos[j]);
}
然后生成了所有的边，这里需要用到桶排，因为如果再进行带$\log$的排序的话则可能会超时。
最小生成树不一定需要
sort，用桶排可能会优化时间
所以我把两个点加到了v[m]中。
然后跑最小生成树即可。
代码：
struct DSU {
std::vector<int> f;
DSU(int n) : f(n) { std::iota(f.begin(), f.end(), 0); }
inline int leader(int x) {
while (x != f[x]) x = f[x] = f[f[x]];
return x;
}
inline bool same(int x, int y) { return leader(x) == leader(y); }
inline bool merge(int x, int y) {
x = leader(x);
y = leader(y);
if (x == y) return false;
f[y] = x;
return true;
}
};
inline void Case_Test()
{
cin>>n;
vector<vector<PII>> v(n);
DSU dsu(n+1);
for (int i=1;i<=n;i++)
{
cin>>p[i];
pos[p[i]] = i;
}
int t = sqrt(n);
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n&&j<=i+t;j++)
{
m = Abs((i-j)*(p[i]-p[j]));
if (m<=n-1) v[m].emplace_back(i,j);
m = Abs((pos[i]-pos[j])*(i-j));
if (m<=n-1) v[m].emplace_back(pos[i],pos[j]);
}
ans = 0;
cnt = 0;
for (int i=0;i<=n-1;i++)
{
for (auto e:v[i])
{
int u = e.first, v = e.second;
if (dsu.same(u,v)) continue;
dsu.merge(u,v);
ans += i;
cnt++;
if (cnt==n-1) {cout<<ans<<endl;return;}
}
}
}
1005.Ironforge
这里没时间了，看ygg的讲解吧。挺妙的——均摊。