首页 > 编程语言 >2024牛客寒假算法基础集训营1（补题）

2024牛客寒假算法基础集训营1（补题）

时间：2024-02-27 14:46:24浏览次数：195  
标签：int rep cin long 2024 补题 ans 集训营 define

目录

A

n的范围很小暴力直接\(O(n^3)\)直接做就行。
我还傻的统计了一下前后缀，不过怎么写都行这道题。

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second

using namespace std;

const int N=30,mod=1e9+7;
int n,m,a[N],b[N],k;
int f[60][60];
char s[60];
int l[60],r[60]; 
bool st=false;



void solve()
{
	int n;cin>>n;
	rep(i,1,59)	l[i]=r[i]=0;
	cin>>(s+1);
	//DFS
	map<char,int>cnt;
	rep(i,1,n)
	{
		if(cnt.find('D')!=cnt.end())	l[i]=1;
		cnt[s[i]]=1;
	}
	cnt.clear();
	fep(i,n,1)
	{
		if(cnt.find('S')!=cnt.end())	r[i]=1;
		cnt[s[i]]=1;
	}
	//
	bool st=1;
	rep(i,1,n)
	{
		if(s[i]=='F'&&l[i]==1&&r[i]==1)
		{
			cout<<1<<' ';
			st=0;
			break;
		}
	}
	if(st)	cout<<0<<' ';
	
	
	//dfs
	st=1;
	rep(i,1,59)	l[i]=r[i]=0;
	cnt.clear();
	
	rep(i,1,n)
	{
		if(cnt.find('d')!=cnt.end())	l[i]=1;
		cnt[s[i]]=1;
	}
	cnt.clear();
	fep(i,n,1)
	{
		if(cnt.find('s')!=cnt.end())	r[i]=1;
		cnt[s[i]]=1;
	}
	rep(i,1,n)
	{
		if(s[i]=='f'&&l[i]==1&&r[i]==1)
		{
			cout<<1<<' ';
			st=0;
			break;
		}
	}
	if(st)	cout<<0<<' ';
	cout<<endl;
}

signed main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
  	int _;
	cin>>_;
	while(_--)
	solve();
	return 0;
}

B

赛时的思路是：周围三个点特判，然后左边求最小和右边求最小，最后和特判取最小。
代码写的比较一坨很乱，最后也没调出来。
遇见这种感觉还是重写吧。
主要就是分类讨论

  1. 看鸡左边被堵没有
  2. 看鸡右边被堵没有
  3. 看鸡左边有没有火
  4. 看鸡右边有没有火
  5. 特判（2，0）
    自己写的太丑了，放一份加了注释的jls的代码吧。
#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    
	//left1表示左边是否有火，right1表示右边是否有火
	//left2表示左边是否能堵住鸡，right2表示右边是否能堵住鸡
    int left1 = 0, left2 = 0;
    int right1 = 0, right2 = 0;
    
    std::set<std::pair<int, int>> s;
    for (int i = 0; i < n; i++) {
        int r, c;
        std::cin >> r >> c;
        
        if (c <= 0) {
            left1 = 1;
        }
        if (c >= 0) {
            right1 = 1;
        }
        s.emplace(r, c);
    }
    
    for (auto [r, c] : s) {
        if (!c) {
            continue;
        }
		//这里和3异或真的简化了很多代码
        if (s.count({r ^ 3, c}) || s.count({r ^ 3, c + (c > 0 ? -1 : 1)})) {
            if (c > 0) {
                right2 = 1;
            } else {
                left2 = 1;
            }
        }
    }
    
    int ans = 4 - left1 - left2 - right1 - right2;
    ans = std::min(ans, int(3 - s.count({2, 0}) - s.count({1, -1}) - s.count({1, 1})));
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

C

\(S_{min}=所有人办事的时间+等待时间\)
\(等待时间=T_1 * n + T_2 * (n-1)+...+ T_n * 1\)
这就转化成了一个经典的问题排序不等式
当\(T_1、T_2、...、T_n\)按从小到大的对应和n~1相乘
然后看鸡能查到谁的前面

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second

using namespace std;

const int N=1e5+10,mod=1e9+7;
int n,q,tc;
int t[N],d[N];

//x为鸡插队的时间
bool check(int x,int m)
{
	//找到受鸡插队影响的第一个位置 
	int l=1,r=n;
	int k=upper_bound(d+1,d+1+n,x)-d;
	int sum=(n-k+1)*tc;
	return sum<=m;
}

