题解 | #Amino Acids#

Amino Acids

https://ac.nowcoder.com/acm/contest/32708/A

2022ICPC昆明补题（第46届ICPC亚洲区域赛（昆明））

A.Amino Acids

题解：挺好玩的大模拟，化学知识得到了提升，属于那种看懂题就能做的类型，平时写得太少导致赛时出锅。

#include<bits/stdc++.h>
using namespace std;

const int N = 105;
map<string,int> mmap;
int num[] = {0,89,132,133,121,146,147,75,149,105,119};
string s[N];
int _min = 10000000;
vector<string> vec[N];
string t1 = "  H H O    ";
string t2 = "  | | ||   ";
string t3 = "H-N-C-C-O-H";
string t4 = "    |      ";
string t5 = "  H-C-H    ";
string t6 = "  O=C-O-H  ";
string t7 = "    H      ";
string t8 = "      |    ";
string t9 = "      H    ";
string t10= "    S      ";
string t11= "  H-C-S-H  ";
string t12= "           ";
string t13= "  H-C-O-H  ";
string t14= "  O=C-N-H  ";
int n,sz;
void f(){
  for(int i=1;i<=10;i++){
    vec[i].push_back(t1);vec[i].push_back(t2);vec[i].push_back(t3);vec[i].push_back(t4);
  }
  vec[1].push_back(t5);vec[3].push_back(t5);
  vec[2].push_back(t5);vec[8].push_back(t5);
  vec[5].push_back(t5);vec[6].push_back(t5);

  vec[1].push_back(t4);vec[1].push_back(t7);
  vec[3].push_back(t4);vec[3].push_back(t6);
  vec[2].push_back(t4);vec[2].push_back(t14);vec[2].push_back(t8);vec[2].push_back(t9);
  vec[4].push_back(t11);vec[4].push_back(t4);vec[4].push_back(t7);
  vec[7].push_back(t7);
  vec[9].push_back(t13);vec[9].push_back(t4);vec[9].push_back(t7);
  vec[8].push_back(t4);vec[8].push_back(t5);vec[8].push_back(t4);vec[8].push_back(t10);
  vec[8].push_back(t4);vec[8].push_back(t5);vec[8].push_back(t4);vec[8].push_back(t7);
  vec[10].push_back(t13);vec[10].push_back(t4);vec[10].push_back(t5);vec[10].push_back(t4);
  vec[10].push_back(t7);
  vec[5].push_back(t4);vec[5].push_back(t5);vec[5].push_back(t4);
  vec[5].push_back(t14);vec[5].push_back(t8);vec[5].push_back(t9);
  vec[6].push_back(t4);vec[6].push_back(t5);
  vec[6].push_back(t4);vec[6].push_back(t6);
}
vector<int> a;
vector<int> res;
int ans = 0;
void print(int n){
  int _max = 0;
  for(int i=0;i<n;i++){
    _max = max(_max,(int)vec[res[i]].size());
  }
  for(int i=0;i<_max;i++){
    if(i==2)
      for(int j=0;j<n;j++){
        int l = 0, r = vec[res[j]][i].size()-1;
        l++;r-=3;
        if(j==0)l--;if(j==n-1)r+=3;
        if(j!=0)cout << "-";
        for(int k = l;k<=r;k++)cout << vec[res[j]][i][k];
      }
    else {
      for(int j=0;j<n;j++){
        int l = 0;int r;
        if(vec[res[j]].size() > i)r = vec[res[j]][i].size()-1;
        l+=2;r--;
        if(j==0)l-=2;
        if(j==n-1)r++;
//if(res[j]==7)cout << vec[res[j]].size() << " " << i << endl;
        if(vec[res[j]].size() <= i){
          r = 9;
          for(int k=l;k<=r;k++)cout << " ";
        }
        else for(int k=l;k<=r;k++)cout << vec[res[j]][i][k];
      }
    }
    cout << endl;
  }
  cout << endl;
}

