B - 3-smooth Numbers
难度: ⭐
题目大意
给定一个数字n, 问是否可以找到两个数x和y, 使得 n = 2x3y;
解题思路
因为n的范围最大到1e18, 所以只需要暴力找x和y即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5+10;
typedef pair<int,int> PII;
int n, m, idx;
signed main(){
cin >> n;
for(int i = 0; i <= 64; i++){
for(int j = 0; j <= 64; j++){
int x = pow(2, i), y = pow(3, j);
if(x * y == n){
cout << "Yes";
return 0;
}
}
}
cout << "No";
return 0;
}
C - Error Correction
难度: ⭐⭐
题目大意
给定一个由小写字母组成字符串S, 我们可以将其修改为字符串T, 由S变为T的合法方案有四种而且只能用其中一个: 一是不变, 二是插入一个小写字母, 三是删除一个小写字母, 四是修改一个小写字母; 给出n个字符串T', 请问其中有多少个是符合合法方案的字符串T;
解题思路
除了不变以外, 我们发现其他三种修改方案的容错率只有1个小写字母; 所以我们可以用双指针遍历S和当前字符串T', 对于每个字符串T'我们只允许它和S的差异只出现一次, 出现差异后我们根据T'和S的长度来判断T'可能是S通过哪种方案得到的, 根据那个方案对当前的遍历进行修补, 如果后面又出现差异就可以直接判错了;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5+10;
typedef pair<int,int> PII;
int n, m, idx;
int f[N], st[N];
bool check(int u){
for(int i = 0; i <= 9; i++) st[i] = 0;
for(int i = 1; i <= n; i++) {
st[f[i]]++;
}
for(int i = 1; i <= n; i++){
int x = u % 10;
u /= 10;
if(st[x]) st[x]--;
else return false;
}
return true;
}
signed main(){
cin >> n;
for(int i = 1; i <= n; i++){
char c;
cin >> c;
f[i] = c - '0';
}
int maxn = 1;
for(int i = 1; i <= n; i++) maxn *= 10;
for(int i = 0; i * i <= maxn; i++){
int x = i * i;
if(check(x)){
idx++;
}
}
cout << idx;
return 0;
}
D - Square Permutation
难度: ⭐⭐⭐
题目大意
给定n个数字, 我们可以对其进行排列, 对于其中一种排列(p1, p2 ... pn), 我们可以得到一个数Q = p1 + p2 * 10 + p3 * 102 ... pn * 10(n-1); 如果Q是一个平方数, 那么这个序列就被称为合法的, 请问存在多少种合法的序列; 如果有多个序列得到了同一个平方数, 那么这些序列只会被记为1个;
解题思路
本题的n最大为13, 所以肯定不能考虑全排列; 题目有句话就已经提示了做法, 如果有多个序列得到了同一个平方数, 那么这些序列只会被记1次; 所以我们不应该去找序列, 而是看有多少种平方数可以被凑出; 因为Q的最大范围是1e14, 所以找其中的平方数只需要1e7的复杂度就可以了; 对于每个平方数Q, 我们遍历Q的每一位数x, 给出的n个序列中是否还有x, 如果有就让它的数量减一, 否则就说明凑不出来;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5+10;
typedef pair<int,int> PII;
int n, m, idx;
int f[N], st[N];
bool check(int u){
for(int i = 0; i <= 9; i++) st[i] = 0;
for(int i = 1; i <= n; i++) st[f[i]]++;
for(int i = 1; i <= n; i++){
int x = u % 10;
u /= 10;
if(st[x]) st[x]--;
else return false;
}
return true;
}
signed main(){
cin >> n;
for(int i = 1; i <= n; i++){
char c;
cin >> c;
f[i] = c - '0';
}
int maxn = 1;
for(int i = 1; i <= n; i++) maxn *= 10;
for(int i = 0; i * i <= maxn; i++){
int x = i * i;
if(check(x)){
idx++;
}
}
cout << idx;
return 0;
}
E - Joint Two Strings
难度: ⭐⭐⭐
题目大意
给定1个字符串S和n个字符串Ti; 问存在多少种二元组(i, j), 使得S的字符串Ti + Tj的一个子序列; (注意是子序列而不是子串);
解题思路
因为问的是子序列, 那么我们可以求出每个字符串Ti对于S的前缀子序列的长度和后缀子序列的长度; 那么我们在找二元组的过程中, 设S的长度为len, Ti对于S的前缀子序列长度为x, 那么我们只需要从其他字符串中找出其对于S的后缀子序列长度至少为(len - x)的Tj即可; 这个可以用前缀和来维护数量;
eg: 字符串S为"basdh", 字符串T为"dbsdahd", T对于S的前缀子序列是"bah", 长度为3; 后缀子序列是"hds", 长度为3;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 5e5+10;
typedef pair<int,int> PII;
int n, m, idx;
string s;
int st[N], ed[N];
int h[N], t[N];
signed main(){
cin >> n >> s;
for(int i = 1; i <= n; i++){
string str;
cin >> str;
int k = 0;
for(int j = 0; j < str.size(); j++){
if(str[j] == s[k]){
k++;
st[i]++;
}
}
k = s.size() - 1;
for(int j = str.size() - 1; j >= 0; j--){
if(str[j] == s[k]){
k--;
ed[i]++;
}
}
}
for(int i = 1; i <= n; i++) t[ed[i]]++;
for(int i = s.size(); i >= 0; i--) t[i] += t[i+1]; // 求前缀和
for(int i = 1; i <= n; i++){
int a = st[i], b = s.size() - a;
if(a == s.size()) idx += n;
else idx += t[b];
}
cout << idx;
return 0;
}
F - Beautiful Path
难度: ⭐⭐⭐⭐
题目大意
一个有向图中有n和节点和m条边, 对于每条边一定是有编号小的点指向编号大的点; 每条边有两个属性b和c, 对于一条路径, 他的价值是路径中所有边的b的和除以c的和, 问从1到n的路径中价值最大的路径的价值是多少;
解题思路
一道0/1分数规划的板子题, 比如说有n个物品，每个物品有两个权值a和b，然后让你选出任意件数的物品，使得这些物品中两个权值的和之间的比值最大; 分数规划一般都是用二分进行求解;
设当前已经选择了一条1到n的路径, 其中属性b的和为sum, 属性c的和为tot, 当前的二分答案为mid, 二分答案是最大价值; 那么一定存在 sum / tot <= mid; 移项就得到了sum - tot * mid <= 0; sum的属性b的和, tot * mid是属性c * mid的和; 这样我们就把路径问题转变了每条边的问题, 所以我们就可以把边的权值设为b - c * mid, 然后求最长路径就可以了; 因为本题不可能存在环, 所以最大路径可以用dp来求; 在二分的check函数中我们就看是否存在一条路径的sum - tot * mid > 0, 如果大于0说明最佳情况可能更大, 否则就更小, 一个普通的二分逻辑;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 5e5+10;
typedef pair<int,int> PII;
int n, m, idx;
struct Node{
int u;
double w;
};
vector<Node> edge[N];
int u[N], v[N], b[N], c[N];
double d[N];
bool check(double mid){
for(int i = 1; i <= n; i++){
edge[i].clear();
d[i] = -1e15;
}
for(int i = 1; i <= m; i++) {
double w = 1.0 * b[i] - c[i] * mid;
edge[v[i]].push_back({u[i], w});
}
d[1] = 0;
for(int i = 1; i <= n; i++){
for(Node t : edge[i]){
int x = t.u;
double w = t.w;
d[i] = max(d[i], d[x] + w);
}
}
if(d[n] > 1e-11) return true;
else return false;
}
signed main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> u[i] >> v[i] >> b[i] >> c[i];
}
double l = 0, r = 1e4;
while(r - l > 1e-11){
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
printf("%.11lf", l);
return 0;
}
- Beginner AtCoder Contest 324 abcbeginner atcoder contest 324 beginner atcoder contest abc contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332