[ABC382C] Kaiten Sushi
题目描述
有 \(N\) 个人,编号从 \(1\) 到 \(N\),他们正在访问一家传送带寿司餐厅。第 \(i\) 个人的美食级别是 \(A_i\)。
现在,将会有 \(M\) 份寿司放置在传送带上。第 \(j\) 份寿司的美味度为 \(B_j\)。每份寿司将按照顺序经过编号为 \(1\),\(2\),\(\dots\),\(N\) 的人。每个人在看到美味度不低于他们美食级别的寿司经过时,会拿走并吃掉那份寿司;否则,他们什么也不做。一旦第 \(i\) 个人拿走并吃掉了寿司,那份寿司就不会再经过编号大于 \(i\) 的人。
对于每份 \(M\) 份寿司中的一份,请确定是谁吃掉了那份寿司,或者是否没有人吃掉它。
约束条件
\(1\le N\),\(M\le2\times10^5\)
\(1\le A_i\),\(B_i\le2\times10^5\)
所有输入值均为整数。
制約
- $ 1\leq\ N,M\ \leq\ 2\times\ 10^5 $
- $ 1\leq\ A_i,B_i\ \leq\ 2\times\ 10^5 $
- 入力は全て整数
解题思路
以吃寿司的人为单位构造结构体,存储位置和美食级别。吃寿司的时候跟位置有关系,如果在后面的人的美食级别比前面的人还高的话,那肯定一口都吃不到,所以没必要存储。
所以存储的优先级第一为位置,第二为美食级别。存的一定是位置递增和美食级别递减的序列。
可以发现,对于美味度为\(d\)的寿司而言,如果能够被吃,一定是在这个序列当中美食级别第一个小于\(d\)的位置被吃的。因此可以考虑使用二分来解决该问题,总时间复杂度为\(O(nlogn)\)
将存储序列逆序排列,那么要找到的就是序列里小于等于\(d\)且最接近\(d\)的元素。因此注意二分的写法应当是
mid = (l + r + 1) / 2;
if(check()) l = mid;
else r = mid - 1;
参考代码为:
//abc382c
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 200005;
int a[N], b[N];
struct pp{
int val, idx;
}p[N];
bool cmp(pp a, pp b){
return a.val < b.val;
}
int main(){
int n, m;
cin >> n >> m;
int minn = 0x3f3f3f, idx = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
if(a[i] < minn){
minn = a[i];
p[++idx].val = a[i];
p[idx].idx = i;
}
}
sort(p, p+idx+1, cmp);
int min_val = p[1].val;
for(int i = 1; i <= m; i++){
cin >> b[i];
if(b[i] < min_val){
cout << -1 << endl;
continue;
}
//bs
int l = 1, r = idx;
int mid = (l + r + 1) / 2;
while(l < r){
mid = (l + r + 1) / 2;
//cout << mid << endl;
if(p[mid].val <= b[i]) l = mid;
else r = mid - 1;
}
cout << p[l].idx << endl;
}
return 0;
}
[ABC382D] Keep Distance
题目描述
给定整数 \(N\) 和 \(M\) 。按照字典序打印出来所有长度为 \(N\) ,且满足如下条件的整数序列 \((A_1, A_2, ..., A_N)\) :
- \(1 \leq A_i\) ;
- 对 \(i=2, ..., N\), 有 \(A_{i-1} + 10 \leq A_i\) ;
- \(A_N \leq M\) 。
输入格式
一行,空格分隔的两个整数: \(N\ M\) 。
输出格式
第一行是一个整数,为所有满足条件的序列的个数;
之后每一行为空格分隔的 \(N\) 个整数,对应一个满足条件的整数序列。
制約
- $ 2\ \leq\ N\ \leq\ 12 $
- $ 10N\ -\ 9\ \leq\ M\ \leq\ 10N $
- 入力される値はすべて整数
解题思路
一道很有意思的递归的题目
- 递归时需要记录下当前递归到的值,以及递归到第几个位置。
- 用一个二位数组记录所有答案(因为要先输出方案数量再输出每个方案)
- 注意剪枝,否则会t。
//abc382d
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
int n, m, idx = 0;
int a[15], ans[500005][15];
void f(int val, int pos){
a[pos] = val;
if(pos == n){
idx ++;
//存答案
for(int i = 1; i <= n; i++) ans[idx][i] = a[i];
return;
}
int sep = 10;
while(val + sep <= m && (m - val - sep) / 10 >= n - pos - 1){
f(val + sep, pos + 1);
sep++;
}
}
int main(){
cin >> n >> m;
for(int i = 1; i + (n-1) * 10 <= m; i++) f(i, 1);
cout << idx << endl;
for(int i = 1; i <= idx; i++){
for(int j = 1; j <= n; j++)
cout << ans[i][j] << " ";
cout << endl;
}
return 0;
}
[ABC383C] Humidifier 3
题目描述
给你一个 \(H\) 行 \(W\) 列的矩阵,如果为 #
代表为障碍物,.
为空地, H
为喷水器。
定义一个地方是湿的,当且仅当有从一个喷水器可以通过最多 \(D\) 步移动(四联通)到达这个地方。
注意,喷水器所在的地方也是湿的。
求有多少个湿的地方。
输入格式
第一行三个整数 \(H,W,D\)。
接下来 \(H\) 行,每行 \(W\) 个字符,描述矩阵。
输出格式
输出一个整数,表示答案。
数据范围
\(1\le H,W\le1000\)
\(1\le D\le H\times W\)
解题思路
用dfs一定会t...别问我怎么知道的
这道题用bfs做就没有问题啦
注意建立一个\(step\)数组,\(step[i][j]\)存储到达坐标点\((i,j)\)时还可以走多少步。
初始状态:所有喷水点的\(step\)值设为\(d\),并且将喷水点入队列。其他点\(step\)值默认都为\(0\)。
扩散状态:每次取队头,朝四个方向扩散,如果扩散到的点\(step[i'][j']<=step[i][j]-1\),代表当前的扩散是可能对答案有贡献的,因此记录新\(step\)值并将新点入队。如果不满足该条件,证明本次扩散已经在前面的状态出现过了,没有必要再入队重复操作。
//abc383c
#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
char ch[1005][1005];
bool flag[1005][1005];
int step[1005][1005];
int h, w, d, ans = 0;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
void bfs(){
while(!q.empty()){
PII t = q.front();
q.pop();
if(step[t.first][t.second] > 0){
for(int i = 0; i < 4; i++){
int xx = t.first + dx[i];
int yy = t.second + dy[i];
if(1 <= xx && xx <= h && 1 <= yy && yy <= w && ch[xx][yy] == '.' && step[xx][yy] <= step[t.first][t.second] - 1){
q.push({xx, yy});
step[xx][yy] = step[t.first][t.second] - 1;
if(!flag[xx][yy]) flag[xx][yy] = 1, ans ++;
}
}
}
}
}
int main(){
cin >> h >> w >> d;
for(int i = 1; i <= h; i++)
for(int j = 1; j <= w; j++)
cin >> ch[i][j];
for(int i = 1; i <= h; i++)
for(int j = 1; j <= w; j++)
if(ch[i][j] == 'H'){
q.push({i, j});
ans ++;
flag[i][j] = 1;
step[i][j] = d;
}
if(!q.empty()) bfs();
cout << ans << endl;
return 0;
}
[ABC383D] 9 Divisors
题目描述
找出不大于 \(N\) 且恰好有 \(9\) 个因数的正整数的个数。
输入格式
只有一行,一个整数 \(N\)。
输出格式
一行一个整数,表示答案。
数据范围
- \(1 \leq N \leq 4 \times 10^{12}\)
- 所有输入值均为整数。
解题思路
前置知识:如何判断一个正整数\(N\)的因数个数
当\(N = p_1^{\alpha_1}* p_2^{\alpha_2}*...*p_k^{\alpha_k}\)(其中\(p_i\)代表质数)
对于一个数的所有约数,一定可以由上面的通式来表示,且有所对应的\(\alpha_1\)、\(\alpha_2\)、\(\alpha_3\)。
约数用M表示,那么\(M = p_1^{\beta_1}* p_2^{\beta_2}*...*p_k^{\beta_k}\)
对于\(\beta_1\)、\(\beta_2\)、\(\beta_3\)的取值范围,为\(0~\)~\(\alpha_i\),就能够表示出来所有的约数。所以求约数个数实际可拆解为组合数学(乘法原理)。
所以对于正整数\(N\)而言,其对应的约数个数为\((\alpha_1+1)*(\alpha_2+1)*(\alpha_3+1)...(\alpha_k+1)\)
对于该结论,结合本道题要求恰好有 \(9\) 个因数,可以分析得出:
-
因数都是成对出现,若一个数\(X\)恰好有\(9\)个因数,代表一定有一对的因数相等,所以\(X\)一定是一个完全平方数。
-
约数个数满足\((\alpha_1+1)*(\alpha_2+1)*(\alpha_3+1)...(\alpha_k+1)=9\),其组合方法可以表示为\(9\)或是\(3*3\)。
1)对于第一种,若\(X=p^8\)且\(X<=N\),那么\(X\)符合题目要求
2)对于第二种,若\(X={p_1}^2*{p_2}^2\)且\(X<=N\),那么\(X\)符合题目要求
因此对于一个可能作为答案的完全平方数\(X\),先去找到所有小于等于\(logX\)的质因数\(p\),再分两种方案枚举可能的值。最终把所有方案数加起来即为答案。
//abc383d
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
typedef long long ll;
const int N = 2e6+5;
ll prime[N];
bool not_prime[N];
int main(){
ll n, idx = 0, ans = 0;
cin >> n;
//找出logn以内的所有指数 埃式筛法
for(ll i = 2; i * i<= n; i++){
if(!not_prime[i]){
prime[++idx] = i;
for(ll j = 2; j * i <= sqrt(n); j++) not_prime[j * i] = 1;
}
}
//算p^8的个数
for(ll i = 1; i <= idx; i++) if(pow(prime[i], 8) <= n) ans ++;
//算p^2和q^2的个数
for(ll i = 1; i < idx; i++){
for(ll j = i + 1; j <= idx; j++){
if (pow(prime[i], 2) * pow(prime[j], 2) <= n) ans ++;
else break;
}
}
cout << ans << endl;
return 0;
}
[ABC383F] Diversity
题目描述
Aya 非常喜欢奶龙。
今天他来到商店,发现商店里正在出售 \(N\) 个奶龙!第 \(i\) 个奶龙的价格是 \(P_i\) 元,实用性是 \(U_i\),颜色是 \(C_i\)。
Aya 可以选择所有奶龙的一个子集进行购买(可以是空集),但最多只能用 \(X\) 元。
Aya 的满意度是 \(S+T\times K\),其中 \(S\) 是购买的奶龙实用性之和,\(T\) 是购买的奶龙中不同颜色的种类数,\(K\) 是一个给定的常数。
请帮 Aya 最大化满意度。
制約
- $ 1\ \leq\ N\ \leq\ 500 $
- $ 1\ \leq\ X\ \leq\ 50000 $
- $ 1\ \leq\ K\ \leq\ 10^9 $
- $ 1\ \leq\ P_i\ \leq\ X $ $ (1\ \leq\ i\ \leq\ N) $
- $ 1\ \leq\ U_i\ \leq\ 10^9 $ $ (1\ \leq\ i\ \leq\ N) $
- $ 1\ \leq\ C_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ N) $
- 入力は全て整数
解题思路
背包问题 选or不选
状态转移方程
\(f[i][j][0]\)表示对于第\(i\)组颜色,花了\(j\)元,不选该颜色能够获得的最大满意度
\(f[i][j][1]\)表示对于第\(i\)组颜色,花了\(j\)元,选了该颜色能够获得的最大满意度
- 在写状态转移方程的时候要注意判断,当前的颜色是否是一个新的颜色
(1)当前面没有出现过该颜色:
\(f[w[i].c][j][0] = max(f[w[i].c-1][j][0], f[w[i].c-1][j][1])\)
\(f[w[i].c][j][1] = max(f[w[i].c-1][j-w[i].p][0],f[w[i].c-1][j-w[i].p][1])+k+w[i].u\) (当\(j>=w[i].p\)时)
可以发现,在很多地方都出现了\(max(f[w[i].c-1][j][0], f[w[i].c-1][j][1])\)
因此可以每计算一组颜色的dp值,统一\(f[w[i].c-1][j][0] = max(f[w[i].c-1][j][0], f[w[i].c-1][j][1])\)
状态转移方程可以改成:
\(f[w[i].c][j][0] = f[w[i].c-1][j][0]\)
\(f[w[i].c][j][1] = f[w[i].c-1][j-w[i].p][0]+k+w[i].u\) (当\(j>=w[i].p\)时)
(2)当前面出现过该颜色:
不选该颜色的状态同样只能从前一种颜色转移而来
\(f[w[i].c][j][0] = f[w[i].c-1][j][0]\)
选该颜色时 (当\(j>=w[i].p\)时),状态可以是:
- 前面的同一颜色都不选,只选当前物品,dp值表示为\(f[w[i].c-1][j-w[i].p][0]+k+w[i].u\)
- 前面已选了当前颜色,还选当前物品,dp值表示为\(f[w[i].c][j-w[i].p][1]) + w[i].u\)
- 前面已选了当前颜色,不选当前物品,dp值表示为\(dp[w[i].c][j][1]\)
这几个值取max即为\(f[w[i].c][j][1]\)的值
几个小点
-
第一维是以颜色种类来表示,题目所给颜色不一定连续,所以要对颜色进行离散化处理
-
相同颜色的物品在dp时所用的是同一空间,所以要注意第二维的枚举要 从后往前,比较最大值时还要记得跟当前位置原本的值比较
-
所有的值只跟当前行和上一行有关系,所以数组的第一维空间可以压缩成\(2\)
//abc383f
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
//分组背包
//dp[i][j][0]代表对于第i个物品,花了j元,不选该物品所属的颜色能够获得的最大满意度
//dp[i][j][1]代表对于第i个物品,花了j元,选了该物品所属的颜色能够获得的最大满意度
ll dp[505][50005][2];
struct nl{
ll p, u, c, cc;
}w[505];
bool cmp(nl a, nl b){
return a.c < b.c;
}
int main(){
ll n, x, k;
cin >> n >> x >> k;
for(int i = 1; i <= n; i++) cin >> w[i].p >> w[i].u >> w[i].c;
sort(w+1, w+n+1, cmp);
//颜色离散化
w[1].cc = 1;
ll i = 2, temp = 1;;
while(i <= n){
while(w[i].c == w[i-1].c){
w[i].cc = temp;
i++;
}
w[i].cc = ++temp;
i ++;
}
//dp过程
for(ll i = 1; i <= n; i++){
//统一前一组颜色的最大值
if(w[i].cc != w[i-1].cc){
for(int j = 0; j <= x; j++) dp[w[i-1].cc][j][0] = max(dp[w[i-1].cc][j][0], dp[w[i-1].cc][j][1]);
}
for(ll j = x; j >= 0; j--){
dp[w[i].cc][j][0] = dp[w[i].cc-1][j][0];
if(j >= w[i].p){
//一个新的颜色
if(w[i].cc != w[i-1].cc)
dp[w[i].cc][j][1] = dp[w[i].cc-1][j-w[i].p][0] + k + w[i].u;
else
dp[w[i].cc][j][1] = max(dp[w[i].cc][j][1], max(dp[w[i].cc-1][j-w[i].p][0] + k, dp[w[i].cc][j-w[i].p][1]) + w[i].u);
}
}
}
ll ans = 0;
for(int i = 1; i <= x; i++){
ans = max(dp[w[n].cc][i][0], ans);
ans = max(dp[w[n].cc][i][1], ans);
}
cout << ans << endl;
return 0;
}
标签:颜色,int,题解,leq,ABC383,ABC382,alpha,include,dp
From: https://www.cnblogs.com/hsy2093/p/18670404