void solve()
{
	cin>>n>>q>>tc;
	rep(i,1,n)	cin>>t[i];
	sort(t+1,t+1+n);
	int sm=0;
	//计算每个人不满意度,sm就是没插队的最小不满意度 
	//di也是每个人完成工作的时间 
	rep(i,1,n)	d[i]=d[i-1]+t[i],sm+=d[i];
	
	rep(i,1,q)
	{
		int m;cin>>m;
		int l=0,r=d[n];
		while(l<r)
		{
			int mid=(l+r)>>1;
			if(check(mid,m))	r=mid;
			else	l=mid+1;
		}
		cout<<l+tc<<endl;
	}
}

signed main()
{
	IOS	
//   	freopen("1.in", "r", stdin);
  	int _;
//	cin>>_;
//	while(_--)
	solve();
	return 0;
}

D

代码是参考jls的，写的真的很优雅
思路：
这里有一个小\(trick\),数相乘的话会很大，而\(M\)只有\(1e9\),\(2^30\)就会到达\(1e9\)。
也就是说，不为0的数相乘很快会超范围有很多不合法的。
对于相同的数，平移的话是都是一样的。
我们考虑不同的数有多少个。
不同的数最多有20个，20个的话就会相乘就会超范围。
然后里面就暴力去瞎搞就行

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define _for(i,a,b) for(int i=(a); i<(b); ++i)
#define pii pair<int, int>
#define pdd pair<double,double>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
#define vi vector<int>

using namespace std;
const int maxn=1e5+10,mod=1e9+7,K=4e4,inf=1e9;


void solve() {
	int n,Q;
	cin>>n>>Q;
	map<int,int>cnt;
	rep(i,1,n) {
		int a;
		cin>>a;
		cnt[a]+=1;
	}
	set<int>s{0};
	//只有当不同的数为20个以内时乘起来才不会超出范围
	if(cnt.size()<=20) {
		//将map中的内容复制到vector中
		vector<pii>a(cnt.begin(),cnt.end());
		int n=a.size();
		int d=a[0].x-K;
		//枚举每一个数
		_for(i,0,n) {
			//枚举每一个数进行两种操作的总的变化量
			for(d=max(d,a[i].x-K); d<=a[i].first+K;d++) {
				//从前往后算一遍答案				
				int res=1;
				_for(j,0,n) {
					//看一下这个数会变成的数，v
					int v=a[j].x-d;
					//1的话对res没有影响
					if(v==1) {
						continue;
					}
					//-1的话看值为这个数的有多少个
					if(v==-1) {
						if(a[j].y%2==1) {
							res*=-1;
						}
						continue;
					}
					//两个都不是的话就把，所有值为这个数的都乘上去
					_for(c,0,a[j].y) {
						res*=v;
						//中间溢出范围直接退出
						if(abs(res)>inf) {
							break;
						}
					}
					//溢出的话直接退出
					if(abs(res)>inf) {
						break;
					}
				}
				//满足的话用set存一下，供查询
				if(abs(res)<=inf) {
					s.insert(res);
				}
			}
		}
	}
	while(Q--) {
		int M;
		cin>>M;
		if(s.count(M)) {
			cout<<"Yes"<<endl;
		} else {
			cout<<"No"<<endl;
		}
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen("1.in", "r", stdin);
	int _;
//	cin>>_;
//	while(_--)
	solve();
	return 0;
}

E

e题看到数据范围n和m都很小，dfs，对于每场比赛，ab两位选手，考虑每场比赛。
ab两位选手

  1. a胜b败
  2. a败b胜
  3. ab平局
#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second

using namespace std;

const int N=20,mod=1e9+7;
int n,m,ans;
struct node
{
	int val,idx;
	bool operator <(const node t)
	{
		return val>t.val;
	}
}a[N],b[N];

PII op[N];

void dfs(int u)
{
	if(u==m+1)
	{
		memcpy(b,a,sizeof a);
		sort(b+1,b+1+n);
//		cout<<"AAAAAA"<<endl;
//		rep(i,1,n)	cout<<a[i].idx<<' '<<a[i].val<<endl;
		int k=0;
		rep(i,1,n)	if(b[i].idx==1)	k=i;
		ans=min(ans,k);
		return;
	}
	int x=find(op[u].x),y=find(op[u].y);
	//x胜
	a[x].val+=3;
	dfs(u+1); 
	a[x].val-=3;
	
	//y胜
	a[y].val+=3;
	dfs(u+1); 
	a[y].val-=3;
	
	//平局
	a[x].val+=1;
	a[y].val+=1;
	dfs(u+1); 
	a[x].val-=1;
	a[y].val-=1;
}

void solve()
{
	cin>>n>>m;
	ans=n;
	rep(i,1,n)
	{
		int x;cin>>x;
		a[i]={x,i};
	}
	int k=0;
	rep(i,1,m)
	{
		int x,y;cin>>x>>y;
		if(x>y)	swap(x,y);
		op[++k]={x,y};
	}
	dfs(1);
	cout<<ans<<endl;
    return;
}

signed main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
  	int _;
	cin>>_;
	while(_--)
	solve();
	return 0;
}

