牛客小白月赛68【A-E】
创始人
2024-06-01 01:46:18
0

文章目录

  • A.Tokitsukaze and New Operation【模拟】
  • B.Tokitsukaze and Order Food Delivery【模拟、特判】
  • C.Tokitsukaze and Average of Substring【暴力、前缀】
  • D.Tokitsukaze and Development Task【记忆化搜索】
  • E.Tokitsukaze and Colorful Chessboard【预处理,二分】

链接
传送门

A.Tokitsukaze and New Operation【模拟】

分析
根据题意模拟就行,合理运用STL可以简化代码。
实现

#include 
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair PII;
void solve() {string a, b;cin >> a >> b;int n = a.size(), m = b.size();if (n != m) {cout << -1 << '\n';return;}string ans;for (int i = 0; i < n; i++) {ans += to_string((a[i] - '0') * (b[i] - '0'));//to_stirng函数可以使得int转换为string类型}cout << ans << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}
}

B.Tokitsukaze and Order Food Delivery【模拟、特判】

分析
这题看似唬人,其实不难,因为这里只说了取一道菜所以只需暴力取最优的即可。
实现

#include 
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair PII;
void solve() {int n, a, b;cin >> n >> a >> b;int ans = inf;while (n--) {int k, x, y;cin >> k >> x >> y;while (k--) {int c;cin >> c;if (c >= a && c >= x) {c = max(0, c - b - y);} else if (c >= a) {c = max(0, c - b);} else if (c >= x) {c = max(0, c - y);}ans = min(ans, c);}}cout << ans << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}
}

C.Tokitsukaze and Average of Substring【暴力、前缀】

分析
这里n的范围是5000,我们可以直接枚举两端,对26个字母统计前缀字符数,即可,时间复杂度O(n^2*26),注意可能卡map,这里用数组。
实现

