2021CCPC哈尔滨（题解）
不够强且运⽓不佳吧。。。喜提银⾸
顺便贴⼀下题⽬代码及题解。
第五题D：
218
由于⼀个数的的长度最多为18(题⽬所给数据范围)，所以可以暴⼒枚举种删去数字的状态，暴⼒判断可⾏性。 判断的时候就是⼀些细节问题了，需要检查是否数字出现次数相等，以及数字顺序(⼦序列)是否匹配，以及注意前导零的问题就好了。(细节挺多的，WA了好久，见代码吧) #include<bits/stdc++.h>
#define maxn 100005
#define inf 1e20
#define ll __int128
#define rep(i,a,b)for(int i=a;i<=b;i++)
using namespace std;
ll A[maxn],B[maxn],a,b,ca,cb,cnta[15],cntb[15],aa,bb,fz,fm,tmp[15],P[maxn],cp;
inline ll read()
{
ll x=0,w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
return w==1?x:-x;
}
inline void write(ll x)
{
if(x>=10)write(x/10);
putchar(x%10+'0');
}
inline ll wk(int sta)
{
ll nw=0,base=1;
rep(i,1,ca)if(sta&(1<<(i-1))) nw+=A[i]*base,base*=10;
return nw;
}
inline bool jud(int sta)
{
罗口袜rep(i,0,9) tmp[i]=cntb[i];
rep(i,1,ca)if(!(sta&(1<<(i-1)))) tmp[A[i]]--;
ll p=wk(sta),xx=p*bb/aa,xxx=xx;if(xx==0||(p*bb)%aa!=0)return false;
while(xx) tmp[xx%10]--,xx/=10;
rep(i,1,9)if(tmp[i])return false;if(tmp[0]<0)return false;
cp=0;while(xxx) P[++cp]=xxx%10,xxx/=10;rep(i,1,tmp[0]) P[++cp]=0;
int nw=1;
rep(i,1,cb)
{
if(B[i]==P[nw]) nw++;
if(nw==cp+1)return true;
}
return false;
}
int main()
{
int T; cin>>T;
int T ; cin >>T ;
while (T --)
{
a =read ();
b =read (); aa =a ; bb =b ;
while (a ) A [++ca ]=a %10,a /=10;
while (b ) B [++cb ]=b %10,b /=10;
rep (i ,1,ca ) cnta [A [i ]]++; rep (i ,1,cb ) cntb [B [i ]]++;
int ed =(1<<ca )-1; fz =inf ;
rep (i ,1,ed ) if (jud (i ))
{
if (fz >wk (i )) fz =wk (i ),fm =fz *bb /aa ;
}
write (fz ); printf (" "); write (fm ); puts ("");
ca =0; cb =0; rep (i ,0,9) cnta [i ]=0,cntb [i ]=0;
}
return 0;
}
第六题G
看完题⼤概发现是个，Hamilton回路的问题，我们可以对每个单车进⾏状压，⽤表⽰使⽤过单车的状态为，当前在节点，到达终点的最优期望时间。纳米铂金
那么dp转移⽅程为：
其中为最短路的处理，为每个节点有单车的概率
剩下的使⽤记忆化搜索就可以实现了。
#include <bits/stdc++.h>
#define maxn 1000005
#define inf 2e9
#define pb push_back
#define rep (i ,a ,b ) for (int i =a ;i <=b ;i ++)
using namespace std ;
inline int read ()
{
int x =0,w =1; char c =getchar ();
while (c <'0'||c >'9') {if (c =='-') w =-1; c =getchar ();}
while (c <='9'&&c >='0') x =(x <<1)+(x <<3)+c -'0',c =getchar ();
return w ==1?x :-x ;
}
inline void write (int x )
{
if (x >=10) write (x /10);
putchar (x %10+'0');
}
struct node {int to ,w ;};
vector <node > mp [maxn ];
inline bool operator < (node a ,node b ){return a .w >b .w ;}
inline bool operator > (node a ,node b ){return a .w <b .w ;}
priority_queue <node > q ;
int n ,m ,t ,r ,k ,A [maxn ],d [25][maxn ],id [maxn ],dp [maxn ][25],ct [maxn ];医用脚轮
bool vis [25][maxn ];
double DP [maxn ][25],P [maxn ];
inline void dij (int id ,int uu )舵角指示器
{
rep (i ,1,n ) d [id ][i ]=inf ; q .push ({uu ,0}); d [id ][uu ]=0;
while (!q .empty ())
{
dp [sta ][u ]sta u dp [sta ][u ]=min (dp [sta ][u ],1.0∗(1−P [u ])∗d [u ][n ]/r +P [u ]∗(1.0∗d [u ][A [i ]]/t +dp [sta ∣(1<<(i −1)][i ]))
d [u ][n ]P [u ]
{
node p(); q.pop();
if(vis[id][u.to])continue; d[id][u.to]=u.w; vis[id][u.to]=1;
for(auto v:])
{
if(d[id][v.to]>d[id][u.to]+v.w)
{
d[id][v.to]=d[id][u.to]+v.w;
q.push({v.to,d[id][v.to]});
}
}
}
}
inline double DFS(int sta,int u)
{
if(DP[sta][u])return DP[sta][u];
double tmp=1.0*P[u]*d[u][n]/t+(1-P[u])*d[u][n]/r;
rep(i,1,k)刷镀液
{
if(sta&(1<<(i-1)))continue;
tmp=min(tmp,1.0*(1-P[u])*d[u][n]/r+P[u]*(1.0*d[u][A[i]]/t+DFS(sta|(1<<(i-1)),i)));
}
return DP[sta][u]=tmp;
}
int main()
{
freopen("t1.in","r",stdin);
t=read(); r=read(); n=read(); m=read();
rep(i,1,m)
{
int u=read(),v=read(),w=read();
mp[u].pb({v,w}); mp[v].pb({u,w});
}
k=read();
rep(i,1,k) A[i]=read(),P[i]=read()/100.0,dij(i,A[i]),id[A[i]]=i;
dij(19,1);dij(20,n); P[19]=1;
if(d[19][n]==inf){puts("-1");exit(0);}
DFS(0,19);int ed=(1<<k)-1;
printf("%.6f\n",DP[0][19]);
return0;
}
第七题C
u
可以发现，假设树上每个节点都有⼀组侯选颜⾊，例如节点的⼦树中：
颜⾊1出现3次，颜⾊2出现2次，颜⾊3出现3次，那么u节点选择颜⾊{1,3}是最优的。
聚结器如果⼀个树的两个⼉⼦的候选集合为{1,3,5} 和 {2,3,5}，那么这个点⼀定选{3,5}是最优的。以此类推，那么这个过程可以使⽤启发式合并维护，维护每个点的候选集合即可解决。
#pragma optimize GCC(3)
#include<bits/stdc++.h>
#define maxn 1000005
#define inf 2e9
#define pb push_back
#define ins insert
#define rep(i,a,b)for(int i=a;i<=b;i++)
using namespace std;
inline int read()
{
int x=0,w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
return w==1?x:-x;
}
int n,col[maxn],FF[maxn],sz[maxn],ans[maxn];
vector <int> mp[maxn];
set <int> s[maxn];
map <int,int> p[maxn],q[maxn];
struct node{int id,w;}b[maxn];
inline void dfs(int u,int fa)
{
FF[u]=u;int mx=0; sz[u]=1;
for(auto v:mp[u])
{
if(v==fa)continue;dfs(v,u);
if(mx<sz[v]) mx=sz[v],FF[u]=FF[v];
sz[u]+=sz[v];
}
mx=1;int opt=1;
if(FF[u]==u){s[u].ins(col[u]);p[u][col[u]]++; q[u][col[u]]=u; ans[u]=1;return;} for(auto v:mp[u])
{
if(FF[v]==FF[u]||v==fa)continue;
int V=FF[v],U=FF[u];
for(auto vv:s[V])
{
if(q[U][vv]!=u&&q[U][vv]) q[U][vv]=u,p[U][vv]=1;
p[U][vv]++;int tmp=p[U][vv];q[U][vv]=u;
if(tmp>mx)
{
mx=tmp; s[U].clear();s[U].ins(vv);
opt=0;
}
else if(tmp==mx) s[U].ins(vv);
}
ans[U]+=ans[V];
}
ans[FF[u]]-=(mx-1);
if(!opt)
{
q[FF[u]].clear();p[FF[u]].clear();
for(auto to:s[FF[u]]) p[FF[u]][to]++;puts("");
}
}
int main()
{
freopen("t1.in","r",stdin);
n=read();
rep(i,2,n)
{
int u=read();
mp[i].pb(u); mp[u].pb(i);
}
rep(i,1,n) col[i]=read();
dfs(1,0); cout<<ans[FF[1]]<<endl;
return0;
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议