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;
}