Solved Problem ID Title Ratio (Accepted / Submitted)
1001 Theramore 65.78% (942/1432)
1002 Darkmoon Faire 42.31% (77/182)
1003 Undercity 51.22% (21/41)
1004 Quel’Thalas 82.78% (995/1202)
1005 Ironforge 12.32% (178/1445)
1006 Thunder Bluff 0.00% (0/535)
1007 Darnassus 7.09% (199/2805)
1008 Orgrimmar 29.54% (768/2600)
1009 Gilneas 67.21% (41/61)
1010 Vale of Eternal 16.47% (85/516)
1011 Stormwind 51.77% (909/1756)
1012 The Dark Temple 17.59% (19/108)
1013 Shattrath City 5.63% (62/1101)
文章目录
- 4.Quel’Thalas
- 1.Theramore
- 11.Stormwind
- 8.Orgrimmar
- 7.Darnassus
4.Quel’Thalas
Quel’Thalas
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 56 Accepted Submission(s): 54
Problem Description
Desperate magic addiction once made us miserable. Territory occupied by natural disasters made us wandering. But the misery should be put behind and we shall enter a new chapter.
Us the same blood flows,we will bring back the glory of the sun again!
Salama ashal’anore!
Kael’thas has a magic square which contains all points on the 2D plane whose coordinates are integers within [0,n].
He can draw several straight fire lines on the plane. Each line will cover all the points on it. Note that the lines have no endpoints and extend to infinity in both directions.
And there is one special rule: he cannot draw a line that covers the point (0,0) because his throne is on (0,0).
What is the minimum number of lines he needs to draw so that the lines will cover all the points of the magic square except (0,0)?
Input
The input consists of multiple test cases.
The first line contains one integer T (1≤T≤50) denoting the number of test cases.
The following are T test cases.
Each test case consists of one line containing one integer n (0≤n≤50).
Output
For each test case, output one line containing one integer indicating the answer.
Sample Input
1
2
Sample Output
4
Hint
One possible answer for the sample is : x = 1, x = 2, y = 1, y = 2
Source
2022“杭电杯”中国大学生算法设计超级联赛（8）
题意：
- 给出一个整数n，现在有一个二维平面，其中
的整点中去掉 
思路：
- 结论题，答案为
。 - 官方证明如下：
#include
using namespace std;
typedef long long LL;
int main(){
int T; cin>>T;
while(T--){
LL n; cin>>n;
cout 1.Theramore
Theramore
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 86 Accepted Submission(s): 71
Problem Description
Those blood-soaked shores of Kalimdor is like a ghost haunting Jaina Proudmoore ever since the day she pushed her father into hell.
Now, standing in front of the devastated ruins of Theramore, she knew how naive she had been to want peace.
The Focusing Iris. It was the most brutal and cowardly killing method Jaina could imagine.
The Horde wants war. They will do anything to destroy us. But if this is all they want, Jaina will be pleased to offer them a big one.
The warships of the Horde can be described as a string s which contains only ‘0’ and ‘1’, denoting the small warship and the large warship. Jaina can perform some magic to the string. In one magic, she chooses an arbitrary interval with odd length and reverse it. Jaina can perform this magic as many times as she likes.
Jaina wants the small warships to be in the front, since they are easier to destroy. She asks for your help, and you need to tell her the lexicographically smallest string that she can obtain.
Note: in this problem, suppose two sequences s and t both have length n, then s is lexicographically smaller than t if there exists a position i(1≤i≤n) such that sj=tj for all 1≤j
Input
The input consists of multiple test cases.
The first line contains an integer T (1≤T≤10) denoting the number of test cases.
Each test case consists of only one line containing a string s (|s|≤105).
Output
Output one line containing the lexicographically smallest string that you can get.
Sample Input
2
101001
01101100000000101010
Sample Output
001011
00000000001010101111
Hint
In the first test case, Jaina performs magic to the interval [3,5] and the string is changed to 100011. Then Jaina performs magic to the interval [1,3] and the string is changed to 001011.
Source
2022“杭电杯”中国大学生算法设计超级联赛（8）
题意：
- 给出一个 01 序列，每次操作可以任意翻转奇数长度的区间，求能达到的最小字典序。
思路：
- 只使用长度为 3 的翻转，那么位置奇偶性相同的位置可以随便换。
- 对奇数位置和偶数位置，分别把 0 放到前面、1 放到后面即可。
#include
using namespace std;
typedef long long LL;
const int maxn = 2e5+10;
char t[maxn];
int main(){
ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
int T; cin>>T;
while(T--){
string s; cin>>s;
int a = 0, b = 0, n = s.size();
for(int i = 0; i = 0; i--){
if(i%2==0){
if(a>0){
t[i] = '1';
a--;
}else{
t[i] = '0';
}
}else{
if(b>0){
t[i] = '1';
b--;
}else{
t[i] = '0';
}
}
}
t[n] = ' ';
cout 11.Stormwind
Stormwind
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 60 Accepted Submission(s): 47
Problem Description
“So, people of Stormwind! Let us unite this day. Let us renew our promise to uphold and protect the Light, and together we will face down this dark new storm and stand firm against it—as humanity always has… and humanity always will!”
The crowd saved its greatest roars for the end. A chorus of “Long live King Varian! Long live King Varian!” rose into the sky with vigor and conviction. The cheers were unending, echoing deep into Elwynn Forest and faintly reaching even the distant peaks of the Redridge Mountains.
Varian Wrynn gained a rectangular piece of gold in the battle, with length n and width m. Now he wants to draw some lines on the gold, so that later he can cut the gold along the lines.
The lines he draws should satisfy the following requirements:
- The endpoints of the lines should be on the boundary of the gold.
- The lines should be parallel to at least one boundary of the gold.
- After cutting along all the lines, each piece of gold is a rectangle with integer length and width.
- After cutting along all the lines, the area of each piece of gold should be at least k.
- Two lines should not share more than one common points.
Varian Wrynn wants to cut the gold in such a way that maximizes the lines he draws.
As Alliance’s Supreme King, he certainly doesn’t have time to do this. So he finds you! Please help him to cut the gold!
Input
The input consists of multiple test cases.
The first line contains an integer T (1≤T≤100) indicating the number of test cases.
Each test case consists of one line containing three integers n,m,k (1≤n,m,k≤105). Its guaranteed that n×m≥k.
Output
For each test case, output one line containing one integer, the maximum number of lines you can draw.
Sample Input
2
5 4 2
10 9 13
Sample Output
5
4
Hint
In the first test case, Varian Wrynn can draw 4 lines parallel to the boundary of length 4 and 1 line parrallel to the boundary of length 5. After cutting along the lines, he can get 10 pieces of gold of size 2.
Source
2022“杭电杯”中国大学生算法设计超级联赛（8）
题意：
- 一个
- 要求这些线划分出的每个小长方形面积都
，求最多可以画几条线。
思路：
- 枚举小长方形的某个边长的最小值，由此可以求出另一个边长允许的最小值，然后求出两个方向分别最多能画几条线。 时间复杂度
。
#include
using namespace std;
int main(){
ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
int T; cin>>T;
while(T--){
int n, m, k; cin>>n>>m>>k;
int ans = 0;
for(int x = 1; x =k
if(x > n || y > m)continue;
ans = max(ans, n/x+m/y-2);
}
cout - 也可以直接分类讨论，先横着画或先竖着画，因为一条线是划到底的，所以根据k/n可以算出横着最多能画多少个，再根据左右两边剩余的面积分类后取max，复杂度
#include
using namespace std;
int calc(int n, int m, int k){
int ans = 0;
int t = k/n;
if(k%n!=0)t++;
int tt = m-(m/t-1)*t;
if(t+tt>T;
while(T--){
int n, m, k; cin>>n>>m>>k;
int ans = max(calc(n,m,k), calc(m,n,k));
cout 8.Orgrimmar
Orgrimmar
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 300 Accepted Submission(s): 134
Problem Description
“In my memory, the last time such a tragic farewell to a respected Horde leader was at the top of Thunder Bluff. That day, Mother Earth was crying for him too. “
“This time, it is the Shadow of the Horde who has left us. At this moment, the entire Horde is whispering affectionately for him. “
“Son of Sen’jin, leader of the Darkspear tribe, Warchief of the Horde – Vol’jin.”
Born in the cunning and vicious troll race, he spent his life explaining to the world what loyalty and faith are.
A dissociation set of an undirected graph is a set of vertices such that if we keep only the edges between these vertices, each vertex in the set is connected to at most one edge.
The size of a dissociation set is defined by the size of the set of vertices.
The maximal dissociation set of the graph is defined by the dissociation set of the graph with the maximum size.
Sylvanas has a connected undirected graph that has n vertex and n−1 edges, and she wants to find the size of the maximal dissociation set of the graph.
But since she just became the warchief of the Horde, she is too busy to solve the problem.
Please help her to do so.
Input
The input consists of multiple test cases.
The first line contains one integer T (1≤T≤10) denoting the number of test cases.
The following are T test cases.
For each test case, the first line contains one integer n (n≤500000), which is the number of vertices.
The following n−1 lines each contains two integers x and y denoting an edge between x and y.
It is guaranteed that the graph is connected.
Output
For each test case, output one line containing one integer indicating the answer.
Notes:
In this problem, you may need more stack space to pass this problem.
We suggest you to add the following code into your main function if you use C++.
int main() {
int size(512And if you use the code above please DON’T forget to add exit(0); in the end of your main function, otherwise your code may get RE.
Sample Input
2
5
1 2
2 3
3 4
4 5
10
1 2
2 4
3 2
5 3
6 4
7 5
8 3
9 8
10 7
Sample Output
4
7
Source
2022“杭电杯”中国大学生算法设计超级联赛（8）
题意：
- 求一棵树的最大分离集的大小。
- 最大分离集指的是原图点集的一个子集，满足这个集合内的点互相之间最多只有一条边（即要么是孤点，要么是只有两个点相连的离散状态）。
思路：
- 可以贪心的考虑一个点是否去掉，对于倒数第二层的点来说，如果叶子节点的个数>=2的话，肯定要将它去掉，不然分离集的大小就会少了那么多的叶子，得不偿失。 而当叶子个数=1的时候，去掉当前点的父节点明显是更优的，因为其余的点更能够和其他点构成分离集。
- 因此确定了去点的策略，可以直接dfs，返回值维护当前节点是否去掉，若一个点的儿子的节点的个数>1，那么就去掉这个点，答案+1即可。如果>=2，那么就去掉这个点的父节点。 最后输出n-ans。
#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
const int maxn = 500010;
vectorG[maxn];
int ans = 0;
int dfs(int u, int f){
int x = 0, y = -1;
for(int v : G[u]){
if(v==f)continue;
x += dfs(v,u);
if(x>1 && y==-1)y = 0, ans++;
}
if(y==0)return 0;
return x+1;
}
int main(){
int size(512>T;
while(T--){
int n; cin>>n;
for(int i = 0; i >u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,-1);
cout - 令
#include
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
const int maxn = 500010;
//分别表示x号点未选，x号点选了且度数0，x号点选了且度数1。x子树内部满足分离集定义的，选择点数的最大值
vectorG[maxn];
int f[maxn][3];
int dfs(int u, int fa){
f[u][0] = 0; f[u][1] = f[u][2] = 1;
for(int v : G[u]){
if(v==fa)continue;
dfs(v, u);
f[u][0] += max({f[v][0], f[v][1], f[v][2]}); //x不选,与子树不冲突,随便加
f[u][2] += f[v][0]; //x选了,且有父亲边, 因此子树不能选
f[u][2] = max(f[u][2], f[u][1]+f[v][1]); //x选了,且有儿子边，与之取max
f[u][1] += f[v][0]; //x选了,孤点,加上儿子的最大集数量
f[u][2] = max(f[u][2], f[u][1]); //x选了,有边,与无边取个max
}
}
int main(){
int size(512>T;
while(T--){
int n; cin>>n;
for(int i = 0; i >u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,-1);
cout 7.Darnassus
Darnassus
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1632 Accepted Submission(s): 341
Problem Description
Even the World Tree must bow to the cycle of life. Everything born will die.
Archimonde has hurt it once, Sylvanas burnt it again.
Now the World Tree is slowly recovering.
The World Tree is burnt apart into n parts. Now it tries to rebuild itself.
Each part of the World Tree has an attribute pi, and all pi (1≤i≤n) forms a permutation of 1,2,3…n.
For all 1≤i
The World Tree is very smart, so it will grow some edges such that all its n parts become connected (in other words, you can go from any part to any other part using only the edges that have been grown), spending the minimum energy.
Please calculate the minimum energy the World Tree needs to spend.
Input
The input consists of multiple test cases.
The first line contains an integer T (1≤T≤5) denoting the number of test cases.
For each test case, the first line contains a single integer n(1≤n≤50000).
The second line contains n integers pi (1≤pi≤n), it’s guaranteed that all pi forms a permutation.
Output
For each test case, output one line containing one integer indicating the answer.
Sample Input
2
5
4 3 5 1 2
10
4 7 3 8 6 1 9 10 5 2
Sample Output
7
24
Source
2022“杭电杯”中国大学生算法设计超级联赛（8）
题意：
- 给出一个长为n的排列
，把每个位置视为点，建一个无向图，
之间的边权为 
。求这个图的最小生成树。
思路：
- 依次连接
，这样的生成树每条边边权都 
，因此存在一种最小生成树中也只有边权 
（Kruskal 算法的原理）。 -
意味着 
和 
必有至少一个 
，因此可以在 
的时间复杂度内找到所有这样的边，然后使用 Kruskal 算法求出最小生成树即可。 - 总时间复杂度
。
#include
using namespace std;
typedef long long LL;
const int maxn = 50010;
int readint(){
int x=0, op=1; char ch = getchar();
while(ch '9'){ if(ch=='-')op=-1; ch = getchar(); }
while(ch >= '0' && ch e[maxn];
int main(){
int T = readint();
while(T--){
int n = readint();
init(n+1);
for(int i = 1; i 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
