牛客小白月赛

朱雀 2024-03-03 08:56 101阅读 0赞

[(0条未读通知) 牛客小白月赛78\_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛\_牛客竞赛OJ (nowcoder.com)][0_ _78_ACM_NOI_CSP_CCPC_ICPC_OJ _nowcoder.com]

### C.第K小表示数 ###

两种写法

法一：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll; 
    const int N  = 1e9 + 10;
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    ll k, a, b, p;
    map<ll, ll> v;
    int main()
    {
    	cin >> k >> a >> b;
    	pq.push(a);
    	v[a] = 1;
    	if(v[b] == 0)
    	{
    		pq.push(b);
    		v[b] = 1;
    	}
    	while(k --)
    	{
    		p = pq.top();
    		if(v[p + a] == 0)
    		{
    			pq.push(p + a);
    			v[p + a] = 1;
    		}
    		if(v[p + b] == 0)
    		{
    			pq.push(p + b);
    			v[p + b] = 1;
    		}
    		pq.pop();
    	}
    	cout << p;
    	return 0;
    }

法二：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll k, a, b, q;
    set<ll>st;
    int main()
    {
    	cin >> k >> a >> b;
    	while(k --)
    	{
    		q = *st.begin();
    		st.insert(q + a);
    		st.insert(q + b);
    		st.erase(q);
    	}
    	cout << *st.begin();
    	return 0;
    }

### D.数树 ###

一种规律

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int M = 1e9 + 7;
    ll t, n, ans;
    int main()
    {
    	cin >> t;
    	while(t --)
    	{
    		ans = 0;
    		cin >> n;
    		for(ll k = 1; k <= n; k <<= 1)
    		{
    			ans += (n - k + 1) / k;
                ans %= M;
    		}
    		cout << ans << '\n';
    	}
    	return 0;
    }

### E.自动计算机 ###

eg.如果n == 10,x = 7, 只需要计算是否有pre\[i\] == 3即可，当然要求最短

num\[pre\[i\]\]存的是pre\[i\]这个数第一次出现的位置

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1e5 + 10;
    ll n, m, x, ans, num[N], a[N], pre[N]; 
    int main()
    {
    	cin >> n >> m >> x;
    	for(int i = 1; i <= n; i ++)num[i] = -1;
    	for(int i = 1; i <= m; i ++)
    	{
    		cin >> a[i];
    		pre[i] = pre[i - 1] + a[i];
    		pre[i] %= n;
    		if(num[pre[i]] == -1)num[pre[i]] = i;//记录需要走的步数（最少） 
    	}
    	ans = -1;
    	for(int i = 1; i <= n; i ++)//枚举轮数，最多走n轮，n轮就会出现循环
    	{
    		ll tmp = n - x;
    		if(!x)//此处说明已经到达目的地，但之前走过了（i- 1）轮 
    		{
    			ans = (i - 1) * m;
    			break;
    		} 
    		if(num[tmp] != -1)//说明还能走 
    		{
    			ans = 1ll * (i - 1) * m + num[tmp];//此处说明之前走了i - 1轮，再加上需要走的最少步数就可以到达目的地 
    			break; 
    		}
    		x = (x + pre[m]) % n;//不断更新 
    	}
    	cout << ans;
    	return 0;
    }

[0_ _78_ACM_NOI_CSP_CCPC_ICPC_OJ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/65157#question