2022.07.12 summer training personal qualifying (VII)

2022.07.12 Summer training Individual qualifying （ 7、 ... and ）

Post game introspection

Not to , Not really , After being stuck by two questions, I don't think about other questions at all . The knapsack question is really simple , Missed the question . at that time J If you miss the question, you can still have black Queen,H I always think my idea is correct , And according to the submitted results, the feedback has always been considered to be a problem of accuracy . Not hard enough, I can only say , And there is a priority queue water problem with segment tree to code , There is also a mistake in the middle , Laugh numb .

Problem C

Source

Codeforces-851B

Answer key

Judge that the three points are not collinear and the length is equal .

// 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, m;


void ready()
{
    

}

int dis(int ax,int ay,int bx,int by){
    
    return (by-ay)*(by-ay)+(bx-ax)*(bx-ax);
}

void work()
{
    
    int ax,ay,bx,by,cx,cy;
    cin>>ax>>ay>>bx>>by>>cx>>cy;
    if(dis(ax,ay,bx,by)!=dis(bx,by,cx,cy) || (by-ay)*(cx-bx)==(cy-by)*(bx-ax)){
    
        cout<<"No";
    }
    else{
    
        cout<<"Yes";
    }
}

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

Problem D

Source

Codeforces-854C

Answer key

First deal with the one with the greatest loss . Every plane cannot fly in advance , Then it is to find the first point that can take off after that time .

Take the points that can take off as an array , Every click saves k+1,k+2,…,k+n, Then build a segment tree , Every time after taking off from a point in time , Turn this point into INF, Finally, the problem becomes a single point of modification , The problem of finding the minimum value of interval .

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=3e5+5;
int n, T = 1, m;
int k;

struct Air{
    
    int val,tim,st;
}a[N];
bool f[N];
int cn[N];
int t[N];
vector<int> loc;

struct Tree{
    
    int l,r,minn;
}tr[N*4];

void pushup(Tree& u,Tree& l,Tree& r){
    
    u.minn=min(l.minn,r.minn);
}

void build(int u,int l,int r){
    
    if(l==r) tr[u]={
    l,r,t[l]};
    else{
    
        tr[u]={
    l,r};
        int mid=tr[u].l+tr[u].r>>1;
        build(u<<1,l,mid); build(u<<1|1,mid+1,r);
        pushup(tr[u],tr[u<<1],tr[u<<1|1]);
    }
}

void modify(int u,int x){
    
    if(x==tr[u].l && tr[u].l==tr[u].r) tr[u].minn=INF;
    else{
    
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x);
        if(mid<x) modify(u<<1|1,x);
        pushup(tr[u],tr[u<<1],tr[u<<1|1]);
    }
}

int query(int u,int l,int r){
    
    if(l<=tr[u].l && tr[u].r<=r) return tr[u].minn;
    int mid=tr[u].l+tr[u].r>>1;
    int lmin=INF,rmin=INF;
    if(l<=mid) lmin=query(u<<1,l,r);
    if(mid<r) rmin=query(u<<1|1,l,r);
    return min(lmin,rmin);
}


bool cmp(Air i,Air j){
    
    if(i.val==j.val){
    
        return i.tim<j.tim;
    }
    return i.val>j.val;
}

void ready()
{
    
    cin>>n>>k;
    ffor(i,1,n){
    
        int c;
        cin>>c;
        a[i]={
    c,i};
        t[i]=i+k;
        loc.push_back(i+k);
    }
    sort(a+1,a+n+1,cmp);
    ffor(i,1,n){
    
        a[i].st=lower_bound(loc.begin(),loc.end(),a[i].tim)-loc.begin()+1;
        //cout<<a[i].tim<<' '<<a[i].st<<'\n';
    }
    build(1,1,n);
    int ans=0;
    //cout<<query(1,3,5);
    ffor(i,1,n){
    
        int id=query(1,a[i].st,n);
        modify(1,id-k);
        ans+=(id-a[i].tim)*a[i].val;
        cn[a[i].tim]=id;
       // cout<<a[i].val<<' '<<a[i].tim<<' '<<a[i].st<<' '<<id<<'\n';
       // cout<<query(1,1,n)<<'\n';
    }
    cout<<ans<<'\n';
    ffor(i,1,n) cout<<cn[i]<<' ';
}


