题目链接 枚举因子如果,那么在这个区间内都有贡献，即这个区间都加上这个贡献，显然用差分解决。 #include<bits/stdc++.h> using namespace std; #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define pr printf #define IN freopen("in","r",stdin); #define OUT freopen("out","w",stdout); typedef long long ll; typedef unsigned long long ...

求出的话一般是的复杂度。可以转移质因子的贡献，优化到的复杂度。 前缀和 知道求 for(int i=1;i<=cnt&&pri[i]<=n;i++){ for(int j=1;j*pri[i]<=n;i++){ a[j * pri[i]] += a[j]; } } 知道求 for(int i = cnt; i ; -- i) { for(int j = n / pri[i]; j ; -- j) { a[j * pri[i]] -= a[j]; } } ...

题目链接 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; ll F[N]; int mu[N]; int Log(int n){ int ans=0; while(n)ans+=n%10,n/=10; return ans; } void pre(){ mu[1]=1; for(int i=1;i<N;i++){ F[i]=Log(i); if (mu[i]){ ...

#include<bits/stdc++.h> using namespace std; #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define pr printf #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); typedef long long ll; typedef unsigned long long ull; const int N=1e7+6; const int mod=1e9+7;...

package main import ( "bufio" "fmt" "os" "sync" ) func min(a, b int) int { if a < b { return a } return b } func max(a, b int) int { if a == min(a, b) { return b } return a } func abs(a int) int { if a < 0 { return -a }...

第一题： #include<bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; for(int i=1;i<(1<<n);i++){ int cnt=0; int x=i; bool flag=false; while(x>m){ if(x==2*m+1)flag=true; x>>=1;cnt++; } if(x==m&&i!=m){ if(flag)cout<&l...

Function #include<bits/stdc++.h> using namespace std; #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define pr printf #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); typedef long long ll; typedef unsigned long long ull; const int N=1e6+6; const in...

虚函数与多态 多态有编译时的多态性：通过函数的重载和运算符的重载实现，也就是函数地址在编译时确定，叫做静态绑定。运行时的多态性：在程序执行前，无法根据函数名和参数来确定该调用哪个函数，必须在程序执行过程中，根据执行的具体情况来动态的确定。也就是函数地址在运行时才确定的，叫做动态绑定。它是通过类继承关系和虚函数来实现的，比如基类指针指向子类对象，调用相应的虚函数，指向不同的子类实现不同的方法。 关键字virtual指明该函数是虚函数，virtual只能用于在类的内部声明，若函数在类外部实现则不需要再加virtual关键字。一个基类的虚函数允许子类去重写他，该函数始终保持虚函数的特征。每个对象有一...

5399. 数位成本和为目标值的最大数字 利用完全背包找出最大的长度，然后贪心从最大的取。 class Solution { public: int dp[5005]={0}; string largestNumber(vector<int>& cost, int v) { for(int i=1;i<=v;i++)dp[i]=-500005; for(int i=1;i<=9;i++){ for(int j=cost[i-1];j<=v;j++){ ...

5407. 切披萨的方案数 设dp[i][j][k]为矩形(i,j),(n,m)内切割了k次的方案数，然后倒推就行。 class Solution { public: int dp[55][55][15]; int sum[55][55]={0}; const int mod=1e9+7; bool ck(int x1,int y1,int x2,int y2){ return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]>0; } int dfs(int...

5387. 每个人戴不同帽子的方案数 设表示前个帽子状态为的合法方案数，表示里这些人是否戴了帽子的集合。那么对于第个帽子,要么只有一个人戴，要么没有人戴。 所以对于合法的第个人戴这个帽子或者没有人戴。 没有人戴这个帽子。 合法的第个人戴这个帽子。 复杂度 class Solution { public: int g[43][11]; int dp[42][1025]={0}; const int mod=1e9+7; int numberWays(vector<vector<int>>& hat) { in...

问题一：最长上升子序列 int seq(vector<int>&a){ int n=a.size(); int dp[n+1]; int len=1; dp[1]=a[0]; for(int i=1;i<n;i++){ if(dp[len]<a[i])dp[++len]=a[i]; else dp[lower_bound(dp+1,dp+1+len,a[i])-dp]=a[i]; } return len; }问题二:最长公共子序列找出序列中最长公共子序列设为中的最长公共子序...

感觉 填空有点难。 时间1个半小时，做变态的填空题，选择，还有编程。 感觉有点不够。 第一题 就是找出字符串s2,是否是s1的子序列，并返回最大的起始下标。 数据不大，所以暴力就行。 复杂度 O(n^2) char s1[300],s2[300]; int n,m; bool ck(int pos){     int cnt=0;     for(int i=pos;i<=n;i++){         if(s1[i]==s2[cnt+1])cnt++;         if(cnt==m)return 1;    ...

虽然AK了但是不知道能不能有面试机会 O_O . 问题1 模拟队列操作 #include<bits/stdc++.h> using namespace std; #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define pr printf #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); typedef long long...