引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
思路:
通过将炮塔放置在行和列均为 KKK 的倍数的位置上,可以确保每个 K×KK\times KK×K 的子矩阵都包含至少一个这样的炮塔。
也就是说行方向需要 ⌊N/K⌋\lfloor N/K \rfloor⌊N/K⌋ 个炮塔,列方向需要 ⌊M/K⌋\lfloor M/K \rfloor⌊M/K⌋ 个炮塔,共需要 ⌊N/K⌋×⌊M/K⌋\lfloor N/K \rfloor \times \lfloor M/K \rfloor⌊N/K⌋×⌊M/K⌋ 个炮塔。
这样便是最优的。
代码:
代码一代码二#define int32 int32_tint32 solve(int32 N, int32 M, int32 K){ int32 ans=0; for(int i=K;i<=N;i+=K){ for( ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
简化题意
有一个有 nnn 层的架子,初始时在第一层(最高层设为第 111 层,最低层设为第 nnn 层)。第 iii 层上有 qiq_iqi 个食物,对于第 iii 层第 jjj 份食物,它可以提供 ci,jc_{i,j}ci,j 的卡路里,并且有 xi,jx_{i,j}xi,j 的概率选到它。最多一次向下 kkk 层,往下 iii 层的概率为 pip_ipi。每当到达某一层时,选择一份食物吃掉,得到它提供的卡路里,然后前往下一层。如果当前层数大于 nnn 则称为离开了架子。输出在离开架子前,预期会吸收多少卡路里?
思路
我们定义 dpdpdp 数组,dpidp_id ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
思路:
首先,考虑极差为 000 的情况需要满足什么:
假设第 iii 个数可以被修改 sumisum_isumi 次,那么这个数的最大值为 ai+sumia_i + sum_iai+sumi,最小值为 ai−sumia_i - sum_iai−sumi,也就是说这个数可以是区间 [ai−sumi,ai+sumi][a_i-sum_i,a_i+sum_i][ai−sumi,ai+sumi] 中的任意数。只要有一个数在所有 aia_iai 被修改后可以是的区间内,那么就说明修改后的 aia_iai 可以全部相等,也就是极差为 000。
考虑用差分维护可以被修改的次数。
对于其它情况:
我们知道极差是序列里最大值和最小值的差,于是我们可以把所有可能的最大值里的最小值和所有可能的最小值里的最大值做差即可。
代码:
#include&l ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
不要问我 (111) 去哪里了,在咕咕咕。
看完后可以看着下面的图再自己独立推一次。
看完后完成 P3950。
P3950 代码
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longconst int MN=3*1e5+10;LL tree[MN*8],tag[MN*8];int n,m,p,q,x;char op;vector<int>tu[MN];int fa[MN],top[MN],dep[MN],son[MN],siz[MN],id[MN],idx;int root=1,k=0;vector ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
简要题意
给出多组字符串,你需要输出每个字符串中出现次数最多的字母(小写输出),如果有多个,则按字典序输出。
输入可能包含大写字母,但是也要计入字母输出次数。
字符串中间可能有空格。
思路
因为字符串中间可能有空格,所以我们需要整行输入,使用 getlline。
考虑使用 map 作为桶。
把字符串的字母全部放进桶中。
处理完字符串后找到出现次数最多的字母,最后按字典序输出。
代码
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longint T;string s;int main(){ //ios::sync_with_stdio(0); //cin.ti ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
简要题意:
给定两个 vector,v1=(x1,x2,⋯ ,xn)v_1 = (x_1, x_2, \cdots, x_n)v1=(x1,x2,⋯,xn) 和 v2=(y1,y2,⋯ ,yn)v_2 = (y_1, y_2,\cdots, y_n)v2=(y1,y2,⋯,yn),要求最小化标量积 x1×y1+x2×y2+⋯+xn×ynx_1 \times y_1 + x_2 \times y_2+ \cdots + x_n \times y_nx1×y1+x2×y2+⋯+xn×yn,两个 vector 中的元素可以任意更改位置。
思路:
将 v1v_1v1 和 v2v_2v2 分别按升序和降序进行排序,然后计算即可。
证明在最后。
代码:
#include<bits/stdc++.h>using name ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
思路:
对于用斐波那契数列将距离从英里转换为公里,我们可以发现一个性质,误差最小的公里数必然是距离真实值 1.6×n1.6 \times n1.6×n 最近的两个整数之一。
通过拆分英里数,我们可以用斐波那契数列中小的数组合出任何大于等于 222 的整数公里数。所以我们也可以组合出与真实值最近的两个整数,我们只需要在两个整数与真实值的差中取最小值就好了。
代码:
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longint n;int main(){ //ios::sync_with_stdio(0); //cin.tie(0);cout.tie(0); ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
前言:
没学过数位 DP 的可以参考 CSP Wiki。
思路:
考虑数位 DP。
本题只需要在填数时判断一下当前相邻数位差的绝对值之和有没有大于 mmm 就行了。
具体地,对于每次填数,我们需要考虑,当前相邻数位差的绝对值之和有没有大于 mmm。
如果大于,返回本次 000 表示没有答案;否则,我们考虑当前数位是否有限制,接着填数,如果最后一位也填了,并且相邻数位差的绝对值之和没有大于 mmm 就代表本次填的答案是可行的。
代码:
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longLL n,m;LL dp[20][300][11];int a[20];int cf(LL x ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
简要题意:
多组数据。
每组数据给定 nnn(0≤n≤10000 \le n \le 10000≤n≤1000)个区间 [si,ei][s_i,e_i][si,ei](0≤si≤ei≤315360000 \le s_i \le e_i \le 315360000≤si≤ei≤31536000),求所有时刻中同时存在的区间数量的最大值。
思路:
考虑扫描线算法。
对于扫描线的基本步骤,可以参考此博文。
将每个区间的开始点和结束点存下来,然后按照时间顺序排序,如果是起点让计数器加一,否则是终点让计数器减一,我们只需要在计算器里取最大值就好了。
因为终点也算在区间里,所以我们在处理时要优先处理起点。
对于每组数据,时间复杂度为 O(nlogn)O(n \log n)O(nlogn)。
代码:
#include<bits/stdc++.h&g ...
引用站外地址,不保证站点的可用性和安全性
洛谷文章链接
xyx404
思路:
通过观察可以发现有一些字母在所有数字中只出现过一次,我们可以先处理这些字母对应的单词。
比如字母 Z 只出现在 ZERO 中。
在处理完这些后,我们可以发现有一些字母在这些单词中只出现过两次,而其中一个单词已经处理过了,这时我们就可以直接处理另外一个单词。
例如 SIX 和 SEVEN,SIX 中的 X 只在它自己里面出现,已经被处理了,而 S 只在这两个单词中出现,所以剩下的 S 都是 777 的了。
以此类推,我们便可以完成此题。
代码:
#include<bits/stdc++.h>using namespace std;#define LL long long#define itn int#define ull unsigned long longint T;string s;int main(){ cin> ...