文章目录
- 1.[岁月神偷](http://acm.usx.edu.cn/aspnet/Question.aspx?qid=1649)
- 2.[字母移动游戏](http://acm.usx.edu.cn/aspnet/Question.aspx?qid=1653)
- 3.[黑孔雀和小太阳](http://acm.usx.edu.cn/aspnet/Question.aspx?qid=1655)
- 4.[埃及分数](http://acm.usx.edu.cn/aspnet/Question.aspx?qid=1657)
- 5.[探索洞穴](http://acm.usx.edu.cn/aspnet/question.aspx?qid=1658)
1.岁月神偷
暴力能过,但是正解是贪心
要使初始状态变为目标状态,我们不仅需要两个状态相邻雕像的相对朝向相同,还需要每个雕像的绝对朝向相同。
观察四种操作,我们可以发现:
操作一,仅改变所有雕像的绝对朝向。
操作四,改变“朱雀”和{“青龙”,“玄武”,“白虎”}的相对朝向。
操作二,改变{“朱雀”,“青龙”}和{“玄武”,“白虎”}的相对朝向。
操作三,改变{“朱雀”,“白虎”}和{“青龙”,“玄武”}的相对朝向。
所以,我们可以按照最少使用操作三、二、四的顺序,修改“玄武”和“白虎”、“青龙”和“玄武”、“朱雀”和“青龙”的相对朝向,最后再用操作一修改绝对朝向,即可使用最少操作达到目标状态。
时间复杂度O(1)。
2.字母移动游戏
直接每个点移一下的话是完全可以在 n次内完成的,我们的目的就是尽可能偷点懒,一些点不移动
手玩一下样例以后会发现实际上是求 S的子序列和 T的子串相同的最大长度
因为我们可以把 S选中的这些点不动,其他的放到前面或后面,发现这些点并在了一起,并且相对顺序没变,所以可以做到与 T完全相同
具体做法可以使用双指针
时间复杂度 O(n2)
3.黑孔雀和小太阳
当小太阳先手时,手动模拟可以发现只有 n是 3的倍数,且 ai都为 1的情况小太阳才会输
(如果熟悉巴什博弈的话,可能不用模拟也能想到 3这个数)
当黑孔雀先手时,因为黑孔雀想赢所以肯定想转换到上述小太阳会输的状态,
所以小太阳在 n是 3的倍数,且有 n−1个数为 1时会输(这时黑孔雀只需从不是 1的那堆石子里拿掉一些石子使状态变为1 1 1),
或者 n是 3的倍数余 1,且 n−1个数为 1时会输(此时黑孔雀只需拿掉一堆石子,小太阳就到了必输态)
4.埃及分数
从 1…inf,每一个分母,都有选中和不选中两种状态,如果选中,那么就减去这个分数,没有就是跳过,我们可以逐次放宽项数的限制,即迭代加深搜索。
主要的两个剪枝如下:
1. 限制开头:并不是每次都要从 1开始遍历分母
假设现在要分解 ba,那么分母 ab就是起点: ab1=ba ,假设起点 s<ab,那么显而易见,起点的分数已经比我们要的总和 ba大了。
2. 限制结尾:
比较简单的限制结尾可以这样看:如果我已经找到分母k了,而现在要分解得分数是 ba,现在还要找 m个单位分数,
那么可以想象:有可能 km<ba,也就是说就算全是 k1,我凑够 m个,也达不到 a/b,
那么说明前面的分配方案肯定有无,直接可以 return了。加上这个剪枝已经可以得到答案了,只是时间有点慢罢了。
5.探索洞穴
因为查询次数较多,范围较大,所以我们记录探索完 i个点所需最小 x。
设 f[i][u][0/1]为探索完 u的子树中 i个节点(包括自己),是 (1)否 (0)回到 u的最短路径长
然后在树上每个点做一边背包就好了
要注意的是,做背包时不能从 1到 n枚举,这样总复杂度是 O(n3)的
考虑到 u中选的点数一定 ≤size[u],那么 dp时可以只枚举到 size[u]
这时就会发现复杂度降为了 O(n2)
原理戳这
#include<cstdio>
#include<cstring>
const int N=502;
int T,i,tot,h[N],l,r,mid,f[N][N][2],n,x,y,z,vis[N],q,sz[N];
struct node{
int to,ne,w;
}e[N<<1];
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
int x=0,fl=1;char ch=gc();
for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
return x*fl;
}
inline void wri(int a){if(a<0)a=-a,putchar('-');if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(int a){wri(a),puts("");}
inline int min(int x,int y){return x<y?x:y;}
void add(int x,int y,int z){e[++tot]=(node){y,h[x],z},h[x]=tot;}
void dfs(int u,int fa){
f[1][u][1]=0,f[1][u][0]=1e9,sz[u]=1;
for (int i=2;i<=n;i++) f[i][u][0]=f[i][u][1]=1e9;
for (int i=h[u],v;i;i=e[i].ne)
if ((v=e[i].to)!=fa){
dfs(v,u),sz[u]+=sz[v];
int w=e[i].w;
for (int i=sz[u];i>1;i--)
for (int j=1;j<i && j<=sz[v];j++)
f[i][u][1]=min(f[i][u][1],f[i-j][u][1]+2*w+f[j][v][1]),
f[i][u][0]=min(f[i][u][0],min(f[i-j][u][1]+w+min(f[j][v][0],f[j][v][1]),f[j][v][1]+w*2+min(f[i-j][u][0],f[i-j][u][1])));
}
}
int main(){
for (T=rd();T;T--){
n=rd(),tot=0,memset(h,0,n<<2);
for (i=1;i<n;i++) x=rd(),y=rd(),z=rd(),add(x,y,z),add(y,x,z),vis[x]=T;
for (i=0;i<n;i++)
if (vis[i]!=T) break;
dfs(i,-1);
for (q=rd();q--;){
x=rd(),l=1,r=n;
while (l<r){
mid=l+r+1>>1;
if (f[mid][i][0]<=x) l=mid;
else r=mid-1;
}
wln(l);
}
}
}