void work()
{
    


}

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

Problem E

Source

Codeforces-864E

Answer key

Deformation of knapsack problem .

First , First sort by urgency , according to d From small to large . If equal , Give Way t In front of the big row . The backpack has the largest capacity d.

$dp[i]$ Said in the first i The maximum value that can be obtained at a point in time .

Look back and forward every time , If one $dp[i]$ Get value , also $i+t<d$, Explain that the current items can be put into the backpack . The amount of data is relatively small , Update the... After each save i+t The order of items that get the maximum value in one time .

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 = 105;

int n, T = 1, maxn;
struct Baby {
    
	int t, d, p, id;
}a[N];
vector<int> ans[3005];
bool f[3005];
int dp[3005];

bool cmp(Baby i, Baby j) {
    
	if (i.d == j.d) return i.t > j.t;
	return i.d < j.d;
}

void ready()
{
    
	cin >> n;
	ffor(i, 1, n)
	{
    
		cin >> a[i].t >> a[i].d >> a[i].p;
		maxn = max(maxn, a[i].d);
		a[i].id = i;
	}
	sort(a + 1, a + n + 1, cmp);
	f[0] = true;
	ffor(i, 1, n) {
    
		int t = a[i].t, d = a[i].d, p = a[i].p, id = a[i].id;
		rrep(j, maxn, 0) {
    
			if (f[j] && j + t < d) {
    
				f[j + t] = true;
				if (dp[j + t] <= dp[j] + p) {
    
					dp[j + t] = dp[j] + p;
					if(ans[j + t].size())
						ans[j + t].clear();
					ans[j + t].insert(ans[j + t].begin(), ans[j].begin(), ans[j].end());
					ans[j + t].push_back(id);
				}
			}
		}
	}
	int all = 0, ansi = 0;
	ffor(i, 1, maxn) {
    
		if (dp[i] > all) {
    
			all = dp[i];
			ansi = i;
		}
	}
	cout << all << '\n';
	cout << ans[ansi].size() << '\n';
	for (auto item : ans[ansi]) {
    
		cout << item << ' ';
	}
}


void work()
{
    

}

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

Problem F

Source

Codeforces-1263C

Answer key

Block .

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, m;


void ready()
{
    

}

stack<int> ans;

void work()
{
    
    cin>>n;
    int k=1;
    while(k<=n){
    
        ans.push(n/k);
        k=n/(n/k)+1;
    }
    ans.push(0);
    cout<<ans.size()<<'\n';
    while(ans.size()){
    
        cout<<ans.top()<<' ';
        ans.pop();
    }
    cout<<'\n';

}

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

Problem H

Source

Codeforces-939E

Answer key （cyp）

Detailed ideas for solving problems

1. In order to make max-mean Maximum , You can think greedily , On the one hand, try to make max Bigger , On the other hand, try to make mean smaller
2. In order to make max As big as possible , consider S The maximum value in is added to the subset
3. In order to make mean As small as possible , Consider adding as many small values as possible to the subset , Lower the average

Key points and difficulties of the algorithm

Mathematical proof of the above greed
1. It can be noted that , hypothesis max Updated with x,mean Will increase x/cnt, among cnt Is the number of elements in the subset , obviously max-mean It doesn't decrease
2. Small values are added to the subset with S An increase in , The optimal solution does not move these values out of the subset , Because the overall average is increasing , More and more small values are needed to reduce the average .

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 = 5e5 + 5;
int n, T = 1, m, ai;
double sum[N], a[N], avgsum;

