1006-Meax
来源: 杭电杯超级联赛6 算法: DFS, 贪心 题目链接: https://acm.hdu.edu.cn/contest/problem?cid=1049&pid=1006 补完: No ## 代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using namespace std;
long long a[500010];
long long b[500010];
vector<int> v[500010];
void dfs(int x,int r){
a[x]=1;
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==r) continue;
dfs(y,x);
a[x]+=a[y];
}
//
//cout<<a[x]<<endl;
//
return ;
}
void toans(int x,int r){
b[x]=a[x];
long long maxx=0;
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(y==r) continue;
toans(y,x);
maxx=max(maxx,b[y]);
}
b[x]+=maxx;
return;
}
signed main(){
ios::sync_with_stdio(false);
std::cin.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;i++){
v[i].clear();
}
for(int i=1;i<=n;i++){
a[i]=0;
b[i]=0;
}
for(int i=1;i<=n-1;i++){
int u1,u2;
cin>>u1>>u2;
v[u1].push_back(u2);
v[u2].push_back(u1);
}
dfs(1,0);
toans(1,0);
cout<<b[1]<<"\n";
}
}
来源: 杭电杯超级联赛6 算法: 向量, 计算几何 题目链接: https://acm.hdu.edu.cn/contest/problem?cid=1049&pid=1009 补完: Yes 完成时间: August 12, 2022
题解
有大地图\(M\)经过旋转压缩得到\(m\), 任落在\(M\)内, 在空间中有一不动点同时在\(M\)和\(m\)上确定同一位置.
设不动点为\(P\), 设相对位置参数\(\lambda,\mu\), 可列方程
\[ \begin{align} \vec{OP}&=\vec{OA}+\lambda\vec{AB}+\mu\vec{AD}\\ \vec{OP}&=\vec{Oa}+\lambda\vec{ab}+\mu\vec{ad} \end{align} \]
化简有
\[ \begin{align} \vec{AP}&=\lambda\vec{AB}+\mu\vec{AD}\\ \vec{aP}&=\lambda\vec{ab}+\mu\vec{ad} \end{align} \]
展开有
\[ \begin{align} P.x-A.x&=\lambda(B.x-A.x)+\mu(D.x-A.x)\\ P.y-A.y&=\lambda(B.y-A.y)+\mu(D.y-A.y)\\ P.x-a.x&=\lambda(b.x-a.x)+\mu(d.x-a.x)\\ P.y-a.y&=\lambda(b.y-a.y)+\mu(d.y-a.y)\\ \end{align} \]
化简有
\[ \begin{align} a.x-A.x&=\lambda(B.x-b.x+a.x-A.x)+\mu(D.x-d.x+a.x-A.x)\\ a.y-A.y&=\lambda(B.y-b.y+a.y-A.y)+\mu(D.y-d.y+a.y-A.y)\\ \end{align} \]
展开有
\[ \begin{align} (a.x-A.x)(D.y-d.y+a.y-A.y)&=\lambda(B.x-b.x+a.x-A.x)(D.y-d.y+a.y-A.y)+\mu(D.x-d.x+a.x-A.x)(D.y-d.y+a.y-A.y)\\ (a.y-A.y)(D.x-d.x+a.x-A.x)&=\lambda(B.y-b.y+a.y-A.y)(D.x-d.x+a.x-A.x)+\mu(D.x-d.x+a.x-A.x)(D.y-d.y+a.y-A.y)\\ \end{align} \]
\[ \begin{align} (a.x-A.x)(B.y-b.y+a.y-A.y)&=\lambda(B.x-b.x+a.x-A.x)(B.y-b.y+a.y-A.y)+\mu(D.x-d.x+a.x-A.x)(B.y-b.y+a.y-A.y)\\ (a.y-A.y)(B.x-b.x+a.x-A.x)&=\lambda(B.x-b.x+a.x-A.x)(B.y-b.y+a.y-A.y)+\mu(D.y-d.y+a.y-A.y)(B.x-b.x+a.x-A.x)\\ \end{align} \]
化简有
\[ \lambda=\frac{(a.x-A.x)(D.y-d.y+a.y-A.y)-(a.y-A.y)(D.x-d.x+a.x-A.x)}{(B.x-b.x+a.x-A.x)(D.y-d.y+a.y-A.y)-(B.y-b.y+a.y-A.y)(D.x-d.x+a.x-A.x)} \]
\[ \mu=\frac{(a.x-A.x)(B.y-b.y+a.y-A.y)-(a.y-A.y)(B.x-b.x+a.x-A.x)}{(D.x-d.x+a.x-A.x)(B.y-b.y+a.y-A.y)-(D.y-d.y+a.y-A.y)(B.x-b.x+a.x-A.x)} \]
最后有
\[ \begin{align} P.x&=\lambda(B.x-A.x)+\mu(D.x-A.x)+A.x\\ P.y&=\lambda(B.y-A.y)+\mu(D.y-A.y)+A.y\\ \end{align} \]
代码
1 |
|
1012-Loop
来源: 杭电杯超级联赛6 算法: 字典序, 栈 题目链接: https://acm.hdu.edu.cn/contest/problem?cid=1049&pid=1012 补完: Yes 完成时间: August 16, 2022
题意简述
给定一个长度为n的数组a，进行严格的k次操作：选择两个整数l，r (1≤l≤r≤n)，让数组a_l到a_r循环左移一位。
使得数组a的字典序最大，输出操作后的数组a。其中字典序比较的是每个a_i的值，不考虑a_i具体的数位。
题目分析
首先，由于l和r可以相等，所谓严格的k次操作其实相当于可以少于k次。
接着，一次操作之后，发生了什么？
不是循环左移一位吗题目又不是很难懂。
我们换个角度看看，既然操作的时候可以任选区间，并且循环左移意味着最左的数字换到区间最右端——那么一次操作实际上是否是任选一个作为区间左节点的数字，把它放到它之后的任意位置呢？是的。
也就是作为左区间的每个数字，都可以自由地插入其后的位置。
既然是自由插入，那我们当然是直接把这部分自由的数字排序好放进去啦~
那么怎么放进去呢？
我们考虑插入前的序列的有序情况：
如果原来的序列是降序的，自由插入一些数字，字典序最小的结果其实就是所有数字降序排列的结果。
如果原来的序列是无序的，对于已经预先排好的待插入数字，每次都插在第一个比自己小的数字之前，才能让字典序更大。
并且，使用无序的一般情况的方案插入有序数列，也能得到有序数列的最优方案，故而我们采用这种混合插入的方式来插入数列。
那区分这个干什么啊。
对待插入的原序列的分类得出的结论，很好地辅助了我们思考如何选取这些自由插入的数字。
首先的首先，由于字典序先比较数列前端，那么在前面的数字优先。
接着，回看前面插入有序序列的情况：往降序序列插入自由的元素，能得到所有元素降序排列的结果。这意味着没有必要把降序的序列数纳入自由元素，也能达到所有元素降序的最优的字典序结果。并且为了节省更多机会，相等的连续元素也视为降序，也就是非严格降序序列都不用纳入自由元素。
而这样节省下来的操作次数，可以抓取更多的后面无序序列的元素，让它变成自由排列的。
换句话说，我们选取破坏了非严格降序序列的数字。
再然后，怎·么判断不用抓取的非严格降序区问呢？
想象两个相邻的非严格降序区问，后一个区问最前端的一小段比前—个区间最后端的一段元素大。如果直接在原序列里做判断，不管怎样都是不够正确的(这里认为k足够大):
后—个区间的第─个数字大于前—个区间的最后—个数字了，认为非严格降序区间结束了，把后—个区问连续扔进自由元素里，显然浪费了操作机会——删去前面—小段就能让剩下的数字合成—个非严格降序区间了。 认为两个区问都是非严格降序区间，在第二个区问之后去抓自由元素，显然结果不够优秀:在更前面的，第三个区间的前端元素偏大，在字典序比较中，这已经比把这些元素抓走后的结果更小了。
那反正就是把中间的抓出来嘛！
然而把第二个区间前一段偏大的抓走也是错误的。
别忘了，”自由“的元素也不是完全自由的。
它们只能往自己的后方插入。看图来理解这个选择：
把两个区间描述成这样的曲线，两个区间有一段大小叠合：
如果是把后一个区间的bc段纳入自由元素，那么它在自由排序的时候会插入ab段中。这是不符合规则的。只有把前一个区间的ab段扔到自由元素里才行——它们会排列进bc段，这是合法的操作。
那么怎么把这些元素放入自由序列呢？双指针指向需要比较的元素也是可行的，但出于好写和好懂的考虑，这里使用了栈的结构。
从原始序列的队首开始，依次把元素压入栈中。
如果新入栈元素比栈顶元素小或相等，不严格降序的结构不被破坏，继续入栈即可。
如果新入栈元素比栈顶元素大，不严格降序的结构被破坏，把原来的栈顶元素弹出，进入自由元素的队列中，消耗一次操作机会（也就是入自由元素队的机会）。继续把新元素和新的栈顶比较，直到不严格降序的结构不被破坏。
最后，我们得到了长度为k的自由元素队，把它们排序后插入序列中即可。
注意，仍然留在栈中的元素记得退回序列。
完整代码
1 |
|