题意：给出一串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';
题意：有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;
}
题意：给出一段数组，求三个分界点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;
}
题意：有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;
}