你最愿意做的哪件事，才是你的天赋所在

0%

Codeforces Round #641 (Div. 2)

发表于 更新于 Valine：

题目链接

Codeforces Round #641 (Div. 2)

A

思路

如果一个数的最小因子是2，那么加上2后肯定还是2，如果不是2，那么肯定是一个奇数，奇数+奇数=偶数，就会变成2，所以考虑第一次加的数，后面肯定都是2

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<vll>
#define pii pair<int,int>
#define pll pair<ll>
inline bool isprime(ll num)
{if(num==2||num==3)return true;
    if(num%6!=1&&num%6!=5)return false;
    for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
    return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
int main(){
   int t;
   scanf("%d",&t);
   while(t--){
       ll n,k;
       cin>>n>>k;
       ll ans = n;
       bool flag = 0;
       for(int i=2;1ll*i*i<=n;i++){
           if(n%i==0){
               flag = 1;
               ans+=i;
               break;
           }
       }
       if(!flag)ans+=n;
       ans+=(k-1)*2;
       cout<<ans<<endl;
   }
}

B

思路

对每个位置进行分解，找到他的因子，当前位置的答案等于因子位置的答案+1即可

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<vll>
#define pii pair<int,int>
#define pll pair<ll>
inline bool isprime(ll num)
{if(num==2||num==3)return true;
    if(num%6!=1&&num%6!=5)return false;
    for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
    return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const int N = 1e5+10;
int s[N];
int mx[N];
int main(){
   int t;
   scanf("%d",&t);
   while(t--){
       int n;
       scanf("%d",&n);
       for(int i=1;i<=n;i++)mx[i]=1;
       for(int i=1;i<=n;i++){
           scanf("%d",&s[i]);
           if(i==1)continue;
           if(s[i]>s[1])mx[i]=mx[1]+1;
           for(int j=2;1ll*j*j<=i;j++){
               if(i%j==0){
                   if(s[i]>s[j])mx[i]=max(mx[i],mx[j]+1);
                   if(s[i]>s[i/j])mx[i]=max(mx[i],mx[i/j]+1);
               }
           }
       }
       int ans = 0;
       for(int i=1;i<=n;i++)ans=max(ans,mx[i]);
       cout<<ans<<endl;
   }
}

C

思路

对每个数进行质因数分解，然后考虑题目的意思，就是求每个质因子的次小值的乘积。注意的是0也要排进去。

#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<vll>
#define pii pair<int,int>
#define pll pair<ll>
inline bool isprime(ll num)
{if(num==2||num==3)return true;
    if(num%6!=1&&num%6!=5)return false;
    for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
    return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const int N = 1e5+10;
int a[N*2];
int prime[N*2],cnt;
bool vis[N*2];
vector<int>v[N*2];
void init(){
    for(int i=2;i<N*2;i++){
        if(!vis[i])prime[cnt++]=i;
        for(int j=0;j<cnt&&1ll*prime[j]*i<N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j])break;
        }
    }
}
int main(){
    init();
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        int t = a[i];
        for(int j=0;j<cnt&&1ll*prime[j]*prime[j]<=t;j++){
            int ccnt = 0;
            while(t%prime[j]==0){
                ccnt++;
                t/=prime[j];
            }
            v[prime[j]].push_back(ccnt);
        }
        if(t!=1)v[t].push_back(1);
    }
    ll ans = 1;
    for(int i=0;i<cnt;i++){
        if(v[prime[i]].size()<n-1)continue;
        sort(v[prime[i]].begin(),v[prime[i]].end());
        if(v[prime[i]].size()==n-1){
            ans=ans*quick_pow(prime[i],v[prime[i]][0]);
        }
        else {
            ans = ans * quick_pow(prime[i], v[prime[i]][1]);
        }
    }
    cout<<ans<<endl;

}

D

思路

显然，只要存在比k大的数是某个子段的中位数就可以一直推到k，例如，当k=5，序列为

5 1 1 1 6 7

的时候，我们可以变成5 6 6 6 6 6 6然后在全部都变成5，于是就变成存在比k大的数能否成为某个子段的中位数，我们只要考虑长度为3的即可，因为它包含了所有情况，可以自己试一下。

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<vll>
#define pii pair<int,int>
#define pll pair<ll>

inline bool isprime(ll num) {
    if (num == 2 || num == 3)return true;
    if (num % 6 != 1 && num % 6 != 5)return false;
    for (int i = 5; 1ll * i * i <= num; i += 6) { if (num % i == 0 || num % (i + 2) == 0)return false; }
    return true;
}

const int mod = 1e9 + 7;

inline ll mul(ll a, ll b, ll c) { return (a * b - (ll) ((ld) a * b / c) * c + c) % c; }

inline ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

inline ll quick_pow(ll a, ll b, ll mod) {
    ll res = 1;
    while (b) {
        if (b & 1)res = mul(res, a, mod);
        a = mul(a, a, mod);
        b >>= 1;
    }
    return res;
}

inline ll quick_pow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1)res = mul(res, a, mod);
        a = mul(a, a, mod);
        b >>= 1;
    }
    return res;
}

inline ll inv(ll x) { return quick_pow(x, mod - 2); }

inline ll inv(ll x, ll mod) { return quick_pow(x, mod - 2, mod); }

inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

inline ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

const int N = 1e5 + 10;
int a[N];
int b[N];
void solve() {
    int n, k;
    scanf("%d %d", &n, &k);
    int ans = -1;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=0;
        if(a[i]==k)ans=0;
        if(a[i]>=k)b[i]=1;
    }
    if(ans==-1){
        printf("no\n");
    }else{
        b[n+1]=b[n+2]=0;
        for(int i=1;i<=n;i++)if(b[i]&&(b[i+1]|b[i+2]))ans=1;
        if(n==1&&a[1]==k)ans=1;
        if(ans==1)printf("yes\n");
        else printf("no\n");
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--)solve();
}
-------------你最愿意做的哪件事才是你的天赋所在-------------