2022.07.15 暑假集训 个人排位赛（十）

赛后反省

最后一场了，马马虎虎吧。最后1小时上了个厕所，回来没有继续研究麻烦的做法，反而从简去思考，然后就过题了。不用把题目想得太过复杂的。

Problem A

出处

HDU-4857

题解

拓扑排序+优先队列维护。

首先思考的是优先队列维护头节点，使得每次编号最小的点先出队。但是这样子做是错误的，例如以下的图
$$
6\longrightarrow 3\longrightarrow 1

$$

$$5⟶4⟶2$$

如果维护头部的最小去做拓扑排序的话，最后的结果会是542631，很明显这不是最优的，因为1号位排在了最后一位。我们也希望在拓扑链上，即使不是头部，但是头部后的某一点小的点也尽量往前排到。所以我们反过来建边，然后每次都是最大号的点出队。这样子能够保证每次出队的都是号数大的，也是靠后去逃生的。最后编号小的会尽可能在最前面出队了。

代码

// Good Good Study, Day Day AC.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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;
}





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
90
91
92
93
94

Problem B

出处

Codeforces-1478B

题解

规律题。

首先，以7为例，先将7的倍数全部记录，7,14,21,28,35,42,49,56,63。看个位数的数字，如果各位数相同，并且大于该倍数，则一定可以组成。例如52，首先会有42的达成，那么我们可以把它变成35+17，也就是把其中一个7加上相差的10，35也能分解出5个7，所以这样子是满足条件的。

另外，最主要的是，如果超过了该个位数的10倍，也是完全可以的！！！因为我可以先用10倍之后再加一些个位数，将剩下的数调整至满足条件，所以也是OK的。例如31，d=2。我们可以用21，将剩下的数调整成10，所以也是满足条件的。

代码

// Good Good Study, Day Day AC.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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<
    }
}


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;
}





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
90
91
92
93
94
95
96

Problem D

出处

Codeforces-540E

题解

树状数组求逆序对。

先将已经调换了的数字进行求逆序对，然后再计算没有动过的位置。如果是一个数跑到了他的前面，那么它到原来位置期间没有动过得到数与它匹配都是逆序对。如果这个数是跑到了后面，那么期间不动的数也是它的逆序对。

代码

// Good Good Study, Day Day AC.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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<

        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<
    int i=1;
    for(auto item:mp){
        if(item.second>item.first){
            ans+=sum[find_(item.second)]-sum[i];
            //cout<
        }
        else{
            ans+=sum[i]-sum[find_(item.second)];
        }
        i++;
    }
    cout<<ans;
}

signed main()
{
	IOS;
	//	cin>>T;
	while (T--) {
		ready();
		work();
	}
	return 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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

Problem G

出处

Codeforces-588B

题解

先分解出因数出来，然后要求最大的，从最大的因子开始往前查找，看是否是某个数的平方的倍数即可。

题解

// Good Good Study, Day Day AC.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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;
}





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