牛客算法入门竞赛笔记1

表达式计算4 (nowcoder.com)

题意就跟标题一样，计算表达式，当时正好数据结构也布置了一个类似的作业，思路是每一次都找到运算级最低的那个符号，将表达式分为两个部分，分别计算。

 #include
 using namespace std;
 string a;
 //string转int
 int num(int l,int r){
  int ans=0;
  for(int i=l;i<=r;i++){
  ans*=10;
  ans+=a[i]-'0';
  }
  return ans;
 }
 //计算l到r的计算式
 int calc(int l,int r){
  int pos1=-1,pos2=-1,pos3=-1;
  int cnt=0;
  //找到不在括号里的优先级最低的运算符的位置
  for(int i=l;i<=r;i++){
  if(a[i]=='('){
  cnt++;
  }
  if(a[i]==')'){
  cnt--;
  }
  if(cnt==0){
  if(a[i]=='+'||a[i]=='-'){
  pos1=i;
  }
  if(a[i]=='*'||a[i]=='/'){
  pos2=i;
  }
  if(a[i]=='^'){
  pos3=i;
  }
  }
  }
  //如果没找到运算符
  if(pos1==-1&&pos2==-1&&pos3==-1){
  //要么是被括号整体括起来了
  //注：后面两个else if是为了排除多余的括号
  if(cnt==0&&a[l]=='('){
  return calc(l+1,r-1);
  }else if(cnt<0&&a[l]=='('){
  return calc(l,r-1);
  }else if(cnt>0&&a[r]==')'){
  return calc(l+1,r);
  }
  //要么是就是一个数字
  return num(l,r);
  }
  //+ -优先级最低，先判断
  if(pos1!=-1){
  if(a[pos1]=='+'){
  return calc(l,pos1-1)+calc(pos1+1,r);
  }else{
  return calc(l,pos1-1)-calc(pos1+1,r);
  }
  }
  //然后是* /
  if(pos2!=-1){
  if(a[pos2]=='*'){
  return calc(l,pos2-1)*calc(pos2+1,r);
  }else{
  return calc(l,pos2-1)/calc(pos2+1,r);
  }
  }
  //最后是乘方
  if(pos3!=-1){
  return pow(calc(l,pos3-1),calc(pos3+1,r));
  }
 }
 ​
 int main(){
  cin>>a;
  cout<  return 0;
 }

1027-kotori和糖果_2021秋季算法入门班第二章习题：递归、分治 (nowcoder.com)

题意：共n堆糖果，一堆一个，合并两堆数量不一样的花费1，求最少总花费

这题本来是个很简单的记忆化搜索，但是我没想清楚应该返回什么，我本来想着返回两端的长度，但是后来转念一想，不对啊，有了n两端长度不是都有了吗，所以应该返回的是形成这两端需要的操作数。

#include
using namespace std;
typedef long long ll;
map mp;
ll getans(ll n){
if(n==0) return 0;
if(mp.count(n)) return mp[n];
if(n&1){
mp[n]=2*getans(n/2);
}else{
mp[n]=getans(n/2)+getans(n/2-1)+1;
}
return mp[n];
}
int main(){
ll t;
scanf("%lld",&t);
while(t--){
ll n;
scanf("%lld",&n);
if(n==0)puts("0");
else printf("%lld\n",getans(n-1));
}
}

艹，我记得我写完这一部分的了，但是好像关电脑前忘了保存，然后就没了，心态爆炸，再写一遍，呜呜呜

小咪买东西 (nowcoder.com)

01分数规划经典题目，题意：给n个物品，每一个物品都有一个价值和花费，求买k个的最大总价值（val）和总花费之比(cos)

思路:我们假设这个最大比值是x，那么比x小的比值一定也存在这样的方案，比x大的比值一定不存在这样的方案，那么我们就可以考虑二分，对于一个比值num来说，如果可行，一定存在一个方案使得val/cos>=num-->val-numcos>=0;因此我们在判断的时候把所有val-numcost最大的k个值算在内，如果这样都不行那就是真的不行。

#include
using namespace std;
#define ll long long
struct node{
ll c,v,mar;
};
ll n,m;
node x[10001];
bool com(node a,node b){
return a.mar>b.mar;
}
bool fun(ll a){
ll num=0;
for(ll i=0;i x[i].mar=x[i].v-a*x[i].c;
}
sort(x,x+n,com);
ll sum=0;
for(ll i=0;i sum+=x[i].mar;
}
if(sum<0){
return false;
}else{
return true;
}
}
int main(){
ll t;
cin>>t;
while(t--){
cin>>n>>m;
for(ll i=0;i cin>>x[i].c>>x[i].v;
}
ll l=0,r=1e8+1;
ll mid=0;
while(l mid=(l+r+1)/2;
if(fun(mid)){
l=mid;
}else{
r=mid-1;
}
}
cout< }
return 0;
}

gpa (nowcoder.com)

和上一题差不多，就是把最大值公式变了一下，我们一样做

#include
using namespace std;
#define INF 0x3f3f3f3f
#define ll double
struct node{
double a,b,tem;
};
node x[100001];
int n,m;
bool com(node a,node b){
return a.tem}
bool fun(ll a){
for(int i=0;i x[i].tem=x[i].a*(x[i].b-a);
}
sort(x,x+n,com);
for(int i=0;i if(x[i].tem<0){
x[i].tem=-INF;
}
}
ll sum=0;
for(int i=0;i if(x[i].tem==-INF){
continue;
}
sum+=x[i].tem;
}
if(sum<0){
return false;
}else{
return true;
}
}
int main(){
cin>>n>>m;
for(int i=0;i cin>>x[i].a;
}
for(int i=0;i cin>>x[i].b;
}
double l=0,r=1e11+1;
while(r-l>1e-6){//这里答案是小数，所以我们用控制精度的方法
double mid=(l+r)/2;
if(fun(mid)){
l=mid;
}else{
r=mid;
}
}
printf("%.6lf\n",l);
return 0;
}