F

考的是知识点 第二类斯特林数
从题目还是比较容易看出来这是一道第二类斯特林数的题目的，直接从前往后求一遍通项公式。
需要补一下组合数学的知识
d7039fd6bc9ff6fe6361180a79f2f5b.jpg
image

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pdd pair<double,double>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
#define vi vector<int>

using namespace std;
const int maxn=1e6+10,mod=1e9+7;

int ksm(int a,int b, int p){
	int res=1;
	while(b){
		if(b&1)	res=res*a%p;
		a=a*a%p;
		b>>=1;	
	}
	return res;
}
int fac[maxn],invfac[maxn];
void solve() {
	int n,m;
	cin>>n>>m;
// 	vi fac(n+1),invfac(n+1);
	fac[0]=invfac[0]=1;
	rep(i,1,maxn){
		fac[i]=fac[i-1]*i%mod;
		invfac[i]=ksm(fac[i],mod-2,mod);
	}      
	int ans=0;
	rep(i,0,m){
		ans+=((m-i)&1?-1:1)*ksm(i,n,mod)%mod*invfac[i]%mod*invfac[m-i]%mod;
        ans%=mod;
	}
	cout<<(ans+mod)%mod<<endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen("1.in", "r", stdin);
	int _;
//	cin>>_;
//	while(_--)
	solve();
	return 0;
}

G

前缀和,先对优惠卷按价格排序，然后根据优惠卷可叠加，我们可以知道只要优惠的钱+m>=商品原价就可以更新答案。

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second

using namespace std;

const int N=1e5+10,mod=1e9+7;
int n,m;
struct node
{
	int x,y;
	bool operator <(const node t)
	{
		return x<t.x;	
	} 
}a[N];

void solve()
{
	cin>>n>>m;
	rep(i,1,n)	cin>>a[i].x>>a[i].y;
	sort(a+1,a+1+n);
	int ans=0,sum=0;
	rep(i,1,n)
	{
		sum+=a[i].y;
		if(sum+m>=a[i].x)
		{
			ans=max(ans,sum+m);
		}
	}
	if(!ans)	cout<<m<<endl;
	else	cout<<ans<<endl;
}

signed main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
  	int _;
	cin>>_;
	while(_--)
	solve();
	return 0;
}

H

位运算贪心
涉及到位运算的题一定要把数字当成二进制串看
并且不存在进位意味着--位和位之间是独立的。
一般都是贪心的考虑每一位。

对于m我们设第x位为1，设选中的物品与起来为sum，如果sum的第x位为0，那么第x位之后所有的位都是任意的

  • 枚举第x位
  • 选择物品的第x位是0
  • 选择物品的高位应该是m高位的子集
  • 低位任意
#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;

void solve()
{
	int n,m;cin>>n>>m;
	vector<int>v(n+1),w(n+1);
	rep(i,1,n)	cin>>v[i]>>w[i];
	
	int ans=0;
	auto check=[&](int s)
	{
		int res=0;
		rep(i,1,n)
		{
            //==的优先级高于&
			if((s&w[i])==w[i])
			{
				res+=v[i];
			}
		}
		ans=max(ans,res);
	};
	
	check(m);
	fep(i,29,0)
	{
		if((m>>i)&1)
		{
			check(m^(1<<i)|((1<<i)-1));	
		}
	}

	cout<<ans<<endl;
	return;
}
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
  	int _;
	cin>>_;
	while(_--)
	solve();
	return 0;
}

I

两种方式的区别在于半径。
我们可以模拟题目中的过程然后在本地多跑几组数据看看r的均值有什么规律
技巧就是打表找规律

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;
const int N=2010;

int mod=1e9+7;

void solve()
{
	int n;cin>>n;
	int s=0;
	rep(i,1,n)
	{
		int x,y,r;cin>>x>>y>>r;
		s+=r;
	}
	if(s/n<20.0)	cout<<"bit-noob"<<endl;
	else	cout<<"buaa-noob"<<endl;
	return;
}
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
  	int _;
	cin>>_;
	while(_--)
	solve();
	return 0;
}

