2024牛客寒假算法基础集训营1

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

A DFS搜索

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

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

#include <bits/stdc++.h>
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<Money> {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 <bits/stdc++.h>
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 <bits/stdc++.h>
#define int long long
#define pii pair<double,double>
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) { // 如果点的数量为0cout<<3<<endl; // 输出3continue;}map<int,int> 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<n;i++) {cin>>x>>y; // 输入x和yif(x==1&&y==1) ans2--; // 如果x=1,y=1，ans2减1if(x==1&&y==-1) ans2--; // 如果x=1,y=-1，ans2减1if(x==2&&y==0) ans2--; // 如果x=2,y=0，ans2减1if(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减1if(r) ans1--; // 如果右区间有点，ans1减1cout<<min(ans1,ans2)<<endl; // 输出两个答案中的较小值}return 0;
}
//3 2 1 5 4
//3 4 5 1 2
/*abcabcabc*/  

这里用到了map来存储对应的地图值，暴力遍历的。

C 按闹分配

##


增加的不满意度就是 tc*排在鸡后面的人数，给定了最大不满意度，所以可以算出来最多人数为m/tc。向下进行取整
此时再将排在鸡前面的时间加起来再加上鸡需要的时间，就是最早的时间了。
AC代码

#include<bits/stdc++.h>#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;
}