void dfs2(int cur,int sum){
  if(sum > sz)return; 
  if(cur>=2){
    ans++;
  }
  //if(cur==n)return;
  for(int i=0;i<n;i++){
    if(cur==0)dfs2(cur+1,sum+num[a[i]]);
    else dfs2(cur+1,sum+num[a[i]]-18);
  }
  return;
}

void dfs(int cur,int sum){
  if(sum > sz)return; 
  if(cur>=2){
    print(cur);
  }
  //if(cur==n)return;
  for(int i=0;i<n;i++){
    res.push_back(a[i]);
    if(cur==0)dfs(cur+1,sum+num[a[i]]);
    else dfs(cur+1,sum+num[a[i]]-18);
    res.pop_back();
  }
  return;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  f();
//cout << vec[7].size() << endl;
  mmap["Ala"] = 1;
  mmap["Asn"] = 2;
  mmap["Asp"] = 3;
  mmap["Cys"] = 4;  
  mmap["Gln"] = 5;
  mmap["Glu"] = 6;
  mmap["Gly"] = 7;
  mmap["Met"] = 8;     
  mmap["Ser"] = 9;
  mmap["Thr"] = 10;
  cin >> n >> sz;
  for(int i=1;i<=n;i++){
    string s;cin >> s;
    a.push_back(mmap[s]);
  }
//   for(int i=0;i<n;i++){
//     for(auto it:vec[a[i]]){
//       cout << it << endl;
//     }
//     cout << endl;
//   }
  sort(a.begin(),a.end());
  dfs2(0,0);
  cout << ans << endl;
  dfs(0,0);
  return 0;
}

B.Blocks

题解：期望dp，n的规模非常小，一个小trick是处理自环的情况，通过移项移到同一边就可以处理了，在判断全部覆盖可以使用容斥定理或者离散化。离散化注意一些边界问题，而且这题数据略水。

//离散化
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(b)-1;i>=a;i--)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define VI vector<int>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 15;
ll qpow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
#define y1 awdjawif

int x1[N],y1[N],x2[N],y2[N];
ll s[1<<N],ns[1<<N],dp[1<<N];
ll inv[20];
bool st[40][40];


vector<int> xx;
vector<int> yy;

int f(int x,VI xx){
  return lower_bound(all(xx),x) - xx.begin();
}
int n;

void init(){
  sort(all(xx));
  sort(all(yy));
  xx.erase(unique(all(xx)),xx.end());
  yy.erase(unique(all(yy)),yy.end());
  int szx = xx.size();
  int szy = yy.size();
  rep(S,0,1<<n){
    ns[S] = 0;
    int cnt = 0;
    rep(i,0,szx)rep(j,0,szy)st[i][j] = 0;
    rep(j,0,n){
      if(((1<<j)&S)){
        int X1 = f(x1[j],xx),Y1 = f(y1[j],yy);
        int X2 = f(x2[j],xx),Y2 = f(y2[j],yy);
        rep(a,X1,X2)rep(b,Y1,Y2){
          if(!st[a][b]){cnt++;st[a][b] = 1;}
        }
      }
    }
    if(cnt == (szx-1) * (szy-1))ns[S] = 1;
  }
}

