本文共 4871 字，大约阅读时间需要 16 分钟。
A题，水题。只要细心一点就能做出来的。
B题，最后的排列只可能是rbrbr..或者brbrb..，那么枚举这两种情况，统计当前序列和他们不同的r或者b的个数，假设为x和y，那么较小的他们互换即可，而剩下的只能重刷，因此，答案是min(x,y)+max(x,y)-min(x,y)=max(x,y)。最后两种情况计算出来的答案取最小值即可。
C题，其实挺水的，但是也很容易写错。从最右边不断的找能进位的数字让其进位即可。小心点写就能A了。代码如下：
1 #include 2 using namespace std; 3 const int N = 200000 + 5; 4 5 char s[N]; 6 int n,t; 7 8 int main() 9 {10 scanf("%d%d",&n,&t);11 scanf("%s",s+1);12 s[0] = '0';13 int p,i;14 for(p=1;p<=n&&s[p]!='.';p++) ; // s[p] == '.'15 for(i=p+1;i<=n&&s[i]<'5';i++) ;// s[i] >= '5'16 for(i=i-1;i>p && t > 0;i--)17 {18 if(s[i+1] >= '5')19 {20 s[i+1] = 0;21 s[i]++;22 t--;23 }24 }25 if(s[p+1] >= '5' && t > 0)26 {27 s[p] = 0;28 while(s[--p] == '9') s[p] = '0';29 s[p]++;30 }31 if(s[0] == '0') puts(s+1);32 else puts(s);33 return 0;34 }
D题，好题。题意不难理解，但是不好做。做法是，线段树的节点维护矩阵，每次成段更新都乘一个矩阵快速幂中那个递推矩阵A的若干次即可。之所以可以这样是因为矩阵乘法在可乘的情况下是满足分配率的，因此节点和加在一起也无妨。值得注意的一点是，在update的时候要把矩阵先做好快速幂再给update当参数，不然只传过去一个改变的量dt等更新具体的节点时再做矩阵的快速幂会超时。代码如下：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #define t_mid (l+r>>1) 10 #define ls (o<<1) 11 #define rs (o<<1|1) 12 #define lson ls,l,t_mid 13 #define rson rs,t_mid+1,r 14 using namespace std; 15 typedef long long ll; 16 const int mod = 1e9+7; 17 const int N = 100000 + 5; 18 19 void add(int &a,int b) 20 { 21 a += b; 22 if(a < 0) a += mod; 23 if(a >= mod) a -= mod; 24 //a %= mod; 25 } 26 27 struct matrix 28 { 29 int e[5][5],n,m; 30 matrix() {} 31 matrix(int _n,int _m): n(_n),m(_m) {memset(e,0,sizeof(e));} 32 matrix operator * (const matrix &temp)const 33 { 34 matrix ret = matrix(n,temp.m); 35 for(int i=1;i<=ret.n;i++) 36 { 37 for(int j=1;j<=ret.m;j++) 38 { 39 for(int k=1;k<=m;k++) 40 { 41 add(ret.e[i][j],1LL*e[i][k]*temp.e[k][j]%mod); 42 } 43 } 44 } 45 return ret; 46 } 47 matrix operator + (const matrix &temp)const 48 { 49 matrix ret = matrix(n,m); 50 for(int i=1;i<=n;i++) 51 { 52 for(int j=1;j<=m;j++) 53 { 54 add(ret.e[i][j],(e[i][j]+temp.e[i][j])%mod); 55 } 56 } 57 return ret; 58 } 59 void getE() 60 { 61 for(int i=1;i<=n;i++) 62 { 63 for(int j=1;j<=m;j++) 64 { 65 e[i][j] = i==j?1:0; 66 } 67 } 68 } 69 }A,E; 70 71 matrix qpow(matrix temp,int x) 72 { 73 int sz = temp.n; 74 matrix base = matrix(sz,sz); 75 base.getE(); 76 while(x) 77 { 78 if(x & 1) base = base * temp; 79 x >>= 1; 80 temp = temp * temp; 81 } 82 return base; 83 } 84 85 void print(matrix p) 86 { 87 int n = p.n; 88 int m = p.m; 89 for(int i=1;i<=n;i++) 90 { 91 for(int j=1;j<=m;j++) 92 { 93 printf("%d ",p.e[i][j]); 94 } 95 cout << endl; 96 } 97 } 98 99 matrix fibo(int x)100 {101 matrix ans = matrix(1,2);102 ans.e[1][1] = ans.e[1][2] = 1;103 return ans * qpow(A, x-1);104 }105 106 matrix c[N<<2],lazy[N<<2];107 int flag[N<<2];108 109 int n,m;110 void up(int o) {c[o] = c[ls] + c[rs];}111 void down(int o,int l,int r)112 {113 if(l == r) return ;114 if(flag[o])115 {116 lazy[ls] = lazy[ls] * lazy[o];117 lazy[rs] = lazy[rs] * lazy[o];118 c[ls] = c[ls] * lazy[o];119 c[rs] = c[rs] * lazy[o];120 flag[ls] = flag[rs] = 1;121 flag[o] = 0; lazy[o].getE();122 }123 }124 void build(int o,int l,int r)125 {126 lazy[o] = E;127 flag[o] = 0;128 if(l == r)129 {130 int t;131 scanf("%d",&t);132 c[o] = fibo(t);133 return ;134 }135 build(lson);136 build(rson);137 up(o);138 }139 void update(int o,int l,int r,int ql,int qr,matrix now_mat)140 {141 if(l == ql && r == qr)142 {143 c[o] = c[o] * now_mat;144 lazy[o] = lazy[o] * now_mat;145 flag[o] = 1;146 return ;147 }148 down(o,l,r);149 if(qr <= t_mid) update(lson,ql,qr,now_mat);150 else if(ql > t_mid) update(rson,ql,qr,now_mat);151 else152 {153 update(lson,ql,t_mid,now_mat);154 update(rson,t_mid+1,qr,now_mat);155 }156 up(o);157 }158 ll query(int o,int l,int r,int ql,int qr)159 {160 if(l == ql && r == qr)161 {162 return c[o].e[1][1];163 }164 down(o,l,r);165 ll ans = 0;166 if(qr <= t_mid)167 {168 ans += query(lson,ql,qr);169 ans = (ans % mod + mod) % mod;170 }171 else if(ql > t_mid)172 {173 ans += query(rson,ql,qr);174 ans = (ans % mod + mod) % mod;175 }176 else177 {178 ans = query(lson,ql,t_mid) + query(rson,t_mid+1,qr);179 ans = (ans % mod + mod) % mod;180 }181 return ans;182 }183 184 int main()185 {186 A = matrix(2,2); A.e[1][2] = A.e[2][1] = A.e[2][2] = 1;187 E = matrix(2,2); E.getE();188 scanf("%d%d",&n,&m);189 build(1,1,n);190 while(m--)191 {192 int op;193 scanf("%d",&op);194 if(op == 1)195 {196 int ql,qr,dt;197 scanf("%d%d%d",&ql,&qr,&dt);198 update(1,1,n,ql,qr,qpow(A,dt));199 }200 else201 {202 int ql,qr;203 scanf("%d%d",&ql,&qr);204 printf("%I64d\n",query(1,1,n,ql,qr));205 }206 }207 return 0;208 }
转载于:https://www.cnblogs.com/zzyDS/p/6323224.html
