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;
}
比赛总结
忙了一天之后打比赛，累得甚至趴着桌子上睡了一会，崩掉大概是我能理解的。
ABC过的速度还可以，但是D题卡住了，于是先去做E，然后F题又假了。
比赛前还是应该调一下状态，注意休息。
标签：AtCoder,cnt,val,Beginner,int,题解,double,include,dp From： https://www.cnblogs.com/yinyuqin/p/17765767.html