神奇的幻方 按照题意模拟
信息传递 不难想到这是一个基环树的森林，找一个最小环就可以了
斗地主 毒瘤搜索题，时限不紧，但是要考虑全所有情况
需要注意的一些地方：
先枚举顺子、再枚举四带二、三带一/二、炸弹等
最后剩下的单牌、对子可以一次统计出来
顺子不一定越长越好，不能有2、大小王
两张王不能当成对子带出去，但可以单着被带出去
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int INF=0x3f3f3f3f;
int T,n,a[16],ans=INF;
inline bool check(){
for(int i=1;i<=14;++i)
if(a[i]) return 0;
return 1;
}
void dfs(int t){
// cout<<t<<endl;
// for(int i=1;i<=14;++i)
// printf("%d ",a[i]);
// puts("");
if(t>ans) return;
if(check()){
ans=min(ans,t);
return;
}
for(int d=1;d<=3;++d){ //顺子
int m=(d==1?5:(5-d));
for(int l=1;l<=13-m;++l)
if(a[l]>=d){
int r=l-1;
while(r<12&&a[r+1]>=d){
++r; a[r]-=d;
if(r-l+1>=m) dfs(t+1);
}
for(int i=l;i<=r;++i) a[i]+=d;
}
}
for(int i=1;i<=13;++i) //炸弹/四带二
if(a[i]>=4){
int cnt=0,b[4];
a[i]-=4;
for(int j=1;j<=14&&cnt<2;++j)
if(a[j]==1) --a[j],b[++cnt]=j;
if(cnt==1) ++a[b[1]];
dfs(t+1);
if(cnt==2) ++a[b[1]],++a[b[2]];
cnt=0;
for(int j=1;j<=13&&cnt<2;++j)
if(a[j]==2) a[j]-=2,b[++cnt]=j;
if(cnt){
dfs(t+1);
a[b[1]]+=2;
if(cnt==2) a[b[2]]+=2;
}
a[i]+=4;
}
for(int i=1;i<=13;++i) //三张/三带一/三带二
if(a[i]>=3){
int k=0;
a[i]-=3;
for(int j=1;j<=14&&!k;++j)
if(j!=i&&a[j]==1) --a[j],k=j;
dfs(t+1);
if(k) ++a[k];
k=0;
for(int j=1;j<=14&&!k;++j)
if(a[j]==2) a[j]-=2,k=j;
if(k){
dfs(t+1);
a[k]+=2;
}
a[i]+=3;
}
int b[16],cnt=0;
for(int i=1;i<=14;++i){
b[i]=a[i];
if(a[i]) ++cnt;
a[i]=0;
}
dfs(t+cnt);
for(int i=1;i<=14;++i) a[i]=b[i];
}
int main()
{
// freopen("out.txt","w",stdout);
scanf("%d%d",&T,&n);
while(T--){
ans=INF;
memset(a,0,sizeof(a));
int x,y;
for(int i=1;i<=n;++i){
scanf("%d%d",&x,&y);
if(x==0) x=14;
else if(x<=2) x+=11;
else x-=2;
++a[x];
}
dfs(0);
printf("%d
",ans);
}
return 0;
}
跳石头 二分答案，贪心check
子串 DP，dp[i][j][k][0/1]表示搞到A的前i个字符、B的前j个字符、取了k段、第i个字符选/不选的方案数
dp[i][j][k][0]=dp[i-1][j][k][0]+dp[i-1][j][k][1]);
if(A[i]==B[j]) dp[i][j][k][1]=dp[i-1][j-1][k-1][0]+dp[i-1][j-1][k-1][1]+dp[i-1][j-1][k][1];
最后滚动数组优化空间
运输计划 毒瘤卡常题，我弃疗了，二分答案d，将所有大于d的k条路径树上差分，取被经过k次的边的最大值，判断删去这条边是否使最长的路径<=d
95pts:
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=300010;
inline int read(){
int x=0; char c=getchar();
while(c<'0') c=getchar();
while(c>='0') x=x*10+c-'0',c=getchar();
return x;
}
int n,m,f[MAXN][25],dep[MAXN],dis[MAXN];
int Head[MAXN],num;
struct Edge{
int to,w,nxt;
} e[MAXN<<1];
inline int add(int x,int y,int z){
e[++num]=(Edge){y,z,Head[x]};
Head[x]=num;
}
struct Path{
int s,t,len,lca;
}p[MAXN];
inline bool cmp(Path x,Path y){
return x.len<y.len;
}
void dfs(int x,int fa){
f[x][0]=fa;
dep[x]=dep[fa]+1;
for(int k=1;(1<<k)<=dep[x];++k)
f[x][k]=f[f[x][k-1]][k-1];
for(int i=Head[x];i;i=e[i].nxt){
int v=e[i].to;
if(v!=fa){
dis[v]=dis[x]+e[i].w;
dfs(v,x);
}
}
}
int Lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=22;i>=0;--i)
if(dep[f[x][i]]>=dep[y])
x=f[x][i];
if(x==y) return x;
for(int i=22;i>=0;--i)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
int K,diff[MAXN],maxx;
int dfs1(int x){
int sum=diff[x];
for(int i=Head[x];i;i=e[i].nxt){
int v=e[i].to;
if(v!=f[x][0]){
int t=dfs1(v);
sum+=t;
if(t==K)
maxx=max(maxx,e[i].w);
}
}
diff[x]=0;
return sum;
}
inline bool check(int d){
int l=1,r=m;
while(l<r){
int mid=(l+r)>>1;
if(p[mid].len>d) r=mid;
else l=mid+1;
}
K=m-l+1;
for(int i=l;i<=m;++i){
++diff[p[i].s];
++diff[p[i].t];
diff[p[i].lca]-=2;
}
maxx=0; dfs1(1);
return p[m].len-maxx<=d;
}
int main()
{
n=read(); m=read();
int x,y,z;
for(int i=1;i<n;++i){
x=read(); y=read(); z=read();
add(x,y,z); add(y,x,z);
}
dfs(1,0);
for(int i=1;i<=m;++i){
x=read(); y=read();
p[i].s=x; p[i].t=y;
p[i].lca=Lca(x,y);
p[i].len=dis[x]+dis[y]-dis[p[i].lca]*2;
}
sort(p+1,p+1+m,cmp);
int l=0,r=p[m].len;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d
",l);
return 0;
}