AtCoder Beginner Contest 234
A – Weird Function
思路分析：
- 直接写就行
代码如下：
#include
using namespace std;
#define ll long long
ll f(ll x)
{
return x * x + 2 * x + 3;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll x;
cin >> x;
cout << f(f(f(x) + x) + f(f(x))) << endl;
return 0;
}
B – Longest Segment
思路分析：
- (o(n^2)暴力即可)
代码如下：
#include
using namespace std;
#define ll long long
const int maxn = 110;
ll x[maxn], y[maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x[i] >> y[i];
}
double d = 0.0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
double tmp = sqrt((x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]));
d = max(d, tmp);
}
}
printf("%.10f\n", d);
return 0;
}
C – Happy New Year!
思路分析：
- 首先找规律我们可以知道，n = 1时只有2，n = 2、3时只有20、22，n = 4、5、6、7时只有200、202、220、222，刚好对应这n的二进制修改，即将一个数的二进制求出来，然后把1替换为2输出即可
代码如下：
#include
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long s;
cin >> s;
string tmp = "";
while (s >= 1)
{
if (s % 2 == 0)
{
tmp = "0" + tmp;
}
else
tmp = "2" + tmp;
s /= 2;
}
cout << tmp << endl;
return 0;
}
D – Prefix K-th Max
思路分析：
- 给你1~n的排列，然后要你求前k、k+1、k+2…n项第k大的数
- 首先我们可以这样想，如果是求前k项中第k大的数的话，实际上就是求前k项最小的数，然后我们去看k+1项，如果k+1项比上一次输出的结果要小的话，那么实际上这个序列的第k大的数依然不变，直接输出即可；如果k+1项比上一次输出结果大的话，那么我们可以知道的是，它肯定会改变结果，所以我们直接把他插入一个set中去找比上次输出答案大的第一个数即可。
代码如下：
#include
using namespace std;
const int maxn = 5e5 + 20;
int p[maxn];
set v;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> p[i];
}
//先得到前面的
sort(p, p + k);
for (int i = 0; i < k; i++)
{
v.insert(p[i]);
}
int ans = p[0];
cout << ans << endl;
for (int i = k; i < n; i++)
{
if (p[i] > ans)
{
v.insert(p[i]);
ans = *v.upper_bound(ans);
cout << ans << endl;
}
else
cout << ans << endl;
}
return 0;
}
E – Arithmetic Number
思路分析：
- 一开始没想出来可以直接暴力，想的是找规律，但是碍于方向错了，所以这题没过
- 看题解发现原来就是暴力，我们只需要把满足条件的数放入到set里面，再用lower_bound就可以求出来结果了
- 具体怎么暴力：首先对于第一位肯定是1-9，公差我们也很容易想到是-9~8，所以我们只需要枚举第一位和公差即可，如果这个数满足我们就把它压入到set中，注意我们是先枚举第一位是啥，再枚举公差是啥，再枚举有多少位，在这个过程中，我们要用到string来存储每轮循环得到的满足条件的数（每次添加一位满足条件的数知道不能添加循环结束），然后每轮都要把结果转化位数存入到set里面就可以了
代码如下：
#include
#define ll long long
using namespace std;
set solve()
{
set res;
for (int fir = 1; fir ans = solve();
ll x;
cin >> x;
cout << *ans.lower_bound(x) << endl;
return 0;
}
F – Reordering
思路分析：
- 这个题目是dp和组合数学混合一起的，难度还算比较大，首先我们肯定是要预处理逆元啥的，这里就不说了，重点还是状态转移
- (dp_{i,j})指的是用到了前i个字符（这个”个”指的是26个小写字母的前几个），构成的长度为j的字符串的数量，所以我们答案肯定就是(\sum_{i = 1}^{s.length()}{dp_{26,i}})
- 那么对于(dp_{i,j})我们怎么得到呢？首先我们可以通过少用一种字母即(dp_{i – 1,j})，也可以少用前面已经构成好的串里删去某个字符换上当前第i个字符（第i种），这样的话就是(dp_{i – 1,j – 1}\times C_j^1)，依次类推，可以删去1，2…min(cnt[i],j)个字符也就是说最后(dp_{i,j}) =(\sum_{k = 0}^{min(j,cnt[i])}{dp_{i – 1,j – k}}\times C_j^k)
- 综上即可得出答案
代码如下：
#include
#define int long long
using namespace std;
const int MAX = 5010, mod = 998244353;
vector fac, finv, inv;
int cnt[26];
int dp[27][MAX];
void init()
{
fac.resize(MAX);
finv.resize(MAX);
inv.resize(MAX);
fac[0] = fac[1] = 1;
inv[1] = 1;
finv[0] = finv[1] = 1;
for (int i = 2; i < MAX; i++)
{
fac[i] = fac[i - 1] * i % mod;
inv[i] = mod - mod / i * inv[mod % i] % mod;
finv[i] = finv[i - 1] * inv[i] % mod;
}
}
int c(int n, int m)
{
return fac[n] * finv[m] % mod * finv[n - m] % mod;
} // c(n,m)
signed main()
{
init();
string s;
cin >> s;
int n = s.length();
for (int i = 0; i < n; i++)
{
cnt[s[i] - 'a']++;
//统计一下每个字母的数量
}
dp[0][0] = 1;
for (int i = 0; i < 26; i++)
{
for (int j = 0; j
Original: https://www.cnblogs.com/csu-yuuki/p/15781970.html
Author: zhy-cx
Title: AtCoder Beginner Contest 234
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584558/
转载文章受原作者版权保护。转载请注明原作者出处！