Codeforces Round #641 (Div. 2)
A. Orac and Factors
题意：
进行 k 次操作：将原数加上它的最小因子（除1外）
思路：
如果 n 是偶数，每次加的都是 2
如果 n 是奇数，第一次加上一个奇数，然后变成了一个偶数，之后都加 2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
const double PI = acos(-1.0);
const int N = 1e6 + 5;
int main()
{
int t;
ll n, k;
scanf("%d", &t);
while(t--)
{
scanf("%lld%lld", &n, &k);
ll tmp = n;
for(ll i = 2; i <= sqrt(n); ++i)
{
if(n % i == 0)
{
tmp = i;
break;
}
}
ll ans = n + tmp + 2 * (k - 1);
cout<<ans<<'\n';
}
return 0;
}
B. Orac and Models
题意：
求最长的按原序排列的严格递增的子序列，序列中任意相邻两数的原下标成倍数关系。
思路：
dp[ i ]表示以 i 为最后序列中的一个数时的最大值
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
const double PI = acos(-1.0);
const int N = 1e5 + 5;
int a[N], dp[N];
int main()
{
int t, n;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
{
dp[i] = 1;
scanf("%d", &a[i]);
}
int maxx = 1;
for(int i = 2; i <= n; ++i)
{
for(int j = 1; j <= sqrt(i); ++j)
{
if(i % j == 0)
{
if(a[j] < a[i])
dp[i] = max(dp[i], dp[j] + 1);
if(a[i / j] < a[i])
dp[i] = max(dp[i], dp[i / j] + 1);
}
}
maxx = max(maxx, dp[i]);
}
cout<<maxx<<'\n';
}
return 0;
}
C. Orac and LCM
题意：
求任意两数的最小公倍数的最大公约数
公式：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
const double PI = acos(-1.0);
const int N = 1e5 + 5;
ll a[N], gcdd[N], lcmm[N];
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b)
{
return a / gcd(a, b) * b;
}
int main()
{
ll n;
while(~scanf("%lld", &n))
{
for(ll i = 1; i <= n; ++i)
{
scanf("%lld", &a[i]);
}
gcdd[n] = a[n];
for(ll i = n - 1; i >= 1; --i)
{
gcdd[i] = gcd(gcdd[i + 1], a[i]);
}
for(ll i = 1; i < n; ++i)
{
lcmm[i] = lcm(a[i], gcdd[i + 1]);
}
ll ans = lcmm[1];
for(ll i = 2; i <= n; ++i)
{
ans = gcd(ans, lcmm[i]);
}
cout<<ans<<'\n';
}
return 0;
}
D. Orac and Medians
对于一个数列，可以进行如下操作：选取连续的一段，将这一段的所有数都改为这一段的中位数，如果序列长度是偶数，修改为较小的那个数。问原序列是否可以全部修改成 k
思路：
（1）如果原序列中没有 k ，肯定不可以
（2）如果原序列中与 k 相邻的数 >= k，这个数就可以修改为 k ，整个序列也可以全部修改成 k ，如1 3 4，全部改成3
（3）如果原序列中与 k 相隔一位的数 >= k，整个序列也可以全部修改成 k ，如1 2 3 2 4，全部改成3
（4）如果不满足以上情况，现试图将一个 >= k 的数移动到 k 附近，考虑某个数a >= k，且 a 可以进行以上两种修改，那么整个序列就可以全部修改成 k 。例如：3 1 1 4 1 4 （全部改为3）=> 3 1 4 4 4 4 => 3 3 3 4 4 4 => 3 3 3 3 3 3
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
const double PI = acos(-1.0);
const int N = 1e5 + 5;
int a[N];
int main()
{
int t, n, k;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &k);
bool flag = 0;
for(int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
if(a[i] == k)
flag = 1;
}
if(!flag)
{
cout<<"no"<<'\n';
continue;
}
if(n == 1)
{
cout<<"yes"<<'\n';
continue;
}
flag = 0;
for(int i = 1; i <= n; ++i)
{
if(i < n && a[i] >= k && a[i + 1] >= k)
{
flag = 1;
break;
}
if(i < n - 1 && a[i] >= k && a[i + 2] >= k)
{
flag = 1;
break;
}
}
if(flag)
cout<<"yes"<<'\n';
else
cout<<"no"<<'\n';
}
return 0;
}
查看5道真题和解析
