代码编织梦想

AtCoder Beginner Contest 332 - AtCoder

打的最难受的一集,前三题阅读理解,D暴力没想出来,E典的子集dp,F一眼区间乘加的线段树但是没时间写,掉大分,要被新生单调队列优化了

A - Online Shopping

题意:

购物,N种商品,每种商品Pi元买Qi个,满S元包邮,否则加K元邮费,问实付多少

题解:

void solve()
{
	int n, s, k;
	LL sum = 0;
	scanf("%d%d%d", &n, &s, &k);
	for (int i = 1; i <= n; ++i)
	{
		int p, q;
		scanf("%d%d", &p, &q);
		sum += p * q;
	}
	if (sum < s)sum += k;
	printf("%lld\n", sum);
}

B - Glass and Mug

题意:

给了俩杯子A, B,容量分别为G, M(初始都为空),你需要进行以下操作K次

1、如果A满了,把A的水全倒了

2、若不满足1,且B空了,则把B杯装满水

3、若同时不满足以上两种情况,则把B中的水往A里倒,直到A满了或者B空了

题解:

K很小,模拟即可

void solve()
{
	int k, g, m, a = 0, b = 0;
	scanf("%d%d%d", &k, &g, &m);
	while (k--)
	{
		if (a == g)
			a = 0;
		else if (b == 0)
			b = m;
		else
		{
			int t = min(g - a, b);
			a += t, b -= t;
		}
	}
	printf("%d %d\n", a, b);
}

C - T-shirts

题意:

你有N天的日程安排,刚开始你拥有M件干净的白T恤,给出一个长N的仅由'0', '1', '2'构成的字符串,若第i个字符为'0'则这天蹲家,为'1'则去吃饭,为'2'则去打比赛。

去吃饭需要穿一件干净的白T恤或者带有标志的T恤,打比赛需要穿一件干净的带有标志的T恤,每件T恤在被穿过之后将变脏,在休息日你不需要穿T恤并且你将在这天洗好你的所有脏T恤。

问你至少需要采购几件干净的带标志的T恤来满足你的日程安排。

题解:

模拟,优先花费白T恤即可

char ch[N];
void solve()
{
	int n, m, ans = 0;
	scanf("%d%d%s", &n, &m, ch + 1);
	ch[n + 1] = '0';
	for (int i = 1, x = 0, y = 0; i <= n + 1; ++i)
	{
		if (ch[i] == '0')
		{
			ans = max(ans, y + max(0, x - m));
			x = 0, y = 0;
		}
		else if (ch[i] == '1')
			++x;
		else
			++y;
	}
	printf("%d\n", ans);
}

D - Swapping Puzzle

题意:

给出两个N行M列的整数矩阵A、B,你可以进行以下操作:1、交换A的相邻两行,2、交换A的相邻两列。问至少进行多少次操作能够使得A=B,若不能输出-1

题解:

暴力枚举所有进行行交换与列交换的结果(如设初始每行的编号1,2,3,进行交换后可能为1,3,2...)共计n!*m!种,再暴力模拟交换操作(类似冒泡的交换操作就能做到最小次数交换)同时记录交换次数cnt,交换完之后与B比对一下是否完全相等,若相等则答案ans与cnt取min即可

时间复杂度O(能过)