int main(){
//cout << qpow(3, 5);
    for(int i=1;i<=11;i++)inv[i] = qpow(i,mod-2);
    int T;scanf("%d",&T);
    while(T--){
        xx.clear();
        yy.clear();
        scanf("%d",&n);
        int W,H;
        scanf("%d%d",&W,&H);
        rep(i,0,n){
            scanf("%d%d%d%d",x1+i,y1+i,x2+i,y2+i);
            xx.pb(x1[i]);xx.pb(x2[i]);
            yy.pb(y1[i]);yy.pb(y2[i]);
        }
        xx.pb(0);xx.pb(W);
        yy.pb(0);yy.pb(H);
        init();
        //ll ss = 1ll * W * H;
        if(!ns[(1<<n)-1]){
            cout << -1 << endl;continue;
        }
 //for(int i=100;i<150;i++)cout << ns[i] << " ";
// cout << endl;
// cout << ns[1] << endl;
// cout << ns[4] << endl;
// cout << ns[15+128] << endl;
        per(i,0,1<<n){
            if(ns[i]){
                dp[i] = 0;
//cout << i << endl;
            }
            else {
                //ll sz = n;
                int c = 0;
                long long t = 1;
                rep(j,0,n){
                  if(((1<<j)&i)==0){
                      t = (t + inv[n] * dp[i|(1<<j)] % mod)%mod; 
                      c++;
                  }
                }
                dp[i] = (ll)t * n % mod * inv[c] % mod; 
	
            }
        }
        cout << dp[0] << endl;
        //cout << dp[(1<<n)-2] << endl;
    }
}

//容斥原理
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(b)-1;i>=a;i--)
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 15;
ll qpow(ll a,ll b){ll t = 1;assert(b>=0);for(;b;b>>=1){if(b&1)t=(ll)t*a%mod;a=(ll)a*a%mod;}return t;}
#define y1 awdjawif
int x1[N],y1[N],x2[N],y2[N];
ll s[1<<N],ns[1<<N],dp[1<<N];
ll inv[20];

signed main(){
//cout << qpow(3, 5);
    for(int i=1;i<=10;i++)inv[i] = qpow(i,mod-2);
    int T;scanf("%lld",&T);
    while(T--){
        int n;scanf("%lld",&n);
        int W,H;
        scanf("%lld%lld",&W,&H);
        rep(i,0,n){
            scanf("%lld%lld%lld%lld",x1+i,y1+i,x2+i,y2+i);
        }
        rep(i,1,1<<n){
            int X1 = 0,Y1 = 0,X2 = W,Y2 = H;
            rep(j,0,n){
                if(i&(1<<j)){
                    X1 = max(X1,x1[j]);
                    X2 = min(X2,x2[j]);
                    Y1 = max(Y1,y1[j]);
                    Y2 = min(Y2,y2[j]);
                }
            }
            s[i] = 1ll * max(0ll,X2-X1) * max(0ll,Y2-Y1);
//cout << s[i] << endl;
        }
        rep(i,1,1<<n){
            ll v = 0;
            for(int j=i;j;j=(j-1)&i){
              v += s[j] * (__builtin_parity(j)?1:-1);
            }
            ns[i] = v;
        }
//cout << ns[(1<<n)-1] << endl;
        if(ns[(1<<n)-1] < 1ll * W * H){
            cout << -1 << endl;continue;
        }
// cout << ns[1] << endl;
// cout << ns[4] << endl;
        per(i,0,1<<n){
            if(ns[i]==1ll * W*H){
                dp[i] = 0;
//cout << i << endl;
            }
            else {
                //ll sz = n;
                long long t = 1;
                int c = 0;
                rep(j,0,n){
                    if(((1<<j)&i)==0){
                        t = (t + inv[n] * dp[i|(1<<j)] % mod)%mod; 
                        c++;
                    }
                }
                dp[i] = (ll)t * n % mod * inv[c] % mod; 
            }
        }
        cout << dp[0] << endl;
        //cout << dp[(1<<n)-2] << endl;
    }
}

C. Cup of Water

题意：还是数学期望题，这套题有三个期望题（合理怀疑出题人在准备概率论考试），有点太多了。题意是给你一个容量为xx的容器，每一轮等概率取0到x0到x的水。问装满单位为1的水杯需要的期望轮数。

题解：正解没咋看懂，这里是看dls代码得来的一个挺显然的思路。

​ 我们先进行一个小变换，可以转换成以下情况，我们每次等概率取0到1的水，装满t=1xt = \frac{1}{x}的水杯。 我们定义f(x)f(x)的含义是装满容量为x的水杯所需要的期望轮数，则问题变为求f(t)f(t)。

