[LDUOJ] the 13th week of training in the second half of 2020 | ACDE problem solution

This week's question seems to be relatively simple

catalogue

A. Combinatorial number problem

Main idea of the title:

Topic idea:

Code:

C. Relay

Main idea of the title:

Topic idea:

Code:

D. Words

Main idea of the title:

Topic idea:

Code:

E. elections

Main idea of the title:

Topic idea:

Code:

A. Combinatorial number problem

Main idea of the title:

Topic idea:

emmm.

Non - number theory contestants can also solve their number theory problems

Considering the multiple problem, we can directly decompose the prime factor

After the prime factor decomposition, the division of the combinatorial number will be changed to the subtraction of the power, so a prefix sum can be obtained for the power

Just judge whether it is greater than all powers of k

However, this place will be blocked by T, because every time you have to calculate n*m and ask t times

So you might as well type the external watch directly and get it directly from O1

Just use the two-dimensional prefix and handle it

Code:

/*** keep hungry and calm CoolGuang!***/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lld\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 1e6+700;
const int mod= 1e9+7;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int cnt = 0;
int dp[2005][21];
ll res[2005][2005];
int prime[300];
int pre[30];
int judge(int x){
    if(x == 1) return 0;
    for(int k=2;k*k<=x;k++)
        if(x%k == 0) return 0;
    return 1;
}
int check(int i,int k){
    if(i<k) return 0;
    for(int j=1;j<=cnt;j++)
        if(dp[i][j]-dp[k][j]-dp[i-k][j] < pre[j]) return 0;
    return 1;
}
int main(){
    for(int i=1;i<=21;i++)
        if(judge(i))
            prime[++cnt] = i;
    int T;read(T);read(p);
    for(int i=1;i<=cnt;i++){
        while(p%prime[i] == 0){
            p/=prime[i];
            pre[i]++;
        }
    }
    for(int i=1;i<=2000;i++){
        ll temp = i;
        for(int k=1;k<=cnt;k++) dp[i][k] = dp[i-1][k];
        for(int k=1;k<=cnt;k++){
            while(temp%prime[k] == 0){
                dp[i][k]++;
                temp /= prime[k];
            }
        }
    }
    for(int i=1;i<=2001;i++){
        for(int k=1;k<=2001;k++){
            res[i][k] = res[i-1][k] + res[i][k-1] - res[i-1][k-1] + check(i-1,k-1);
        }
    }
    while(T--){
        read(n);read(m);
        m = min(m,n);
        n++;m++;
        printf("%lld\n",res[n][m]);
    }
    return 0;
}

C. Relay

Main idea of the title:

Topic idea:

Very simple simulation problem

Just maintain the earliest end time of each player, that is, maintain a small top pile with a priority queue and give priority to the end time of running

So you just need to get the smallest one out of the team every time, and then use this person to update the person "connected" with this person

Add a mark during the period, under which you can check whether you have visited

Code:

/*** keep hungry and calm CoolGuang!***/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lld\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 1e6+700;
const int mod= 1e9+7;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
vector<int>v[maxn];
ll dis[maxn];
ll a[maxn];
int vis[maxn];
ll bfs(){
    ll ans = 0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    q.push({a[1],1});
    vis[1] = 1;
    while(!q.empty()){
        auto u = q.top();q.pop();
        ll w = u.first,id = u.second;
        ans = max(ans,w);
        for(int e:v[id]){
            if(!vis[e]){
                q.push({w+a[e],e});
                vis[e] = 1;
            }
        }
    }return ans;
}
int main(){
     priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        int x;read(x);
        for(int k=1;k<=x;k++){
            int y;read(y);
            v[i].push_back(y);
        }
    }
    printf("%lld\n",bfs());
    return 0;
}

D. Words

Main idea of the title:

Topic idea:

For any two strings, the relationship between letters can be judged by n^3

Next, we only need to consider the unique solution, no solution and multiple solutions in the graph

1. Unique solution: the topology path is unique

