AtCoder Beginner Contest 215 Problem solving (A-F)

A. Your First Judge

Main idea of the title:

Determine whether the string is equal to " H e l l o , W o r l d ! " "Hello,World!" "Hello,World!"， Output on exact match " A C " "AC" "AC", otherwise output " W A " "WA" "WA".

Problem solving ideas:

Check in question.

code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    puts(s=="Hello,World!"?"AC":"WA");
    return 0;
}

B. log2(N)

Main idea of the title:

For the given N N N seeking ⌊ l o g 2 N ⌋ \left\lfloor log_2N\right\rfloor ⌊log2​N⌋.

Problem solving ideas:

If you directly use the l o g 2 ( ) log2() log2() will have precision problems, so it's best to simulate it manually.

code:

#include<bits/stdc++.h>
using namespace std;
long long n;
int main()
{
    cin>>n;
    for(int i=0;;i++){
        if((1ll<<i)>n){
            cout<<i-1<<endl;
            break;
        }
    }
    return 0;
}

C. One More aab aba baa

Main idea of the title:

For the given string S S S find the second k k k small string arrangement.

Problem solving ideas:

You can sort the whole string from small to large to get the smallest string arrangement, and then run k − 1 k-1 k − 1 time next_permutaion() gets the second k k k small arrangement.

code:

#include<bits/stdc++.h>
using namespace std;
string s;
int k;
int main()
{
    cin>>s>>k;
    sort(s.begin(),s.end());
    for(int i=0;i<k-1;i++) next_permutation(s.begin(),s.end());
    cout<<s<<endl;
    return 0;
}

D. Coprime 2

Main idea of the title:

give N N N integers A 1 , A 2 , . . . , A N A_1,A_2,...,A_N A1​,A2​,..., AN, find out all [ 1 , M ] [1,M] An integer in [1,M] that satisfies the following conditions k k k:

• g c d ( k , A i ) = 1 , 1 ≤ i ≤ N gcd(k,A_i)=1,1\le i \le N gcd(k,Ai​)=1,1≤i≤N.

Problem solving ideas:

You can use this N N All the prime factors of N integers are extracted, and then they are extracted with the idea similar to the Elsevier sieve [ 1 , M ] [1,M] All multiples of these prime factors in [1,M] interval can be screened out, or all these prime factors can be marked and enumerated [ 1 , M ] [1,M] [1,M] judge whether each integer has these factors in the process of all integers.

The time complexity is O ( N N + N l o g N ) O(N\sqrt N+NlogN) O(NN + NlogN) and O ( 2 N N ) O(2N\sqrt N) O(2NN ​).

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int a[N];
int n,m;
bool vis[N];
LL gcd(LL a,LL b){
    return b?gcd(b,a%b):a;
}
void check(int x){
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            vis[i]=true;
            while(x%i==0) x/=i;
        }
    }
    if(x>1) vis[x]=true;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        check(a[i]);
    }
 
    vector<int> res;
    for(int i=1;i<=m;i++){
        bool flag=true;
        for(int j=1;j<=i/j;j++){
            if(i%j==0&&(vis[i/j]||vis[j])){
                flag=false;
                break;
            }
        }
        if(flag) res.push_back(i);
    }
 
    printf("%d\n",res.size());
    for(auto i :res) printf("%d\n",i);
    return 0;
}

E. Chain Contestant

Main idea of the title:

Give a length of N N N string, the string is composed of A − J A-J A − J is composed of ten capital English letters. Ask how many different subsequences satisfy that the same letters in the subsequence are next to each other, that is, all the same letters are continuous 998244353 998244353 998244353 take the mold.

Problem solving ideas:

Because there are only ten letters in the string, we can consider using binary to represent the composition of letters in the state.

set up f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] indicates before consideration i i i letters. The current letter composition status is j j j and k k The sum of states ending in k.

Next, consider state transition:

• Consider following a previous subsequence
  • If the previous subsequence is k k The end of k can obviously be followed by, at this time f [ i ] [ j ] [ k ] = ∑ u = 1 i − 1 f [ u ] [ j ] [ k ] f[i][j][k]=\sum \limits_{u=1}^{i-1} f[u][j][k] f[i][j][k]=u=1∑i−1​f[u][j][k].
  • If the previous subsequence is not k k k ends if k k k does not appear in the subsequence, we can also connect it later, and we can find that the state of the subsequence that can be transferred is p r e = j − ( 1 < < k ) pre=j-(1<<k) pre=j − (1 < < K), at this time f [ i ] [ j ] [ k ] = ∑ u = 1 i − 1 ∑ y = 0 9 f [ u ] [ p r e ] [ y ] f[i][j][k]=\sum\limits_{u=1}^{i-1}\sum\limits_{y=0}^9 f[u][pre][y] f[i][j][k]=u=1∑i−1​y=0∑9​f[u][pre][y].
