本文最后更新于:2020年9月21日 晚上
D1T1 神奇的幻方
简单模拟
#include<bits/stdc++.h>
using namespace std;
int n;
int a[50][50];
int main()
{
scanf("%d",&n);
int x=1,y=(n+1)/2;
a[x][y]=1;
for(int i=2;i<=n*n;i++)
{
if(x==1 && y!=n) x=n,y++;
else if(x!=1 && y==n) x--,y=1;
else if(x==1 && y==n) x++;
else if(!a[x-1][y+1]) x--,y++;
else x++;
a[x][y]=i;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
printf("%d%c",a[i][j],(j<n)?' ':'\n');
}
D1T2 信息传递
n个点,每个点出度为1,形成的图为基环(内向)树构成的森林。题目要求最小的环长。
可以用并查集维护,这样就能找出所有环上的某一条边了,沿环绕一圈求出环长。这样每个环只遍历一次,复杂度线性。
#include<bits/stdc++.h>
using namespace std;
#define N 200010
#define rep(i,l,r) for(int i=l;i<=r;++i)
int n;
int a[N];
int fa[N];
int getfa(int x)
{
return x==fa[x]?x:fa[x]=getfa(fa[x]);
}
bool Union(int x,int y)
{
x=getfa(x);
y=getfa(y);
if(x==y) return false;
fa[x]=y;
return true;
}
int walk(int x)
{
int ans=0,y=x;
while(true)
{
y=a[y];
++ans;
if(y==x) break;
}
return ans;
}
int main()
{
scanf("%d",&n);
rep(i,1,n) scanf("%d",a+i),fa[i]=i;
int ans=~0U>>1;
rep(i,1,n)
if(!Union(i,a[i]))
ans=min(ans,walk(i));
printf("%d\n",ans);
}
D1T3 斗地主
搜索剪枝结合贪心,贪心即考虑枚举的牌型顺序,肯定优先走出牌多的,比如顺子,四带二等等,这样就能使最优性剪枝发挥出作用了。
#include<bits/stdc++.h>
using namespace std;
int T,n,ans;
int a[16];
int calc()
{
int now=0;
for(int i=0;i<=14;++i)
if(a[i])
++now;
return now;
}
void dfs(int step,int x)
{
if(step>=ans) return;
ans=min(ans,step+calc());
for(int i=3;i<=13;++i)//san shun
{
int j=i;
while(j<=14 && a[j]>=3) ++j;
if(j-i<2) continue;
a[i]-=3;
for(int k=i+1;k<j;++k)
{
a[k]-=3;
dfs(step+1,x-(k-i+1)*3);
}
for(int k=i;k<j;++k)
a[k]+=3;
}
for(int i=3;i<=12;++i)// shuang shun
{
int j=i;
while(j<=14 && a[j]>=2) ++j;
if(j-i<3) continue;
a[i]-=2;a[i+1]-=2;
for(int k=i+2;k<j;++k)
{
a[k]-=2;
dfs(step+1,x-(k-i+1)*2);
}
for(int k=i;k<j;++k)
a[k]+=2;
}
for(int i=3;i<=10;++i) //dan shun
{
int j=i;
while(j<=14 && a[j]>=1) ++j;
if(j-i<5) continue;
a[i]--;a[i+1]--;a[i+2]--;a[i+3]--;
for(int k=i+4;k<j;++k)
{
a[k]--;
dfs(step+1,x-(k-i+1));
}
for(int k=i;k<j;++k)
a[k]++;
}
for(int i=2;i<=14;++i)
if(a[i]==4)
{
a[i]=0;
dfs(step+1,x-4);
for(int j=0;j<=14;++j)
if(a[j]>0)
{
a[j]--;
for(int k=j;k<=14;++k)
if(a[k]>0)
{
a[k]--;
dfs(step+1,x-6);
a[k]++;
}
a[j]++;
}
for(int j=2;j<=14;++j)
if(a[j]>1)
{
a[j]-=2;
for(int k=j;k<=14;++k)
if(a[k]>1)
{
a[k]-=2;
dfs(step+1,x-8);
a[k]+=2;
}
a[j]+=2;
}
a[i]=4;
}
for(int i=2;i<=14;++i)
if(a[i]>=3)
{
a[i]-=3;
dfs(step+1,x-3);
for(int j=0;j<=14;++j)
if(a[j]>=1)
{
a[j]--;
dfs(step+1,x-4);
a[j]++;
}
for(int j=2;j<=14;++j)
if(a[j]>=2)
{
a[j]-=2;
dfs(step+1,x-5);
a[j]+=2;
}
a[i]+=3;
}
}
int main()
{
scanf("%d%d",&T,&n);
while(T--)
{
memset(a,0,sizeof(a));
for(int i=1;i<=n;++i)
{
int x;
scanf("%d%*d",&x);
if(x==1) x=14;
a[x]++;
}
ans=n;
dfs(0,n);
printf("%d\n",ans);
}
}
D2T1 跳石头
非常基本的二分答案+贪心。二分一个最短跳跃距离mid,判断是否可行,即需要移走的块数是否小于等于M。可行,说明答案大于等于mid;不可行,说明答案小于mid、
#include<bits/stdc++.h>
using namespace std;
#define N 50010
#define rep(i,l,r) for(int i=l;i<=r;++i)
int a[N];
int n,m,H;
bool ok(int len)
{
int last=0,i=0,ans=0;
while(true)
{
while(i<=n&& a[i]-last<len) ++i;
if(i>n) break;
++ans;
last=a[i];
}
if(ans>0 && H-last<len) --ans;
return n-ans<=m;
}
int main()
{
scanf("%d%d%d",&H,&n,&m);
rep(i,1,n) scanf("%d",a+i);
int l=1,r=H;
while(l<r)
{
int mid=l+(r-l+1)/2;
if(ok(mid)) l=mid;
else r=mid-1;
}
printf("%d\n",l);
}
D2T2 子串
记表示字符串A考虑前 个字符,字符串B考虑前 个字符,分 段的方案数。
目前虽然AC了,但较为暴力,改天优化一下。
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,K;
int dp[2][1005][205];
char a[1005],b[205];
void add(int &x,int y)
{
x+=y;
if(x>=mod) x-=mod;
}
int main()
{
scanf("%d%d%d",&n,&m,&K);
scanf("%s",a+1);
scanf("%s",b+1);
for(int i=0; i<=n; ++i)
dp[0][i][0]=1;
for(int k=1; k<=K; ++k)
{
memset(dp[k&1],0,sizeof(dp[k&1]));
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
{
add(dp[k&1][i][j],dp[k&1][i-1][j]);
int l=0;
while(l<j && l<i && a[i-l]==b[j-l])
{
++l;
add(dp[k&1][i][j],dp[(k&1)^1][i-l][j-l]);
}
//cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<endl;
}
}
printf("%d\n",dp[K&1][n][m]);
}
D2T3 运输计划
二分答案+树上差分
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 300010
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define dow(i,l,r) for(int i=l;i>=r;--i)
int e,head[N<<1],w[N<<1],last[N<<1],p[N];
int deep[N],fa[N],num[N],son[N];
int top[N];
int a[N],dis[N];
int u[N],v[N],lca[N],val[N];
int n,m;
void add(int x,int y,int c)
{
head[++e]=y;w[e]=c;
last[e]=p[x];
p[x]=e;
}
void dfs(int x,int pre,int dep)
{
deep[x]=dep;
fa[x]=pre;
num[x]=1;
for(int j=p[x];j;j=last[j])
{
int y=head[j];
if(y==pre) continue;
dis[y]=dis[x]+w[j];
dfs(y,x,dep+1);
num[x]+=num[y];
if(son[x]==-1||num[y]>num[son[x]])
son[x]=y;
}
}
void dfs_son(int x,int rt)
{
top[x]=rt;
if(son[x]==-1) return;
else dfs_son(son[x],rt);
for(int j=p[x];j;j=last[j])
if(head[j]!=fa[x] && head[j]!=son[x])
dfs_son(head[j],head[j]);
}
void dfs(int x)
{
for(int j=p[x];j;j=last[j])
{
int y=head[j];
if(y==fa[x]) continue;
dfs(y);
a[x]+=a[y];
}
}
int calc(int x,int y)
{
int f1=top[x],f2=top[y];
while(f1!=f2)
{
if(deep[f1]<deep[f2])
{
swap(x,y);
swap(f1,f2);
}
x=fa[f1];
f1=top[x];
}
if(deep[x]>deep[y]) swap(x,y);
return x;
}
bool ok(int mid)
{
int tot=0,mx=0,ans=0;
memset(a,0,sizeof(a));
rep(i,1,m)
if(val[i]>mid)
{
a[u[i]]++;
a[v[i]]++;
a[lca[i]]-=2;
++tot;
ans=max(ans,val[i]);
}
dfs(1);
rep(i,1,n)
if(a[i]>=tot)
mx=max(mx,dis[i]-dis[fa[i]]);
return ans-mx<=mid;
}
int main()
{
scanf("%d%d",&n,&m);
rep(i,1,n-1)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
add(x,y,c);
add(y,x,c);
}
memset(son,-1,sizeof(son));
dfs(1,0,1);
dfs_son(1,1);
rep(i,1,m)
{
scanf("%d%d",u+i,v+i);
lca[i]=calc(u[i],v[i]);
val[i]=dis[u[i]]+dis[v[i]]-2*dis[lca[i]];
}
int l=0,r=4e8;
while(l<r)
{
int mid=(l+r)>>1;
if(ok(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",l);
return 0;
}
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!