void ready()
{
    
    int cnt = 1;
    double avg = 0, avgsum = 0;
    cin >> n;
    ffor(i, 1, n) {
    
        int op;
        cin >> op;
        if (op == 1) {
    
            cin >> a[++ai];
            sum[ai] = a[ai] + sum[ai - 1]; 
        }
        else {
    
            avg = (sum[cnt] + a[ai]) / (cnt + 1); 
            while (cnt + 1 < ai && (sum[cnt + 1] + a[ai]) / (cnt + 2)  <= avg) {
    
                cnt++; 
                avg = (sum[cnt] + a[ai]) / (cnt + 1);
            } 
            double ans = a[ai] - avg;
            printf("%.10lf\n", ans);
        }
    }
}


void work() {
    

}


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

Problem J

Source

Codeforces-734D

Answer key

Be careful , Presence black Queen.

Save white Queen What kind of black chess is the closest to it in eight directions . If it can be eaten Yes.

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, m;
int qx, qy;

char lu = '0', ru = '0', ld = '0', rd = '0', u = '0', d = '0', l = '0', r = '0';
int dlu, dru, dld, drd, du, dd, dl, dr;

bool check_(PII a, PII b) {
    
    int ax = a.first, ay = a.second, bx = b.first, by = b.second, cx = qx, cy = qy;
    return ((by - ay) * (cx - bx) == (cy - by) * (bx - ax));
}

int dis(PII a, PII b) {
    
    int ax = a.first, ay = a.second, bx = b.first, by = b.second;
    return (by - ay) * (by - ay) + (bx - ax) * (bx - ax);
}

void ready()
{
    
    cin >> n >> qx >> qy;
    ffor(i, 1, n) {
    
        char ch;
        int dister;
        int x, y;
        cin >> ch >> x >> y;
        PII item = {
     x,y }, queen = {
     qx,qy };
        dister = dis(item, queen);
        if (check_(item, {
     qx - 1,qy + 1 }) && x < qx) {
    
            if (!dlu || dlu > dister) {
    
                dlu = dister;
                lu = ch;
            }
        }
        if (check_(item, {
     qx - 1,qy - 1 }) && x < qx) {
    
            if (!dld || dld > dister) {
    
                dld = dister;
                ld = ch;
            }
        }
        if (check_(item, {
     qx + 1,qy + 1 }) && x > qx) {
    
            if (!dru || dru > dister) {
    
                dru = dister;
                ru = ch;
            }
        }
        if (check_(item, {
     qx + 1,qy - 1 }) && x > qx) {
    
            if (!drd || drd > dister) {
    
                drd = dister;
                rd = ch;
            }
        }
        if (x == qx) {
    
            if (y > qy) {
    
                if (!du || du > dister) {
    
                    du = dister;
                    u = ch;
                }
            }
            if (y < qy) {
    
                if (!dd || dd > dister) {
    
                    dd = dister;
                    d = ch;
                }
            }
        }
        if (y == qy) {
    
            if (x > qx) {
    
                if (!dr || dr > dister) {
    
                    dr = dister;
                    r = ch;
                }
            }
            if (x < qx) {
    
                if (!dl || dl > dister) {
    
                    dl = dister;
                    l = ch;
                }
            }
        }
    }
}



bool work()
{
    
    if (l == 'Q' || l == 'R' || r == 'Q' || r == 'R' || u == 'Q' || u == 'R' || d == 'Q' || d == 'R') return true;
    if (ld == 'Q' || ld == 'B' || lu == 'Q' || lu == 'B' || rd == 'Q' || rd == 'B' || ru == 'Q' || ru == 'B') return true;
    return false;
}

signed main()
{
    
    IOS;
    ready();
    //cin>>T;
    while (T--) {
    
        if (work()) cout << "YES";
        else cout << "NO";
    }
    return 0;
}