A - Humidifier 1
首先要知道,题目是按时间线的顺序给出了每一次加水操作的
加湿器每分钟会消耗1升水
对于这种要记录时间线的题目,通常我们应该自己记录一个 T T T
一开始时间 T = 0 ,答案剩余水 a n s = 0 T=0,答案剩余水ans=0 T=0,答案剩余水ans=0
每一次加水的时候,时间是 T [ i ] ,加水 V [ i ] T[i],加水V[i] T[i],加水V[i]
那么先考虑在此之前消耗了多少水,也就是在此之前过了多少时间 T [ i ] − T T[i]-T T[i]−T
那么你剩余的水就应该减去 T [ i ] − T T[i]-T T[i]−T ,但是注意,不能减为负数,然后把这一次操作的水加进来
#include<bits/stdc++.h>
using namespace std;int main() {int n;cin>>n;int ans=0;int t=0;//表示上一个时间线 for(int i=1;i<=n;i++){int ti,v;cin>>ti>>v;//ans=max(ans-(ti-t),0)+v;t=ti;} cout<<ans;return 0;
}
B - Humidifier 2
曼哈顿距离已经出现很多次了,要知道是什么概念。这个题我们直接枚举在哪两个位置放加湿器,然后再去检查其他所有的可以的地方,能不能加湿就行了
#include<bits/stdc++.h>
using namespace std;
char s[20][20];
int main() {int n,m,d;cin>>n>>m>>d;for(int i=1;i<=n;i++){cin>>s[i]+1;}int ans=0;//最终答案 for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int p=1;p<=n;p++){for(int q=1;q<=m;q++){//枚举在(i,j) (p,q)放加湿器if(s[i][j]=='.'&&s[p][q]=='.'){if(i==p&&q==j)continue;//重复int cnt=2;//当前能被加湿的点数量 for(int x=1;x<=n;x++){for(int y=1;y<=m;y++){if(x==i&&y==j||x==p&&y==q||s[x][y]=='#')continue;//跟加湿器重合 if(abs(x-i)+abs(y-j)<=d||abs(x-p)+abs(y-q)<=d){cnt++;}}}ans=max(ans,cnt); } }}}}cout<<ans;return 0;
}
C D题不讲 很简单
E - Kaiten Sushi
题目要读懂,意思就是 N N N个人 排成一排,等待吃寿司,每个人有个数值 A [ i ] A[i] A[i] ,接下来依次流水线过来的 M M M个寿司,寿司有个值 B [ i ] B[i] B[i] ,如果寿司 B B B的值 > = >= >= 人的 A A A值 那么这个人就是要吃寿司的。题目问,请我们确定每个寿司被谁吃掉,或者不被吃。
我们可以记录一个数据, p [ i ] p[i] p[i]表示前 i i i个人当中,最小的A值
那么对于每个寿司来说,我们看这个图
很明显,当从左往右的人越多时,前缀当中的最小A值曲线就会降低。
而我们每个寿司需要满足,它的B值>= 某个人的A值 才能被吃掉
根据这个曲线,我们很明显要找到第一个能吃这个寿司的人,也就是第一个 A值 小于等于B值的人的位置。
所以我们可以先统计 P [ i ] P[i] P[i] 记录一个前缀最小值数组, P [ i ] 表示 A [ 1 到 i ] 当中的最小值 P[i]表示A[1到i]当中的最小值 P[i]表示A[1到i]当中的最小值
推导就是 P [ i ] = m i n ( P [ i − 1 ] , A [ i ] ) P[i]=min(P[i-1],A[i]) P[i]=min(P[i−1],A[i])
然后枚举每个寿司,去 P P P数组当中二分查找即可,查找第一个<= 这个寿司的位置
找不到就是-1
#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n,m,a[N],b[N],p[N];
int main(){cin>>n>>m;p[0]=1e9;for(int i=1;i<=n;i++){cin>>a[i];p[i]=min(p[i-1],a[i]);}for(int i=1;i<=m;i++)cin>>b[i];for(int i=1;i<=m;i++){//寻找第一个小于等于a[i]的b[j] int l=1,r=n;while(l<r){int mid=(l+r)/2;if(p[mid]<=b[i]){r=mid;}else l=mid+1;}if(p[r]<=b[i])cout<<r<<endl;else cout<<-1<<endl;}return 0;
} //60 60 60 45 45 45 37 37 37 22//39
F - 11/22 String
简单的字符串模拟题
按要求写就行了
G - 1122 String
跟F差不多的题,
#include<bits/stdc++.h>
using namespace std;
char s[110];
int vis[30];
int main(){cin>>s+1;int n=strlen(s+1);for(int i=1;i<=n;i++){vis[s[i]-'a'+1]++;}if(n%2==0){bool ok=true;for(int i=1;i<=n/2;i++){if(s[2*i-1]!=s[2*i]){ok=false;break;}} for(int i=1;i<=26;i++){if(vis[i]==0||vis[i]==2)continue;else {ok=false;break;}}if(ok)cout<<"Yes";else cout<<"No";}else{//奇数长度 cout<<"No";}return 0;
}
H题 11/22 Substring
直接枚举每个/的位置,然后倒着算该符号左边有多少个连续的1,右边有多少个连续的2 ,取最小值即可。放心不会超时的
#include<bits/stdc++.h>
using namespace std;
char s[200010];
int main(){int n;cin>>n;cin>>s+1;int ans=0;for(int i=1;i<=n;i++){if(s[i]=='/'){int L=0;int R=0;for(int j=i-1;j>=1;j--){if(s[j]=='1')L++;else break;} for(int j=i+1;j<=n;j++){if(s[j]=='2')R++;else break;} ans=max(ans,min(L,R)*2+1); }}cout<<ans;return 0;
}