hihocoder编程收割赛20
hihocoder1542 : 无根数变有根树
思路:
树的遍历
ac代码:
// hihocompete20_01.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<unordered_map>
using namespace std;
int n, k; //1 <= k <= n <= 1000
int main()
{
cin >> n >> k;
vector<vector<int> >map(n + 1);
int a, b;
for (int i = 0; i < n - 1; i++)
{
cin >> a >> b;
map[a].push_back(b);
map[b].push_back(a);
}
vector<int> res(n + 1, -1);
queue<int> q;
q.push(k);
res[k] = 0;
while (!q.empty())
{
int t = q.front();
q.pop();
for (int i = 0; i < map[t].size(); i++)
{
if (res[map[t][i]] == -1)
{
q.push(map[t][i]);
res[map[t][i]] = t;
}
}
}
for (int i = 1; i < n; i++)
{
cout << res[i] << " ";
}
cout << res[n] << endl;
return 0;
}
hihocoder1543 : SCI表示法
思路:
这题(n + n + k) * (k + 1) = 2 * y. y就是输入的数。然后找2y的约数。复杂度是O(sqrt(n)).感觉很皮皮。我一开始用二次函数的求解公式做。复杂度是O(n).虽然就差了一点,但是就是tle。贼气。
ac代码:
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<unordered_map>
#include<cmath>
using namespace std;
int main()
{
int t;
long long y;
cin >> t;
while (t--)
{
cin >> y;
int temp = 2 * y;
int res = 0;
for (int i = 1; i * i <= temp; i++)
{
if (temp % i == 0)
{
int x = temp / i;
int y = x - i + 1;
if (y % 2 == 0)
{
res = max(res, i);
}
}
}
cout << res << endl;
}
return 0;
}