2.5比赛（CF二合一）

A题
题意：分配n个人，使其leader和手下总和为n
思路：暴力，遍历

#include <vector>
#include<stdio.h>
#include<string.h>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
#include<cstring>
#define ll long long
#define MODD 1000000007
#define  pii  pair<int,int>
#include<stdio.h>
#include<string.h>
//#define  ll long long
using namespace std;
int arr[15000];int n;
int brr[15000];
int vis[10000]={0};
int viss[10000]={0};
map<int ,int >mp;
vector<int >v;
int main() {
  int n;cin >>n;
  int nn = n;int sum =0 ;
  for(int i=1;i<=(n+1)/2;i++){
    if((nn-i)%i==0){
        sum++;
    }
  }
cout<<sum<<endl;
    return 0;



}

B题
题意：问纪少最后要支付多少硬币
思路：模拟，因为过x=y这条直线就要支付一个硬币，所以就看是否过x = y这条直线
代码

#include <vector>
#include<stdio.h>
#include<string.h>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
#include<cstring>
#define ll long long
#define MODD 1000000007
#define  pii  pair<int,int>
#include<stdio.h>
#include<string.h>
//#define  ll long long
using namespace std;
int arr[15000];int n;
int brr[15000];
int vis[10000]={0};
int viss[10000]={0};
map<int ,int >mp;
vector<int >v;
int main() {
  int n; cin >>n;
  string s; 
  cin >>s;
  int x =0 , y =0 ;int sum =0 ;
  int f =0 ;
  for(int i=0;i<n;i++){
      if(s[i]=='U'){
          y++;
      }
      else if(s[i]=='D'){
          y--;
      }
      else if(s[i]=='L')x--;
      else if(s[i]=='R')x++;
      if(x != y){

          if(x<y ){
              if(f==0)f= 2;
              else if(f ==1){
                  sum++;
              f = 2;
              }

          }
          else if(x>y){
              if(f==0) f= 1;
                  else if(f ==2){
              sum ++;
              f =1 ;
              }

          }
      }
  }
  cout<<sum<<endl;
    return 0;



}

C题
题意：找到一个点（路由器的位置），和半径，解释一下，题目的给的数值,r是房子的半径，x1,y1 是房子的坐标，x2 , y2 ,是FAFA的位置
思路：先考虑一下FAFA 的位置
当FAFA 在房子半径得外面的时候，直接输出房子的坐标和半径
当FAFA跟房子重合，找一个园和房子的半径的相切
当FAFA 在圆内且不与房子重合
具体图看这个博客 

#include <vector>
#include<stdio.h>
#include<string.h>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
#include<cstring>
#define ll long long
#define MODD 1000000007
#define  pii  pair<int,int>
#include<stdio.h>
#include<string.h>
//#define  ll long long
using namespace std;
int arr[15000];int n;

int brr[15000];
int vis[10000]={0};
int viss[10000]={0};
map<int ,int >mp;
vector<int >v;
char ch[10000000];
int cc[500]={0};
struct node {
    int x ,pos ;
};
node p[10000000];
int cmp(node a, node b){
    return a.x>b.x;
}
int main() {
 double r, x1,y1,x2,y2;
 cin >>r>>x1>>y1>>x2>>y2;
 double dis =0 ;
 dis = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
 if(dis >=r){
 //    cout<<x1<<" "<<y1<<endl;
     printf("%.8f %.8f %.8f\n",x1,y1,r);
 }
 else {
     double rr = (r+dis)*0.5;
     double xx =(r-rr)/dis*(x1-x2)+ x1;
     double yy =(r-rr)/dis*(y1-y2) + y1;
     if(x1== x2 && y1==y2){
         xx = x1+ rr;yy = y1;
     }

     printf("%.8f %.8f %.8f\n",xx,yy,rr);

 }
    return 0;



}

D题
题意：给你一个N和M，两个纯数字的数组，问你第一个数组比第二个打的概率是多少
思路：可暴力（不会），可概率DP（听别人的公式写的）
附上大佬的推的公式 

#include <vector>
#include<stdio.h>
#include<string.h>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
#include<cstring>
#include<queue>
#include<assert.h>
#define ll long long
#define MODD 1000000007
#define  pii  pair<int,int>
#include<stdio.h>
#include<string.h>
//#define  ll long long
using namespace std;
const ll maxn = 1e6;

