INWF

Educational Codeforces Round 154 (Rated for Div. 2) C题题解C. Queries for the Array 题解[C. Queries for the Array]: nums[]存当前数组，len 表示当前数组长度 nums[i]=1 时表示 $1{\sim}i$ 的数据是递增的 nums[i]=0 时表示 $1{\sim}i$ 的数据增减性不确定，即可能递增可能递减 nums[i]=-1 时表示 $1{\sim}i$ 的数据是递减的 当 s[i]=='+' 时，如果原数组是降序，那么加完新元素后的新数组也是降序的，即 s[len]=-1 当 s[i]=='-' 时，如果原数组是升序的，那么删完后还是升序，即 s[len]=1 ，由于还得 s[len]=0 防止影响后续的判断 当 s[i]=='1' 时，若 s[len]==-1 即降序，则输出 $NO$ ,否则 s[len]=1 表示升序 当 s[i]=='0' 时，若 s[len]==1 即升序，则输出 $Y ...

背包01 背包1234567891011121314151617181920212223242526272829#include<iostream>#include<cstring>using namespace std;const int N=20020;const int M=50;int dp[N];int v[M];int w[M];int main(){ int V,n; for(int i=1;i<=n;i++) { cin>>v[i]>>w[i]; } for(int i=1;i<=n;i++) { for(int j=V;j>=v[i];j--) //从后往前 { dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } cout<<dp[V]<<endl; ...

质约数判断质数 $O(\sqrt{n})$123456789101112bool isPrime(int x){ if (x<2) return false; for (int i=2;i<=x/i;i++) { if (x%i==0) { return false; } } return true;} 分解质因数 $O(\log{n}) O(\sqrt{n})$最多只包含一个大于 $\sqrt{n}$ 的 质因数 1234567891011121314151617void divide(int n){ for(int i=2;i<=n/i;i++) { if(n%i==0) { int s=0; while(n%i==0) { n= ...

模板（二）DFS 深度优先搜索 1234void dfs(int u){ if(u==n) //pd[u] 表示点u已经被遍历过 { } for (```) { if(```) { 1234 dfs(u+1); } }} 树的 DFS12345678910int dfs(int u){ pd[u] = true; // pd[u] 判断点u已经被遍历过 for (int i=h[u];i!=-1;i=ne[i]) { int j =e[i]; if(!st[j]) dfs(j); }} BFS 宽度优先搜索12void bfs(int a,int b){ q.push({a,b}); while (!q.empty()) { for(```) ...

模板快速排序1234567891011121314void quick_sort(int q[],int l,int r){ if(l>=r) return; int i=l-1,j=r+1,x=q[l+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]); } quick_sort(q,l,j); quick_sort(q,j+1,r);} 归并排序123456789101112131415161718void merge_sort(int q[],int l,int r){ if(l>=r) return; int mid=l+r>>1; merge_sort(q,l,mid); merge_sort(q,mid+1,r); in ...

string.empty() 函数123string s1, s2 = "abcd";cout << s1.empty() << endl;cout << s2.empty() << endl; 输出：10 string.empty()函数表示检查字符串是否为空，若为空，则返回1，若不为空，则返回0 string 的输入123string s;getline(cin,s); //可以读入空格cin>>s; //不可以读入空格 substr(begin,lenth) 函数和 find(“”) 函数123456//cde和efgstring s1="abcdefg";string s2=s1.substr(2,3);string s3=s1.substr(s1.find("efg"),3);cout<<s2<<endl;cout<<s3<<endl; 输出cdeefg string.substr( ...

01背包问题 问题描述有 N 件物品和一个容量（可承受最大重量）是 W 的背包。每件物品只能使用一次。 第 i 件物品的重量是 w[i] 价值是 v[i] 。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。 输入格式第一行两个整数， N ， W ，用空格隔开，分别表示物品数量和背包容积。 接下来有 N 行，每行两个整数 w[i] , v[i] ,用空格隔开，分别表示第 i 件物品的体积和价值。 输出格式输出一个整数，表示最大价值。 输入样例123454 51 22 43 44 5 输出样例：18 动态规划思路使用动态规划可以解决01背包问题，具体思路如下： 定义状态：dp[i][j]表示前i个物品中，在总容量为j的情况下，能够获得的最大价值。 状态转移方程：分为两类：①：背包不可装（第i个物品体积大于背包总容量）即dp[i][j]=dp[i-1][j] ②：背包可装（第i个物品体积小于背包总容量）->分析第i个装/不装哪个总价值最大。即dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[ ...

高精度阶乘常规阶乘直接上代码 递归： 1234long long fac(int n){ return n==0? 1 : n*fac(n-1);} 循环 12345sum=1;while(i=1;i<=n;i++){ sum*=i} 但是，当阶乘的数值非常大时，递归法和循环法都会出现溢出的问题，无法准确地表示大阶乘的数值。为了解决这个问题，需要使用高精度阶乘算法。 C++ 实现高精度阶乘为了计算 n! 的值，该程序采用了两个循环嵌套的方式：外层循环控制阶乘的乘数，内层循环则负责乘法运算。 具体地，先将ans[0]初始化。之后，将外层循环变量i依次从1到n进行循环。在每次外层循环中，内层循环变量j从0到39999进行循环，完成乘法运算，具体计算方式如下： 计算当前位上的值：将ans[j]乘以i，并加上上一位相乘可能得到的进位x。将乘积对10取模的结果存入ans[j]，作为ans数组当前位的值。 计算位上的进位：计算向下一位可能得到的进位值x：将ans[j]除以10后得到的值就是当前位上实际得到的进位数。 初始化a ...

高精度乘法背景高精度乘法是指两个非常大的整数相乘的计算方法，传统的乘法算法不适合处理太大的整数。举个例子，计算两个200位数的乘积，不论是int类型还是long long类型都会溢出。因此需要用高精度乘法来完成大数乘法的计算 代码介绍本文介绍的是一种使用C++实现大整数相乘的方法。采用的方法是将两个大整数的每一位分别存入两个数组中，然后逐位相乘，结果再存入结果数组中，最后将结果数组逆序输出即可 优点 可以计算较大的整数相乘，不会受到int类型变量的限制 避免了精度损失的问题 缺点 时间复杂度较高，当两个数长度相等时，时间复杂度为O(n^2)，而当两个数长度不相等时，时间复杂度为O(m*n)，其中m和n分别为两个数的长度。所以比较适合计算中小规模的数字 代码实现中使用了大量的数组操作，可能会浪费大量的空间 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include<iostre ...

高精度减法前言有些时候我们需要计算两个很大的整数的差，但是 C++ 中 int或者long long 类型的范围很小，无法存储大整数。下段代码两个大整数输入转化为整型数组，并用数组计算出两数的差，并将结果输出。 代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include<iostream>#include<cstring>using namespace std;void rev(int fir[],int sec[],string a,string b) //将两个字符串转化为数组{ for(int i=0;i<a.length();i++) //倒序存入fir数组中 { fir[i]=a[a.length()-i-1]-'0'; } for(in ...