T1 拼接单词
我这里是暴力做法,30tps,set内存爆了
#include <bits/stdc++.h>
using namespace std;
vector<string> ve;
int main()
{
string a, b;
cin >> a >> b;
auto n = a.size(), m = b.size();
string temp, temp1;
for (unsigned int i = 0; i < n; i++)
{
temp1 += a[i], temp = "";
for (int j = m - 1; j >= 0; j--)
{
temp = b[j] + temp;
ve.push_back(temp1 + temp);
}
}
set<string> s(ve.begin(), ve.end());
cout << s.size();
return 0;
}
T2 八进制小数
正解应该是秦九韶+高精度+快速幂,我这里还没订正,只采用秦九韶(30tps)
#include <bits/stdc++.h>
using namespace std;
int main()
{
char eight[600];
double sum;
int i;
scanf("%s", eight);
sum = 0.0;
for (int i = 0; eight[i] != '\0'; i++)
sum += (eight[i] - '0') * pow(0.125, i + 1);
while (sum > 0)
{
sum *= 10;
cout << (int)sum;
sum -= (int)sum;
}
return 0;
}
T3 最长路
正解参照树的直径两次dfs,算次大和最大的路径长度
我这里瞎写的dfs(0tps)
#include <bits/stdc++.h>
using namespace std;
const int N = 201000;
vector<int> son[N], father[N];
bool vis[N];
int ans = 0, cnt = 0, n;
void dfs(int s, int sum)
{
vis[s] = 1, cnt++;
if (cnt == n)
{
ans = max(ans, sum);
return;
}
if (father[s].size())
{
for (auto v : father[s])
if (!vis[v])
{
dfs(v, sum + 1);
cnt--;
}
}
if (son[s].size())
{
for (auto v : son[s])
if (!vis[v])
{
dfs(v, sum + 1);
cnt--;
}
}
}
int main()
{
cin >> n;
for (int i = 2; i <= n; i++)
{
int u;
cin >> u;
son[u].push_back(i);
son[i].push_back(u);
}
for (int i = n; i <= n; i++)
{
ans = 0;
memset(vis, 0, sizeof(vis));
dfs(i, 0);
cout << ans << ' ';
}
return 0;
}
T4 最大频率
我们先算出每一个区间的起始位置和结束位置,离散化一下,然后询问时参照下图
然后用三个if语句判断一下即可。
(样例已过)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
struct node
{
int num, id;
} a[N];
pair<int, int> x[N];
int main()
{
int cnt = 1;
cin >> n >> m;
a[1].id = 1;
x[1].first = 1;
for (int i = 1; i <= n; i++)
{
cin >> a[i].num;
if (a[i].num != a[i - 1].num && i > 1)
{
a[i].id = ++cnt;
x[(cnt - 1)].second = i - 1;
x[cnt].first = i;
}
else
a[i].id = cnt;
}
x[cnt].second = n;
while (m--)
{
int l, r;
cin >> l >> r;
int ans = 0, y = 0;
for (int i = l; i <= r; i++)
{
if (x[a[i].id].first >= l && x[a[i].id].second <= r)
ans = max(ans, x[a[i].id].second - x[a[i].id].first + 1);
else if (x[a[i].id].first >= l && x[a[i].id].second > r)
ans = max(ans, r - x[a[i].id].first + 1);
else if (x[a[i].id].first < l && x[a[i].id].second <= r)
ans = max(ans, x[a[i].id].second - l + 1);
}
cout << ans << endl;
}
return 0;
}
时间复杂度 \(O(nm)\) 预测60tps
标签:cnt,12,IAI,int,sum,son,ans,id From: https://www.cnblogs.com/ljfyyds/p/17018640.html