int brr[15000];
int vis[10000]={0};
int viss[10000]={0};
map<int ,int >mp;
vector<int >v;
ll ar[maxn],br[maxn];
queue<ll>q,p;
ll exgcd(ll a, ll b, ll &x, ll &y) {
 if (b == 0) { x = 1; y = 0; return a; }
 ll ret = exgcd(b, a % b, y, x);
 y -= a / b * x;
 return ret;
 }
ll inv(ll a, ll M) {
 static ll x, y;
 assert(exgcd(a, M, x, y) == 1);
 return (x % M + M) % M;
 }
//void gcd(ll a,ll b,ll &d,ll &x,ll &y){
//    if(!b){
//        d=a;x=1;y=0;
//    }else{
//        gcd(b,a%b,d,y,x);
//        y-=x*(a/b);
//    }
//}
//ll inv(ll a,ll n){
//    ll d,x,y;
//    gcd(a,n,d,x,y);
//    return d==1?(x+n)%n:-1;
//}
// LL get_inv(LL a, LL M) {
// static LL x, y;
// assert(exgcd(a, M, x, y) == 1);
// return (x % M + M) % M;
// }

int n,  m ;ll mod = 1e9+7;
ll dp(int x){
    if(x == n)return 0;
    else {
        if(ar[x]==br[x]&&ar[x]!=0&&br[x]!=0)return dp(x+1);
    if(ar[x]>br[x]&&ar[x]!=0&&br[x]!=0)return 1;
    if(ar[x]<br[x]&&ar[x]!=0&&br[x]!=0)return 0;
        else {

            if(!ar[x]&&br[x])return ((m-br[x])%mod*inv(m,mod)%mod+dp(x+1)%mod*inv(m,mod)%mod)%mod;
            if(!br[x]&&ar[x])return ((ar[x]-1)%mod*inv(m,mod)%mod+dp(x+1)%mod*inv(m,mod)%mod)%mod;
            if(!ar[x]&&!br[x])    return ((m-1)%mod*inv(2*m,mod)%mod+dp(x+1)%mod*inv(m,mod)%mod)%mod;

        }
    }
}
int main() {

  cin >>n >>m;
   for(int i=0;i<n;i++)cin >>ar[i];
   for(int i=0;i<n;i++)cin >>br[i];
   ll sum = dp(0);
   cout<<sum<<endl;
    return 0;



}

E题
题意：给你N个数，和d,找出一个数组最多里面数最多的时候，最大值-最小值<=d 的时候需要删去 的最少数
思路：一数据不大，直接暴力走起

#include <vector>
#include<stdio.h>
#include<string.h>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
#include<cstring>
#define ll long long
#define MODD 1000000007
#define  pii  pair<int,int>
#include<stdio.h>
#include<string.h>
//#define  ll long long
using namespace std;
int arr[15000];int n;
int brr[15000];
int vis[10000]={0};
int viss[10000]={0};
map<int ,int >mp;
vector<int >v;
int main() {
  int n,d ;cin >>n>>d;
  int sum =1, len =0 ;
  for(int i=0;i<n;i++)cin >>arr[i];
  sort(arr,arr+n);
  for(int i=0;i<n;i++){
      for(int j =i;j<n;j++){
          if(i==j)continue ;
          else {
              if(arr[j]-arr[i]<=d){
                  sum++;
              }
          }
      }
//      cout<<sum<<endl;
      len = max(len, sum);
      sum =1 ;

  }
  cout<<n-len<<endl;
    return 0;



}

F题
题意：问你从n变成 1 需要花费的最小费用
且由两种费用模式，第一种-1，第二种/k
思路：按照说的模拟就行，注意一个坑点，当k==1 时，其实第一种和第二种是一样的，所以直接(n-1)*a;

