SMU Summer 2023 Contest Round 3

A. Curriculum Vitae

题意就是要求\(1\)后面不能有\(0\)的情况下的子序列最长长度, 也就是求一个最长不下降子序列,不过由于这是个\(01\)序列,也可以分别做一个前缀和求出\(0\)的数量,后缀和求\(1\)的数量,最后跑一遍循环,找一个最大值即可,

这里我是\(dp\)写的一个最长不下降子序列

#include  <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

int n,m;
void solve(){
    cin >> n;
    vector<int> s(n);
    int one = 0;
    for(auto &i : s){
        cin >> i;
    }
    vector<int> dp(n);
    int ans = 0;
    for(int i = 0;i < n;i ++){
        dp[i] = 1;
        for(int j =0; j < i;j ++){
            if(s[i] >= s[j]){
                dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int Ke_scholar = 1;
//    cin >> Ke_scholar;
    while(Ke_scholar--)
        solve();
    return 0;
}
/*
 */

B. Math Show

这题由于数据范围很小,可以直接暴力贪心求解

#include  <bits/stdc++.h>
#define endl '\n'
#define int long long
#define all(a) (a).begin(),(a).end()

using namespace std;

int n,m;
int match[N];
void solve(){
   int k,M;
   cin >> n >> k >> M;
   vector<int> a(k + 1);
   int sum = 0;
   for(int i = 1;i<= k;i++){
       cin >> a[i];
       sum += a[i];
   }
   sort(all(a));

   int ans = 0;
   for(int i = 0;i <= n;i ++){
       int score = i * k + i, t = sum * i, r = n - i;
       /*
       score 是完成i个人时的初始分数,因为完成一个人要+1,所以这里是直接+i;
       t是完成i个人所消耗的时间,当t大于M时就可以直接退出;
       r是目前为止还有几个人任务未完成.
       */
       if(t > M ) break;
       for(int j = 1;j <= k;j ++){
           if(t >= M) break;
           for(int p = 1;p <= r;p ++){
               t += a[j];
               if(t > M) break;
               score ++;
           }
       }
       ans = max(ans, score);
   }
   cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int Ke_scholar = 1;
//    cin >> Ke_scholar;
    while(Ke_scholar--)
        solve();
    return 0;
}
/*
 */

C. Four Segments

题意翻译过来就在一个序列里找到\(i,j,k\)三个分界点使得\(sum(0, i) - sum(i, j) + sum(j, k) - sum(k, n)\)的值最大,\(sum( i,j)\)就是\(j\)的前缀和减去\(i\)的前缀和,如果直接暴力三层循环的话,时间肯定是不够的,这里我们可以发现这个公式前半部分\(sum(0,i) - sum(i,j)\)与它的的后半部分\(sum(j,k) - sum(k,n)\)在\(j\)是一个确定的值时其实是互不影响的,所以我们单独循环\(j\),然后分别去循环\(i\)和\(k\),找到两个部分的最大值时的\(i,k\)的值即可.

#include  <bits/stdc++.h>
#define endl '\n'
#define int long long
#define all(a) (a).begin(),(a).end()

using namespace std;

int n,m;
void solve(){
   cin >> n;
   vector<int> a(n + 1), pre(n + 1);
   for(int i = 1;i <= n;i ++){
       cin >> pre[i];
       pre[i] += pre[i - 1];
   }
   int ans = -LLONG_MAX;

   int ansi, ansk, ansj;
   for(int j = 0;j <= n;j ++){
      int sum1 = -inf, sum2 = -inf, sum;
      int si,sk;
      for(int i = 0;i <= j;i ++){
          if(pre[i] - (pre[j] - pre[i]) > sum1){
              sum1 =  pre[i] - (pre[j] - pre[i]);
              si = i;
          }
      }
      
      for(int k = j;k <= n;k ++){
          if(pre[k] - pre[j] - (pre[n] - pre[k]) > sum2){
              sum2 = pre[k] - pre[j] - (pre[n] - pre[k]);
              sk = k;
           }
       }
       
       sum = sum1 + sum2;
       if(sum > ans){
           ans = sum ;
           ansi = si, ansj = j, ansk = sk;
       }
   }
   cout << ansi << ' ' << ansj << ' ' << ansk << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int Ke_scholar = 1;
//    cin >> Ke_scholar;
    while(Ke_scholar--)
        solve();
    return 0;
}
/*
 */

D. Monitor

题意就是给出\(q\)个坏掉的像素点坐标和坏掉的时间,当这些点构成一个\(k*k\)的正方形时,说明显示屏会坏掉,而我们要找到它坏掉时的最小时间,如果\(q\)个坐标都不能构成这个正方形,则说明没坏,输出\(-1\).

做法是二分+二维前缀和,即先对每个坏掉的像素点坏掉的时间排序,然后去对这\(q\)个像素点二分,每次去检查它是否能构成一个\(k*k\)的正方形,不能就往后寻找,最后\(l > q\)的话则说明\(q\)个像素点都不能构成此正方形.

#include  <bits/stdc++.h>
#define endl '\n'
#define int long long
#define all(a) (a).begin(),(a).end()

using namespace std;

int n,m;
struct Node{
    int x,y,t;
};
vector<vector<int>> gg(501,vector<int> (501));
void solve(){
   int k , q;
   cin >> n >> m >> k >> q;
   vector<Node> a(q + 1);
   for(int i = 1;i <= q;i ++)
       cin >> a[i].x >> a[i].y >> a[i].t;

   sort(a.begin() + 1,a.end(),[](Node a, Node b){return a.t < b.t;});
   //这里如果你是从1开始输入的话,排序一定要从1开始排,因为它的t是可以等于0的

   auto check = [&](){
        for(int i = k;i <= n;i ++)
            for(int j = k; j <= m;j ++)
                if(gg[i][j] - gg[i - k][j] - gg[i][j - k] + gg[i - k][j - k] == k * k)
                    return true;
        return false;
   };

   int l = 1, r = q;
   while(l <= r){
       int mid = (l + r) >> 1;

       vector<vector<int>> g(n + 1, vector<int> (m + 1, 0));
       for(int i = 1;i <= mid;i ++)
           g[a[i].x][a[i].y] = 1;

       for(int i = 1;i <= n;i ++)
           for(int j = 1; j <= m;j ++)
               gg[i][j] = gg[i - 1][j] + gg[i][j - 1] - gg[i - 1][j - 1] + g[i][j];

       if(check())
           r = mid - 1;
       else
           l = mid + 1;
   }

   cout << (l > q ? -1 : a[l].t) << endl;

}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int Ke_scholar = 1;
//    cin >> Ke_scholar;
    while(Ke_scholar--)
        solve();
    return 0;
}
/*
 */