K

基环树

L

这道题应该是个签到题。主要是题面有点吓人。
直接考虑光源在最下面，这种情况地上的未被照射到的面积应该是最大的。
面积很好求，就是一个等腰梯形的面积。

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second

using namespace std;

const int N=1e5+10,mod=1e9+7;
int n,q,tc;

void solve()
{
	int c,d,h,w;cin>>c>>d>>h>>w;
	db ans=1.0*(6*w)*c/2;
	printf("%.5lf\n",ans);
}
signed main()
{
// 	IOS	
//  	freopen("1.in", "r", stdin);
  	int _;
	cin>>_;
	while(_--)
	solve();
	return 0;
}

标签：int,rep,cin,long,2024,补题,ans,集训营,define
From： https://www.cnblogs.com/cxy8/p/18005065

相关文章

  • 2024-02-27-物联网系统编程(7- 共享内存)
    7.共享内存7.1共享内存概述​共享内存允许两个或者多个进程共享给定的区域共享内存的特点共享内存是进程间共享数据的一种最快的方法；一个进程向共享的内存区域写入了数据，共享这个内存区域的所有进程就可以立刻看到其中的内容。使用共享内存要注意的是多个进程之......
  • 20240219
    State的使用在Compose中，我们可以使用State来管理数据，State是一个可以被观察的数据，当数据发生变化时，State会通知所有的观察者。我们可以使用State来管理UI的状态，比如显示和隐藏组件、改变组件的样式等。什么时候使用State当我们需要管理UI的状态时，我们可以使用State。比如，当我们......
  • 20240218
    记账本App主页页面的绘制记账本App的主页界面绘制@OptIn(ExperimentalMaterial3Api::class)@ComposablefunExpenseTrackerApp(appViewModel:ExpenseTrackerViewModel=viewModel()){valappUiStatebyappViewModel.uiState.collectAsState()Box(modifie......
  • 【2024-02-18】连岳摘抄
    23:59在即将远行和改变生活方式的时刻，善于反省的人总怀着一种严肃的心情。每逢这样的时刻，人们通常是检查过去和计划未来。                                                ......
  • 【2024-02-17】连岳摘抄
    23:59尽管如此，还要坚持，希望就像盐巴一样，没有营养，但它给面包增添了味道。                                                 ——若泽·萨拉马戈强者可以制定规则，强者......
  • 2024-02-27-物联网系统编程(6-消息队列)
    6.消息队列6.1IPC对象​除了最原始的进程间通信方式信号、无名管道和有名管道外，还有三种进程间通信方式，这三种方式称之为IPC对象:消息队列、共享内存、信号灯集。​IPC对象也是在内核空间开辟区域，每一种IPC对象创建好之后都会将其设置为全局，并且会给其分配一......
  • 2024 省选复习 (updating)
    前言快省选了，在复习，但是不知道干什么。所以就写点东西吧。就是瞎写写，所以可能有很多错误，如果发现了欢迎指出。常见错误&注意事项数组不能开大，也不能开小题目要求什么千万不能读错，最好手算一下样例算法复习树状数组进阶P6619原本是树状数组二分的模板题，但是用......
  • 20240226
    非常意识流的日记，精神状态极度不佳下打出来的。模拟赛垫底，不过是意料之中的，没造成太大影响。下午也很正常，一直在硬刚Border，不过有些微疲倦。晚自习就开始颓废了，不想学习。然后下去散步的时候唐了，成小丑了，破防了。当时看到青蛙的博客时真正体会到了什么是「整个人都麻了」的......
  • 2024.2.26
    前言还有\(4\)天就结束了呜呜呜，我还不想走，我还没打过国赛呜呜呜。博弈以为是个吊题，结果真是签到题啊QAQ。首先我们要读明白题，我们一个点可以放多个棋子，所以可以得出一个结论：每个点是互不影响的。所以我们可以每个点分开来算。正如题解所说：“因为在自己所属点上的棋子是完......
  • 近期总结 2024.2.26
    dp专场*2。CF1608FMEXCounting题意：给出\(n,m,b_{1...n}\)，求出有多少个长度为\(n\)的序列\(a\)满足\(\foralli\in[1,n],\space0\lea_i\len\)且\(|\operatorname{mex}\{a_1,a_2,...,a_i\}-b_i|\lem\)。\(1\len\le2000,\space1\lek\le50\)很简单的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99