526互联

AtCoder Beginner Contest 324

发布时间 2023-10-15 16:31:50作者: 不o凡

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;
}
结束了