AtCoder Beginner Contest 324 DF题题解-526互联

D - Square Permutation

其实比较简单，但是比赛时候脑子不转了，竟然在尝试枚举全排列，然后算了一下复杂度直接不会做了。

正解应该是枚举完全平方数，底数枚举到 \(sqrt(10^{14})\) 即可，因为 n 最大为 13。

然后统计一下这个完全平方数各个数字出现了多少个，和读入的比较一下是否相等即可。

注意这个完全平方数不能超过 n 位，且不足 n 位时前面要补 0。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
int n,ans,a[10],dig[10];
string s;
int main()
{
    ios::sync_with_stdio(false);
	cin>>n>>s;
	for(int i=1;i<=n;i++) a[s[i-1]-'0']++;
	for(int i=0;i<10000000;i++){
		long long x=1ll*i*i;
		memset(dig,0,sizeof(dig));
		for(int i=1;i<=n;i++) dig[x%10]++,x/=10;
		if(x) continue;
		for(int i=0;i<=9;i++){
			if(dig[i]!=a[i]){
				ans--;
				break;
			}
		}
		ans++;
	}
	cout<<ans;
    return 0;
}

F - Beautiful Path

这种算法其实以前学过，叫做 01分数规划，即分子和分母都是一些数字的和，要求最大/小的这个分数值。

好久没做的我赛场上以为是个dp，写了好久最后一直wa，赛后发现他不满足最优子结构（到达u节点的分数最大时并不一定是最优解，因为可能分子和分母都很大，导致后面一些价值高的边“贬值”了）。

正解是二分这个最大值 X，然后判断 \(\max \{ \sum (a_i-Xb_i) \} > 0\) 是否成立。

这种形式是可以用dp来求的。

日语题解里好像提到了一种可以优化到O(n)的Dinkelbach 算法，没看懂。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
const double eps=1e-10;
const int maxn=200005;
int n,m,cnt,p[maxn],vis[maxn];
double dp[maxn];
struct node{
	int v,next;
	double val,w;
}e[maxn];
void insert(int u,int v,double val,double w){
	cnt++;
	e[cnt].v=v;
	e[cnt].val=val;
	e[cnt].w=w;
	e[cnt].next=p[u];
	p[u]=cnt;
}
bool check(double x){
	memset(dp,0,sizeof(dp));
	memset(vis,0,sizeof(vis));
	vis[1]=1;
	for(int u=1;u<=n;u++){
		if(!vis[u]) continue;
		for(int i=p[u];i!=-1;i=e[i].next){
			int v=e[i].v;
			if(vis[v]) dp[v]=max(dp[v],dp[u]+e[i].val-e[i].w*x);
			else dp[v]=dp[u]+e[i].val-e[i].w*x;
			vis[v]=1;
		}
	}
	if(dp[n]>0) return 1;
	return 0; 
}
int main()
{
    ios::sync_with_stdio(false);
    memset(p,-1,sizeof(p));
	memset(dp,-1,sizeof(dp));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		double w,val;
		cin>>u>>v>>val>>w;
		insert(u,v,val,w);
	}
	double l=0,r=10000;
	while(abs(r-l)>eps){
		double mid=(l+r)/2;
		if(check(mid)) l=mid;
		else r=mid;
	}
	cout<<fixed<<setprecision(10)<<l;
    return 0;
}