• In addition to being followed by a subsequence, this letter can also be used as a new subsequence f [ i ] [ 1 < < k ] [ k ] + = 1 f[i][1<<k][k]+=1 f[i][1<<k][k]+=1

Time complexity O ( 10 × n × 2 10 ) O(10\times n\times2^{10}) O(10×n×210)

Because the state transition can be regarded as a transition from all previous states and does not require stratification of States, one-dimensional compression can be considered.

If d p dp If you are proficient in dp, it's easy to think of directly using two-dimensional. In order to make it clearer, we'll explain it with three-dimensional state, A t c o d e r Atcoder The official solution of Atcoder uses three-dimensional, not hyperspace, so just choose the way you're used to.

code:

#include<bits/stdc++.h>
using namespace std;
const int N=1100,mod=998244353;
int f[N][10];
char s[N];
int n,a[N];
int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++) a[i]=s[i]-'A';
    for(int i=1;i<=n;i++){
        int x=a[i];
        for(int j=0;j<1<<10;j++){
            if((j&(1<<x))==0) continue;
            f[j][x]=(f[j][x]+f[j][x])%mod;
            int k=j-(1<<x);
            for(int y=0;y<10;y++){
                f[j][x]=(f[j][x]+f[k][y])%mod;
            }
        }
        f[1<<x][x]=(f[1<<x][x]+1)%mod;
    }
    int res=0;
    for(int i=0;i<1<<10;i++)
        for(int j=0;j<10;j++) res=(res+f[i][j])%mod;
    printf("%d\n",res);
    return 0;
}

F. Dist Max 2

Main idea of the title:

give N N Points of N 2D planes, defining two points ( x i , y i ) , ( x j , y j ) (x_i,y_i),(x_j,y_j) The distance between (xi, yi), (xj, yj) is min ⁡ ( ∣ x i − x j ∣ , ∣ y i − y j ∣ ) \min(|x_i-x_j|,|y_i-y_j|) min(∣ xi − xj ∣, ∣ yi − yj ∣), ask what is the maximum distance between two points in all points.

• 2 ≤ N ≤ 200000 2\le N\le 200000 2≤N≤200000
• 0 ≤ x i , y i ≤ 1 0 9 0\le x_i,y_i\le 10^9 0≤xi​,yi​≤109

Problem solving ideas:

Before looking at the solution, I didn't expect to do it with two points. The way of check ing this problem is very cool.

The maximum distance must be monotonous, so the main idea is right [ 0 , 1 0 9 ] [0,10^9] [0109] split this interval.

If we want to judge whether the maximum distance can be reached this time m i d mid mid, because min ⁡ ( ∣ x i − x j ∣ , ∣ y i − y j ∣ ) ≥ m i d → ∣ x i − x j ∣ ≥ m i d ， ∣ y i − y j ∣ ≥ m i d \min(|x_i-x_j|,|y_i-y_j|)\ge mid\rightarrow|x_i-x_j|\ge mid，|y_i-y_j|\ge mid min(∣ xi − xj ∣, ∣ yi − yj ∣) ≥ mid → ∣ xi − xj ∣ ≥ mid, ∣ yi − yj ∣ ≥ mid, so we can maintain a set y y The maximum and minimum values of y and make the largest in this set x x x is less than or equal to the current x i − m i d x_i-mid xi​−mid.

So you can think of it by x x x is used as the first keyword to sort in ascending order. Each time you check, a double pointer is used to maintain the maximum and minimum values of the set.

You can see the code for specific practices. After reading the code, you will be very clear.

Time complexity O ( n l o g 1 0 9 ) O(nlog10^9) O(nlog109).

code:

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10;
PII a[N];
int n;
bool check(int mid){
    int Min=1e9,Max=0;
    for(int i=1,j=1;i<=n;i++){
        while(j<=n&&a[i].first>=a[j].first+mid){
            Min=min(Min,a[j].second);
            Max=max(Max,a[j].second);
            j++;
        }
        if(a[i].second<=Max-mid||a[i].second>=Min+mid) return true;
    }
    return false;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].first,&a[i].second);
    sort(a+1,a+1+n);
    int l=0,r=1e9;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d\n",r);
    return 0;
}