当前位置：网站首页>牛客小白月賽52

牛客小白月賽52

2022-06-30 08:01:00 【晁棠】

牛客小白月賽52

Problem A

直接分類討論判斷，7點每次到，八點1分~5分遲到，其餘曠課。

Problem B

模擬，按10比特數的規則去試是否可以進比特。注意當看到 5000 的時候可以進比特變成 10000 。

Problem C

前綴和維護區間累加，最後看哪一部分累加次數最少，此時除了該指令外其他指令都是錯的情况下是錯誤指令最多的。

Problem D

樹狀數組 & ST錶

一個圓桌，所以要增長至2倍。由題意的值每次只能取一個圓弧（也可以是整圓），依次枚舉從每個蛋糕開始吃，用二分找出在能吃飽的情况下吃到哪一個蛋糕，然後再用ST錶找到這一區間內的奶油最大值。時間複雜度 O ( n log ⁡ n ) O(n\log n) O(nlogn)

這種方法過了，但在寫題解的時候有點疑惑為什麼能過，感覺這麼枚舉似乎不能恰好保證奶油量最高的最低的所在的奶油組是不包括其他更高的奶油吧？好像我也錶達不太清楚。

Problem E

一開始想了想平衡數，抄了一發模板然後WA了，因為沒有考慮後面加入的組的元素的貢獻。

題解的正解是：二分加容斥

找出需求值在所有數之中的貢獻，再减去需求值在該組之中的貢獻即可。

Problem F

分組背包，沒做。

Code：

Problem A


// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm> 
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;



int n, T = 1;

void ready()
{
    
	int a = 0, b = 0;
	cin >> n;
	while (n--) {
    
		string st;
		cin >> st;
		if (st[0] == '7') continue;
		if (st[0] == '9') b++;
		if (st[0] == '8') {
    
			int t = (st[2] - '0') * 10 + st[3] - '0';
			if (t <= 5 && t != 0) a++;
			else if (t > 5) b++;
		}
	}
	cout << a << ' ' << b << '\n';
}


void work()
{
    

}

signed main()
{
    
	IOS;
	cin>>T;
	while (T--) {
    
		ready();
		work();
	}
	return 0;
}

Problem B


// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm> 
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;



int n, T = 1;

void ready()
{
    
	cin >> n;
}


void work()
{
    
	int t = 1, ans = n;
	if (ans < 10) {
    
		if (ans >= 5) ans = 10;
	}
	while (n >= t) {
    
		t *= 10;
		int b = n % t; 
		if (b >= 10) while (b >= 10) b = b / 10;
		n = n / t * t;
		if (b >= 5) n += t;
		//cout << "b=" << b << '\n';
		ans = max(ans, n);
		//cout << "n= " <<n<< '\n';
		//cout << "t=" << t << '\n'<<'\n';
	}
	cout << ans << '\n';
}

signed main()
{
    
	IOS;
	cin>>T;
	while (T--) {
    
		ready();
		work();
	}
	return 0;
}

Problem C


// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm> 
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;


const int N = 1e6 + 6;
int n, T = 1, m;
int sum[N];

void ready()
{
    
	cin >> n >> m;
	ffor(i,1,m) {
    
		int op, x, y;
		cin >> op;
		if (op == 1) {
    
			cin >> x >> y;
			sum[x]++; sum[y + 1]--;
		}
		if (op == 2) {
    
			cin >> x;
			sum[x]++;
		}
		if (op == 3) {
    
			cin >> x;
			sum[1]++; sum[x+1]--;
		}
	}
	int ans = inf, cnt = 0;
	ffor(i, 1, n) {
    
		sum[i] += sum[i - 1];
		ans = min(sum[i], ans);
	}
// ffor(i, 1, n) cout << sum[i] << ' '; cout << '\n';
	cout << m - ans << ' ';
	ffor(i, 1, n) {
    
		if (sum[i] == ans) {
    
			cnt++;
		// cout << "i=" << i << '\n';
		}
	}
	cout << cnt;
}


void work()
{
    

}

signed main()
{
    
	IOS;
	// cin>>T;
	while (T--) {
    
		ready();
		work();
	}
	return 0;
}

Problem D


// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm> 
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;


const int N = 1e6 + 5;;
int n, T = 1, s;
int b[N], d[N][22];

int lowbite(int x)
{
    
	return x & (-x);
}

void add_in(int i, int num, int c[])
{
    
	while (i <= n * 2)
	{
    
		c[i] += num;
		i += lowbite(i);
	}
	return;
}

int get_sum(int x, int c[])
{
    
	int sum = 0;
	while (x)
	{
    
		sum += c[x];
		x -= lowbite(x);
	}
	return sum;
}

void ready()
{
    
	cin >> n >> s;
	ffor(i, 1, n) {
    
		int bi;
		cin >> bi;
		add_in(i, bi, b);
		add_in(i + n, bi, b);
	}
	ffor(i, 1, n) {
    
		int di;
		cin >> di;
		d[i][0] = d[n + i][0] = di;
	}
	ffor(j, 1, 19) {
    
		ffor(i, 1, 2 * n) {
    
			d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
		}
	}
}

int get_max(int x, int y)
{
    
	int mid = log2(y - x + 1);
	return max(d[x][mid], d[y - (1 << mid) + 1][mid]);
}

void work()
{
    
	if (get_sum(n, b) < s) {
    
		cout << -1;
		return;
	}
	int ans = inf;
	for (int i = 1; i <= n; i++) {
    
		int l = i, r = n + i - 1, mid;
		while (l < r) {
    
			mid = l + r >> 1;
			if (get_sum(mid, b) - get_sum(i - 1, b) < s) l = mid + 1;
			else r = mid;
		}
		ans = min(ans, get_max(i, l));
	}
	cout << ans;
}

signed main()
{
    
	IOS;
	// cin>>T;
	while (T--) {
    
		ready();
		work();
	}
	return 0;
}

Problem E


// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm> 
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;

const int N = 1e6 + 6;
const int mod = 998244353;

int n, T = 1, k;
vector<int> ve[N], alls;

void ready()
{
    
	cin >> n >> k;
	ffor(i, 1, n) {
    
		int s;
		cin >> s;
		ffor(j, 1, s) {
    
			int x;
			cin >> x;
			alls.push_back(x);
			ve[i].push_back(x);
		}
		sort(ve[i].begin(), ve[i].end());
	}
	sort(alls.begin(), alls.end());
}


void work()
{
    
	int ans = 0;
	ffor(i, 1, n) {
    
		for (auto item : ve[i]) {
    
			int x = k - item;
			ans += (alls.end() - lower_bound(alls.begin(), alls.end(), x)) - (ve[i].end() - lower_bound(ve[i].begin(), ve[i].end(), x));
		}
	}
	ans /= 2;
	cout << ans % mod;
}

signed main()
{
    
	IOS;
	// cin>>T;
	while (T--) {
    
		ready();
		work();
	}
	return 0;
}
原网站

版权声明
本文为[晁棠]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/181/202206300759259995.html

边栏推荐

猜你喜欢

随机推荐