首页 > 代码库 > HDU5068（Harry And Math Teacher）
HDU5068（Harry And Math Teacher）
题目地址：Harry And Math Teacher
题目大意：
有N层楼，每层楼都有两个门，i 层楼的两扇门到i+1层楼的两扇门各有通道互不影响（例如：i层楼门号有1、2，i+1层楼门号有1、2则有四条通道 1->1、1->2、2-> 1 、2-> 2），其中可以修改通道的状态，如果op值为‘1’的时候 将x楼与x+1层楼之间的y-z门的这条通道的状态改变，如果先前是通路则切断无法通过，如果先前是断路的状态，则恢复通路可以通过。如果op为‘0’，在表示询问a->b 有多少种路径可以到达。
解题思路：
线段数，节点存储通道路径的矩阵，矩阵的相乘结果刚好是下一层楼四条边的路径种类和，之前用的方法是想，计算左边门和右边门的所有情况和，然后加和，但是难判断的是上一层的右边得到的路径种类和以及左边得到的路径种类和，汇流到了下一层的左边边门和右边门时，很难分配该层的到下一层的左右门各有多少条路径，反正说不太清，代码编的就很乱，不想在改了。 正好利用矩阵完美解决了路径汇总到下一层左右门时路径种类个数的问题，最后计算出矩阵，然后将矩阵里所有的值相加就是答案。
代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 #define PI 3.1415927 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {0,-1,0,1}; 26 const int d1y[]= {-1,0,1,0}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 const int dirx[]= {-1,1,-2,2,-2,2,-1,1}; 32 const int diry[]= {-2,-2,-1,-1,1,1,2,2}; 33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 34 /***************************************/ 35 void openfile() 36 { 37 freopen("data.in","rb",stdin); 38 freopen("data.out","wb",stdout); 39 } 40 priority_queue<int> qi1; 41 priority_queue<int, vector<int>, greater<int> >qi2; 42 /**********************华丽丽的分割线,以上为模板部分*****************/ 43 const int M=50010; 44 const int64 MOD=1000000007; 45 struct tree 46 { 47 int64 matrix[3][3]; 48 int left,right; 49 } node[M*4]; //需开四倍的空间大小 50 int64 cnt; 51 tree pp; 52 tree mul(tree a,tree b,int l,int r) 53 { 54 int i,j,k; 55 memset(pp.matrix,0,sizeof(pp.matrix)); 56 pp.left=l; 57 pp.right=r; 58 for(i=1; i<=2; i++) 59 for(j=1; j<=2; j++) 60 for(k=1; k<=2; k++) 61 { 62 pp.matrix[i][j]+=a.matrix[i][k]%MOD*b.matrix[k][j]%MOD; 63 pp.matrix[i][j]%=MOD; 64 } 65 return pp; 66 } 67 void build__tree(int id,int l,int r) //建树 68 { 69 int mid=(l+r)/2; 70 node[id].left=l; //初始化赋值区间的坐标 71 node[id].right=r; 72 if (l==r) 73 { 74 node[id].matrix[1][1]=1; 75 node[id].matrix[1][2]=1; 76 node[id].matrix[2][1]=1; 77 node[id].matrix[2][2]=1; 78 return ; 79 } 80 build__tree(id*2,l,mid); //左孩子 81 build__tree(id*2+1,mid+1,r); //右孩子 82 node[id]=mul(node[id*2],node[id*2+1],l,r); 83 return ; 84 } 85 tree tmp; 86 int query(int id,int l,int r) //查询区间的总和 87 { 88 int mid=(node[id].left+node[id].right)/2; 89 if (node[id].left==l&&node[id].right==r) 90 { 91 tmp=mul(tmp,node[id],l,r); 92 } 93 else if (l>mid) //[l，r]在右孩子部分 94 query(id*2+1,l,r); 95 else if (r<=mid) // [l，r]在左孩子部分 96 query(id*2,l,r); 97 else //[l，r]区间，左右孩子都有分别递归。 98 { 99 query(id*2,l,mid);100 query(id*2+1,mid+1,r);101 }102 return 0;103 }104 void updata(int id,int pos,int y,int z) //从上向下寻找节点，找到节点后然后从下往上更新节点的val值105 {106 if (node[id].left==pos&&node[id].right==pos)//找到该节点107 {108 node[id].matrix[y][z]=1-node[id].matrix[y][z];109 return ;110 }111 int mid=(node[id].left+node[id].right)/2;112 if (pos<=mid) //节点在左孩子部分113 updata(id*2,pos,y,z);114 else //节点在右孩子部分115 updata(id*2+1,pos,y,z);116 node[id]=mul(node[id*2],node[id*2+1],node[id].left,node[id].right);117 }118 int main()119 {120 int n,m;121 while(scanf("%d%d",&n,&m)!=EOF)122 {123 build__tree(1,1,n-1);124 int op;125 int i;126 for(i=0; i<m; i++)127 {128 scanf("%d",&op);129 if (!op)130 {131 tmp.matrix[1][1]=1;132 tmp.matrix[1][2]=0;133 tmp.matrix[2][1]=0;134 tmp.matrix[2][2]=1;135 int a,b;136 scanf("%d%d",&a,&b);137 query(1,a,b-1);138 cnt=0;139 for(int i=1;i<=2;i++)140 for(int j=1;j<=2;j++)141 {142 cnt+=tmp.matrix[i][j]%MOD;143 cnt%=MOD;144 }145 printf("%I64d\n",cnt);146 }147 else148 {149 int x,y,z;150 scanf("%d%d%d",&x,&y,&z);151 updata(1,x,y,z);152 }153 }154 memset(node,0,sizeof(node));155 }156 return 0;157 }
错误的代码：
很乱，但是编了好长时间 ，舍不得，回头有时间在看看把。
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 #define PI 3.1415927 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {0,-1,0,1}; 26 const int d1y[]= {-1,0,1,0}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 const int dirx[]= {-1,1,-2,2,-2,2,-1,1}; 32 const int diry[]= {-2,-2,-1,-1,1,1,2,2}; 33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 34 /***************************************/ 35 void openfile() 36 { 37 freopen("data.in","rb",stdin); 38 freopen("data.out","wb",stdout); 39 } 40 priority_queue<int> qi1; 41 priority_queue<int, vector<int>, greater<int> >qi2; 42 /**********************华丽丽的分割线,以上为模板部分*****************/ 43 const int M=50010; 44 const long long MOD=1000000007; 45 struct tree 46 { 47 long long sum; 48 long long sum1,sum2; 49 long long x,y; 50 long long d[5]; 51 int left,right; //记录区间的左右闭区间坐标 52 } node[M*4]; //需开四倍的空间大小 53 long long cnt1,cnt2; 54 long long aaans; 55 void MM() 56 { 57 long long b=MOD-2; 58 long long ans=1; 59 long long a=2; 60 while(b) 61 { 62 if (b&1) 63 ans=(ans%MOD*a%MOD)%MOD; 64 a=(a%MOD*a%MOD)%MOD; 65 b>>=1; 66 } 67 aaans=ans; 68 return ; 69 } 70 long long aaans1; 71 void MMM() 72 { 73 long long b=MOD-2; 74 long long ans=1; 75 long long a=4; 76 while(b) 77 { 78 if (b&1) 79 ans=(ans%MOD*a%MOD)%MOD; 80 a=(a%MOD*a%MOD)%MOD; 81 b>>=1; 82 } 83 aaans1=ans; 84 return ; 85 } 86 void build__tree(int id,int l,int r) //建树 87 { 88 int mid=(l+r)/2; 89 node[id].left=l; //初始化赋值区间的坐标 90 node[id].right=r; 91 for(int i=1; i<=4; i++) 92 node[id].d[i]=1; 93 if (l==r) 94 { 95 node[id].sum1=2; //初始化区间节点的val值 96 node[id].sum2=2; 97 node[id].x=2; 98 node[id].y=2; 99 node[id].sum=node[id].sum1+node[id].sum2;100 return ;101 }102 build__tree(id*2,l,mid); //左孩子103 build__tree(id*2+1,mid+1,r); //右孩子104 node[id].x=node[id*2+1].x;105 node[id].y=node[id*2+1].y;106 node[id].sum=(node[id*2].sum%MOD*node[id*2+1].sum%MOD)%MOD*aaans%MOD;107 node[id].sum1=(node[id].sum%MOD*node[id].x%MOD)%MOD*aaans1%MOD;108 node[id].sum2=(node[id].sum%MOD*node[id].y%MOD)%MOD*aaans1%MOD;109 }110 int query(int id,int l,int r) //查询区间的总和111 {112 int mid=(node[id].left+node[id].right)/2;113 if (node[id].left==l&&node[id].right==r)114 {115 cnt1=(cnt1*node[id].sum1)%MOD;116 cnt2=(cnt2*node[id].sum2)%MOD;117 return 0;118 }119 else if (l>mid) //[l，r]在右孩子部分120 query(id*2+1,l,r);121 else if (r<=mid) // [l，r]在左孩子部分122 query(id*2,l,r);123 else //[l，r]区间，左右孩子都有分别递归。124 {125 query(id*2,l,mid);126 query(id*2+1,mid+1,r);127 }128 return 0;129 }130 void updata(int id,int pos,int val) //从上向下寻找节点，找到节点后然后从下往上更新节点的val值131 {132 if (node[id].left==pos&&node[id].right==pos)//找到该节点133 {134 if (node[id].d[val]==1)135 {136 node[id].d[val]=0;137 if (val%2)138 {139 node[id].x--;140 node[id].sum1--;141 }142 else143 {144 node[id].y--;145 node[id].sum2--;146 }147 }148 else149 {150 node[id].d[val]=1;151 if (val%2)152 {153 node[id].x++;154 node[id].sum1++;155 }156 else157 {158 node[id].y++;159 node[id].sum2++;160 }161 }162 node[id].sum=node[id].sum1+node[id].sum2;163 return ;164 }165 int mid=(node[id].left+node[id].right)/2;166 if (pos<=mid) //节点在左孩子部分167 updata(id*2,pos,val);168 else //节点在右孩子部分169 updata(id*2+1,pos,val);170 node[id].x=node[id*2+1].x;171 node[id].y=node[id*2+1].y;172 int b;173 int ans;174 if (node[id*2].sum*node[id*2+1].sum<4)175 {176 node[id].sum1=node[id*2].sum1%MOD*node[id*2+1].sum1%MOD;177 node[id].sum2=node[id*2].sum2%MOD*node[id*2+1].sum2%MOD;178 node[id].sum=(node[id].sum1+node[id].sum2)%MOD;179 }180 else181 {182 long long a=node[id].x+node[id].y;183 node[id].sum=(node[id*2].sum%MOD*node[id*2+1].sum%MOD)%MOD*aaans%MOD;184 /*ans=1;185 a=node[id].x+node[id].y;186 b=MOD-2;187 while(b)188 {189 if (b&1)190 ans=(ans%MOD*a%MOD)%MOD;191 a=(a%MOD*a%MOD)%MOD;192 b>>=1;193 } */194 if (a)195 {196 node[id].sum1=(node[id].sum%MOD*node[id].x%MOD)%MOD/a%MOD;197 node[id].sum2=(node[id].sum%MOD*node[id].y%MOD)%MOD/a%MOD;198 }199 else200 {201 node[id].sum1=0;202 node[id].sum2=0;203 }204 }205 }206 int main()207 {208 int n,m;209 MM();210 MMM();211 while(scanf("%d%d",&n,&m)!=EOF)212 {213 build__tree(1,1,n-1);214 int op;215 int i;216 for(i=0; i<m; i++)217 {218 scanf("%d",&op);219 if (!op)220 {221 int a,b;222 cnt1=1;223 cnt2=1;224 scanf("%d%d",&a,&b);225 query(1,a,b-1);226 printf("%I64d\n",(cnt1+cnt2)%MOD);227 }228 else229 {230 int x,y,z;231 scanf("%d%d%d",&x,&y,&z);232 int ce=0;233 if (y==1&&z==1)234 ce=1;235 if (y==1&&z==2)236 ce=2;237 if (y==2&&z==1)238 ce=3;239 if (y==2&&z==2)240 ce=4;241 updata(1,x,ce);242 }243 }244 }245 return 0;246 }247 /*248 50000 100249 0 1 50000250 0 2 50000251 0 10000 10001252 0 10000 10010253 1 10000 1 1254 1 10010 2 1255 1 10000 2 1256 1 10000 1 2257 0 10000 50000258 0 10000 10001259 0 10000 10002260 0 10000 10003261 0 10000 10004262 0 10000 10005263 0 10000 10006264 0 10000 10007265 0 10000 10008266 0 10000 10009267 0 10000 10010268 0 10000 10011269 0 10000 10012270 0 1 2271 0 1 3272 0 1 4273 0 1 5274 0 1 6275 0 2 3276 0 2 4277 0 2 5278 0 3 4279 0 3 5280 0 3 6281 0 4 5282 0 4 6283 0 5 6284 */285 /*286 50000 100287 1 3 1 1288 1 3 2 1289 1 3 1 2290 1 1 1 1291 1 1 2 1292 1 1 1 2293 1 2 1 1294 1 2 2 1295 1 2 1 2296 0 1 50000297 0 2 50000298 0 3 50000299 0 4 50000300 0 10000 10001301 0 10000 50000302 */
HDU5068（Harry And Math Teacher）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。