A
https://ac.nowcoder.com/acm/problem/209426
发现 ,显然不能暴力枚举。
发现是拆成两个不同的数之和,那这题不就按奇偶讨论一下就行了?
时间复杂度:。
class Solution { public: int solve(int n) { if(n%2) return n/2; else return n/2-1; } };
B
https://ac.nowcoder.com/acm/problem/207796
考烂了的 01 背包,,直接爆搜即可。
时间复杂度:。
class Solution { public: bool p[20]; int v_[22],g_[22],V_,ans=-1,n; void work() { int sum=0; for(int i=1;i<=20;i++) if(p[i]) sum+=v_[i]; if(sum!=V_) return; sum=0; for(int i=1;i<=20;i++) if(p[i]) sum+=g_[i]; ans=max(ans,sum); return; } void dfs(int dep) { if(dep==n+1) { work(); return; } dfs(dep+1); p[dep]=1; dfs(dep+1); p[dep]=0; return; } int Maximumweight(vector<int>& v, vector<int>& g, int V) { n=v.size(); for(int i=0;i<v.size();i++) v_[i+1]=v[i]; for(int i=0;i<g.size();i++) g_[i+1]=g[i]; V_=V; dfs(1); return ans; } };
C
https://ac.nowcoder.com/acm/problem/210281
真前缀与真后缀的话,显然如果相同,长度也一定相同。
明显枚举长度不能省,考虑优化比较两个字符串的方法,想到可以 Hash 做,于是就做完了。
时间复杂度:。
class Solution { public: typedef unsigned long long ull; const int base=13331; ull bm[1000010],ha[1000010]; int ans=-1; int solve(string s) { int len=s.size(); bm[0]=1; for(int i=0;i<len;i++) { bm[i+1]=bm[i]*base; ha[i+1]=ha[i]*base+s[i]; } for(int i=1;i<len;i++)//ha[6]-ha[4]* if(ha[i]==(ha[len]-ha[len-i]*bm[i])) ans=max(ans,i); return ans; } };
D
不会,没学过对数,爬了。