预计得分：100+70+100+50=320
实际得分100+63+77+30=270
Ctrl_C+Ctrl_V时不要粘贴翻译的，直接粘原文，
In a single line of the output print an integer — the maximum loyalty among all paths from the first node to the n-th one. If such paths do not exist or the maximum loyalty equals 0, print in a single line "Nice work, Dima!" without the quotes. 输出能从1出发到n的总数值数，如果没有，输出“Nice work,Dima!”两个判错之间在逗号前差了一个空格 QAQ
T1
dfs+剪枝
对于搜到的一组（a,b,c），将a*t^2+b*t+1（t>=20）标记，下一次再经过时就直接return
代码
#include<bits/stdc++.h>
using namespace std;
int n,k;
int numa,numb,numc,ans[100100],cnt;
int vis[100100];
bool sum[100100],pd;
inline int getsum(int a,int b,int c){return a*441+b*21+c;}
void dfs(int deep,int a,int b,int c)
{
if(a>numa||b>numb||c>numc)return;
//cout<<a<<"!"<<b<<"!"<<c<<endl;system("pause");
sum[a*441+b*21+c]=1;
if(!a)
{
if(!vis[c])ans[++cnt]=c;
//cout<<c<<endl;
vis[c]=1;
}
if(a)
{
int k=getsum(0,a+b,c),kk=getsum(a+b-numb,numb,c);
if(a+b<=numb&&!sum[k])sum[k]=1,dfs(deep+1,0,a+b,c);
else
{
if(!sum[kk]&&a+b>numb) sum[kk]=1,dfs(deep+1,a+b-numb,numb,c);
}
k=getsum(0,b,a+c);kk=getsum(a+c-numc,b,numc);
if(a+c<=numc&&!sum[k])sum[k]=1,dfs(deep+1,0,b,a+c);
else
{
if(!sum[kk]&&a+c>numc) sum[kk]=1,dfs(deep+1,a+c-numc,b,numc);
}
}
if(b)
{
int k=getsum(a+b,0,c),kk=getsum(numa,a+b-numa,c);
if(a+b<=numb&&!sum[k])sum[k]=1,dfs(deep+1,a+b,0,c);
else
{
if(!sum[kk]&&a+b>numa)sum[kk]=1,dfs(deep+1,numa,a+b-numa,c);
}
k=getsum(a,0,b+c);kk=getsum(a,b+c-numc,numc);
if(b+c<=numc&&!sum[k])sum[k]=1,dfs(deep+1,a,0,b+c);
else
{
if(!sum[kk]&&b+c>numc) sum[kk]=1,dfs(deep+1,a,b+c-numc,numc);
}
}
if(c)
{
int k=getsum(a+c,b,0),kk=getsum(numa,b,a+c-numa);
if(a+c<=numa&&!sum[k])sum[k]=1,dfs(deep+1,a+c,b,0);
else
{
if(!sum[kk]&&a+c>numa) sum[k]=1,dfs(deep+1,numa,b,a+c-numa);
}
k=getsum(a,b+c,0);kk=getsum(a,numb,b+c-numb);
if(b+c<=numb&&!sum[k])sum[k]=1,dfs(deep+1,a,b+c,0);
else
{
if(!sum[kk]&&b+c>numb) sum[kk]=1,dfs(deep+1,a,numb,b+c-numb);
}
}
}
int main()
{
scanf("%d%d%d",&numa,&numb,&numc);
dfs(1,0,0,numc);
sort(ans+1,ans+cnt+1);
for(int i=1;i<=cnt;i++)printf("%d ",ans[i]);
}
T1
T2
容易想到区间一定是连续的
但是这种容易想到的一般都是错的
例如数据
3 3
1 2 1 2
2 3 1 10000
1 2 7 8
显然区间不是连续的。
于是，我们的思路是枚举下界，二分上界，用dfs或是并查集维护1-n的连通
dfs太难打了，david-alwal太懒了，所以用了并查集
#include<bits/stdc++.h>
using namespace std;
struct edge
{
int from,to,nxxt,le,ri;
}e[100100<<1];
int head[100100],n,m,cnt,t,maxx=-1,ans;
inline void addedge(int u,int v,int l,int r)
{
cnt++;
e[cnt].from=u;
e[cnt].le=l;
e[cnt].ri=r;
e[cnt].to=v;
e[cnt].nxxt=head[u];
head[u]=cnt;
}
int lef[100100],num;
int f[100100];
int getroot(int x){if(x!=f[x])f[x]=getroot(f[x]);return f[x];}
inline int check(int l,int r)
{
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=cnt;i++)
{
int from=e[i].from,to=e[i].to;
int le=e[i].le,ri=e[i].ri;
if(le<=l&&ri>=r)
{
int f1=getroot(from);
int f2=getroot(to);
if(f1!=f2)f[f1]=f2;
}
}
if(getroot(1)==getroot(n))return 1;return 0;
}
void ef(int l,int r,int k)
{
if(l==r)
{
while(k<=l&&check(k,l)==0)l--;
ans+=l-k+1;
if(l>=k)
t=max(t,l);
return;
}
int mid=(l+r)>>1;
if(check(k,mid+1))ef(mid+1,r,k);
else ef(l,mid,k);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v,l,r;
scanf("%d%d%d%d",&u,&v,&l,&r);
addedge(u,v,l,r);
addedge(v,u,l,r);
lef[++num]=l;
maxx=max(maxx,r);
}
sort(lef+1,lef+num+1);
for(int i=1;i<=num;i++)
{
if(lef[i]<=t)continue;
else ef(lef[i],maxx,lef[i]);
}
if(ans<=0)puts("Nice work, Dima!");
else printf("%d",ans);
}
T2
T3
个人认为是最简单的一道题
一个BFS就可以解决
下标不能为负数！！
上代码
#include<bits/stdc++.h>
using namespace std;
int n,k;
queue<int>q;
int num[500100],vis[500100];
int maxx;
int main()
{
scanf("%d%d",&n,&k);
//if(n>=k){printf("%d",n-k);return 0;}
maxx=max(n,k)<<1;
q.push(n);
vis[n]=1;
while(!q.empty())
{
int now=q.front();q.pop();
if(now==k)break;
if((!vis[now+1])&&(now+1<maxx))
{
num[now+1]=num[now]+1;
vis[now+1]=1;
q.push(now+1);
}
if((!vis[now<<1])&&((now<<1)<maxx))
{
num[now<<1]=num[now]+1;
vis[now<<1]=1;
q.push(now<<1);
}
if((!vis[now-1])&&(now-1>=0))
{
num[now-1]=num[now]+1;
vis[now-1]=1;
q.push(now-1);
}
}
printf("%d",num[k]);
}
T3
T4
dfs+剪枝
剪枝1:，可行性剪枝：对于一个点（x，y），如果它左上角的颜色加上它走到底下的格子数大于k，就return 0
剪枝2，对称性剪枝：例如我们当前填到了某个格子，我们记录一下整个矩阵已使用的颜色，例如3，5都还没用，那么这个格子填上3或5，两者最终算出的方案数是相同的，这样我们就可以只计算3的方案数，5的直接加上3的就可以了。
用状压存状态特别方便
没有单独讲状态压缩的博客，只有讲状压DP的，大家就只看状压那部分的吧 详解状压 David-alwal太懒了
上代码
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int m,n,k,a[101][101],f[101][101],num[101];
//f数组存状压之后的状态，例如5个颜色，f[x][y]=13的话，
//因为13(10)=01101(2),这就代表了(x,y)左上角的点取了2,3,5,没有取1,4
int dfs(int x,int y)
{
if(y>m)x++,y=1;
if(x>n)return 1;
int ret=0,d=-1,now=f[x-1][y]|f[x][y-1],c=0;
for(int i=now;i;i-=i&-i)c++;
if(m+n-x-y+1>k-c)return 0;//剪枝1
int can=(~now)&((1<<k)-1);//能取的
for(int i=can;i;i-=i&(-i))//提取每一位二进制
{
int temp=i&(-i);
int t=log(temp+0.5)/log(2)+1;
if(a[x][y]==0||a[x][y]==t)
{
f[x][y]=now|temp;
num[t]++;
if(num[t]==1)//剪枝2
{
if(d==-1)d=dfs(x,y+1);
ret+=d;
}
else ret+=dfs(x,y+1);
ret%=mod;
num[t]--;
}
}
return ret;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
if(n+m-1>k){puts("0");return 0;}//剪枝1
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j])num[a[i][j]]++;//统计数量
}
printf("%d",dfs(1,1)%mod);
}
T4