2022.07.08 summer training personal qualifying (III)

2022.07.08 Summer training Individual qualifying （ 3、 ... and ）

Post game introspection

The sensitivity of dynamic planning is not enough , It's still the wrong way all the time . Then another question is not sensitive to some characteristics , It is close to the positive solution , One step away. .

Continue refueling .

Problem A

Source

Codeforces-689D

Answer key

ST surface + Two points

utilize ST After the table , Enumerate the left coordinates of the interval . When the right range continues to expand , The maximum value is an increasing sequence , The minimum value is a decreasing sequence . So use two two points , To find out whether there is an interval in which the maximum and minimum values are equal in the two sequences .

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 + 6;
int n, T = 1;
int a[N][22];
int b[N][22];

int get_max(int x, int y) {
    
    int mid = log2(y - x + 1);
    return max(a[x][mid], a[y - (1 << mid) + 1][mid]);
}

int get_min(int x, int y) {
    
    int mid = log2(y - x + 1);
    return min(b[x][mid], b[y - (1 << mid) + 1][mid]);
}

bool check_L(int x, int y) {
    
    int minn = get_min(x, y);
    int maxn = get_max(x, y);
    if (maxn >= minn) return true;
    else return false;
}

bool check_R(int x, int y) {
    
    int minn = get_min(x, y);
    int maxn = get_max(x, y);
    if (maxn > minn) return true;
    else return false;
}


void ready()
{
    
    cin >> n;
    ffor(i, 1, n) {
    
        cin >> a[i][0];
    }
    ffor(j, 1, 18) {
    
        ffor(i, 1, n) {
    
            a[i][j] = max(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
        }
    }
    //mst(b,INF);
    ffor(i, 1, n) {
    
        cin >> b[i][0];
    }
    ffor(j, 1, 18) {
    
        ffor(i, 1, n) {
    
            b[i][j] = min(b[i][j - 1], b[i + (1 << (j - 1))][j - 1]);
        }
    }
    int ans = 0;
    ffor(i, 1, n) {
    
        int L = 0, R = 0;
        int l = i, r = n, mid;
        while (l < r) {
    
            mid = l + r >> 1;
            if (check_L(i, mid)) {
    
                r = mid;
            }
            else {
    
                l = mid + 1;
            }
        }
        L = l;
        l = i; r = n;
        while (l < r) {
    
            mid = l + r + 1>> 1;
            if (check_R(i, mid)) {
    
                r = mid - 1;
            }
            else {
    
                l = mid;
            }
        }
        R = l;
       // cout << "i=" << i << ' ' << L << ' ' << R << '\n';
        if (get_max(i, L) == get_min(i, R)) {
    
            ans += R - L + 1;
        }
    }
    cout << ans;
}


void work()
{
    

}

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

Problem B

Source

Codeforces-687C

Answer key

Dynamic programming .

$dp[i][j]$ The value represents i Whether time can be j Construct for . If yes, it is 1, No is 0.

If $dp[i][j]=1$, Then when adding a new value c when ,$dp[i+c][j]=1$ and $dp[i+c][j+c]=1$ All set up . Then the transfer equation is also obtained .

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 = 505;
bool dp[N][N];
int n, T = 1, k;

void ready()
{
    
	cin >> n >> k;
	dp[0][0] = true;
	ffor(t, 1, n) {
    
		int c;
		cin >> c;
		rrep(i, k, c) {
    
			ffor(j, 0, k-c) {
    
				if (dp[i - c][j])
					dp[i][j] = dp[i][j + c] = true;
			}
		}
	}
}


void work()
{
    
	int ans = 0;
	ffor(i, 0, k) ans += dp[k][i];
	cout << ans << '\n';
	ffor(i, 0, k) {
    
		if (dp[k][i])
			cout << i << ' ';
	}
}

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

Problem F

Source

Codeforces-702D

Answer key

Thinking questions .

The distance is relatively small , Drive directly to .

If k Distance time , Walk faster than the car and repair the car , Then drive away first k km , Walk the rest of the way .

If k Distance time , Walk slower than the car and repair the car , Then each of the following k Drive every kilometer , Until there is more than k When I didn't walk for a kilometer , Consider whether it's faster to repair the car or walk directly , Just choose .

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;
int d,k,a,b,t;


void ready()
{
    
    cin>>d>>k>>a>>b>>t;
    if(d<=k){
    
        cout<<d*a;
        return;
    }
    if(a*k+t>b*k){
    
        int ans=k*a;
        d-=k;
        ans+=d*b;
        cout<<ans;
        return;
    }
    else{
    
        int cnt=d/k;
        int ans=cnt*a*k + (cnt-1)*t;
        d=d%k;
        if(cnt==0) ans=0;
        if(a*d+t>=b*d)
            ans+=b*d;
        else{
    
            ans+=a*d;
            if(cnt) ans+=t;
        }
        cout<<ans;
    }
}


void work()
{
    

}

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

Problem G

Source

Codeforces-1234A

Answer key

The average , Carry up .

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;


void ready()
{
    

}


void work()
{
    
    cin>>n;
    int sum=0;
    ffor(i,1,n){
    
        int x;
        cin>>x;
        sum+=x;
    }
    int ans=(sum+n-1)/n;
    cout<<ans<<'\n';
}

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