const int INF = 0x3f3f3f3f;
int n, m, a[6][6], b[6][6], ans = INF;
int r[6], c[6], fr[6], fc[6];
void swapr(int t[][6], int i)
{
	for (int j = 1; j <= m; ++j)
		swap(t[i][j], t[i + 1][j]);
}
void swapc(int t[][6], int i)
{
	for (int j = 1; j <= n; ++j)
		swap(t[j][i], t[j][i + 1]);
}
void check()
{
	int t[6][6], tr[6], tc[6], cnt = 0;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
			t[i][j] = a[i][j];
		tr[i] = r[i];
	}
	for (int i = 1; i <= m; ++i)
		tc[i] = c[i];
	for (int i = 1; i <= n; ++i)
	{
		for (int j = n - 1; j >= i; --j)
		{
			if (tr[j + 1] == i)
			{
				swap(tr[j], tr[j + 1]);
				swapr(t, j);
				++cnt;
			}
		}
	}
	for (int i = 1; i <= m; ++i)
	{
		for (int j = m - 1; j >= i; --j)
		{
			if (tc[j + 1] == i)
			{
				swap(tc[j], tc[j + 1]);
				swapc(t, j);
				++cnt;
			}
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
			if (t[i][j] != b[i][j])return;
	}
	ans = min(ans, cnt);
}
void dfsc(int step)
{
	if (step > m)
	{
		check();
		return;
	}
	for (int i = 1; i <= m; ++i)
	{
		if (!fc[i])
		{
			c[step] = i;
			fc[i] = 1;
			dfsc(step + 1);
			fc[i] = 0;
		}
	}
}
void dfsr(int step)
{
	if (step > n)
	{
		dfsc(1);
		return;
	}
	for (int i = 1; i <= n; ++i)
	{
		if (!fr[i])
		{
			r[step] = i;
			fr[i] = 1;
			dfsr(step + 1);
			fr[i] = 0;
		}
	}
}
void solve()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
			scanf("%d", &a[i][j]);
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
			scanf("%d", &b[i][j]);
	}
	dfsr(1);
	if (ans == INF)printf("-1\n");
	else printf("%d\n", ans);
}

E - Lucky bag

题意:

有N件物品,价值分别为Wi,将这些物品装入D个袋子里,问这些袋子内物品总价值的最小方差

题解:

子集dp,赛时不会,赛后看水友群说是子集dp一查发现是典

首先平均值是可以直接计算的,先算出来方便后面计算方差

dp[i][f]表示前i个袋子已经使用了集合为f的物品时的最小方差(先不除d),转移为dp[i][f]=min(dp[i-1][t]+cost[f\oplus t]),t\subseteq f

枚举所有状态f以及每个状态f的所有子集t的时间为O(3^n),总的时间复杂度O(d * 3^n)

最终答案为dp[d][(1 << n) - 1] / d

double w[16], dp[16][1 << 15], cost[1 << 15];
void solve()
{
	int n, d;
	scanf("%d%d", &n, &d);
	double avg = 0;
	for (int i = 1; i <= n; ++i)
	{
		scanf("%lf", &w[i]);
		avg += w[i];
	}
	avg /= d;
	for (int f = 0; f < 1 << n; ++f)
	{
		for (int i = 1; i <= n; ++i)
		{
			if (f >> (i - 1) & 1)
				cost[f] += w[i];
		}
		cost[f] -= avg, cost[f] *= cost[f];
		for (int i = 0; i <= d; ++i)
			dp[i][f] = 1e18;
	}
	dp[0][0] = 0;
	for (int i = 1; i <= d; ++i)
	{
		for (int f = 0; f < 1 << n; ++f)//枚举状态f
		{
			for (int t = f & (f - 1);; t = f & (t - 1))//枚举状态f的子集t
			{
				dp[i][f] = min(dp[i][f], dp[i - 1][t] + cost[f ^ t]);
				if (t == 0)break;
			}
		}
	}
	printf("%.10lf\n", dp[d][(1 << n) - 1] / d);
}

F - Random Update Query

题意:

给出一个长度为N的数组A,Q次操作,每次操作能使得区间Li到Ri中的随机一个数变成Xi,问最终每个数的期望值(MOD998244353)

题解:

设Ai是区间L, R中的一个数(期望值),len = r - l + 1,则进行操作之后Ai=\frac{len-1}{len}*Ai+\frac{1}{len}*X,显然只需要一个进行区间乘和区间加单点查询操作的线段树就行

没存板子赛时看了没时间手搓了,赛后补了个,这是没维护区间和的(毕竟题目只需要单点查询巨懒得写了)

