Codeforces Round #335 (Div. 2) （A-E）

A - Magic Spheres

把多余的都拿出来看能不能生成需要的那么多即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int main() {
  ios::sync_with_stdio(false);
  int a,b,c,x,y,z;
  cin>>a>>b>>c>>x>>y>>z;
  int dis=0,d=0;
  if(a>x)dis+=(a-x)/2;
  else d+=(x-a);
  if(b>y)dis+=(b-y)/2;
  else d+=y-b;
  if(c>z)dis+=(c-z)/2;
  else d+=z-c;
 
  if(dis>=d)cout<<"Yes\n";
  else cout<<"No\n";
  return 0;
}

B - Testing Robots

给你一个机器人移动序列，问你执行完前i个命令后就爆炸的炸弹安放方案有几种。
爆炸的条件：执行完所有命令/遇到炸弹。
显然如果移动经过的前i个格子有重复的就显然不行，否则是1。最后的时候要注意可以放在别的地方，因为走完也会爆炸。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
char a[N];
int main() {
  ios::sync_with_stdio(false);
  int x,y,s,t;
  cin>>x>>y>>s>>t>>a+1;
  --s;--t;
  --x;--y;
  vector<vector<int>>vis(x+1,vector<int>(y+1,0));
  int n=strlen(a+1);
  cout<<1<<' ';
  vis[s][t]=1;
  int cnt=1;
  for(int i=1;i<=n;i++){
    if(a[i]=='U'){
      s--;
      s=max(s,0);
    }else if(a[i]=='D'){
      s++;
      s=min(s,x);
    }else if(a[i]=='R'){
      t++;
      t=min(t,y);
    }else{
      t--;
      t=max(t,0);
    }
    if(vis[s][t]){
      if(i!=n)cout<<'0'<<' ';
      else{
        cout<<(x+1)*(y+1)-cnt<<'\n';
      }
    }
    else{
      vis[s][t]=1;
      ++cnt;
      if(i!=n)cout<<1<<' ';
      else{
        cout<<(x+1)*(y+1)-cnt+1<<'\n';
      }
    }
  }
  return 0;
}

C - Sorting Railway Cars

大意：给你一个序列，你每次可以把一个数放在头或者尾，问你使之递增的最小操作数。
思路：dp找到一个连续最长自序列即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int main() {
  ios::sync_with_stdio(false);
  int n,ans=0;
  cin>>n;
  vector<int>a(n),f(n+1,0);
  for(int i=0;i<n;i++){
    cin>>a[i];
    f[a[i]]=max(f[a[i]-1]+1,1);
    ans=max(ans,f[a[i]]);
  }
  cout<<n-ans<<'\n';
  return 0;
}

D - Lazy Student

大意：给你一些边的权值和是否是MST的边，让你构造一个这样的图，或者输出NO
思路：我们根据克鲁斯卡尔算法的步骤，每次都是添加权值最小的不成环边。
那么我们先把边按权值排个序，然后枚举边，如果当前边权值是最小的且在MST中，那我们把他加进树里，若不在MST中，那我们就让他成环，如果成环的边已经塞满了，显然无解。简单的做法就是树是一条链，完全图剩下的边，就是可以成环的边了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
struct uzi{
  int a,b,i;
  bool operator <(const uzi &t)const{
    if(a==t.a)return b>t.b;
    return a<t.a;
  }
};
int main() {
  ios::sync_with_stdio(false);
  int n,m;
  cin>>n>>m;
  vector<uzi>a(m);
  for(int i=0;i<m;i++){
    cin>>a[i].a>>a[i].b;
    a[i].i=i;
  }
  sort(a.begin(),a.end());
  vector<int>res;
  vector<pair<int,int>>ans(m);
  int l=1,r=2;
  int L=1,R=3;
  if(!a[0].b)return cout<<-1,0;
  ans[a[0].i]=make_pair(l,r);
  for(int i=1;i<m;i++){
    if(a[i].b){
      ans[a[i].i]=make_pair(++l,++r);
    }else{
      if(R>r)return cout<<-1,0;
      ans[a[i].i]=make_pair(L++,R);
      if(R-L<=1){
        R++;
        L=1;
      }
    }
  }
  for(int i=0;i<m;i++)cout<<ans[i].fi<<' '<<ans[i].se<<'\n';
  return 0;
}

E - Freelancer’s Dreams

大意：让你使用最少的天数d使得以下不等式成立
${\begin{matrix} <mstyle displaystyle="false" scriptlevel="0"> M i n i m i s e <mtext> </mtext> \sum_{i = 1}^{n} c_{i} = d </mstyle> \\ <mstyle displaystyle="false" scriptlevel="0"> \sum_{i = 1}^{n} c_{i} a_{i} \geq p </mstyle> \\ <mstyle displaystyle="false" scriptlevel="0"> \sum_{i = 1}^{n} c_{i} b_{i} \geq q </mstyle> \end{matrix}$

这个问题正着不好做，我们找他的对偶问题：

即：
${\begin{matrix} <mstyle displaystyle="false" scriptlevel="0"> M a x i m i s e <mtext> </mtext> p y_{1} + q y_{2} </mstyle> \\ <mstyle displaystyle="false" scriptlevel="0"> a_{i} y_{1} + b_{i} y_{2} \leq 1 <mtext> </mtext> i \in [1, n] </mstyle> \end{matrix}$
那么对每一个 $y_{1}$ 来说都会有一个最大 $y_{2}$ 对应，那么三分 $y_{1}$ 即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int main() {
  ios::sync_with_stdio(false);
  int n, p, q;
  cout << fixed << setprecision(10);
  cin >> n >> p >> q;
  vector<int> a(n), b(n);
  int l = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
    l = max(l, a[i]);
  }
  auto get = [&](double x) {
    double f = 1e18;
    for (int i = 0; i < n; i++) {
      f = min(f, (1 - x * a[i]) / b[i]);
    }
    return x * p + f * q;
  };
  double x = 0, y = 1.0 / l;
  for (int i = 0; i < 50; i++) {
    double dx = x + (y - x) / 3, dy = y - (y - x) / 3;
    if (get(dx) > get(dy)) {
      y = dy;
    } else
      x = dx;
  }
  cout << get((x + y) / 2) << '\n';
  return 0;
}