#include <vector>
#include<stdio.h>
#include<string.h>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
#include<cstring>
#define ll long long
#define MODD 1000000007
#define  pii  pair<int,int>
#include<stdio.h>
#include<string.h>
//#define  ll long long
using namespace std;
int arr[15000];int n;
int brr[15000];
int vis[10000]={0};
int viss[10000]={0};
map<int ,int >mp;
vector<int >v;
int main() {
  ll n, k , a ,b;
  cin >>n >>k >>a>>b;
  ll x = n;ll sum =0 ;
  if(k==1)return cout<<(n-1)*a<<endl,0;
  while(x!=1){
      if(x%k==0&&x>=k){
          if(b<a*(x-x/k))sum +=b ;
          else sum +=a*(x-x/k);
          x /=k;
      //    cout<<x<<endl;
      }
    else {

        ll o =x-x/k*k; 
        if(o==0){
            sum +=(x-1)*a;
            x= 1;
        }
        else {
            sum+= a*o;
        x -= o;
        }

    }
//    cout<<x<<endl;
//    cout<<sum<<endl;

  }cout<<sum<<endl;
    return 0;



}

G题
题意：字符串比较问题，首先给你一个N,k,n是字符串的长度，K 是你要输出的字符串长度。然后输出比这个字符串大的最小字符串
思路：
我是按照K和n的关系来的
细分为小于， 等于， 大于
大于的好说，直接在后面加最小的就行，
等于的首先要从后往前找第一个小于最大字符的字符，然后把它变为这个字符下一个字符就行，剩下和上面大于一样
小于和等于差不多，就是记得数量是比N小的就行

#include <vector>
#include<stdio.h>
#include<string.h>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
#include<cstring>
#define ll long long
#define MODD 1000000007
#define  pii  pair<int,int>
#include<stdio.h>
#include<string.h>
//#define  ll long long
using namespace std;
int arr[15000];int n;

int brr[15000];
int vis[10000]={0};
int viss[10000]={0};
map<int ,int >mp;
vector<int >v;
char ch[10000000];
int cc[500]={0};
struct node {
    int x ,pos ;
};
node p[10000000];
int cmp(node a, node b){
    return a.x>b.x;
}
int main() {
  int n ,k;cin>>n>>k;    int num =0 ;
  for(int i=0;i<n;i++){
      cin >>ch[i];

      if(!cc[ch[i]-'a']){
          cc[ch[i]-'a'] = ch[i]-'a'+1;
          p[num].x = ch[i]-'a'+1;p[num].pos =  num ;
          num++;

      }
  }
  sort(p,p+num,cmp);int len =-1 ;int r =0;
  if(k<n){
      char chc;
      for(int i=k-1;i>=0;i--){
          if(ch[i]!=char(p[0].x+'a'-1)){
              len = i;chc = ch[i];
              break;
          }
      }
      for(int i=num-1;i>=0;i--){
          if(char(p[i].x+'a'-1)>chc){
              r = i;break;
          }
      }
//      cout<<len <<" "<<r<<endl;
      for(int i=0;i<len;i++)cout<<ch[i];
      cout<<char(p[r].x+'a'-1);
      for(int i=len+1;i<k;i++)cout<<char(p[num-1].x+'a'-1);
      cout<<endl;

  }
  else if(k==n){
      char chc;
      for(int i=k-1;i>=0;i--){
          if(ch[i]!=char(p[0].x+'a'-1)){
              len = i;chc = ch[i];
              break;
          }
      }
        for(int i=num-1;i>=0;i--){
          if(char(p[i].x+'a'-1)>chc){
              r = i;break;
          }
      }
      //cout<<len <<" "<<r<<endl;
      for(int i=0;i<len;i++)cout<<ch[i];
      cout<<char(p[r].x+'a'-1);
      for(int i=len+1;i<k;i++)cout<<char(p[num-1].x+'a'-1);
      cout<<endl;
//      cout<<p[ch[i]]
  }
else if(k>n){
    char chc;
  for(int i=0;i<n;i++) cout<<ch[i];
  for(int i=n;i<k;i++)cout<<char(p[num-1].x+'a'-1);
  cout<<endl;
}
    return 0;



}

H题
题意：给你个n，有N个数，长度为N 的字符串，然后经过题上给条件，找出l， r的数值
（题上条件其实第三个没用。。。）
思路：其实是一道思维题，想明白就好做了，首先当前的字符为1是，找前面的四个是不是0，不是就continue，是的话，就判断l（l要大于这五个的a）
0的同理

#include <vector>
#include<stdio.h>
#include<string.h>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
#include<cstring>
#include<queue>
#define ll long long
#define MODD 1000000007
#define  pii  pair<int,int>
#include<stdio.h>
#include<string.h>
//#define  ll long long
using namespace std;
const ll maxn = 1e6;

