T1 景区路线规划

这题对刚学完概率期望的我来说简直水爆了好吗。。

因为存在时间限制，不好跑高斯消元，就直接跑dp就完了。

令i为当前所在景点，j为已过时间，

f[i][j]=∑f[u][j-t[k]-c[i]]/out,(u与i联通，k为u，i，之间边的编号）

因为每次在合法的景点中做选择，所以out并不是u的出度，而是u可选的合法景点，每次要遍历一遍求得。

code：

1 #include
2 using namespace std;
3 int n,m,k,st[20001],to[20001],nex[20001],head[101],c[101],t[20001],h1[101],h2[101];
4 double f1[101][481],f2[101][481],ans1,ans2;
5 inline void add(int a,int b,int e,int d)
6 {
7 st[d]=a; to[d]=b; nex[d]=head[a]; head[a]=d; t[d]=e;
8 st[d+m]=b; to[d+m]=a; nex[d+m]=head[b]; head[b]=d+m; t[d+m]=e;
9 }
10 inline double dfs1(int loc,int tim)
11 {
12 if(f1[loc][tim]) return f1[loc][tim];
13 int out=0;
14 for(int i=head[loc];i;i=nex[i])
15 {
16 int v=to[i];
17 if(tim+t[i]+c[v]<=k) out++;
18 }
19 f1[loc][tim]=h1[loc];
20 if(!out) return f1[loc][tim];
21 for(int i=head[loc];i;i=nex[i])
22 {
23 int v=to[i];
24 if(tim+t[i]+c[v]<=k)
25 f1[loc][tim]+=dfs1(v,tim+t[i]+c[v])/out;
26 }
27 return f1[loc][tim];
28 }
29 inline double dfs2(int loc,int tim)
30 {
31 if(f2[loc][tim]) return f2[loc][tim];
32 int out=0;
33 for(int i=head[loc];i;i=nex[i])
34 {
35 int v=to[i];
36 if(tim+t[i]+c[v]<=k) out++;
37 }
38 f2[loc][tim]=h2[loc];
39 if(!out) return f2[loc][tim];
40 for(int i=head[loc];i;i=nex[i])
41 {
42 int v=to[i];
43 if(tim+t[i]+c[v]<=k)
44 f2[loc][tim]+=dfs2(v,tim+t[i]+c[v])/out;
45 }
46 return f2[loc][tim];
47 }
48 int main()
49 {
50 scanf("%d%d%d",&n,&m,&k);
51 for(int i=1;i<=n;i++)
52 scanf("%d%d%d",&c[i],&h1[i],&h2[i]);
53 for(int i=1;i<=m;i++)
54 {
55 int x,y,z;
56 scanf("%d%d%d",&x,&y,&z);
57 add(x,y,z,i);
58 }
59 for(int i=1;i<=n;i++)
60 {
61 ans1+=dfs1(i,c[i]);
62 ans2+=dfs2(i,c[i]);
63 }
64 ans1/=n; ans2/=n;
65 printf("%.5lf %.5lf",ans1,ans2);
66 return 0;
67 }

T2 树

有两种解法，可以跑树状dp，也能高斯消元之后搜出最优解。

考场上没想太多，直接打了个异或高斯消元，结果把第n+1维和解的关系搞乱了，还没搜多组解，捞了40。。

把方程组消元后会出现若干个自由元，通过搜索与回溯遍历每组合法的解，最后找到最优解。

code：

1 #include
2 using namespace std;
3 int n,a[101][102],c,ans;
4 void gauss()
5 {
6 int c=1;
7 for(int i=1;i<=n;i++) 8 { 9 int r=c; 10 for(int j=c+1;j<=n;j++) 11 if(a[r][i]=ans) return;
24 if(!h)
25 {
26 ans=now;
27 return;
28 }
29 if(a[h][h]) dfs(h-1,now+a[h][n+1]);
30 else
31 {
32 if(a[h][n+1]) return;
33 dfs(h-1,now);
34 for(int i=h;i>0;i--) a[i][n+1]^=a[i][h];
35 dfs(h-1,now+1);
36 for(int i=h;i>0;i--) a[i][n+1]^=a[i][h];
37 }
38 }
39 int main()
40 {
41 scanf("%d",&n);
42 while(n)
43 {
44 ans=INT_MAX;
45 for(int i=1;i<=n;i++)
46 for(int j=1;j<=n+1;j++)
47 a[i][j]=0;
48 for(int i=1;i<n;i++)
49 {
50 int x,y;
51 scanf("%d%d",&x,&y);
52 a[x][y]=a[y][x]=1;
53 }
54 for(int i=1;i<=n;i++) a[i][i]=a[i][n+1]=1;
55 gauss();
56 dfs(n,0);
57 printf("%d\n",ans);
58 scanf("%d",&n);
59 }
60 return 0;
61 }

T2高斯消元

树规做法还没整出来，等更新8（咕咕咕

5.30 upd:　　竟然没鸽，太感动了

没想到树规代码如此简单OTZ（虽然感觉思路很难想

定义状态数组f[i][1],f[i][0],g[i][1],g[i][0],f表示当前点按了开关，g表示没按；第二维0表示按后这个点亮灯，1表示按后不亮。

状态通过子节点和自己的其他状态进行转移：

当前点按开关，子节点就必须不亮；当前点不亮，要么自己原来不亮，子节点按了，要么自己原来就亮，子节点不动。反之亦然。

思路有了，状态转移方程还是很好想的。最后输出f[1][1]与g[1][0]的较小值。

code：

1 #include
2 using namespace std;
3 int n,to[210],nex[210],head[110],f[110][2],g[110][2];//f按g不按 0不亮1亮
4 inline int read()
5 {
6 int x=0,f=1;
7 char ch=getchar();
8 while(ch<'0'||ch>'9')
9 {
10 if(ch=='-')
11 f=-1;
12 ch=getchar();
13 }
14 while(ch>='0'&&ch<='9') 15 { 16 x=(x<<1)+(x<<3)+(ch^48); 17 ch=getchar(); 18 } 19 return x*f; 20 } 21 void write(int x) 22 { 23 if(x<0) 24 { 25 putchar('-'); 26 x=-x; 27 } 28 if(x>9)
29 write(x/10);
30 putchar(x%10+'0');
31 }
32 inline void add(int a,int b,int d)
33 {
34 to[d]=b; nex[d]=head[a]; head[a]=d;
35 to[d+n-1]=a; nex[d+n-1]=head[b]; head[b]=d+n-1;
36 }
37 void dfs(int x,int fa)
38 {
39 f[x][0]=g[x][1]=n+1; f[x][1]=1; g[x][0]=0;
40 int f0,f1,g0,g1,v;
41 for(int i=head[x];i;i=nex[i])
42 {
43 v=to[i];
44 if(v==fa) continue;
45 dfs(v,x);
46 f0=f[x][0]; f1=f[x][1]; g0=g[x][0]; g1=g[x][1];
47 f[x][0]=min(f1+f[v][0],f0+g[v][0]);
48 f[x][1]=min(f0+f[v][0],f1+g[v][0]);
49 g[x][0]=min(g1+f[v][1],g0+g[v][1]);
50 g[x][1]=min(g0+f[v][1],g1+g[v][1]);
51 }
52 }
53 int main()
54 {
55 n=read();
56 while(n)
57 {
58 memset(head,0,sizeof(head));
59 for(int i=1;i<n;i++) add(read(),read(),i);
60 dfs(1,0);
61 write(min(f[1][1],g[1][1])); putchar('\n');
62 n=read();
63 }
64 return 0;
65 }

T2树形DP

（不知道为什么不加return 0最后一个点会WA，属实迷惑

T3 奇怪的道路

k<=8，可以想到状压。（但当时没时间没思路只能拿特判跟组合数骗分，结果没打longlong骗的还没输出0骗的多。。。

思路有点像动物园，第i个点前后不能兼顾，只考虑一边即可，另一边由之后的点保证。这里考虑之前的点。

状态用0，1表示该点连边的奇偶，另外除了考虑之前k个点的连边，还要考虑当前点，所以状态压k+1位。

状态数组考虑开四维，第一维点数，第二维边数，第三维状态，第四维l表示已更新到第i-l个点，对转移进行限制（不然会发生重复计数

对于第i个点，连了j条边，状态为u，更新到第i-l个点：

如果连边：f[i][j+1][u^1^(1<

如果不连：f[i][j][u][l-1]+=f[i][j][u][l]

当l已转移至0时向下一个点转移：f[i+1][j][u<<1][min(i,k)]+=f[i][j][u][0]

code：

1 #include
2 using namespace std;
3 const int p=1000000007;
4 int n,m,k,f[32][32][1<<9][9]; 5 inline int read() 6 { 7 int x=0,f=1; 8 char ch=getchar(); 9 while(ch<'0'||ch>'9')
10 {
11 if(ch=='-')
12 f=-1;
13 ch=getchar();
14 }
15 while(ch>='0'&&ch<='9') 16 { 17 x=(x<<1)+(x<<3)+(ch^48); 18 ch=getchar(); 19 } 20 return x*f; 21 } 22 void write(int x) 23 { 24 if(x<0) 25 { 26 putchar('-'); 27 x=-x; 28 } 29 if(x>9)
30 write(x/10);
31 putchar(x%10+'0');
32 }
33 int main()
34 {
35 n=read(); m=read(); k=read();
36 f[1][0][0][0]=1;
37 for(int i=1;i<=n;i++) 38 for(int j=0;j<=m;j++) 39 for(int u=0;u<(1<<(k+1));u++) 40 { 41 for(int l=min(i,k);l>0;l--)
42 {
43 if(j>k)&1)) f[i+1][j][u<<1][min(i,k)]+=f[i][j][u][0], f[i+1][j][u<<1][min(i,k)]%=p;
47 }
48 write(f[n][m][0][0]);
49 return 0;
50 }

T3

一些感受与反思

成绩貌似还行，但好像也没啥很厉害的地方。。

自由元的深搜应该也不难想，但考场上因为感觉很麻烦就没管它；T3一看求方案数就感觉是排列组合，瞬间头大…

自认为还有很多需要磨砺的地方，不管是思路还是代码能力方面。

未来的路还很长啊……

手机扫一扫
移动阅读更方便

你可能感兴趣的文章