D - Square Permutation
须知：最大的平方数的平方一定小于等于10n，平方数最多为10(n/2)（因为再大会越界）
因为要求的数一定是原数的排列组合，所以它们的元素和对应的元素个数一定相同
所以只要判断平方数的字符串是否与原字符串相等即可（这里可以利用排序判断）
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 5e5 + 10;
int a[13];
int main() {
int ans = 0, n;
string s;
cin >> n >> s;
sort(s.begin(),s.end());
long long mx = pow(10, n);
for (LL i = 0; i * i < mx; i++) {
string t = to_string(i * i);//将数字转换成字符串
t.resize(n, '0');//补全，使得与s的长度相等
sort(t.begin(), t.end());
if (t == s) ans++;//判断
}
cout << ans;
return 0;
}
E - Joint Two Strings
注意：可以不连续，只要里面有t的所有字符就行
思路：
1.记录s[i]包含t的前后缀数
2.如果i,j满足，则i的前缀+j的后缀>=t.size
3.累加ans
如此简单
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 5e5 + 10;
string s[N], t;
int a[N], c[N], b[N];
int bu_f(string s1) {
int k = 0;
for (auto c : s1) {//注意可以不连续
if (k >= t.size()) break;
if (c == t[k]) k++;
}
return k;
}
int main() {
int n;
cin >> n >> t;
for (int i = 1; i <= n; i++) cin >> s[i];
for (int i = 1; i <= n; i++) a[i] = bu_f(s[i]);//记录t的前缀数
reverse(t.begin(), t.end());//翻转
for (int i = 1; i <= n; ++i) {
reverse(s[i].begin(), s[i].end());//翻转与t对应
b[i] = bu_f(s[i]);
c[b[i]]++;//记录s[i]包含t的后缀数
}
LL ans = 0;
for (int i = 1; i <= n; i++) {
int l = max((int)(t.size() - a[i]),0);//前缀还缺的数，可能会有负数，特判0
for (int j = l; j <= t.size(); j++) {
ans += c[j];
}
}
cout << ans;
return 0;
}
F - Beautiful Path
注意：如果TLE可能是开的太小或太大
分数规划经典题
设b为美观和，c为代价和，b/c>=k，求k的最大值
转换成b-kc>=0或kc-b<=0
1.可以把边的权值转换成最长路或者最短路的模板
2.二分求k值
注意：因为u<=v，DAG(有向无环图),可以dp直接枚举
如此简单？
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define db double
const int N = 2e5 + 10;
int n, m;
struct node {
int to, b, c;
};
vector<node> g[N];
db dp[N];
const db esp = 1e-11;//开的太小把自己坑死
bool check(db x) {
for (int i = 1; i <= n; i++) dp[i] = -1e12;
dp[1] = 0;
for (int i = 1; i <= n; i++) {//暴力枚举
for (auto v : g[i]) {
db w=v.b-v.c*x;
dp[v.to] = max(dp[v.to], dp[i] + w);//最长路
}
}
return dp[n] >= 0;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, b,c;
cin >> u >> v >> b >> c;
g[u].push_back({ v,b,c });
}
db l = 0, r = 1e10;
while (r-l>esp) {
db mid = (r + l) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.10lf", l);
return 0;
}