A. Marketing Scheme
题目大意:
有顾客想购买x（ l < = x < = r ）包猫粮，你可以选择a包猫粮并且将其打包，顾客会首先买打包好的，而后剩余的x mod a包猫粮将会一包一包买，除非x mod a ≥ a / 2
你需要使得所有的顾客买的猫粮都高于想买的，即为( l < = x < = r ）上所有的顾客都满足x mod a ≥ a / 2
思路:
很明显重要的条件是满足x mod a ≥ a / 2，即为使得等式左边大，右边小
x最大即为r，所有可以假设a=r+1，这样既可满足上述条件，再判断l是否满足即可
AC Code:
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int l, r, a;
void solve(){
cin>>l>>r;
a=r+1;
if(l%a >= (a+1)/2) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return ;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
B. Reverse Binary Strings
题目大意:
给你一个01字符串，你每次可以选择一个连续的子串进行左右翻转
求将其翻转成0，1交替出现的字符串的最小操作次数
思路:
显然每次翻转只能改变子串的两端的字符，所以每次翻转最多改变一个连续两个的1和一个连续的两个的0
即为每次操作可以使得连续的0和1的部分的连续长度减一
所以最小的操作次数即为连续的两个0和1的数量的最大值
AC Code:
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n;
string s;
void solve(){
cin>>n>>s;
int ans1=0, ans0=0;
for(int i=0; i<s.length()-1; i++){
if(s[i]=='1' && s[i+1]=='1') ans1++;
if(s[i]=='0' && s[i+1]=='0') ans0++;
}
cout<<mymax(ans1,ans0)<<endl;
return ;
}
signed main(){
int T;
cin>>T;
while(T--) solve();
return 0;
}
C. Chef Monocarp（dp）
题目大意:
厨师刚刚把菜放进烤箱。他知道第i道菜的最佳烹饪时间是ti 分钟。在任何正整数分钟，厨师最多只能从烤箱中拿出一个盘子。如果第i盘在某一分钟被端出，那么它令人不快的值就是i 和ti之间的绝对差值。菜一出烤箱就放不进去了。厨师应该把所有的盘子从烤箱中拿出来。求厨师能获得的最小总不愉快值是多少
思路:
dp[i][j]表示在第i道菜在第j分钟被拿出的最小总不愉快值
注意点，n道菜最多2n时间被全部拿出
AC Code:
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=209;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, a[N], dp[N][N*2];
void solve(){
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
sort(a+1, a+1+n);
memset(dp, INF, sizeof(dp));
for(int i=0; i<=n*2; i++) dp[0][i]=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n*2; j++)
dp[i][j]=min(dp[i][j-1], dp[i-1][j-1]+abs(a[i]-j));
cout<<dp[n][n*2]<<endl;
return ;
}
signed main(){
int T;
cin>>T;
while(T--) solve();
return 0;
}
D. Minimal Height Tree
题目大意:
已知一个BFS的遍历顺序，每个结点的子节点是按照升序从左到右排列的
求树的最少的层数
思路:
将每个升序的子序列接到树的目前的根结点，并且该子序列的长度即为下次可以接的子树的个数
AC Code:
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int T, n, a[N];
int ans, now, cnt, sum;
void solve(){
cin>>n;
ans=sum=1;
cnt=now=0;
cin>>a[1];
for(int i=2; i<=n; i++){
cin>>a[i];
if(a[i]>a[i-1]) now++;
else{
cnt++;
if(cnt==sum){
ans++;
cnt=0;
sum=now;
}
}
}
cout<<ans<<endl;
return ;
}
signed main(){
int T;
cin>>T;
while(T--) solve();
return 0;
}
Comments NOTHING