​ 根据概率论的基础知识，可以得到f(t)=∫01f(t−x)dxf(t) = \int_{0}^{1}f(t-x)dx,正解就是吧这个求出来，但这个式子求出后不是个初等形式，所以使用了大量的技巧，在高数基础不够的情况下，我们该怎么办呢？对，没错，就是暴力，虽然他是个连续的式子，但是我们可以想起微积分的切片法，这样就可以把连续的式子分割成离散的，因为这道题对精度的要求比较低，实测把单位1分割成300000300000份就可以达到题目需要的精度要求。还有一个问题就是我们发现1x\frac{1}{x}离散后可能为0，易得f(0)=0f(0) = 0,但这个显然不对，我们根据题意可以得到，只要1/x1/x不为00，那么期望必然不为00，所以离散化得注意和11取一个maxmax。

#include <bits/stdc++.h>
using namespace std;
#define db double
const int dx=300000;
double f[dx*20+10],s[dx*20+10];
int main() {
    f[0]=0;
    s[0]=0;
    for(int i=1;i<20*dx+2;i++) {
        f[i]=1.0+(s[i-1]-s[max(i-dx,0)])/((db)dx);
        s[i]=s[i-1]+f[i];
    }
    int _;
    for (scanf("%d",&_);_;_--) {
        db x;
        scanf("%lf",&x);
        printf("%.16lf\n",f[max(int(dx/x),1)]);
    }
}

D.Divisions

题意：让你构造一个序列，使得这个序列有k种划分，使得划分分别递增和递减。

题解：0，1特判，对于k大于等于2的情况，可以发现如果序列如同111223333，则k为1+(23−1)+(22−1)+(24−1)1 + (2^{3}-1) + (2^{2} - 1) + (2^{4} -1)，那个另外的1是空集的情况，我们可以发现通过2k−12^{k-1}构造出答案。

#include<bits/stdc++.h>
using namespace std;

vector<int> res;

int main(){
    int k;
    cin >> k;
    if(k==0)cout << "5" << endl << "2 3 1 5 4" << endl;
    else if(k==1)cout << "6" << endl << "1 1 4 5 1 4"<< endl;
    else {
        k -- ;
        int ind = 1;
        while(k){
            int cnt = 0;
            for(;;cnt++){
                if((1 << (cnt + 1)) - 1> k)break;
            }
            k -= (1<<cnt)-1;
            while(cnt--)res.push_back(ind);
            ind ++;
        }
        cout << res.size() << endl;
        for(int i=0;i<res.size();i++){
            cout << res[i] << " ";
        }
        cout << endl;
    }
}

E. Easy String Problem

题意：好懒的人啊，自己看题~~~

题解：这道题正解是莫队，那么我们怎么可以想到莫队的呢？有以下几个特征点可以指引我们想到莫队，首先是数据规模1e51e5,这个1e51e5其实对应的算法是不多的，比如莫队，分块，块状链表等等，第二是区间询问是莫队的典型特征。其实根据数据规模能得到很多信息的，毕竟出题人也不傻~~~。

​ 我们由此可以得到一个初步判断，他就是莫队，基于这个去思考这道题的性质将会容易很多。 看到这不妨停下来自己想想，莫队需要哪些性质，而我们怎么挖掘与其相关的性质？

​ 不知道聪明的你想到了没有，其实很简单，观察12321，我们假设询问区间是3 3，我们使用正难则反的思路，左边的坐标有三个选择，右边同样是三个，所以可以得到3∗3=93 * 3 = 9这个答案，我们考虑如何去重，可以发现，删去2 3和3 4一样，1 3和3 5一样，发现好像与区间两旁的重复部分有关系，再比如11312，同样询问3 3，答案同样是 9−29 - 2，我们可以发现和两边重复数字的个数乘积有关系，没错一个询问区间答案就是全部取法减去两边重复数字个数的乘积。我们通过莫队可以轻松维护~~~

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ll long long

