A-水鹽平衡_牛客小白月賽86 (nowcoder.com)

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int a,b,c,d;
void solve() {cin>>a>>b>>c>>d;if((double)a/b>(double)c/d) cout<<'S'<<endl;else cout<<'Y'<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

B-水平考試_牛客小白月賽86 (nowcoder.com)

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
string s,t;
void solve() {cin>>s>>t;if(t.size()>1){//多選題map<char,int>mp;for(int i=0;i<(int)t.size();i++){mp[t[i]]++;}for(int i=0;i<(int)s.size();i++){if(!mp[s[i]]){//選錯不得分cout<<0<<endl;return;}}cout<<10<<endl;}else{//單選題if(s==t) cout<<10<<endl;else cout<<0<<endl;}
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

C-數組段數_牛客小白月賽86 (nowcoder.com)

長度為n的數組a
m次詢問，問區間[l,r]有多少段
段：分成連續的k段，每段元素種類只有一種，k要求最小

前綴和，預處理有幾對相鄰的后一個不同于前一個

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10;
int a[N];
int sum[N];
int n,m;
void solve() {cin>>n>>m;for(int i=1;i<=n;i++) sum[i]=0;for(int i=1;i<=n;i++) cin>>a[i];sum[1]=1;for(int i=2;i<=n;i++){if(a[i]!=a[i-1]) sum[i]=sum[i-1]+1;else sum[i]=sum[i-1];}
//	for(int i=1;i<=n;i++) cout<<sum[i]<<' ';
//	cout<<endl;while(m--){int l,r;cin>>l>>r;cout<<sum[r]-sum[l]+1<<endl;}
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

D-剪紙游戲_牛客小白月賽86 (nowcoder.com)

n*m的字符矩陣（點和星號）
星號表示保留的部分
表示被剪去的部分
問減去的圖案中有幾個矩形

即連通塊有幾個是矩形
dfs一遍，把一個連通塊的每個點的下標記錄，行最小是多少，行最大是多少，列最小是多少 ，列最大是多少，然后檢查整個矩形里是不是都是點
或者看個數是否等于大矩形的個數

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1010;
char s[N][N];
int n,m;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool st[N][N];
int minline,maxline,mincol,maxcol;
int cnt;
void dfs(int x,int y){st[x][y]=true;cnt++;minline=min(minline,x);maxline=max(maxline,x);mincol=min(mincol,y);maxcol=max(maxcol,y);for(int i=0;i<4;i++){int tx=x+dx[i],ty=y+dy[i];if(tx<1||tx>n||ty<1||ty>m||st[tx][ty]||s[tx][ty]=='*') continue;dfs(tx,ty);}
}
void solve() {cin>>n>>m;int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>s[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){minline=2e9,maxline=0,mincol=2e9,maxcol=0;cnt=0;if(!st[i][j]&&s[i][j]=='.'){dfs(i,j);
//				cout<<cnt<<endl;
//				cout<<minline<<' '<<maxline<<' '<<mincol<<' '<<maxcol<<endl;
//				cout<<(maxline-minline+1)*(maxcol-mincol+1)<<endl;
//				cout<<"--------"<<endl;if(cnt==(maxline-minline+1)*(maxcol-mincol+1)) ans++;}}}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

E-可口蛋糕_牛客小白月賽86 (nowcoder.com)

n個蛋糕
wi表示第i個蛋糕的飽腹度，di表示第i個蛋糕的可口值

吃掉一段連續的蛋糕，使得飽腹度之和大于等于W，然后問最大可口值之和是多少

必須連續一段區間，然后由于飽腹度均為正，要使得飽腹度之和大于等于W，區間長度只能長不能短
對于每個點，作為右端點，二分它的左端點至少到哪里，記為l，然后在此基礎上，求dp[l-1]，表示以[l-1]為右端點，區間和最大是多少,如果dp[l-1]大于0,那么加上

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e6+10;
int w[N],d[N];
int dp[N];
int n,W;
int sum[N];
int sum1[N];
void solve() {cin>>n>>W;for(int i=1;i<=n;i++) cin>>w[i];for(int i=1;i<=n;i++) cin>>d[i];for(int i=1;i<=n;i++) sum[i]=sum[i-1]+w[i];for(int i=1;i<=n;i++) sum1[i]=sum1[i-1]+d[i];dp[0]=0;for(int i=1;i<=n;i++) dp[i]=max(d[i],dp[i-1]+d[i]);
//	for(int i=1;i<=n;i++) cout<<sum[i]<<' ';
//	cout<<endl;
//	for(int i=1;i<=n;i++) cout<<sum1[i]<<' ';
//	cout<<endl;
//	for(int i=1;i<=n;i++) cout<<dp[i]<<' ';
//	cout<<endl;
//	cout<<"-----------"<<endl;int ans=-1e18;for(int i=1;i<=n;i++){//枚舉區間右端點int l=1,r=i;//二分區間左端點while(l<r){int mid=(l+r+1)/2;if(sum[i]-sum[mid-1]>=W) l=mid;else r=mid-1;}
//		cout<<l<<' '<<i<<' '<<sum[i]-sum[l-1]<<endl;if(l>=1&&sum[i]-sum[l-1]>=W){ans=max(ans,sum1[i]-sum1[l-1]+max(0ll,dp[l-1]));}}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}