voidinsert( int l , int r , int c)//插入操作,作用有二 { //一 初始化差分数组,相当于把每一个数插入全部为0的数组 b[l] += c ; //二 插入,使某段 l r 之间的所有数都加上 c b[r + 1] -= c ; //原理: 将l处的差分加上一个数,使用差分的前缀和计算原数组的时候,l后的所有数都加上c } // 将 r+1 处的差分减去 c 抵消了后续所有数加上的 c , 保持不变 // 最终达到只在此段全部加 c 的目标
intmain() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); ////初始化差分数组 insert( i , i, a[i]); }
while( m --) { int l , r , c ; scanf("%d%d%d" , &l , &r , &c);//进行插入 insert( l , r, c); }
for ( int i = 1; i <= n ; i++) //对差分进行前缀和求原数组 { b[i] += b[i - 1]; printf( "%d " , b[i]); } return0; }
vector<int> add(vector<int> &A, vector<int> &B)//& 是加快了读入的速度 { vector<int> C; int t = 0; // 模拟进位的变量 for (int i = 0; i < A.size() || i < B.size(); i++) { if (i < A.size()) //还有位数就加 t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); //进位的模拟 t /= 10; } if (t) //进到了最高位,加一位数 C.push_back(1); return C; }
intmain() { string a, b; cin >> a >> b; vector<int> A, B;
for (int i = a.size() - 1; i >= 0; i--) //把字符串填进动态数组 A.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0'); auto C = add(A, B); //auto 关键字,自动识别类型
for (int i = C.size() - 1; i >= 0; i--) //反向输出 printf("%d", C[i]);
boolcmp(vector<int> &A, vector<int> &B) { if (A.size() != B.size()) //先比较位数,位数多的大 return A.size() > B.size(); for (int i = A.size() - 1; i >= 0; i--) //从大到小比较每一位 if (A[i] != B[i]) //数字不一样, 比较 大小,一样继续比较下一位 return A[i] > B[i]; returntrue; //全都一样,大小相等,0,不用加负号 }
vector<int> sub(vector<int> &A, vector<int> &B) { vector<int> C; //定义一个每个循环开始的时候值是0或1的t来表示借位 for (int i = 0, t = 0; i < A.size(); i ++) { t = A[i] + t; //是否被借位 if (i < B.size()) //还有可以减的位数 t -= B[i]; C.push_back((t + 10) % 10); //(t + 10) % 10可以同时处理借位与不借位的情况 if (t < 0) //标记是否借位了 t = -1; else t = 0; }
return C; } intmain() { string a, b; //输入大数与储存 cin >> a >> b; vector<int> A, B; for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0'); if (cmp(A, B)) //判断两个数的大小,决定用谁减谁 { auto C = sub(A, B);
for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]); } else { auto C = sub(B, A); //小数减去大数,前面加上一个零 printf("-"); for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]); } return0; }
vector<int> mul(vector<int> &A, int b) { vector<int> C; int t = 0; for (int i = 0; i < A.size() || t; i++) { if (i < A.size()) //将每一个数直接乘上这个数即可 t += A[i] * b; C.push_back(t % 10); //进位机制同加法 t /= 10; }
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C; }
intmain() { string a; int b; cin >> a >> b; vector<int> A; for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0'); auto C = mul(A, b); for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]); return0; }
vector<int> div(vector<int> &A, int b, int &r) { vector<int> C; r = 0; for (int i = A.size() - 1; i >= 0; i--) { r = r * 10 + A[i]; //每一次除完接下一位数,即余数 *10 ,加上下一位数 C.push_back(r / b) ; //上商 r %= b; //得余数
voidquick_sort( int q[] , int l , int r ) { if (l >= r) //排序完成,退出函数 return; int x = (q[l]+q[r]) /2; //设置基准点 int i = l -1 ; int j = r + 1 ; while( i < j ) //i 与 j 的每一次交换操作 { do i++; while (q[i] < x ); do j--; while (q[j] > x ); if (i < j) //只有两个指针还没有互相越过的时候才可以交换 swap(q[i] , q[j]); //一样了就交换 } quick_sort(q , l , j); // 递归处理左右两边 quick_sort(q , j + 1 , r); }
intmain() { scanf("%d" , &n); for ( int i = 0 ; i < n ; i++) scanf("%d", & q[i]); quick_sort( q, 0 , n - 1); for ( int i = 0 ; i < n ; i++) printf("%d ", q[i]); return0; }
引申:快速选择算法
给定一个长度为 n 的整数数列,以及一个整数 k,请用快速选择算法求出数列从小到大排序后的第 k 个数。
intquick_sort( int l, int r, int k )//直接返回第k个数值 { if (l == r) return q[l]; //相当于只有一个数字了,直接返回就可以了
int x = (q[l] + q[r]) / 2, i = l - 1, j = r + 1; //同快排的步骤 while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); } int sl = j- l +1; //计算 左边的数字数目, 与k比较 if( sl >= k) returnquick_sort( l, j, k ); //数目 大于 等于 k , 只需要对左边进行递归就可以了 returnquick_sort( j + 1, r , k-sl); //小于 k , 则对右边进行递归 }
intmain() { scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &q[i]); printf("%d", quick_sort( 0, n - 1,k)); return0; }
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.