const int N = 1e5+5;
int a[N];
int len;
ll ans[N];
int n,m;

struct Query{
  int id,l,r;
}q[N];

int get(int x){
  return x/len;
}

int cntr[N];
int cntl[N];

void addr(int x,ll& quan){
  cntr[x]--;
  quan -= cntl[x];
}

void delr(int x,ll& quan){
  cntr[x]++;
  quan += cntl[x];
}

void addl(int x,ll& quan){
  cntl[x]--;
  quan -= cntr[x];
}

void dell(int x,ll& quan){
  cntl[x]++;
  quan += cntr[x];
}

int main(){
  cin >> n;
  len = max(1,(int)sqrt(n));
  for(int i=1;i<=n;i++)cin >> a[i];
  cin >> m;
  rep(i,0,m){
    int l,r;cin >> l >> r;
    q[i] = {i,l,r};
  }
  sort(q,q+m,[&](Query a,Query b){
    int i = get(a.l), j = get(b.l);
    if(i!=j)return i < j;
    return a.r < b.r;
  });
  int L = 1, R = n;
  ll quan = 0;
  rep(i,0,m){
    int l = q[i].l,r = q[i].r,id = q[i].id;
    while(R < r)addr(a[++R],quan);
    while(R > r)delr(a[R--],quan);
    while(L > l)addl(a[--L],quan);
    while(L < l)dell(a[L++],quan);
//cout << quan << " " << l << " " << r  << endl;
    ans[id] = 1ll * l * (n + 1 - r) - quan;
  }
  rep(i,0,m){
    printf("%lld\n",ans[i]);
  }
}

F. Find the Maximum

题解：另外一道签到题，推一推可以发现，所求值的最大就是选定结点的平均值的平方除以4，根据平均的性质，可以判断最多选3个点，然后跑所有情况取最大即可。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define db long double
#define all(x) x.begin(),x.end()

const int N = 1e5+5;
db a[N];
db f(db t){return t*t/4.0;}
vector<int> G[N];

int main(){
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
    scanf("%Lf",a+i);
  }
  db res = 0;
  rep(i,0,n-1){
    int u,v;
    scanf("%d%d",&u,&v);
    res = max(res,f((a[u]+a[v])/2.0));
    G[u].push_back(v);G[v].push_back(u);
  }
  for(int i=1;i<=n;i++){
    sort(all(G[i]),[&](int ii,int j){
      return a[ii] > a[j];
    });
  }
  for(int i=1;i<=n;i++){
    int sz = G[i].size() - 1;
    if(G[i].size()>=2){
      res = max(res, f((a[i]+a[G[i][0]]+a[G[i][1]])/3.0));
      res = max(res, f((a[i]+a[G[i][sz]]+a[G[i][sz-1]])/3.0));
    }
  }
  cout << fixed << setprecision(18) << res << endl;
}

G.Glass Bead Game

题解：又是一个期望题，考虑多个太麻烦，不妨只考虑两个之间的关系，则i在j前面的概率为pjpi+pj\frac{pj}{pi+pj},其它的是不用考虑，因为不影响他们之间的先后关系。通过这个结论，稍加思考就可以得到答案。

#include<bits/stdc++.h>
using namespace std;

const int N = 104;
double p[N];

int main(){
    int n;
    cin >> n;
    for(int i =1;i<=n;i++)cin >> p[i];
    double res = 0;
    for(int i=1;i<=n;i++){
        double tp = 0;
        for(int j=1;j<=n;j++){
            if(i==j)continue;
            tp += p[j]/(p[i]+p[j]);
        }
        tp *= p[i];
        res += tp;
    }
    cout << fixed << setprecision(12) <<  res << endl;
}

K.King of Gamers