int brr[15000];
int vis[10000]={0};
int viss[10000]={0};
map<int ,int >mp;
vector<int >v;
ll ar[maxn],br[maxn];
queue<ll>q,p;
int main() {
  int n;cin >>n;
  for(int i=1;i<=n;i++)cin >>ar[i];
  string s;cin >>s;
  for(int i=0;i<n;i++)br[i+1] = s[i]-'0';
//  cout<<"?";
  ll r =1e9, l = -1e9;
  for(int i=5;i<=n;i++){
      if(br[i]==0&&br[i-1]==1&&br[i-2]==1&&br[i-3]==1&&br[i-4]==1){
          r = min(r,min(ar[i]-1,min(ar[i-1]-1,min(ar[i-2]-1,min(ar[i-3]-1,ar[i-4]-1)))));

      }
    else if(br[i]==1&&br[i-1]==0&&br[i-2]==0&&br[i-3]==0&&br[i-4]==0){
        l = max(l,max(ar[i]+1,max(ar[i-1]+1,max(ar[i-2]+1,max(ar[i-3]+1,ar[i-4]+1)))));
    }
//    cout<<l<<" "<<r<<endl;
  }
  cout<<l<<" "<<r<<endl;
    return 0;



}
全部评论

相关推荐

头像
maelstrom
05-05 23:43
蚌埠坦克学院 计算机类
拼多多 网易雷火 hr面
hr面比技术面还要汗流浃背，全是开放题。技术面好歹面完就知道对不对，hr面只会对你说嗯嗯嗯，然后就没了，声音清一色的甜妹但是无感情的声音，一边说话一边狂敲键盘总结一下两次hr面的问题，每个都在十分钟左右：家里人同意来这里实习吗目前的offer情况有没有女朋友有没有团队合作的经历团队合作中遇到的困难，怎么克服课外兴趣能实习多久实习的目的是什么（当然是实习）怎么学习一个新的技术栈目前掌握的技术栈（为什么hr会了解这玩意？？？难不成是程序员转专业）为什么想来本公司工作（跪舔）以后的规划，领导层还是走技术路线公司加班情况了解吗，怎么看待（拼多多）问我有什么问题要问，都是三件套：转正率（两个都说只要好好...
点赞 评论 收藏
转发
头像 会员标识 头像
sorano_
05-09 21:48
门头沟学院 计算机类
点赞 评论 收藏
转发
头像
普普通通狗
05-08 20:05
蚌埠坦克学院
点赞 评论 收藏
转发
头像
牛客578290712号
05-08 10:53
已编辑
算法工程师
点赞 评论 收藏
转发
3 1 评论
分享

全站热榜

正在热议
# 牛客帮帮团来啦！有问必答 #
644742次浏览 10752人参与
# 无实习如何秋招上岸 #
208623次浏览 3254人参与
# 找工作中的意难平 #
183205次浏览 3333人参与
# 租房前辈的忠告 #
30158次浏览 2009人参与
# 硬件人的简历怎么写 #
75569次浏览 775人参与
# 秋招开了，你想投哪些公司呢 #
114266次浏览 3228人参与
# 我想象的工作vs实际工作 #
89236次浏览 1514人参与
# 简历中的项目经历要怎么写 #
419407次浏览 7098人参与
# 五一之后，实习真的很难找吗？ #
15066次浏览 94人参与
# 华为开奖那些事 #
691733次浏览 5948人参与
# 本周投递记录 #
193190次浏览 4992人参与
# 第一份工作应该选择高薪还是大平台 #
33513次浏览 252人参与
# 浅聊一下我实习的辛苦费 #
78238次浏览 724人参与
# 金融银行面经 #
4163次浏览 98人参与
# 软件开发投递记录 #
461743次浏览 7081人参与
# 你已经投递多少份简历了 #
283733次浏览 4304人参与
# 你投了多少份简历，才拿到offer？ #
4655次浏览 49人参与
# 春招已经启动啦 硬件uu开始投了吗？ #
85035次浏览 669人参与
# 我的成功项目解析 #
79690次浏览 2330人参与
# 我的上岸简历长这样 #
156174次浏览 3105人参与
牛客网
牛客企业服务