#include 
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair PII;
const int N = 5005;
char s[N];
int cnt[26][N];
void solve() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {for (int j = 0; j < 26; j++) {cnt[j][i] = 0;}}scanf("%s", s + 1);for (int i = 1; i <= n; i++) {char ch = s[i];for (int j = 0; j < 26; j++) {if (ch - 'a' == j) cnt[j][i] = cnt[j][i - 1] + 1;else cnt[j][i] = cnt[j][i - 1];//继承前缀}} 
//	for (int i = 0; i < 26; i++) {
//		for (int j = 1; j <= n; j++) {
//			cout << cnt[i][j] << ' ';
//		}
//		cout << '\n';
//	}double ans = 0;for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++) {int sum = 0;for (int k = 0; k < 26; k++) {int c = cnt[k][j] - cnt[k][i - 1];sum += c * (c - 1) / 2;//统计相同的对数}ans = max(ans, 1.0 * sum / (j - i + 1));}}printf("%.6lf\n", ans);
}
int main() {
//	ios::sync_with_stdio(false);
//	cin.tie(0);int T = 1;cin >> T;while (T--) {solve();}
}

D.Tokitsukaze and Development Task【记忆化搜索】

分析
首先300的数目步数最多300,总共有8种更新方法,求最小操作次数,但是这里组数有点多,考虑用记忆化搜索,总时间复杂度为O(n^2).
实现

#include 
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair PII;
const int N = 5005;
int go[6] = {1, -1, 10, -10, 100, -100};
int dp[305];
bool vis[305];
void bfs(int tar) {for (int i = 10; i <= 300; i++) vis[i] = 0;vis[10] = 1;queue q;q.push({10, 0});while (!q.empty()) {int x = q.front().first, s = q.front().second;if (x == tar) {//找到目标值就弹出,先进先出,所以步数是最小的dp[tar] = s;return;}q.pop();for (int i = 0; i < 8; i++) {int nx;if (i < 6) nx = x + go[i];else if (i == 6) nx = 10;else nx = 300;if (nx < 10 || nx > 300 || vis[nx]) continue;vis[nx] = 1;int ns = s + 1;q.push({nx, ns});}}
}
void solve() {int a, b, c, d;
//	cin >> a;
//	bfs(a);
//	cout << dp[a] << '\n';cin >> a >> b >> c >> d;if (dp[a] == -1) bfs(a);if (dp[b] == -1) bfs(b);if (dp[c] == -1) bfs(c);if (dp[d] == -1) bfs(d);cout << dp[a] + dp[b] + dp[c] + dp[d] << '\n';  
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;for (int i = 11; i <= 305; i++) dp[i] = -1;//0也算,所以初始化-1while (T--) {solve();}
}

E.Tokitsukaze and Colorful Chessboard【预处理,二分】

分析
为了更加充分地利用空间,我们需要紧凑地使用格子,所以把棋盘分成奇数格和偶数格使用,预处理平方数,可以得到所有奇数格的数目和偶数格的数目,如果平方数是偶数则两者一样多否则奇数多1个,我们查询的两个数较大的那一个放在奇数格上,利用二分,但是,此时另一个数可能不行,因为如果说这个数是对应的平方数是奇数,而两者又是一样大的话,是无法放入的,例如:n=3,b[3]=5,c[3] = 4, x = y = 5,必须往右挪一格(可能前面有需要几格的,但是不多)到y符合,在向右挪的时候由于单调性,x始终符合。注意爆int。
实现

#include 
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair PII;
const int N = 1e5 + 5;
int go[6] = {1, -1, 10, -10, 100, -100};
ll a[N], b[N], c[N];
void solve() {ll x, y;cin >> x >> y;if (x < y) swap(x, y);int n = 1e5;int p = lower_bound(b + 1, b + 1 + n, x) - b;
//	cout << b[p] << '\n';while (c[p] < y) p++;//稍微挪一格左右cout << p << '\n'; 
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;int m = 1e5;for (int i = 1; i <= m; i++) a[i] = 1ll * i * i;//这里爆intfor (int i = 1; i <= m; i++) {b[i] = (a[i] + 1) / 2;c[i] = a[i] - b[i];}
//	cout << b[70000] << '\n';
//	for (int i = 1; i <= 5; i++) cout << c[i] << '\n';while (T--) {solve();}
}

相关内容

热门资讯

安卓系统对比骁龙,性能与生态的... 你有没有想过,为什么你的手机里装的是安卓系统,而不是苹果的iOS呢?又或者,为什么你的安卓手机里搭载...
qt程序安卓系统运行,基于Qt... 你有没有想过,为什么有些手机上的程序运行得那么顺畅,而有些却总是卡得让人抓狂?今天,就让我来给你揭秘...
安卓系统免费应用推荐,助你畅享... 手机里的应用是不是越来越多,有时候都挑花眼了呢?别急,今天我就来给你推荐一些安卓系统上的免费应用,让...
安卓系统视频通话app,打造无... 你有没有发现,现在手机上的视频通话功能越来越强大了?尤其是安卓系统上的那些视频通话app,简直让人爱...
安卓系统发现高危病毒,守护手机... 亲爱的手机用户们,最近可是有个大消息在安卓系统用户群里炸开了锅!没错,就是安卓系统发现了一款高危病毒...
安卓系统疯狂弹广告,揭秘广告软... 你有没有遇到过这种情况?手机里突然弹出一个广告,让你瞬间心情大崩溃?没错,说的就是安卓系统那让人头疼...
ebook 10进入安卓系统 你有没有发现,最近你的安卓手机里多了一个新伙伴——那就是电子书(ebook)10!没错,就是那个我们...
安卓系统如何调听筒,安卓系统调... 手机听筒声音突然变小了?别急,让我来教你如何轻松调教安卓系统的听筒,让它重新恢复活力!一、检查音量设...
安卓系统是怎么手机,解锁智能生... 你有没有想过,我们每天不离手的安卓手机,它背后的安卓系统究竟是怎么一回事呢?今天,就让我带你一探究竟...
安卓系统能代替windows系... 你有没有想过,我们日常使用的安卓系统和Windows系统,哪个才是真正的霸主呢?是不是有时候觉得安卓...
lp108安卓系统,功能特点与... 你有没有听说最近LP108安卓系统火得一塌糊涂?没错,就是那个让无数手机用户都为之疯狂的新系统!今天...
安卓系统挂载u盘,轻松实现数据... 你有没有想过,你的安卓手机或平板电脑突然变成了一个移动的U盘?没错,就是那种可以随意存取文件的神奇设...
i5 安卓系统,引领智能终端新... 你有没有想过,为什么你的手机总是卡得要命,而别人的手机却能流畅如丝?是不是因为你的手机搭载了那个传说...
安卓手机系统没有升级,揭秘潜在... 你有没有发现,你的安卓手机系统好像好久没升级了呢?是不是觉得有点out了?别急,今天就来给你详细聊聊...
安卓14系统定制v,创新功能与... 你知道吗?最近安卓系统又出新花样了!安卓14系统定制版V,这名字听起来就让人兴奋不已。今天,就让我带...
手机安卓系统越高越好,探索最新... 你有没有发现,每次手机更新系统,你的手机就像脱胎换骨了一样?没错,说的就是你,那个安卓手机!今天,咱...
鸿蒙系统怎么用回安卓,轻松实现... 你是不是也和我一样,对鸿蒙系统的新鲜感还没过,却又忍不住想回到熟悉的安卓世界?别急,今天就来手把手教...
苹果7跟安卓系统,性能对决与用... 你有没有想过,为什么苹果7那么受欢迎,而安卓系统却有着庞大的用户群体?今天,我们就来聊聊这个话题,看...
安卓手机刷简化系统,轻松实现流... 你有没有想过,你的安卓手机其实可以变得更加轻快、流畅呢?没错,就是通过刷简化系统!今天,就让我带你一...
社保掌上通安卓系统,轻松掌握在... 你有没有发现,现在的生活越来越离不开手机了?无论是购物、聊天还是办公,手机都能轻松搞定。这不,今天就...