typedef long long LL;
const LL N = 2e5 + 10, MOD = 998244353, INF = 0x3f3f3f3f;
LL qpow(LL x, LL y)
{
	x %= MOD;
	if (y == 0)return 1;
	if (y & 1)
		return qpow(x * x, y >> 1) * x % MOD;
	return qpow(x * x, y >> 1) % MOD;
}
LL inv(LL x)
{
	return qpow(x, MOD - 2);
}
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define a(i) (tr[i].a)
#define lz1(i) (tr[i].lz1)
#define lz2(i) (tr[i].lz2)
struct node
{
	LL a, lz1, lz2;
}tr[N << 2];
void push_down(int i)
{
	if (lz1(i) != 1)
	{
		a(ls(i)) = (a(ls(i)) * lz1(i)) % MOD;
		lz1(ls(i)) = (lz1(ls(i)) * lz1(i)) % MOD;
		lz2(ls(i)) = (lz2(ls(i)) * lz1(i)) % MOD;
		a(rs(i)) = (a(rs(i)) * lz1(i)) % MOD;
		lz1(rs(i)) = (lz1(rs(i)) * lz1(i)) % MOD;
		lz2(rs(i)) = (lz2(rs(i)) * lz1(i)) % MOD;
		lz1(i) = 1;
	}
	if (lz2(i))
	{
		a(ls(i)) = (a(ls(i)) + lz2(i)) % MOD;
		lz2(ls(i)) = (lz2(ls(i)) + lz2(i)) % MOD;
		a(rs(i)) = (a(rs(i)) + lz2(i)) % MOD;
		lz2(rs(i)) = (lz2(rs(i)) + lz2(i)) % MOD;
		lz2(i) = 0;
	}
}
void build(int l, int r, int i)
{
	lz1(i) = 1;
	if (l == r)
	{
		scanf("%lld", &a(i));
		a(i) %= MOD;
		return;
	}
	int mid = l + r >> 1;
	build(l, mid, ls(i));
	build(mid + 1, r, rs(i));
}
void motify_multi(int ql, int qr, LL data, int l, int r, int i)
{
	if (ql <= l && r <= qr)
	{
		a(i) = (a(i) * data) % MOD;
		lz1(i) = (lz1(i) * data) % MOD;
		lz2(i) = (lz2(i) * data) % MOD;
		return;
	}
	push_down(i);
	int mid = l + r >> 1;
	if (ql <= mid)motify_multi(ql, qr, data, l, mid, ls(i));
	if (qr > mid)motify_multi(ql, qr, data, mid + 1, r, rs(i));
}
void motify_add(int ql, int qr, LL data, int l, int r, int i)
{
	if (ql <= l && r <= qr)
	{
		a(i) = (a(i) + data) % MOD;
		lz2(i) = (lz2(i) + data) % MOD;
		return;
	}
	push_down(i);
	int mid = l + r >> 1;
	if (ql <= mid)motify_add(ql, qr, data, l, mid, ls(i));
	if (qr > mid)motify_add(ql, qr, data, mid + 1, r, rs(i));
}
LL query(int p, int l, int r, int i)
{
	if (l == r)return a(i);
	push_down(i);
	int mid = l + r >> 1;
	if (p <= mid)return query(p, l, mid, ls(i));
	return query(p, mid + 1, r, rs(i));
}
void solve()
{
	int n, q;
	scanf("%d%d", &n, &q);
	build(1, n, 1);
	while (q--)
	{
		int l, r, x;
		scanf("%d%d%d", &l, &r, &x);
		LL t = inv(r - l + 1);
		motify_multi(l, r, t * (r - l) % MOD, 1, n, 1);
		motify_add(l, r, t * x % MOD, 1, n, 1);
	}
	for (int i = 1; i <= n; ++i)
		printf("%lld ", query(i, 1, n, 1));
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Muelsyse_/article/details/134923902

java-爱代码爱编程

目录  一.  二分查找(递归): 代码详解: 运行结果: 二分查找优化: 优化代码:  运行结果(返回对应查找数字的下标集合):  ​编辑  二分查找(非递归): 二. 插值查找  代码详解: 运行结果:  三. 斐波那契[黄金分割查找] 代码详解:  运行结果:  一.  二分查找(递归): 前提条件: 所要

力扣344-爱代码爱编程

反转字符串 题目链接 解题思路 双指针算法两个指针向中间靠拢,直至相遇交换两个指针的值 class Solution { public: void reverseString(vector<

14 归并排序和其他排序-爱代码爱编程

1.归并排序 2.计数排序 1. 归并排序 基本思想 建立在归并操作上的一种排序算法,采用分治法的一个典型应用。将已有序的子序列合并,得到完全有序的序列,将两个有序表合成一个称为二路归并。 原数组无序,以中间分割为

(52)只出现一次的数字iii-爱代码爱编程

文章目录 每日一言题目解题思路代码结语 每日一言 十年磨一剑,风雨未曾阻挡;愿你乘风破浪,不负韶华时光。 题目 题目链接:只出现一次的数字 给你一个整数数组 nums,其中恰好有两个元

【算法训练营】数字盒子,重编码,成绩排序(python实现)-爱代码爱编程

数字盒子 问题描述 你有一个盒子,你可以往里面放数,也可以从里面取出数。 初始时,盒子是空的,你会依次做 Q 个操作,操作分为两类: 插入操作:询问盒子中是否存在数 x,如果不存在则把数 x 丢到盒子里。删除操作:询问盒子中是否存在数 x,如果存在则取出 x。 对于每个操作,你需要输出是否成功插入或删除。 输入格式

leetcode力扣 面试经典150题 详细题解 (1~5) 持续更新中-爱代码爱编程

目录 1.合并两个有序数组 2.移动元素  3.删除有序数组中的重复项  4.删除排序数组中的重复项 II 暂时更新到这里,博主会持续更新的 1.合并两个有序数组 题目(难度:简单): 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。

【数据结构和算法】-爱代码爱编程

目录 一、交换排序1.1 冒泡排序1.2 快速排序1.2.1 hoare法1.2.2 挖坑法1.2.3 前后指针法 1.3 快速排序优化1.3.1 三数取中法选key1.3.2 递归到小的子区间使用插入

洛谷b2095 白细胞计数(java)-爱代码爱编程

题目描述 医院采样了某临床病例治疗期间的白细胞数量样本 n 份,用于分析某种新抗生素对该病例的治疗效果。为了降低分析误差,要先从这 n 份样本中去除一个数值最大的样本和一个数值最小的样本,然后将剩余 n−2 个有效样本的平均值作为分析指标。同时,为了观察该抗生素的疗效是否稳定,还要给出该平均值的误差,即所有有效样本(即不包括已扣除的两个样本)与该平均值之

【算法训练营】等式,道路升级(c++,python实现)-爱代码爱编程

等式 问题描述 有n个变量和m个“相等”或“不相等”的约束条件,请你判定是否存在一种赋值方案满足所有m个约束条件。 输入格式 第一行一个整数T,表示数据组数。 接下来会有T组数据,对于每组数据: 第一行是两个整数n,m,表示变量个数和约束条件的个数。 接下来m行,每行三个整数a,

寿司转盘,用 c 编码-爱代码爱编程

文章目录 题目描述输入描述输出描述示例一示例二代码 题目描述 寿司店周年庆,正在举办优惠活动回馈新老客户寿司转盘上总共有 n 盘寿司,prices[i] 是第 i 盘寿司的价格,如果客户选择了第 i

atcoder abc332 题解a-爱代码爱编程

前言 这场比赛跟之前的ABC比赛比起来难度还是要高不少,前面的几题也没有之前的比赛那么签,中间的中档题也要难不少(个人感觉),下面的题解,我赛时过了的题我会尽量讲一下我做题时候的心理过程,是如何想出答案的,赛时没过但是后面