题意：签到题，答案就在题面上，注意0的特判。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        LL n,a,b;
        cin >> n >> a >> b;
        if(a==0)cout << 1 << endl;
        else if(n*a%b==0)cout << n*a/b << endl;
        else if(n==1)cout << 1 << endl;
        else {
            long long y = n*a/b + 1;
            if(b*(y-1) <= a*(n-1));
            else y--;
            cout << y << endl;
        }
    }
}
全部评论
加一也是为了达到这个目的。
点赞 回复 分享
发布于 2022-05-14 14:26
我们发现1x离散后可能为0，易得f(0)=0,但这个显然不对，我们根据题意可以得到，只要1/x不为0，那么期望必然不为0，所以离散化得注意和1取一个max。
点赞 回复 分享
发布于 2022-05-14 14:25
大佬，c题式子好像写错了？有个+1吧qaq
点赞 回复 分享
发布于 2022-05-07 21:48

相关推荐

04-18 08:53
招联金融_风险策略
点赞 评论 收藏
分享
04-22 19:51
门头沟学院 Java
点赞 评论 收藏
分享
03-14 20:13
淮北师范大学 Java
第一次找实习，请问大家这些要求正常吗
大摆哥：刚好要做个聊天软件，直接让你帮他干活了
点赞 评论 收藏
分享
03-11 23:45
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
04-20 16:45
叮咚买菜_商品运营(准入职员工)
叮咚买菜内推叮咚买菜内推码
前段时间参加了叮咚买菜的面试，现在想和大家分享一下我的经历，希望能给准备面试叮咚买菜的小伙伴一些参考。我应聘的是供应链专员岗位，通过校园招聘投递简历后，很快就收到了面试邀请。面试流程整体推进得比较快，效率很高。一面：是&nbsp;HR&nbsp;面，通过电话沟通。首先是让我进行自我介绍，大概&nbsp;2&nbsp;-&nbsp;3&nbsp;分钟，主要介绍了自己的教育背景、相关实习经历和个人优势。之后，HR&nbsp;针对我的简历进行了深挖，问了我在实习中参与的具体项目，比如在&nbsp;[实习公司名称]&nbsp;实习时负责的供应链优化项目，详细询问了我在项目里承担的角色、遇到的困难以及如何解决的。还问了我对供应链管理的理解，以及为什么选择叮咚买菜这个公司和供应链专员这个岗位。...
点赞 评论 收藏
分享
评论
17
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 京东美团大战，你怎么看？ #
42199次浏览 264人参与
# 机械人避雷的岗位/公司 #
10360次浏览 63人参与
# 平安产险科技中心求职汇总 #
245206次浏览 2614人参与
# 实习进度记录 #
189119次浏览 2215人参与
# 工作经验重要还是工资重要？ #
121082次浏览 824人参与
# 小红书取消大小周 #
8565次浏览 84人参与
# 产品人求职现状 #
195312次浏览 1801人参与
# 设计人如何选offer #
96716次浏览 675人参与
# 毕业论文怎么查AI率 #
9274次浏览 604人参与
# 选择和努力，哪个更重要？ #
72363次浏览 668人参与
# 顺丰求职进展汇总 #
47618次浏览 268人参与
# 我的求职精神状态 #
10498次浏览 229人参与
# 一觉醒来，我成论文导师了… #
6932次浏览 129人参与
# 租房找室友 #
13370次浏览 95人参与
# 哪个瞬间让你对大厂祛魅了？ #
290660次浏览 2112人参与
# 拼多多工作体验 #
15928次浏览 149人参与
# 正在实习的你，在做dirty work吗 #
110233次浏览 748人参与
# TP-LINK工作体验 #
43930次浏览 812人参与
# 读研or工作，哪个性价比更高？ #
54726次浏览 663人参与
# 我在牛客求捞 #
43436次浏览 214人参与
# 比亚迪求职进展汇总 #
690080次浏览 3046人参与
牛客网
牛客企业服务