A. 接力比赛
跑两遍背包，再进行一些玄学的剪枝
代码
#include<cstdio>
#include<algorithm>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e3+5,maxm=1e6+5;
int n,m,maxa,maxb,mmax;
long long fa[maxm],fb[maxm],ans=0;
struct asd{
int val,cost;
}b1[maxn],b2[maxn];
bool cmp(asd aa,asd bb){
return aa.val>bb.val;
}
int main(){
n=read(),m=read();
for(rg int i=1;i<=n;i++){
b1[i].cost=read(),b1[i].val=read();
}
for(rg int i=1;i<=m;i++){
b2[i].cost=read(),b2[i].val=read();
}
mmax=700;
std::sort(b1+1,b1+1+n,cmp);
std::sort(b2+1,b2+1+m,cmp);
for(rg int i=1;i<=mmax;i++){
maxa+=b1[i].cost;
}
for(rg int i=1;i<=mmax;i++){
maxb+=b2[i].cost;
}
for(rg int i=1;i<=maxa;i++){
fa[i]=-0x3f3f3f3f3f3f3f3f;
}
for(rg int i=1;i<=maxb;i++){
fb[i]=-0x3f3f3f3f3f3f3f3f;
}
for(rg int i=1;i<=mmax;i++){
for(rg int j=maxa;j>=b1[i].cost;j--){
fa[j]=std::max(fa[j],fa[j-b1[i].cost]+b1[i].val);
}
}
for(rg int i=1;i<=mmax;i++){
for(rg int j=maxb;j>=b2[i].cost;j--){
fb[j]=std::max(fb[j],fb[j-b2[i].cost]+b2[i].val);
}
}
for(rg int i=1;i<=maxa;i++){
ans=std::max(ans,fa[i]+fb[i]);
}
printf("%lld
",ans);
return 0;
}
B. 树上竞技
单独考虑每一条边的贡献
设该边一侧关键点的个数为 (x) ，则另一侧关键点的个数为 (m-x)
那么最终的集合点一定会选在点比较多的那一侧，因为我们要让尽量少的点经过这条边
设该边一侧点的个数为 (s) ，则另一侧点的个数为 (n-s)
该边的答案就是 (sum_{i=1}^{m-1}C_s^i imes C_{n-s}^{m-i} imes min(i,m-i))
带着 (min) 不好处理，我们把它展开
[sum_{i=1}^{frac{m-1}{2}} C_{S}^{i} C_{n-S}^{m-i} imes i + sum_{i=1}^{frac{m-1}{2}} C_{S}^{m-i} C_{n-S}^{i} imes i + [m\%2=0] imes C
_{S}^{frac{m}{2}} imes C_{n-S}^{frac{m}{2}} imes frac{m}{2}]
前两项本质是相同的，最后一项加的时候特判一下即可
变一下形式(sum_{i=1}^{frac{m-1}{2}} C_{S}^{i} C_{n-S}^{m-i} imes i=sum_{i=1}^{frac{m-1}{2}} C_{S-1}^{i-1} C_{n-S}^{m-i} imes s)
令 (k=frac{m-1}{2})
则 (G(S) = sum_{i=1}^{k} C_{S-1}^{i-1} C_{n-S}^{m-i})
所以我们只需要求出 (G(s)) 即可
我们现在考虑 (G(s)) 的组合意义,可以理解为 (n-1) 个物品里一共要选 (m-1) 个，前面 (s-1) 个里最多选 (k-1) 个的方案数
要从 (G(i)) 变成 (G(i+1))，发现答案变少的部分就是前面 (i-1) 个选了 (k-1) 个，而 (i) 也被选中了
只有这种情况会被 (G(i)) 计算而不会被 (G(i+1)) 计算
(O(n)) 递推即可计算,最后枚举每一条边算贡献再累加即可
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int mod=1e9+7,maxn=1e6+5;
int h[maxn],tot=1,n,m;
struct asd{
int to,nxt;
}b[maxn<<1];
void ad(rg int aa,rg int bb){
b[tot].to=bb;
b[tot].nxt=h[aa];
h[aa]=tot++;
}
int siz[maxn],ans;
void dfs(rg int now,rg int lat){
siz[now]=1;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==lat) continue;
dfs(u,now);
siz[now]+=siz[u];
}
}
int ny[maxn],jc[maxn],jcc[maxn],fa[maxn];
int getC(rg int nn,rg int mm){
return 1LL*jc[nn]*jcc[mm]%mod*jcc[nn-mm]%mod;
}
void pre(){
ny[1]=1;
for(rg int i=2;i<maxn;i++){
ny[i]=1LL*(mod-mod/i)*ny[mod%i]%mod;
}
jc[0]=jcc[0]=1;
for(rg int i=1;i<maxn;i++){
jc[i]=1LL*jc[i-1]*i%mod;
jcc[i]=1LL*jcc[i-1]*ny[i]%mod;
}
}
int anss[maxn];
int js(rg int aa,rg int bb){
if(aa>bb) std::swap(aa,bb);
if(anss[aa]!=-1) return anss[aa];
rg int nans=0;
for(rg int i=1;i<=m-1;i++){
rg int j=m-i;
if(aa<i) break;
if(bb<j) continue;
nans+=1LL*getC(aa,i)*getC(bb,j)%mod*std::min(i,j)%mod;
if(nans>=mod) nans-=mod;
}
return anss[aa]=nans;
}
void dfs2(rg int now,rg int lat){
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==lat) continue;
ans+=js(siz[u],n-siz[u]);
if(ans>=mod) ans-=mod;
dfs2(u,now);
}
}
int getsum(int num){
return 1LL*num*(num+1)/2LL%mod;
}
bool haha=1;
int main(){
memset(h,-1,sizeof(h));
memset(anss,-1,sizeof(anss));
n=read(),m=read();
for(rg int i=2;i<=n;i++){
fa[i]=read();
if(fa[i]!=i-1) haha=0;
ad(fa[i],i);
ad(i,fa[i]);
}
pre();
if(n<1000000 && m>=200000) {
rg int cs;
if(m!=1){
pre();
for(rg int i=1;i<=n;i++){
if(i-1<m/2 || n-i<m/2) continue;
cs=1LL*getC(i-1,m/2)*getC(n-i,m/2)%mod;
ans+=1LL*cs*(m/2)%mod*getsum(i-1)%mod*ny[i-1]%mod;
if(ans>=mod) ans-=mod;
ans+=1LL*cs*(m/2)%mod*getsum(n-i)%mod*ny[n-i]%mod;
if(ans>=mod) ans-=mod;
}
}
} else {
dfs(1,0);
dfs2(1,0);
}
printf("%d
",ans);
return 0;
}
C. 虚构推理
可以枚举每一个时刻，然后取最小值
但是秒不一定是整数，所以直接枚举精度不大好处理
于是可以模拟退火
把时针和分针提前排好序可以做到 (log(n)) 计算答案，可以多做不少遍模拟退火
代码比较玄学，多交几遍可以 (AC)
代码
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<ctime>
#define rg register
const int maxn=5e4+5;
typedef double db;
const db eps=1e-6,xs=0.999;
struct asd{
int a,b,c;
}jl[maxn];
struct jie{
db jd;
int id;
}orza[maxn],orzb[maxn];
bool cmp(jie aa,jie bb){
return aa.jd<bb.jd;
}
int n,jla,jlb;
db jlc,ans=1000;
db jsfz(rg db a1,rg db b1,rg db c1,rg db a2,rg db b2,rg db c2){
rg db ans1=(db)b1*6.0+(db)c1/10.0;
rg db ans2=(db)b2*6.0+(db)c2/10.0;
return fabs(ans1-ans2);
}
db jssz(rg db a1,rg db b1,rg db c1,rg db a2,rg db b2,rg db c2){
rg db ans1=a1*30+(db)b1/2.0+(db)c1/120.0;
rg db ans2=a2*30+(db)b2/2.0+(db)c2/120.0;
return fabs(ans1-ans2);
}
int ef1(db aa){
rg int l=1,r=n,mids;
if(aa>=360) aa-=360;
if(aa<0) aa+=360;
while(l<=r){
mids=(l+r)>>1;
if(orza[mids].jd>=aa) r=mids-1;
else l=mids+1;
}
return l;
}
int ef2(db aa){
rg int l=1,r=n,mids;
if(aa>=360) aa-=360;
if(aa<0) aa+=360;
while(l<=r){
mids=(l+r)>>1;
if(orzb[mids].jd>=aa) r=mids-1;
else l=mids+1;
}
return l;
}
db jsa(rg int now,rg db aa,rg db bb,rg db cc){
rg int id;
if(now<1 || now>n) return 0;
rg db ans1,ans2;
id=orza[now].id;
ans1=jsfz(aa,bb,cc,jl[id].a,jl[id].b,jl[id].c);
ans2=jssz(aa,bb,cc,jl[id].a,jl[id].b,jl[id].c);
ans1=std::min(ans1,360.0-ans1);
ans2=std::min(ans2,360.0-ans2);
return std::max(ans1,ans2);
}
db jsb(rg int now,rg db aa,rg db bb,rg db cc){
rg int id;
if(now<1 || now>n) return 0;
rg db ans1,ans2;
id=orzb[now].id;
ans1=jsfz(aa,bb,cc,jl[id].a,jl[id].b,jl[id].c);
ans2=jssz(aa,bb,cc,jl[id].a,jl[id].b,jl[id].c);
ans1=std::min(ans1,360.0-ans1);
ans2=std::min(ans2,360.0-ans2);
return std::max(ans1,ans2);
}
db js(rg db aa,rg db bb,rg db cc){
rg db nans=0,jd1=jssz(aa,bb,cc,0,0,0),jd2=jsfz(aa,bb,cc,0,0,0);
rg int wz=ef1(jd1+180.0);
nans=std::max(nans,jsa(wz-1,aa,bb,cc));
nans=std::max(nans,jsa(wz,aa,bb,cc));
nans=std::max(nans,jsa(1,aa,bb,cc));
nans=std::max(nans,jsa(n,aa,bb,cc));
wz=ef2(jd2+180.0);
nans=std::max(nans,jsb(wz-1,aa,bb,cc));
nans=std::max(nans,jsb(wz,aa,bb,cc));
nans=std::max(nans,jsb(1,aa,bb,cc));
nans=std::max(nans,jsb(n,aa,bb,cc));
return nans;
}
void mnth(){
db t=1.0;
rg int aa=12,bb=60;
while(t>eps){
if(aa) aa--;
if(bb) bb--;
rg int na=(jla+aa*(rand()%2-1))%12;
rg int nb=(jlb+bb*(rand()%2-1))%60;
db nc=jlc+(rand()*2-RAND_MAX)%60*t;
if(na<0) na+=12;
if(nb<0) nb+=60;
if(nc<0) nc+=60;
if(nc>=60) nc-=60;
db nw=js(na,nb,nc);
db cha=nw-ans;
if(cha<0){
jla=na,jlb=nb,jlc=nc,ans=nw;
} else if(exp(-cha/t)*RAND_MAX>rand()){
jla=na,jlb=nb,jlc=nc;
}
t*=xs;
}
}
int main(){
srand(time(0));
scanf("%d",&n);
rg char ch1,ch2;
for(rg int i=1;i<=n;i++){
scanf("%02d%c%02d%c%02d",&jl[i].a,&ch1,&jl[i].b,&ch2,&jl[i].c);
jl[i].a%=12;
orza[i].id=orzb[i].id=i;
orza[i].jd=jssz(jl[i].a,jl[i].b,jl[i].c,0,0,0);
orzb[i].jd=jsfz(jl[i].a,jl[i].b,jl[i].c,0,0,0);
}
std::sort(orza+1,orza+1+n,cmp);
std::sort(orzb+1,orzb+1+n,cmp);
ans=js(jla,jlb,jlc);
for(rg int i=1;i<=350;i++){
mnth();
}
printf("%.8f
",ans);
return 0;
}
D. 记忆碎片
考虑 (DP)
设 (f[i][s]) 表示当前考虑了前 (i) 短的边,联通状态为 (s) 的方案数,(s) 的表示方法可以使用最小表示法(其实就是(sort)之后拿(vector)存一下再用 (map) 映射)
状态数不是很多，最多只有 (37338)
转移时只需要分两种情况
1、当前的边不是最小生成树中的边，此时只能从某一个联通块中选两个没有边的点去连
2、当前的边是最小生成树中的边，考虑当前边连接了哪两个之前没有相连的联通块即可
常数巨大
代码
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#define rg register
const int maxn=45,maxm=40005,mod=1e9+7;
int n,f[maxn*maxn][maxm],tot,sum[maxm],m;
bool vis[maxn*maxn];
std::vector<int> g[maxm],cs;
std::map<std::vector<int>,int> mp;
void dfs(rg int now,rg int lat){
if(lat==0){
if(now==0){
g[++tot]=cs;
for(rg int i=0;i<g[tot].size();i++){
rg int u=g[tot][i];
sum[tot]+=1LL*u*(u-1)/2%mod;
if(sum[tot]>=mod) sum[tot]-=mod;
}
}
return;
}
dfs(now,lat-1);
if(now>=lat){
cs.push_back(lat);
dfs(now-lat,lat);
cs.pop_back();
}
}
int main(){
scanf("%d",&n);
m=(n-1)*n/2;
rg int aa;
for(rg int i=1;i<n;i++){
scanf("%d",&aa);
vis[aa]=1;
}
dfs(n,n);
for(rg int i=1;i<=tot;i++){
std::reverse(g[i].begin(),g[i].end());
mp[g[i]]=i;
}
f[0][1]=1;
for(rg int i=0;i<m;i++){
for(rg int j=1;j<=tot;j++){
if(f[i][j]){
if(vis[i+1]){
for(rg int k=0;k<g[j].size();k++){
for(rg int o=k+1;o<g[j].size();o++){
cs.clear();
cs.push_back(g[j][k]+g[j][o]);
for(rg int p=0;p<g[j].size();p++){
if(p!=k && p!=o){
cs.push_back(g[j][p]);
}
}
std::sort(cs.begin(),cs.end());
f[i+1][mp[cs]]+=1LL*f[i][j]*g[j][k]%mod*g[j][o]%mod;
if(f[i+1][mp[cs]]>=mod) f[i+1][mp[cs]]-=mod;
}
}
} else {
f[i+1][j]+=1LL*f[i][j]*(sum[j]-i)%mod;
if(f[i+1][j]>=mod) f[i+1][j]-=mod;
}
}
}
}
printf("%d
",f[m][tot]);
return 0;
}