[NOIP2016]蚯蚓 (nowcoder.com)

题意：给你n个数，每次会将一个数分割成比例为定值的两个数，求m次分割怎么让每个数尽可能小，每个数还会随时间增长一定值。

这题本来觉得没啥难的，优先队列嘛，谁不会啊（），但是看了眼数据范围，完蛋，会t，没办法，只能听雨巨讲了。

思路真的很巧妙，假设我们将最初的序列排序，拆分之后将两段分别放进两个队列里面，因为我们每次拆分的一定都比上一次小（或者一样）因此拆分后的两段一定也比先前的两段小，所以我们后放入队列的一定比先放入的小，这样就保证了有序，每次选择最大的时候只要去找三个队列的头即可。tql，未曾设想的道路。

但是这个输出要求就很恶心，我好不容易写完，你非要在输出上折磨我是什么意思

#include
#include
#include
using namespace std;
#define ll long long
int main() {
queueq[3];
int x[100001];
ll n, m, Q, u, v, t;
cin >> n >> m >> Q >> u >> v >> t;
double p = (double)u / v;
for (int i = 0; i cin >> x[i];
}
sort(x, x + n, greater());
for (int i = 0; i q[0].push(x[i]);
}
int now = 0;
while (now int mn = -0x3f3f3f3f, maxindex=-1;
for (int i = 0; i <3; i++) {
if (!q[i].empty() && q[i].front() > mn) {
mn = q[i].front();
maxindex = i;
}
}
if (maxindex==-1) {
break;
}
mn += now * Q;
q[maxindex].pop();
q[1].push((int)(u * mn/v) - now * Q-Q);
q[2].push(mn - (int)(u * mn/v) - now * Q-Q);

if ((now+1) % t == 0) {
cout < }
now++;
}
cout < now=1;
while (!q[0].empty() || !q[1].empty() || !q[2].empty()) {
int mn = -0x3f3f3f3f, maxindex=-1;
for (int i = 0; i <3; i++) {
if (!q[i].empty() && q[i].front() > mn) {
mn = q[i].front();
maxindex = i;
}
}
if (maxindex==-1) {
break;
}
if(now%t==0){
cout < }
now++;
q[maxindex].pop();
}
return 0;
}

Sliding Window (nowcoder.com)

动态维护一个在i-k~i之间可能成为答案的队列。

以最大值为例，如果后一个比前一个大，那么前一个就失去了成为答案的机会，就可以出队了，反之就不出队，但是当这个值的位置比区间的左端点还小的时候也要出队，本来我想用队列存数据的，但是雨巨点醒了我，存数据的话还要直到下标，所以我们直接把下标存起来，到原数组里找对应的数据即可。

第一次用对拍，有点爽，第一次交的时候wa在了长度为1的时候。

#include
using namespace std;
int x[1000011];
int main(){
// freopen("a.in","r",stdin);
// freopen("std.out","w",stdout);
int n,k;
cin>>n>>k;
for(int i=0;i cin>>x[i];
}
if(n==1){
cout< return 0;
}
dequeq;
// q.push_back(0);第一次wa在这.以后别tm提前插入行不行，对拍的时候是很爽，但是写起来很麻烦
for(int i=0;i while(!q.empty()&&x[q.back()]>x[i]){
q.pop_back();
}
q.push_back(i);
if(q.front()<=i-k){
q.pop_front();
}
if(i+1>=k){
cout< }
}
cout< q.clear();
for(int i=0;i while(!q.empty()&&x[q.back()] q.pop_back();
}
q.push_back(i);
if(q.front()<=i-k){
q.pop_front();
}
if(i+1>=k){
cout< }
}
return 0;
}

Largest Rectangle in a Histogram (nowcoder.com)

单调栈的板子题，所谓单调栈就是我们维护一个单调的栈，每当有新数据进来时，如果它破坏了原有的单调性，我们就一直出栈直到单调为止。

题意：给你一串高度不等高的等宽柱子，求能够在里面划出的最大的矩形的面积。

思路：我们存下每个柱子往左能够延伸的最大长度，如果新加的柱子比之前的高，那它的最大宽度就是1，如果新加的柱子比之前的矮，那我们在出栈的过程中把每一个出栈的柱子的往左延伸的最大长度相加得到的就是这个新柱子的最大长度，当然，如果一个柱子出栈了，就说明它不可能再向右延申了，这时我们用高度×它能向左延申的最大长度就是一个可能的最大面积。

#include
using namespace std;
#define ll long long
int x[100001];
int num[100001];//记录每个柱子能够向左延伸的最大长度
int main(){
int n;
while(cin>>n&&n){
for(int i=1;i<=n;i++){
cin>>x[i];
}
stackstk;
ll ans=0;
x[++n]=0;
for(int i=1;i<=n+1;i++){
ll temp=0;
while(!stk.empty()&&x[i]<=x[stk.top()]){
temp+=num[stk.top()];
ans=max(ans,temp*x[stk.top()]);
stk.pop();
}
stk.push(i);
num[stk.top()]=temp+1;
}
cout< }
return 0;
}