2022.07.15 summer training personal qualifying (10)

2022.07.15 Summer training Individual qualifying （ Ten ）

Post game introspection

The last one , Just so . Last 1 I went to the toilet in an hour , I didn't continue to study the troublesome practice after coming back , Instead, think simply , Then it's over . Don't think too complicated about the topic .

Problem A

Source

HDU-4857

Answer key

A topological sort + Priority queue maintenance .

The first thing to think about is the priority queue maintenance header node , Make the point with the smallest number out of the team first . But this is wrong , For example, the following figure
$$
6\longrightarrow 3\longrightarrow 1

$$

$$5*4*2$$

If you maintain the minimum of the header to do topological sorting , The end result will be 542631, Obviously this is not optimal , because 1 The number is last . We also hope that on the topological chain , Even if it's not the head , But a small point behind the head should also be arranged forward as far as possible . So we build the side in turn , Then every time, the largest one points out . In this way, it can ensure that every time the team is out of the big number , I also went back to escape . The last one with a small number will be out of the team as far as possible .

Code

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;


const int N = 30005, M = 100005;
int n, T = 1, m;
priority_queue<int> q;
int in_[N];
vector<int> ve[N];

void ready()
{
    
    cin >> n >> m;
    ffor(i, 1, n) {
    
        in_[i] = 0;
        ve[i].clear();
    }
    ffor(i, 1, m) {
    
        int u, v;
        cin >> u >> v;
        ve[v].push_back(u);
        in_[u]++;
    }
    ffor(i, 1, n) {
    
        if (!in_[i])
            q.push(i);
    }
}

int ans[N], ansi;

void work()
{
    
    ansi = n;
    while (q.size()) {
    
        int u = q.top(); q.pop();
        ans[ansi] = u;
        ansi--;
        for (auto v : ve[u]) {
    
            in_[v]--;
            if (!in_[v])
                q.push(v);
        }
    }
    ffor(i, 1, n) {
    
        cout << ans[i];
        if (i < n) cout << ' ';
    }
    cout << '\n';
}

signed main()
{
    
    IOS;
    cin >> T;
    while (T--) {
    
        ready();
        work();
    }
    return 0;
}

Problem B

Source

Codeforces-1478B

Answer key

Regular questions .

First , With 7 For example , First the 7 Multiples of all records ,7,14,21,28,35,42,49,56,63. Look at the single digit numbers , If you have the same number , And greater than this multiple , It must be able to form . for example 52, First of all, there will be 42 Of , Then we can turn it into 35+17, That is, one of them 7 Plus the difference 10,35 Can also be decomposed 5 individual 7, So this condition is satisfied .

in addition , The main thing is , If it exceeds the single digit 10 times , It's totally possible ！！！ Because I can use it first 10 Times and then add some single digits , Adjust the remaining number to meet the conditions , So too. OK Of . for example 31,d=2. We can use 21, Adjust the remaining number to 10, So it also meets the conditions .

Code

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;



int n, T = 1, ans;
int dp[10][20];
bool f[10][20];
bool vis[10];

void ready()
{
    
    ffor(i,1,9){
    
        ffor(j,1,10)
            dp[i][j]=i*j;
       // ffor(j,1,9) cout<<dp[i][j]<<' ';cout<<'\n';
    }
}


void work()
{
    
    int d;
    cin>>n>>d;
    ffor(i,1,n){
    
        bool flag=false;
        int a,b;
        cin>>a;
        if(a>=10*d) flag=true;
        if(a%d==0) flag=true;
        for(int j=1;j<=9;j++){
    
            int t=j*d;
            if(t>a) break;
            int b=a-t;
            if(b==0 || (b%10==0 || b%d==0)){
    
                flag=true;
                break;
            }
            while(b){
    
                if(b%10==d) flag=true;
                b=b/10;
            }
        }
        while(a){
    
            if(a%10==d) flag=true;
            a=a/10;
        }
        
        if(!flag) cout<<"NO\n";
        else cout<<"YES\n";
    }
}

signed main()
{
    
	IOS;
    ready();
	cin>>T;
	while (T--) {
    
		work();
	}
	return 0;
}

Problem D

Source

Codeforces-540E

Answer key

Tree array reverse order pair .

First, reverse the numbers that have been changed , Then calculate the position that has not been moved . If a number runs in front of him , Then it has not moved during its original position, and the matching number with it is in reverse order . If this number is behind , Then the fixed number in the period is also its reverse pair .

Code

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;


const int N=1e6;
int n, T = 1, ans;
map<int,int> mp;
map<int,int> loc;
vector<int> alls;
priority_queue<int, vector<int>, greater<int> > q;
int t[N];
int sum[N];

int lowbite(int x){
    
    return x&(-x);
}

void add(int x){
    
    while(x<=alls.size()){
    
        t[x]++;
        x+=lowbite(x);
    }
    return;
}

int get_sum(int x){
    
    int res=0;
    while(x){
    
        res+=t[x];
        x-=lowbite(x);
    }
    return res;
}

void ready()
{
    
    cin>>n;
    ffor(i,1,n){
    
        int a,b;
        cin>>a>>b;
        if(mp[a]==0) mp[a]=a;
        if(mp[b]==0) mp[b]=b;
        swap(mp[a],mp[b]);
    }
    int li=0;
    int i=1,las=0;
    for(auto item:mp){
    
        //if(item.first == item.second) continue;
        q.push(item.second);
        alls.push_back(item.first);
        loc[item.second]=item.first;
        //cout<<item.first<<' '<<item.second<<'\n';

        sum[i]=item.first-las-1;
        sum[i]+=sum[i-1];
        las=item.first;
        i++;
    }
    sort(alls.begin(),alls.end());
}

int find_(int x){
    
    int res=lower_bound(alls.begin(),alls.end(),x)-alls.begin();
    res++;
    return res;
}

void work()
{
    
    while(q.size()){
    
        int u=q.top();q.pop();
        int i=find_(u);
        int now=find_(loc[u]),to=i;
        ans+=get_sum(alls.size())-get_sum(now);
        add(now);
        //ans+=(u-loc[u])-(get_sum(i)-get_sum(loc[u]));
        //add(loc[u]);
    }
    //cout<<ans<<"ans\n";
    int i=1;
    for(auto item:mp){
    
        if(item.second>item.first){
    
            ans+=sum[find_(item.second)]-sum[i];
            //cout<<ans<<'\n';
        }
        else{
    
            ans+=sum[i]-sum[find_(item.second)];
        }
        i++;
    }
    cout<<ans;
}

signed main()
{
    
	IOS;
	// cin>>T;
	while (T--) {
    
		ready();
		work();
	}
	return 0;
}

Problem G

Source

Codeforces-588B

Answer key

First, decompose the factors to come out , Then ask for the biggest , Start with the largest factor and look forward , See if it is a multiple of the square of a number .

Answer key

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;



int n, T = 1;
vector<int> ans;

void ready()
{
    

}



void work()
{
    
    cin>>n;
    ffor(i,1,sqrt(n)){
    
        if(n%i==0){
    
            ans.push_back(i);
            ans.push_back(n/i);
        }
    }
    sort(ans.begin(),ans.end());
    rrep(i,ans.size()-1,0){
    
        int t=ans[i];
        bool flag=true;
        ffor(j,2,sqrt(t)){
    
            int jj=j*j;
            if(t%jj==0){
    
                flag=false;
                break;
            }
        }
        if(flag){
    
            cout<<t;
            return;
        }
    }
}

signed main()
{
    
	IOS;
	// cin>>T;
	while (T--) {
    
		ready();
		work();
	}
	return 0;
}