2. No solution: Ring generation

3. Multiple solutions: the topological path is not unique

Two approaches are recommended:

Topological sorting: when dealing with multi solution problems, topological sorting only needs to consider whether the points with out degree of 0 and in degree of 0 are unique

No solution - there is a ring. There is no need to say more about the solution of this topological sorting

Floyd:

mp[x][y] edge construction means Y > X

Floyd can judge whether there is a self ring. Just judge whether mp[i][i] is 1

In the case of multiple solutions, you can look at the current ranking. Everyone's ranking calculation: just find out how many mp[x][k] are. K satisfies that mp[x][k] is 1, so the ranking of X is n-k

As long as there is no repetition

Only Floyd's code is below

Code:

/*** keep hungry and calm CoolGuang!***/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lld\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 1e6+700;
const int mod= 1e9+7;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
char s[100][102];
int pre[maxn];
int rk[30],vis[30];
int mp[30][30];
int cnt = 0;

int Find(int x){
    return pre[x] == x?x:pre[x] = Find(pre[x]);
}
int main(){
    read(n);
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
        for(int k=1;s[i][k];k++){
            vis[s[i][k]-'a'] ++;
        }
    }
    for(int i=0;i<26;i++){
        pre[i] = i;
        if(vis[i]) cnt++;
    }
    int cot = cnt;

    for(int i=1;i<=n;i++){
        for(int k=i+1;k<=n;k++){
            int len = strlen(s[i]+1);
            for(int j=1;j<=len;j++){
                if(s[i][j] != s[k][j]){
                    int x = s[i][j] - 'a';
                    int y = s[k][j] - 'a';
                    int dx = Find(x),dy = Find(y);
                    if(dx != dy) pre[dx] = dy,cnt--;
                    mp[x][y] = 1; ///y > x
                    break;
                }
            }
        }
    }

    if(cnt > 1) printf("?");
    else{
        for(int k=0;k<26;k++){
            for(int i=0;i<26;i++){
                for(int j=0;j<26;j++){
                    if(mp[i][k] && mp[k][j]) mp[i][j] = 1;
                }
            }
        }
        for(int k=0;k<26;k++){
            if(mp[k][k]){
                printf("!\n");
                return 0;
            }
        }
        for(int k=0;k<26;k++){
            if(vis[k]){
                int res = 0;
                for(int j=0;j<26;j++)
                    if(mp[k][j]) res++;
                if(!rk[cot-res]) rk[cot-res] = k+1;
                else{
                    printf("?\n");
                    return 0;
                }
            }
        }
        for(int i=1;i<=cot;i++)
            printf("%c",rk[i]-1+'a');
        printf("\n");
    }
    return 0;
}

E. elections

Main idea of the title:

 

Topic idea:

Simulate according to the meaning of the topic

Code:

/*** keep hungry and calm CoolGuang!***/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lld\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 1e6+700;
const int mod= 1e9+7;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
struct node{
    string name;
    int id;
    ll x;
    bool friend operator<(node a,node b){
        return a.name < b.name;
    }
}q[maxn];
pair<int,int>s[maxn];
int res[maxn];
int main(){
    read(m);read(n);
    for(int i=1;i<=n;i++){
        cin>>q[i].name;
        cin>>q[i].x;
        q[i].id = i;
    }
    int cnt = 0;
    for(int i=1;i<=n;i++){
        if(q[i].x*100>=5*m){
            for(int k=1;k<=14;k++)
                s[++cnt] = {q[i].x/k,i};
        }
    }
    sort(s+1,s+1+cnt,greater<pair<int,int>>());
    for(int i=1;i<=14;i++)
        res[s[i].second] ++;
    sort(q+1,q+1+n);
    for(int i=1;i<=n;i++){
        int id = q[i].id;
        if(res[id]){
            cout<<q[i].name<<" "<<res[id]<<endl;
        }
    }
    return 0;
}

 

Posted by Elephant on Wed, 04 May 2022 23:56:08 +0300