- 1001迷失 https://acm.hdu.edu.cn/showproblem.php?pid=6996 期望dp + 二进制优化 + 快速幂优化
大意：有 n 个点，初始位置在 1 号点，m条无向边，每条边有个状态即是否附魔，0代表没有，1代表附魔。现需要恰好经过 k 条边到达 n 号点，且此时为附魔状态。初始为无附魔状态，每经过一次附魔的桥自身的附魔状态就会发生改变，经过普通的桥则不会发生变化。每次在某点时等概率的选择一条路走，问到n号点且为附魔状态的概率。(2<=n<=100, 1<=m<=n*(n-1)/2, 1<=k<=1e6)
思路：显然这题并不是一道推公式的题，搜索可以做但是复杂度太高。所以我们用期望dp 做。因为 步数k 很大，直接循环显然是不行的。因为步数是可以简单累加的，k 可以写成若干个二进制数相加的形式。所以我们用二进制优化。即 f[s,i,j,w]表示从 i 号节点，恰好走
2
s
2^s
2s 步，到达 j 号节点且此时附魔状态为 w 的概率。然后就可以写个 O(
n
3
l
o
g
k
n^3logk
n3logk) 的状态转移方程。最后用快速幂的求最终结果就好了。
具体看代码：
#include <bits/stdc++.h>
using namespace std;
const int N=110,M=998244353;
typedef long long LL;
int qmi(int a,int b)
{
int res=1;
while(b)
{
if(b&1)res=(LL)res*a%M;
a=(LL)a*a%M;
b>>=1;
}
return res%M;
}
int n,m,k,w[N][N],d[N],invd[N];
int f[20][N][N][2];
int F[20][N][2];//最后快速幂求结果
vector<int> g[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int _;
cin>>_;
while(_--)
{
cin>>n>>m>>k;
while(m--)
{
int x,y,v;
cin>>x>>y>>v;
d[x]++;d[y]++;//纪录度数，用于计算走一步的概率，从该点出发有x条路径，那么任选一条的概率即为 1/x.
g[x].push_back(y);
g[y].push_back(x);
w[x][y]=w[y][x]=v;//纪录路径附魔状态
}
for(int i=1;i<=n;i++)invd[i]=qmi(d[i],M-2);//求逆元
// f[s][i][j][0/1] dp状态定义
for(int i=1;i<=n;i++) //先求出 s=0,即走一步的概率，不能走到的概率为0，符合实际
for(int &j:g[i])
{
int &p=f[0][i][j][w[i][j]];
p+=invd[i];
if(p>=M)p-=M;//p的变化不会太大，减法取模更快一些
}
// 状态转移,无脑转移就好，不合法的本来就是0，无影响
for(int s=1;s<=19;s++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
{
f[s][i][j][0]=
(1LL*f[s-1][i][k][0]*f[s-1][k][j][0]+1LL*f[s-1][i][k][1]*f[s-1][k][j][1]+f[s][i][j][0])%M;
f[s][i][j][1]=
(1LL*f[s-1][i][k][0]*f[s-1][k][j][1]+1LL*f[s-1][i][k][1]*f[s-1][k][j][0]+f[s][i][j][1])%M;
}
//快速幂求走 k 步的 f[][1][n][1];
int nw=0,cnt=0;
F[0][1][0]=1;//int res=1;
while(k)
{
if(k&1) //类比快速幂中的res=res*a%M;
{
nw++;
for(int i=1;i<=n;i++) //从1号点走到了i号点，因为每次都是从1号点开始，所以起点可以不记录，F数组可以去掉一维
for(int j=1;j<=n;j++) //可以从哪个点过来
{
F[nw][i][0]=
(1LL*F[nw-1][j][0]*f[cnt][j][i][0]+1LL*F[nw-1][j][1]*f[cnt][j][i][1]+F[nw][i][0])%M; // 可以理解成多项式相乘
F[nw][i][1]=
(1LL*F[nw-1][j][0]*f[cnt][j][i][1]+1LL*F[nw-1][j][1]*f[cnt][j][i][0]+F[nw][i][1])%M;
}
}
cnt++; // 类比快速幂中的a=a*a
k>>=1;
}
cout<<F[nw][n][1]<<"\n";
memset(d,0,sizeof d);
for(int i=1;i<=n;i++)g[i].clear();
memset(f,0,sizeof f);
memset(F,0,sizeof F);
}
return 0;
}
总结：回过头来再想这道题感觉也没多难。主要是优化想不到。一旦想到用dp 写，写个不优化的dp还是很简单的，然后就是好好想想怎么优化。又收获了一种dp 的优化方式。
- 1003鸽子 https://acm.hdu.edu.cn/showproblem.php?pid=6998 dp
大意：有 n 台电脑，第 k 台电脑是坏的，现给出 m 条指令，每次要求将第
u
i
u_i
ui? 和
v
i
v_i
vi? 台电脑交换，这样坏的电脑就可能被换到新的位置。当然你可以拒绝若干条指令，对于每个 j =1,2,3…n。求出将坏的电脑换到第 j 号 位置最少拒绝的指令是多少。如果不能换到输出-1.
(1<=n,m<=1e5)
思路：显然对于每条指令执行不执行都是有可能的，即有限制的选择问题。所以用 dp 来写。 f[i,j] 表示考虑前 i 条指令，坏的电脑在位置 j 的最少拒绝的指令数。
对于第 i 条指令 交换 x , y f[i,x]=min(f[i-1,x]+1,f[i-1,y]) f[i,y]=min(f[i-1,y]+1,f[i-1,x])。对于其他位置的是不用变的，所以我们完全可以开个一维数组，每次只修改需要修改的位置，这样修改的时间复杂度就是 O(1)了。但是不能直接拿原数组直接修改。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int f[N],n,m,k;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int _;
cin>>_;
while(_--)
{
memset(f,0x3f,sizeof f);
cin>>n>>m>>k;
f[k]=0;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
int t1=f[x],t2=f[y];
f[x]=min(t1+1,t2);
f[y]=min(t2+1,t1);
}
for(int i=1;i<=n;i++)cout<<(f[i]==0x3f3f3f3f ? -1:f[i])<<(i!=n ? " ":"\n");
}
return 0;
}
-
1004萌新 https://acm.hdu.edu.cn/showproblem.php?pid=6999 签到 -
1008猎人杀 https://acm.hdu.edu.cn/showproblem.php?pid=7003 模拟、签到 -
1006 https://acm.hdu.edu.cn/showproblem.php?pid=7001 思维
大意：给定一个长度为 n 初始全为 0 的序列，有 n 次操作，1 , x 代表把 x 位置修改成 1; 2 x代表如果把 x 位置修改为 1，求最大 i 满足 1~i-1 位置上全为 1。
思路：一看到单点修改、区间查询一直在想数据结果，实际上是个思维题。其实设置两个数，维护最左边的两个 0 就好了。 记为 a,b 。
对于查询操作，如果将 a 修改成了 1，那么答案就是 b 否则就是 a
对于修改操作，如果将 a 修改成了 1 那么令 a=b。b递增找到下一个 0。如果将 b 修改成 1,那么还是 b 递增，找到下一个0。时间复杂度O(n)。
代码如下：代码是对的，理论复杂度也ok，杭电的机子不行，加快读才能过。
#include <bits/stdc++.h>
using namespace std;
const int N=5000010;
bool st[N];
int n;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
int a=1,b=2;
for(int i=1;i<=n;i++)
{
int op,x;
cin>>op>>x;
if(op==1)
{
st[x]=1;
if(x!=a&&x!=b)continue;
if(x==a)a=b;
b++;
while(st[b])b++;
}
else cout<<(x==a?b:a)<<"\n";
}
return 0;
}
|