526互联

SMU Summer 2023 Contest Round 3

发布时间 2023-07-14 18:29:04作者: kingqiao

A. Curriculum Vitae

题意：给出一串01序列，可以删除任意个元素，使得1后面没有0

思路：枚举01分界点，使得统计前面0的个数和后面1的个数，取最大值。

点击查看代码 

#include<bits/stdc++.h>
using namespace std;
 
int a[110];
 
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,ans = 1;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){  //01分界点
        int temp = 0;
        for(int j=1;j<=i;j++){
            if(!a[j]) temp++;
        }
        for(int j=i;j<=n;j++){
            if(a[j]==1) temp++;
        }
        ans = max(ans,temp);
    }
    cout<<ans<<'\n';

B. Math Show

题意：有n个相同的任务，每个任务含有k个子任务，解决每个任务要花费ti时间，每完成一子任务会加一分，每完成一个完整的任务会额外加一分，问：在m时间内最多能得多少分？

思路：先对子任务完成时间排序，枚举完成完整任务的个数，再用剩余时间完成每n个1到k-1任务。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define int long long

int a[610],sum,ans;

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,k,m;
    cin>>n>>k>>m;
    for(int i=1;i<=k;i++)
        cin>>a[i],sum += a[i];
    sort(a+1,a+1+k);
    int cnt;
    if(m/sum>=n) cnt = n;
    else cnt = m/sum;
    for(int i=0;i<=cnt;i++){
        int temp = 0;
        int flag = m - i * sum;
        for(int j=1;j<k;j++){
            for(int k=1;k<=n-i;k++){
                flag -= a[j];
                if(flag>=0) temp+=1;
                else break;
            }
            if(flag<=0) break;
        }
        temp += (k + 1) * i;
        ans = max(ans,temp);
    }
    cout<<ans<<'\n';
    return 0;
}

C. Four Segments

题意：给出一段数组，求三个分界点d1,d2,d3，得到四段数字和sum1，sum2，sum3，sum4，ans = sum1 + sum2 - sum3 - sum4, 求ans最大值

思路：求前缀和，枚举d1,d3,在d1,d2间前缀和最小的点作为d2,取最值。

点击查看代码 
#include <bits/stdc++.h>
using namespace std;

#define ll long long;

const int N = 1e6 + 10;
int n, m, k, d1, d2, d3;
ll sum[N];

ll cal(int l, int r) {
    return sum[r - 1] - sum[l - 1];
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> sum[i];
        sum[i] += sum[i - 1];
    }

    ll ans = -(1ll << 60);

    for (int i = 0; i <= n; ++i) {
        ll temp = sum[i];
        int pos = i;
        for (int j = i; j <= n; ++j) {
            if (sum[j] < temp) {
                pos = j;
                temp = sum[j];
            }
            ll Sum = cal(1, i + 1) - cal(i + 1, pos + 1) + cal(pos + 1, j + 1) - cal(j + 1, n);
            if (Sum >= ans) {
                d1 = i;
                d2 = pos;
                d3 = j;
                ans = Sum;
            }

        }
    }
    cout<<d1<<" "<<d2<<" "<<d3<<'\n';
    return 0;
}

D. Monitor

题意：有q个像素在坐标x，y，在时间t后损坏，当损坏的像素组成k*k的正方形时显示器无法工作，求这一时间的最小值，

思路：二分彻底损坏时间，每个损坏的像素记录其为1,求损坏的像素前缀和,枚举i，j为右下角的边长为k的正方形，前缀和为k*k时该时间符合条件。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

int n,m,k,q,ans=1e9+610,sum[610][610];
struct node{
    int x,y,c;
}p[250610];

bool check(int mid){
    memset(sum,0,sizeof sum);
    for(int i=1;i<=q;i++)
        if(p[i].c<=mid)
            sum[p[i].x][p[i].y] = 1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
            if(i>=k&&j>=k&&sum[i][j]-sum[i-k][j]-sum[i][j-k]+sum[i-k][j-k]==k*k)
                return 1;
        }
    return 0;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k>>q;
    int maxn = 0;
    for(int i=1;i<=q;i++){
        int a,b,c;
        cin>>a>>b>>c;
        p[i] = {a,b,c};
        maxn = max(maxn,p[i].c);
    }
    int l = -1, r = maxn+1;
    while(l+1<r){
        int mid = l + r >> 1;
        if(check(mid)){
            r = mid;
            ans = min(ans,mid);
        }else l = mid;
    }
    if(ans == 1e9+610) cout<<-1<<'\n';
    else cout<<ans<<'\n';
    return 0;
}