文章目录

• • A DFS搜索
  • M牛客老粉才知道的秘密
  • G why外卖
  • E 本题又主要考察了贪心
  • B 关鸡
  • C 按闹分配

    今天的牛客，说是都是基础题，头昏昏的，感觉真不会写，只能赛后补题了

    A DFS搜索

    写的时候刚开始以为还是比较难的，和dfs有关，读完题目发现就是一个序列中含有dfs，而且字符串的长度小于等于五十，可以直接三层暴力搜索即可。

    需要注意要考虑长度小于3的情况，刚开始没有考虑到，如果小于3，肯定是不符合的。
    AC代码

    #include 
    using namespace std;
    int main()
    {
      int n;
      cin >> n;
      string s1 = "DFS";
      string s2 = "dfs";
      while (n--)
      {
        bool flag1 = false;
        bool flag2 = false;
        int t;
        string s;
        cin >> t >> s;
        if (s.length() < 3)
        {
          cout << "0"
               << " "
               << "0" << endl;
          continue;
        }
        for (int i = 0; i < s.length() - 2; i++)
        {
          if (s[i] == 'D')
          {
            for (int j = i + 1; j < s.length() - 1; j++)
            {
              if (s[j] == 'F')
              {
                for (int k = j + 1; k < s.length(); k++)
                {
                  if (s[k] == 'S')
                  {
                    // 满足条件的
                    flag1 = true;
                  }
                }
              }
            }
          }
        }
        for (int i = 0; i < s.length() - 2; i++)
        {
          char c = s[i];
          if (s[i] == 'd')
          {
            for (int j = i + 1; j < s.length() - 1; j++)
            {
              if (s[j] == 'f')
              {
                for (int k = j + 1; k < s.length(); k++)
                {
                  if (s[k] == 's')
                  {
                    // 满足条件的
                    flag2 = true;
                  }
                }
              }
            }
          }
        }
        if (flag1 == true)
        {
          cout << "1"
               << " ";
        }
        else
        {
          cout << "0"
               << " ";
        }
        if (flag2 == true)
        {
          cout << "1" << endl;
        }
        else
        {
          cout << "0" << endl;
        }
      }
    }
    

    M牛客老粉才知道的秘密

    
    这道题目其实可以看做是数论和找规律的题目，属于div4了。

    每次只能显示6道题目，刚开始去模拟了一遍，超时间复杂度了，需要的是O(1)；

    可以这样想着，如果为6的整数，那么最左侧一道的可能性，往后移动应该是n/6，并且向右和向左是相同的位置

    如果不是6的整数呢？先移动n/6次，再+一次移动到了最右边。此时为n/6+1；
    从最右边往左开始移动，可以发现，最左边的位置和向右移动只可能在1的时候会有重复，其他是不可能重复的，因为刚才发生移位了。
    所以数量为n/6-1 。综上就是n/6*2；

    AC代码

    import java.util.Scanner;
    public class Main {
        public static void main(String[] args) {
            Scanner scanner=new Scanner(System.in);
            int t=scanner.nextInt();
            while (t-->0){
                int sum=0;
                int n=scanner.nextInt();
                int k=n%6;
                if (k!=0){
                    //简单的逻辑思维题目
                    int m=n/6;
                    sum+=m+m;
                }else{
                    sum+=n/6;
                }
                System.out.println(sum);
            }
        }
    }
    

    G why外卖

    这也是一道模拟题目，感觉是基本的高中数学题目，要想明白他们之间的关系，我感觉就可以了
    
    可以使用优惠卷，但是购买物品的价格必须大于所用的优惠卷，我刚开始在想如果花费价格小于优惠卷如何解决？
    其实这个问题是可以不同解决的。
    
    sum是可以减去的钱，sum+m可以你可以购买最大商品的价值，如果sum+m大于了当前的优惠卷，就可以ans就等于n+sum;
    但是如果现在是100 80 只有10块钱，那么不符合要求，为什么sum还要加上八十呢？
    这个80现在其实只是加在了sum里面，并没有加到ans里面。因为数组是升序的，也就是后面如果大于了，说明前面一定也是大于的。就可以加进来。

    package 牛客寒假训练营.第一场.G;
    import java.util.Arrays;
    import java.util.Scanner;
    class Money implements Comparable {
        long a;
    long b;
    public Money(long a, long b) {
        this.a = a;
        this.b = b;
    }
    @Override
    public int compareTo(Money other) {
        return Long.compare(this.a, other.a);
    }
    }
    public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            solve(scanner);
        }
    }
    static void solve(Scanner scanner) {
        int n = scanner.nextInt();
        long m = scanner.nextLong();
        Money[] c = new Money[100005];
        long ans = m;
        long sum = 0;
        for (int i = 1; i <= n; i++) {
            long a = scanner.nextLong();
            long b = scanner.nextLong();
            c[i] = new Money(a, b);
        }
        Arrays.sort(c, 1, n + 1); //排序，出来的按照优惠的价格进行排序
        for (int i = 1; i <= n; i++) {
            sum += c[i].b;//优惠的价格
            if (sum + m >= c[i].a) {
                ans = m + sum;
            }
        }
        System.out.println(ans);
    }
    }
    

    E 本题又主要考察了贪心

    不能被题目的名称所迷惑，说是贪心考点，其实并不是贪心。

    这道题在考场如何去做呢？先看数据范围。
    
    每次比赛都有三种对应的可能，m<=10，说明最多有十场比赛，也就是3的10次方，这个时间复杂度是可以接收的，可以想到用dfs去解决。

    #include 
    using namespace std;
    int n, m;
    int x[101], y[101];
    int ans, a[101];
    // u是对应的场数 当u>m表示比赛已经结束的时候
    void dfs(int u)
    {
        if (u > m)
        {
            int rank = 1;
            for (int i = 2; i <= n; i++)
                {
                    if (a[1] < a[i])
                        rank++;
                }
            ans = min(ans, rank);
            return;
        }
        a[x[u]] += 3;
        dfs(u + 1);
        a[x[u]] -= 3;
        a[y[u]] += 3;
        dfs(u + 1);
        a[y[u]] -= 3;
        a[x[u]]++;
        a[y[u]]++;
        dfs(u + 1);
        a[x[u]]--;
        a[y[u]]--;
    }
    int main()
    {
        int t;
        cin >> t;
        while (t--)
            {
                cin >> n >> m;
                ans = n;
                for (int i = 1; i <= n; i++)
                    {
                        cin >> a[i];
                    }
                for (int i = 1; i <= m; i++)
                    {
                        cin >> x[i] >> y[i];
                    }
                dfs(1);
                cout << ans << endl;
            }
    }
    

    其实就是可以看作为一个三叉树来看，每一次都是有A赢或者B赢或者AB平局，走遍每一个路径，需要找到最好的排名。时间复杂度 o(n*3^m);
    用a数组来存左边操作的玩家，用b数组来存储右边操作的玩家。
    dfs结束的条件，就是u>m表示游戏轮数结束了

    B 关鸡

    如何将这个鸡关在里面呢？
    
    想要这个鸡不跑出去有两个情况，第一个是需要四个点，各方在两边即可。第二个是三个火点直接将g包围即可。
    所以刚开始让ans1=4，ans2=3 看两个哪个小，ans2需要全部包围只能由一种情况，就是刚开始是包围的。并且如果n==0，一定是最小需要三个，直接包围起来。

    #include 
    #define int long long
    #define pii pair
    using namespace std;
    const int N=2e5+5;
    int t,n,m,k;
    int x,y,a[N],b[N];
    signed main() {
        cin>>t; // 输入测试用例数量
        while(t--) {
            cin>>n; // 输入点的数量
            if(n==0) { // 如果点的数量为0
                cout<<3< ma1,ma2; // 定义两个map，用于统计x=1和x=2的y的出现次数
            int ans1=4,ans2=3; // 初始化两个答案，分别对应x=1和x=2的情况
            bool ll=0,rr=0; // 判断左右区间是否有点
            for(int i=0;i
                cin>>x>>y; // 输入x和y
                if(x==1&&y==1) ans2--; // 如果x=1,y=1，ans2减1
                if(x==1&&y==-1) ans2--; // 如果x=1,y=-1，ans2减1
                if(x==2&&y==0) ans2--; // 如果x=2,y=0，ans2减1
                if(y<=0) ll=1; // 如果y<=0，左区间有点
                if(y>=0) rr=1; // 如果y>=0，右区间有点
                if(x==1) {
                    ma1[y]++; // 统计x=1的y出现的次数
                }
                if(x==2) {
                    ma2[y]++; // 统计x=2的y出现的次数
                }
            }
            if(ll) ans1--; // 如果左区间有点，ans1减1   左边有端点
            if(rr) ans1--; // 如果右区间有点，ans1减1   右边有端点
            bool l=0,r=0; // 判断左右区间是否有点
            for(auto it:ma1) {
                int p=it.first; // 获取y的值
                if(p<0) {
                    //存在一个点周围有其他点，那边这里肯定是出不去的 下面ans还需要--；
                    if(ma2[p-1]||ma2[p]||ma2[p+1]) l=1; // 如果左区间存在点，l置为1
                }
                if(p>0) {
                    if(ma2[p-1]||ma2[p]||ma2[p+1]) r=1; // 如果右区间存在点，r置为1
                }
            }
            if(l) ans1--; // 如果左区间有点，ans1减1
            if(r) ans1--; // 如果右区间有点，ans1减1
            cout< 
    这里用到了map来存储对应的地图值，暴力遍历的。
     
     
    C 按闹分配
     
    ##
    
    
    增加的不满意度就是 tc*排在鸡后面的人数，给定了最大不满意度，所以可以算出来最多人数为m/tc。向下进行取整
    此时再将排在鸡前面的时间加起来再加上鸡需要的时间，就是最早的时间了。
    AC代码
     
    #include
    #define int long long
    #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    const int N = 1e5+10;
    int t[N],s[N];
    int tt[N],ss[N];
    signed main(){
    	IOS;
    	int n,q,tc;
        cin >> n >> q >> tc;
        for(int i=1;i<=n;i++){
            cin >> t[i];
        }
        sort(t+1,t+1+n);
        for(int i=1;i<=q;i++){
            int m;
            cin >> m;
            int ans=0;
            int w=m/tc;
            for(int i=1;i<=n-w;i++) ans+=t[i];
            cout << ans+tc << '\n';
        }
    	return 0;
    }
     
     移动端页面设计  免费视频网站建设  web网页制作代码  数字广东网络建设公司  中国网站排名查询  百度推广找谁