• “蔚来杯“2022牛客暑期多校训练营2

    G. Link with Monotonic Subsequence（规律）

    给出n，构造一个permutation，使得其最长上升子序列和最长下降子序列的最大值最小。

    思路： 从比较特殊的情况考虑，当我们把一个数组类似1,2,3,4,5,6,7两两互换位置后，很容易得到其最长下降子序列为2，最长上升子序列是互换的组数。我们要使得这两个数尽可能的接近，这样才能尽可能最小化两数的最大值。考虑每\left \lceil \sqrt{n} \right \rceil个数分为一组并倒置，例如3,2,1,6,5,4,7，这样我们一起考虑到每组分的个数和组数两个因素，并使其尽可能缩小差值，最长上升子序列是分成的组数，最长下降子序列是每组的个数。

    AC Code：

    1. #include 
    2.  
    3. const int N=1e6+5;
    4. int t,n;
    5. int a[N];
    6.  
    7. int main(){
    8.     std::ios::sync_with_stdio(false);
    9.     std::cin.tie(0);
    10.     std::cout.tie(0);
    11.     std::cin>>t;
    12.     while(t--){
    13.         std::cin>>n;
    14.         memset(a,0,sizeof(a));
    15.         for(int i=1;i<=n;i++){
    16.             a[i]=i;
    17.         }
    18.         int pos;
    19.         for(int i=1;i<=n;i++){
    20.             if((ll)i*(ll)i>=n){
    21.                 pos=i;
    22.                 break;
    23.             }
    24.         }
    25.         for(int i=1;i*pos<=n;i++){
    26.             for(int j=i*pos;j>=(i-1)*pos+1;j--){
    27.                 std::cout<' ';
    28.             }
    29.         }
    30.         if(n%pos){
    31.             int res=n%pos;
    32.             for(int i=n;i>=n-res+1;i--){
    33.                 std::cout<' ';
    34.             }
    35.         }
    36.         std::cout<<'\n';
    37.     }
    38.     return 0;
    39. }

    os：签到都好难想，唉

     J. Link with Arithmetic Progression（最小二乘法）

    给定一个数列a，将其修改为一个等差数列b，代价为\sum_{i=1}^{n}(a_{i}-b_{i})^{2}，最小化代价。

    思路：看到这个等差数列，是一次函数的模型，且最小化代价，看到这个最小代价，联想到：

     直接带入公式计算残差平方和即可。

    AC Code：

    1. #include 
    2.  
    3. const int N=1e5+5;
    4. int t,n;
    5. int a[N];
    6.  
    7. int main(){
    8.     scanf("%d",&t);
    9.     while(t--){
    10.         scanf("%d",&n);
    11.         double ax=0,ay=0,tmpx=0,tmpy=0;
    12.         for(int i=1;i<=n;i++){
    13.             scanf("%d",&a[i]);
    14.             ax+=i,ay+=a[i];
    15.         }
    16.         ax/=(double)n,ay/=(double)n;
    17.         for(int i=1;i<=n;i++){
    18.             tmpx+=(i-ax)*(i-ax);
    19.             tmpy+=(i-ax)*(a[i]-ay);
    20.         }
    21.         double bb=tmpy/tmpx;
    22.         double aa=ay-bb*ax;
    23.         double ans=0;
    24.         for(int i=1;i<=n;i++){
    25.             ans+=(bb*i+aa-a[i])*(bb*i+aa-a[i]);
    26.         }
    27.         printf("%.15lf\n",ans);
    28.     }
    29.     return 0;
    30. }

    os：这波是队友带飞了，队友一下就看出来线性回归方程，我高中的东西都忘干净了hhh

     K. Link with Bracket Sequence I（DP）

    给出长度为n的字符串s，这个字符串是由长度为m的合法字符串删去若干括号得到的，求合法的字符串有多少。

    思路：学习大佬的思路考虑三位DP数组，f[i][j][k]代表字符串长度为i，匹配长度为j，左括号比右括号多的数目为k时的方案数。左括号时，可以任意匹配；当是右括号时，只有当左括号数目大于右括号数目时才可以匹配。

    AC Code：

    1. #include 
    2.  
    3. const int N=105;
    4. const int mod=1e9+7;
    5. int t,n,m;
    6. std::string s;
    7. int f[N][N][N];
    8.  
    9. int main(){
    10.     std::ios::sync_with_stdio(false);
    11.     std::cin.tie(0);
    12.     std::cout.tie(0);
    13.     std::cin>>t;
    14.     while(t--){
    15.         std::cin>>n>>m>>s;
    16.         s=' '+s;
    17.         memset(f,0,sizeof(f));
    18.         f[0][0][0]=1;
    19.         for(int i=0;i
    20.             for(int j=0;j<=n;j++){
    21.                 for(int k=0;k<=i;k++){
    22.                     f[i+1][j+(s[j+1]=='(')][k+1]=(f[i+1][j+(s[j+1]=='(')][k+1]+f[i][j][k])%mod;
    23.                     if(k)
    24.                         f[i+1][j+(s[j+1]==')')][k-1]=(f[i+1][j+(s[j+1]==')')][k-1]+f[i][j][k])%mod;
    25.                 }
    26.             }
    27.         }
    28.         std::cout<0]<<'\n';
    29.     }
    30.     return 0;
    31. }

    解释：循环i枚举字符串长度，循环j枚举匹配成功的长度，循环k枚举左括号比右括号多的数量；如果是左括号时，可以直接匹配，字符串长度+1，左括号比右括号多的数目+1；仅当左括号数目大于右括号时，才进行右括号匹配，字符串长度+1，左括号比右括号多的数目-1。

    os：完了，不仅是简单DP搞不出来，这种要自己选择每维表示什么更难了啊

    D. Link with Game Glitch（判负环）

    有n种物品，m个关系，每个关系a，b，c，d表示可以用a个b类型的物品来制作c个d类型物品，现在要求找到一个最大的w，使得满足用a个b物品制作c*w个d物品，且不会出现制作出无限物品的情况。

    思路：我们可以考虑建立b与d之间的关系，即每个b物品可以制作c/a个d，二分出答案w，若存在一个环使得一个x可以制作出大于1的x，则不满足条件，w需要小一点。

    特殊处理：因为c/a大部分都是小于1的，所以很多个相乘很容易等于0，我们可以取对数，使得小于1的数，都变成较大的负数，利用log(x*y)=log(x)+log(y)，这样解决了精度问题，而对于原问题判断是否大于1的问题，也转化为是否大于0的问题。

    注：因为是带负权图，处理可以采用Bellman-Ford，注意更新w条件是不出现一个正环，这样才可以保证不会无限制造物品。浮点数二分时直接自定义一个循环次数，不要用while(l

    AC Code：

    1. #include 
    2.  
    3. const int N=1050;
    4. int n,m,a,b,c,d;
    5. double dis[N];
    6.  
    7. struct node{
    8.     int u,v;
    9.     double w;
    10. };
    11.  
    12. std::vectorvec;
    13.  
    14. bool check(double k){
    15.     for(int i=1;i<=n;i++) dis[i]=0;
    16.     k=log(k);
    17.     int cnt=0;
    18.     while(1){
    19.         bool flag=true;
    20.         for(auto it:vec){
    21.             int u=it.u,v=it.v;
    22.             double w=it.w;
    23.             if(dis[u]+k+w>dis[v]){
    24.                 dis[v]=dis[u]+k+w;
    25.                 flag=false;
    26.             }
    27.         }
    28.         if(flag) break;
    29.         cnt++;
    30.         if(cnt>n+10) return false;
    31.     }
    32.     return true;
    33. }
    34.  
    35. int main(){
    36.     std::ios::sync_with_stdio(false);
    37.     std::cin.tie(0);
    38.     std::cout.tie(0);
    39.     std::cin>>n>>m;
    40.     for(int i=1;i<=m;i++){
    41.         std::cin>>a>>b>>c>>d;
    42.         double w=(double)c/(double)a;
    43.         vec.push_back({b,d,log(w)});
    44.     }
    45.     double l=0,r=1;
    46.     double ans=0;
    47.     for(int i=1;i<=100;i++){
    48.         double mid=(l+r)/2;
    49.         if(check(mid)){
    50.             ans=std::max(ans,mid);
    51.             l=mid;
    52.         }
    53.         else r=mid;
    54.     }
    55.     std::cout<setprecision(10)<'\n';
    56.     return 0;
    57. }

    os：才发现原来cin cout也可以确定浮点数精度   std::fixed<

    L. Link with Level Editor I（滚动数组）

     有n个世界，每个世界都有m个点，在第i个世界中，最多可以选择一条边u->v，从u移动到v（可以选择不移动）。随后进入到第i+1个世界中的点v。如果选择在u点上不移动，则进入第i+1个世界的点u，现要求找到一段连续的世界[L,R]，使得可以从点1到点m，最小化这个区间。

    思路：学习大佬的思路对于第i个世界，我们枚举这个世界中的边u->v，想要到达v有两种方式，从i-1世界中的v到达，从i-1世界中的u到达i世界的u，再到v。因为我们只需要考虑1到m穿越世界的个数，随意我们记录到每个点u最近的点1的世界编号。

    采用滚动数组pre表示i-1的世界，now为当前i世界，若存在u->v且v=m，那么我们用min(ans,i-now[v]+1)来更新穿越世界的最小值。注意now[v]为最近的点1所在的世界。那么对于u->v还需要更新now[v]的值，now[v]=max(now[v],pre[u])。

    AC Code：

    1. #include 
    2.  
    3. #define INF 0x3f3f3f3f
    4. const int N=2e5+5;
    5. int n,m;
    6.  
    7. signed main(){
    8.     std::ios::sync_with_stdio(false);
    9.     std::cin.tie(0);
    10.     std::cout.tie(0);
    11.     std::cin>>n>>m;
    12.     std::vector<int>pre(m+1,-INF),now(m+1,-INF);
    13.     int ans=INF;
    14.     for(int i=1;i<=n;i++){
    15.         int l;
    16.         std::cin>>l;
    17.         pre[1]=i;
    18.         for(int j=1;j<=l;j++){
    19.             int u,v;
    20.             std::cin>>u>>v;
    21.             now[v]=std::max(now[v],pre[u]);
    22.             if(v==m) ans=std::min(ans,i-now[v]+1);
    23.         }
    24.         pre=now;
    25.     }
    26.     if(ans>n) std::cout<<-1<<'\n';
    27.     else std::cout<'\n';
    28.     return 0;
    29. }

    H. Take the Elevator（模拟）

    n个人坐电梯，楼高k，每个人有起始楼层和目标楼层，电梯有载客量限制m，可以上升至任意层下降，但是下降一定要到第一层后再上升，电梯每秒运行一层，换方向和上下人不占用时间，问电梯最短运行时间。

    大佬的思路

    思路：把所有人分两类考虑，上行的一类，下降的一类，两者是相同的。对于电梯的一次上行，首先取出需要到达最高的，同时维护一个电梯中人员序列，仅记录其上电梯的时刻，当序列长度小于m时，继续取到达位置高的，若电梯已满，只能选择进电梯楼层最高的还没上之前就把人运到，因而选择最大的、同时下电梯位置不超过序列中最大的进电梯的人加入电梯，这样维护一次电梯能带走多少人，记录最高楼层。上行下行倒道理一样，一次运行必定满足一次上行和一次下行，做归并即可。

    AC Code：

    1. #include 
    2.  
    3. typedef long long ll;
    4. typedef std::pairPLL;
    5. #define INF 0x3f3f3f3f
    6. const int N=2e5+5;
    7. int n,m,k;
    8.  
    9. std::vector cal(std::vector &que){
    10.     std::sort(que.begin(),que.end());
    11.     std::multisets;
    12.     for(auto i:que){
    13.         auto it=s.upper_bound(i.first);
    14.         if(it!=s.begin()) s.erase(prev(it));
    15.         s.insert(i.second);
    16.     }
    17.     std::vectorans;
    18.     while(!s.empty()){
    19.         int times=m;
    20.         ans.push_back(*s.rbegin());
    21.         while(!s.empty()&×--)
    22.             s.erase(s.find(*s.rbegin()));
    23.     }
    24.     return ans;
    25. }
    26.  
    27. int main(){
    28.     std::ios::sync_with_stdio(false);
    29.     std::cin.tie(0);
    30.     std::cout.tie(0);
    31.     std::cin>>n>>m>>k;
    32.     std::vectorup,down;
    33.     for(int i=1;i<=n;i++){
    34.         int a,b;
    35.         std::cin>>a>>b;
    36.         if(apush_back({a,b});
    37.         else down.push_back({b,a});
    38.     }
    39.     auto f1=cal(up),f2=cal(down);
    40.     ll ans=0;
    41.     int len1=f1.size(),len2=f2.size();
    42.     for(int i=0;imax(len1,len2);i++){
    43.         ll d1=isize()?f1[i]:0;
    44.         ll d2=isize()?f2[i]:0;
    45.         ans+=2*(std::max(d1,d2)-1);
    46.     }
    47.     std::cout<'\n';
    48.     return 0;
    49. }

    os：难度较大的贪心

     C. Link with Nim Game（Nim博弈）

     有n堆石头，A和B轮流进行操作，A先手，每次操作可以从任意一堆石头中取正整数个石头，若无法完成操作则输，在双方都采取最优策略情况下，必败一方想尽可能慢的结束游戏，必胜的一方想尽可能快的结束游戏，求游戏结束时进行的操作和第一轮可能进行的操作种类数。

    大佬的思路

    思路：首先判断胜负是Nim游戏的结论，若所有n堆石子数异或和不为0时，先手必胜，反之后手必胜。分类讨论，若先手必胜则第一次先手会拿最多的石头；若先手必败，则二人必定一个一个拿，对于方案数需要判断拿一个石头后下一步是否必须也拿一个石头。

    先看先手必胜时，因为希望尽快结束比赛，那么就要找到能取出的最大值，取出后使得剩余石头堆的异或和为0，对于最大值的计算，若假设对a[i]取，剩下x，即sum^a[i]^x=0，那么a[i]-x即最大值；对于先手必败时，输的人必须一个一个拿，但是不能让对手有拿若干石头也能让异或和变为0的情况，也就是说我们需要在某一堆拿掉一个石头，记录每一堆拿掉一个石头剩下的异或和放入set去重，再转化为刚才分析必胜态的状态，找到使得异或和为0的值，若取出的值可以大于1，那么对手存在拿多个石头而加速游戏结束的状态，因此我们只需要找到哪些方案拿完一个石头接下来必拿一个石头的种类即可。

    AC Code：

    1. #include 
    2.  
    3. typedef long long ll;
    4. typedef std::pairPLL;
    5. #define int long long
    6. #define INF 0x3f3f3f3f
    7. const int N=2e5+5;
    8. int t,n;
    9. std::vector<int>a(N,0);
    10.  
    11. signed main(){
    12.     std::ios::sync_with_stdio(false);
    13.     std::cin.tie(0);
    14.     std::cout.tie(0);
    15.     std::cin>>t;
    16.     while(t--){
    17.         std::cin>>n;
    18.         int sum=0,tot=0;
    19.         for(int i=1;i<=n;i++){
    20.             std::cin>>a[i];
    21.             sum^=a[i],tot+=a[i];
    22.         }
    23.         if(sum){
    24.             int max=0,ans=0;
    25.             for(int i=1;i<=n;i++){
    26.                 int x=a[i]-(sum^a[i]);
    27.                 max=std::max(max,x);
    28.             }
    29.             for(int i=1;i<=n;i++){
    30.                 int x=a[i]-(sum^a[i]);
    31.                 if(x==max) ans++;
    32.             }
    33.             std::cout<1<<' '<'\n';
    34.         }
    35.         else{
    36.             std::set<int>S,T;
    37.             for(int i=1;i<=n;i++){
    38.                 int x=sum^a[i]^(a[i]-1);
    39.                 S.insert(x);
    40.             }
    41.             for(auto u:S){
    42.                 for(int i=1;i<=n;i++){
    43.                     int x=sum^a[i]^u;
    44.                     if(a[i]-x>1) T.insert(u);
    45.                 }
    46.             }
    47.             for(auto u:T) S.erase(u);
    48.             int ans=0;
    49.             for(int i=1;i<=n;i++)
    50.                 if(S.count(a[i]^(a[i]-1)))
    51.                     ans++;
    52.             std::cout<' '<'\n';
    53.         }
    54.     }
    55.     return 0;
    56. }

    补不动了。。。

  • 相关阅读:
    使用Loadrunner进行性能测试
    【数据可视化】第一章——了解NumPy库的基本原理
    匿名内部类（2022.7.20）
    Trie树（字典树）C++详解
    Spark-机器学习（3）回归学习之线性回归
    【SpringBoot】一文吃透SpringBoot多环境开发
    ubuntu/Linux连接redis教程
    号称年薪30万占比最多的专业，你知道是啥嘛？
    c 取字符串中的子串
    计算系统DFR
  • 原文地址：https://blog.csdn.net/m0_62289613/article/details/125976620