【笔试训练】day24-day48合集（1）：https://developer.aliyun.com/article/1515228
day30
一、爱吃素
两个大于0的数相乘，如果没有1 ，那么一定是非质数。如果有1，就看对方是不是质素。数据太大，不能直接相乘后计算是否是质数。
代码：
#include <iostream> using namespace std; typedef long long LL; bool isprem(LL x){ if(x==1)return false; for(int i=2;i<=x/i;i++){ if(x%i==0)return false; } return true; } int main() { int t; cin>>t; while(t--){ LL a,b; cin>>a>>b; if((a==1&&isprem(b))||(b==1&&isprem(a))){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } } return 0; }
二、相差不超过k的最多数
排序后二分。枚举每一个数，看如果这个数字作为选出组合的最小数，那这个组合最大能选的数的坐标是多少。
代码：
#include <iostream> #include<algorithm> using namespace std; const int N=2e5+10; int a[N]; int main() { int n,k; cin>>n>>k; for(int i=0;i<n;i++)cin>>a[i]; sort(a,a+n); int ans=0; for(int i=0;i<n;i++){ int l=i-1; int r=n; while(l+1!=r){ int mid=(l+r)>>1; if(a[mid]<=a[i]+k)l=mid; else r=mid; } ans=max(l-i+1,ans); } cout<<ans<<endl; return 0; }
三、最长公共子序列（一）
动态规划板子题。
朴素做法。用f[i][j]表示字符串a的前i个字符和b的前j个字符里面，最长公共子序列是多少。
如果a[i]==b[i]那么f[i][j]=f[i-1][j-1]否则上一个f[i][j]只能由上一个状态f[i-1][j]或者f[i][j-1]中转移过来。
代码：
#include <iostream> using namespace std; const int N=1100; int f[N][N]; int main() { int n,m; cin>>n>>m; string a,b; cin>>a>>b; for(int i=1;i<=a.size();i++){ for(int j=1;j<=b.size();j++){ if(a[i-1]==b[j-1]){ f[i][j]=f[i-1][j-1]+1; }else{ f[i][j]=max(f[i-1][j],f[i][j-1]); } //cout<<f[j]<<endl; } } cout<<f[n][m]<<endl; return 0; }
再思考进阶做法。进阶做法时间复杂度没有改变，也就是优化空间复杂度。看能不能将二维f改成一维。假设b字符串是较小的那个。f[i][j]的状态只由上一个状态转移过来(f[i-1][j]或者f[i][j-1])，除了相等的时候。 于是我们可以用一个变量存f[i-1][j-1],这个变量的值严格上升，再去掉f[i]这一维，没有影响。
#include <iostream> using namespace std; const int N=1100; int f[N]; int main() { int n,m; cin>>n>>m; string a,b; cin>>a>>b; if(a.size()<b.size())swap(a,b); int p=0; for(int i=1;i<=a.size();i++){ for(int j=1,p=0;j<=b.size();j++){ int t=f[j]; if(a[i-1]==b[j-1]){ f[j]=p+1; }else{ f[j]=max(f[j],f[j-1]); } //cout<<f[j]<<endl; p=t; } } cout<<f[b.size()]<<endl; return 0; }
day31
一、小红的口罩
贪心。每次都戴最舒服的口罩，即不舒适度最低的口罩。用完这个值就*2。保证每次用最舒服的口罩，可以使用最小堆。
代码：
#include <iostream> #include<queue> using namespace std; const int N=1e5+10; int a[N]; int main() { int n,k; cin>>n>>k; priority_queue<int,vector<int>,greater<int>> q; for(int i=0;i<n;i++){ cin>>a[i]; q.push(a[i]); } int ans=0; while(!q.empty()&&k>0){ int t=q.top(); q.pop(); k-=t; if(k>=0)ans++; q.push(t*2); } cout<<ans<<endl; return 0; }
二、春游
这题老坑了。
贪心。总和费用最少，那就是人均最少。比较双人船和三人船的人均费用。谁费用少就优先考虑谁。直到最后会剩下几个人，可能剩下1或者2个人。
如果大部分用的是双人船，最后剩下的这个人要么自己坐双人，要么和之前坐双人船的队友拉下来坐一个三人船。
如果大部分用的是三人船，最后会剩下1或者2人。如果是一个人，这个人可以选择坐三人船，也可以选择拉下一队三人船的队友，一起坐两艘双人船。如果是两个人，那么这两个人可以一起坐三人，也可以一起坐双人船。
最后值得注意的是，如果n的值很小，在上面的方案中要避免出现答案为负数的情况。
代码
#include <iostream> using namespace std; typedef long long LL; int main() { int t; cin>>t; while(t--){ LL n,a,b; cin>>n>>a>>b; LL ans=0; if (n <= 2) { cout<<min(a,b)<<endl; continue; } if(3*a>=2*b){ int k=n%3; ans+=n/3*b; if(k==2)ans+=min(a,b); else if(k==1){ ans+=min(min(a,b),2*a-b); } }else{ int k=n%2; ans+=n/2*a; if(k){ ans+=min(a,b-a); } } cout<<ans<<endl; } return 0; }
三、数位染色
暴力枚举或者dp。把所有数位拿出来，看能不能选一堆数凑成总和的一半。用dp做的话就是用dp[j]表示是否存在凑成剩余容量j的方案。这里不多讲。我的做法是用二进制位表示某一个位数是否染色，由于数位总数最大18。枚举完所有状态就是2的18次方。
代码：
#include <iostream> #include<vector> #include<algorithm> using namespace std; int main() { string str; cin>>str; vector<int> a; int s=0; for(int i=0;i<str.size();i++){ int u=str[i]-'0'; s+=u; a.push_back(u); } if(s%2){ cout<<"No"<<endl; return 0; } int n=a.size(); int f=0; int ma=(1<<(n+1))-1; for(int i=1;i<ma;i++){ int t=0; for(int j=0;j<n;j++){ if((i>>j)&1)t+=a[j]; } if(t==s/2){ f=1; break; } } if(f)cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }
day32
一、素数回文
用字符串模拟一遍，注意long long
#define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include<vector> #include<algorithm> using namespace std; bool isprime(long long x) { if (x == 1)return false; for (int i = 2; i <= x / i; i++) { if (x % i == 0)return false; } return true; } int main() { string str; cin >> str; int n = str.size(); for (int i = n - 2; i >= 0; i--) { str.push_back(str[i]); } long long ans = 0; for (int i = 0; i < str.size(); i++) { int u = str[i] - '0'; ans = ans * 10 + u; } if (isprime(ans)) { cout << "prime" << endl; } else { cout << "noprime" << endl; } return 0; }
二、活动安排
贪心。先对所有区间进行排序，结束时间越早的排在前面，结束时间相等，那就开始时间越大的排在前面。然后枚举所有区间，如果当前活动的开始时间大于上一个加入答案活动的结束时间，ans++.
代码：
#include <iostream> #include<algorithm> #include<vector> using namespace std; typedef pair<int,int> PII; bool cmp(PII& A,PII& B){ if(A.second==B.second){ return A.first>B.first; } return A.second<B.second; } int main() { int n; cin>>n; vector<PII> v(n); for(int i=0;i<n;i++){ cin>>v[i].first>>v[i].second; } sort(v.begin(),v.end(),cmp); int ans=1; int t=v[0].second; for(int i=1;i<n;i++){ if(v[i].first>=t){ t=v[i].second; ans++; } } cout<<ans<<endl; return 0; }
三、合唱团
背包问题。每个人都有选和不选两种状态。
f[i][j]表示以第i个人结尾，选出j个人的最大值。由于相邻位置差小于d。所以f[i][j]这个状态从i的前d个人选 j-1个人的状态转移过来。所以f[i][j]=max(f[z][j-1],f[i]][j])。z表示i的前d个人中的某一个。
但值得注意的是，题目给的数据有负数。有负数会有什么影响呢？由于一个越大的数乘一个负数会变得越小。且一个越小的数，乘以一个负数，就会变得越大。对于f[i][j]来说，它不仅可能由f[z][j-1]转移过来，也有可能从minf[z][j-1]转移过来（minf[z][j]表示以第z个人结尾，选出j个人的最小值）。即假设第i个人是一个负数，则从minf[z][j-1]转移过来。
由于f[][]和minf[][]的含义类似，我们在更新f的同时可以顺便更新minf。
代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include <climits> #include <iostream> #include<vector> using namespace std; typedef long long LL; const int N = 1100; LL a[N]; int main() { int n, k, d; cin >> n >> k >> d; for (int i = 0; i < n; i++)cin >> a[i]; vector<vector<LL>> minf(n + 1, vector<LL>(k + 1)); vector<vector<LL>> maxf(n + 1, vector<LL>(k + 1)); for (int i = 0; i < n; i++) { minf[i][1] = a[i]; maxf[i][1] = a[i]; } for (int i = 0; i < n; i++) { for (int j = 2; j <= k; j++) { for (int z = max(0, i - d); z < i; z++) { maxf[i][j] = max(max(maxf[z][j - 1] * a[i], minf[z][j - 1] * a[i]), maxf[i][j]); minf[i][j] = min(min(maxf[z][j - 1] * a[i], minf[z][j - 1] * a[i]), minf[i][j]); } } } LL ans = maxf[0][k]; for (int i = 1; i < n; i++) { ans = max(ans, maxf[i][k]); } cout << ans << endl; return 0; }
day33
一、跳台阶扩展问题
找规律。青蛙一次可以跳【1~n】级台阶。从最后一步看，跳到第n级台阶可以从起点跳，也可以从第1级、2、3、4、...n-1。即f[n]=f[n-1]+f[n-2]+...f[1]+f[0]。f[n]表示跳到第n级台阶的方法数。找下规律。很容易看出来，f[n]=2^n-1。
代码：
#include <iostream> using namespace std; int main() { int n; cin>>n; cout<<(1<<(n-1)); return 0; }
二、包含不超过两种字符的最大子串。
滑动窗口。维护一个区间，这个区间的字符种类不超过2.用一个数组表示当前区间每种字符大的数量。遍历到当前字符就加加，如果加加后为1，说明有新种类的字符出现。用一个遍历维护种类数，其实就是字符数量大于0的个数。出现矛盾后从左区间缩小区间，字符数量减1，为0说明消失一个字符种类。
代码：
#include <iostream> using namespace std; int a[200]; int main() { string str; cin>>str; int n=str.size(); int ans=0; int cnt=0; for(int i=0,j=0;i<n;i++){ a[str[i]]++; if(a[str[i]]==1)cnt++; while(j<i&&cnt>2){ a[str[j]]--; if(a[str[j]]==0)cnt--; j++; } ans=max(ans,i-j+1); } cout<<ans<<endl; return 0; }
三、字符串的排列
dfs求全排列。由于字符串可能有重复的字符，对下标进行全排列会出现重复排列的可能。如“aa".
所以可以在dfs的时候检查当前位置的字符是否重复遍历过，或者下标全排列之后排序去重。我这里是后者。
代码：
class Solution { public: void dfs(int u,vector<string>& ans,string t,int n,string str,vector<bool>& st){ if(u==n){ ans.push_back(t); return ; } for(int i=0;i<n;i++){ if(!st[i]){ st[i]=true; t.push_back(str[i]); dfs(u+1,ans,t,n,str,st); st[i]=false; t.pop_back(); } } } vector<string> Permutation(string str) { int n=str.size(); vector<bool> st(300,false); vector<string> ans; string t=""; dfs(0,ans,t,n,str,st); sort(ans.begin(),ans.end()); ans.erase(unique(ans.begin(),ans.end()),ans.end()); return ans; } };
