2021-09-16 19:41:18 星期四
淦，上一个大集合卡展了，写博客写到一半就崩溃，崩溃了好几次了，于是新开了一个
打怪
打正解是不可能打正解的~~这个是考完了用乱搞贪心水掉的，然后拿沈sir程序造hack数据hack自己结果把沈sir hack了...数据是XIN造的，把我也hack了，本来以为只有自己会无脸测试点分治结果沈sir也来了个if(n<=10)...虽然沈sir不偷懒改改就能过吧...
Code
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("fittest.in","r",stdin);freopen("fittest.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline ll min(ll a,ll b){return a<b?a:b;}
inline void pi(ll x){pf("%lld ",x);}inline void pn(){pf("\n");}
const int N=3e5+10;
struct pt{
int cheng;db chu;
int c,a,d,id;
}p[N];int n,b,sum;bool vis[N];ll ans=1e18;
inline bool com(pt a,pt b){return a.cheng==b.cheng?a.a>b.a:a.cheng>b.cheng;}
inline bool Com(pt a,pt b){return a.chu<b.chu;}
inline void solve(){
std::sort(p+1,p+n+1,Com);
F(i,1,n)F(j,i+1,n){
vis[i]=vis[j]=1;
int sum=0;ll aans=0;
F(k,1,n)if(!vis[k])sum+=p[k].a;
F(k,1,n)if(!vis[k]){
sum-=p[k].a;aans+=1ll*p[k].a*p[k].c;
aans+=1ll*sum*(p[k].c+1);
}
vis[i]=vis[j]=0;
ans=min(ans,aans);
}pi(ans);
}
inline short main(){
file();
n=read();b=read();
F(i,1,n){
p[i].id=i;
p[i].a=read(),p[i].d=read();
sum+=p[i].a;
p[i].c=(p[i].d-1)/b;
p[i].cheng=p[i].c*p[i].a;
p[i].chu=(db)1.0*(p[i].c+1)/(db)p[i].a;
}
if(n<=200){solve();return 0;}
std::sort(p+1,p+n+1,com);
vis[p[1].id]=vis[p[2].id]=1;
sum-=p[1].a,sum-=p[2].a;
std::sort(p+1,p+n+1,Com);ans=0;
F(i,1,n)if(!vis[p[i].id]){
sum-=p[i].a;ans+=1ll*p[i].a*p[i].c;
ans+=1ll*sum*(p[i].c+1);
}pi(ans);
return 0;
}
}
signed main(){return EMT::main();}
选择
首先每个点连接的边<=10,n<=1e3于是可以状压dp，考试时想到了这个，但是不会处理经过根节点的路径和叶子节点的关系，
可以尝试状压表示经过根节点最多路径有几条，尝试删去某个子树，如果删掉之后答案没变，那么可以将这个子树对应的儿子的延伸结点复制过来，其他的就是普通树形dp统计上子树内的路径即可。
Code
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
namespace EMT{
typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;
#define pf printf
#define F(i,a,b) for(register int i=a;i<=b;i++)
#define D(i,a,b) for(register int i=a;i>=b;i--)
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void file(){freopen("select.in","r",stdin);freopen("select.out","w",stdout);}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline void pi(int x){pf("%d ",x);}inline void pn(){pf("\n");}
const int N=1e3+10;
int head[N],co,n,m,id[N];
int f[N][1<<10],dp[N];
struct pair{int a,b;};
bool graph[N][N];pair rec[N];int cnt,Rec[N],Cnt;
std::vector<int>son[N],touch[N];
struct node{
int next,to;
}e[N<<1];
inline void add(int next,int to){e[++co]=(node){head[next],to};head[next]=co;}
inline void dfs1(int k,int fa){
int tot=0;
for(register int i=head[k],j;i;i=e[i].next){
if((j=e[i].to)==fa)continue;
++tot;son[k].push_back(j);
id[j]=tot;
dfs1(j,k);
}
}
inline void dfs(int k){
touch[k].push_back(k);
for(auto j:son[k])dfs(j),dp[k]+=dp[j];
cnt=Cnt=0;
for(auto i:son[k])
for(auto j:son[k])if(id[i]<id[j]){
for(auto l:touch[i])
for(auto o:touch[j])
if(graph[l][o])
{rec[++cnt]=(pair){i,j};goto ed;}
ed:;
}
for(auto i:son[k])
for(auto j:touch[i])
if(graph[k][j])Rec[++Cnt]=i;
int maxn=0;
F(i,0,(1<<son[k].size())-1){
maxn=max(maxn,f[k][i]);
F(j,1,cnt){
int u=rec[j].a,v=rec[j].b;
if(i&(1<<(id[u]-1))||i&(1<<(id[v]-1)))continue;
f[k][i|(1<<(id[u]-1))|(1<<(id[v]-1))]=max(f[k][i|(1<<(id[u]-1))|(1<<(id[v]-1))],f[k][i]+1);
}
F(j,1,Cnt){
int u=Rec[j];
if(i&(1<<(id[u]-1)))continue;
f[k][i|(1<<(id[u]-1))]=max(f[k][i|(1<<(id[u]-1))],f[k][i]+1);
}
}dp[k]+=maxn;
for(auto x:son[k]){
int Maxn=0;
F(i,0,(1<<son[k].size())-1)f[k][i]=0;
F(i,0,(1<<son[k].size())-1){
Maxn=max(Maxn,f[k][i]);
F(j,1,cnt){
int u=rec[j].a,v=rec[j].b;
if(u==x||v==x)continue;
if(i&(1<<(id[u]-1))||i&(1<<(id[v]-1)))continue;
f[k][i|(1<<(id[u]-1))|(1<<(id[v]-1))]=max(f[k][i|(1<<(id[u]-1))|(1<<(id[v]-1))],f[k][i]+1);
}
F(j,1,Cnt){
int u=Rec[j];
if(u==x)continue;
if(i&(1<<(id[u]-1)))continue;
f[k][i|(1<<(id[u]-1))]=max(f[k][i|(1<<(id[u]-1))],f[k][i]+1);
}
}
if(Maxn==maxn)for(auto i:touch[x])touch[k].push_back(i);
}
}
inline short main(){
file();
n=read();
F(i,1,n-1){
int x=read(),y=read();
add(x,y);add(y,x);
}dfs1(1,0);
m=read();
F(i,1,m){
int u=read(),v=read();
graph[u][v]=graph[v][u]=1;
}dfs(1);
pi(dp[1]);
return 0;
}
}
signed main(){return EMT::main();}