[toc]
每日一题 3384 二叉树遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <iostream> using namespace std;void dfs () { char x; scanf ("%c" ,&x); if (x>='a' && x<='z' ){ dfs (); printf ("%c " ,x); dfs (); } } int main () { dfs (); return 0 ; }
4956冶炼金属 最简单的答案--数学推导 我自己想的,二分查找,只能过前八个样例 最后答案也很好看
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <iostream> using namespace std;int res_max,res_min;int main () { int n; scanf ("%d" ,&n); res_min = 0 ; res_max = 1e9 +100 ; for (int i = 0 ;i<n;++i){ int a,b; scanf ("%d%d" ,&a,&b); res_max = min (a/b,res_max); res_min = max (a/(b+1 )+1 ,res_min); } printf ("%d %d" ,res_min,res_max); return 0 ; }
基本思路是,给定的两个数能找到其范围内的最大值和最小值。不详细说明了,反正是一个很傻瓜的算法,后面不知道什么原因过不了最后两个样例。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #include <iostream> using namespace std;bool judge_ceil (int a,int b,int c) { return b>(double )a/c; } bool judge_floor (int a,int b,int c) { return b>=(double )a/c-1 ; } void get_range (int a,int b,int &mn,int &mx) { mn = mx = 0 ; int l = 0 ,r = a; while (l<r){ int mid = (l+r)>>1 ; if (judge_floor (a,b,mid)) r = mid; else l = mid+1 ; } if (judge_floor (a,b,l)) mn = l; else mn = l+1 ; l = 0 ,r = a; while (l<r){ int mid = (l+r)>>1 ; if (judge_ceil (a,b,mid)) r = mid; else l = mid+1 ; } if (judge_ceil (a,b,l)) mx = l-1 ; else mx = l; } int res_max,res_min;int main () { int n; scanf ("%d" ,&n); res_min = 0 ; res_max = 1e9 +100 ; for (int i = 0 ;i<n;++i){ int a,b,tmp_max,tmp_min; scanf ("%d%d" ,&a,&b); get_range (a,b,tmp_min,tmp_max); res_max = min (tmp_max,res_max); res_min = max (tmp_min,res_min); } cout<<res_min<<" " <<res_max<<endl; return 0 ; }
4958 接龙数列 先复习一下模板(我又忘得差不多了)
acwing-895.最长上升子序列 第一次尝试:递推 第二次尝试:最长上升子序列的变体(时间复杂度太高) 第三次尝试(Y总的思路): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <iostream> using namespace std;const int N = 1010 ;int f[N]; int g[N];int n;int main () { cin>>n; int mx = 0 ; for (int i = 1 ;i<=n;++i)cin>>g[i]; for (int i = 1 ;i<=n;++i){ f[i] = 1 ; for (int j = 0 ;j<=i-1 ;++j) if (g[i]>f[j]) f[i] = max (f[i],f[j]+1 ); mx = max (mx,f[i]); } cout<<mx<<endl; return 0 ; }
关键在于理解这一部分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 for (int i = 1 ;i<=n;++i){ f[i] = 1 ; for (int j = 0 ;j<=i-1 ;++j) if (g[i]>g[j]) f[i] = max (f[i],f[j]+1 ); mx = max (mx,f[i]); } for (int i = 1 ;i<=n;++i){ f[i] = 1 ; for (int j = i-1 ;j>0 ;--j) if (g[i]>g[j]) f[i] = max (f[i],f[j]+1 ); mx = max (mx,f[i]); }
按从1—n的次序更新f(n)的值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include <iostream> using namespace std;const int N = 1e5 +10 ;int d[N];int f[N];int num[N];int n;bool check (int a,int b) { int tail = a%10 ; int head = 0 ; while (b){ head = b%10 ; b/=10 ; } return tail==head; } int main () { scanf ("%d" ,&n); for (int i = 1 ;i<=n;++i)scanf ("%d" ,&num[i]); int last = num[1 ]; f[1 ] = 1 ; for (int i = 2 ;i<=n;++i){ if (check (last,num[i])){ last = num[i]; f[i] = f[i-1 ]+1 ; }else { f[i] = f[i-1 ]; } } cout<<n-f[n]<<endl; return 0 ; }
具体思路:
由第一个往后推,如果后一个是当前最长接龙的下一个位置,则更新当前最长接龙尾部的数为当前数并且将fi = length++ 否则 fi = length。
问题:贪心思想没法找到全局最优解。当前这个可以是最长接龙的尾巴但是不是最好的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <iostream> using namespace std;const int N = 1e5 +10 ;int d[N];int f[N];int num[N];int n;bool check (int a,int b) { int tail = a%10 ; int head = 0 ; while (b){ head = b%10 ; b/=10 ; } return tail==head; } int main () { scanf ("%d" ,&n); for (int i = 1 ;i<=n;++i)scanf ("%d" ,&num[i]); f[1 ] = 1 ; int mx = 0 ; for (int i = 1 ;i<=n;++i){ f[i] = 1 ; for (int j = i-1 ;j>0 ;--j){ if (check (num[j],num[i])) f[i] = max (f[i],f[j]+1 ); } mx = max (f[i],mx); } cout<<n-mx<<endl return 0 ; }
TLE 时间复杂度为 超时了。
对于前面的最长上升子序列的优化,主要优化部分是两重循环。
分析:第二层循环是在前i-1个数据中找到以第i个数头结尾的最长的子序列长度,所以只要记录这个值就ok,因为:==以i个数头结尾的最长的子序列长度是可以穷举,有限的(只有十个)==,而最长子序列无法使用这种方法是因为他需要遍历前面所有的数据找到最值,而这个最值是无法有限次记录的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include <iostream> #include <cstring> using namespace std;const int N = 1e5 +10 ;int h[N],l[N],G[11 ];int f[N];int n;int main () { scanf ("%d" ,&n); int mx = 0 ; for (int i = 1 ;i<=n;++i){ char s[11 ]; scanf ("%s" ,s); h[i] = s[0 ]-'0' ; l[i] = s[strlen (s)-1 ]-'0' ; f[i] = 1 ; f[i] = max (f[i],G[h[i]]+1 ); G[l[i]] = max (f[i],G[l[i]]); mx = max (f[i],mx); } cout<<n-mx<<endl; return 0 ; }
4964 子矩阵 数位DP、单调队列。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <iostream> #include <cstring> using namespace std;const int N = 1010 ;const int mod = 998244353 ;const int INF = 1e9 +10 ;int g[N][N];int m,n,a,b;int main () { scanf ("%d%d%d%d" ,&n,&m,&a,&b); for (int i = 1 ;i<=n;++i) for (int j = 1 ;j<=m;++j)scanf ("%d" ,&g[i][j]); int sum = 0 ; for (int i = 1 ;i<=n-a+1 ;++i){ for (int j = 1 ;j<=m-b+1 ;++j){ int mx = 0 ; int mi = INF; for (int q = i;q<i+a;++q){ for (int p = j;p<j+b;p++){ mx = max (mx,g[q][p]); mi = min (mi,g[q][p]); } } sum=(sum+(mx*mi))%mod; } } printf ("%d" ,sum); return 0 ; }
时间复杂度可能要到
3431 skew数 很简单的一道字符串模拟题目
1 2 3 4 5 6 7 8 9 10 11 12 #include <iostream> #include <cstring> using namespace std;int main () { string str; while (getline (cin,str)){ int res = 0 ; for (int i = str.length ()-1 ,k = 2 ;i>=0 ;--i,k<<=1 ) res += (str[i]-'0' )*(k-1 ); cout<<res<<endl; } }
3446 整数奇偶排序 一道很简单的排序题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include <algorithm> #include <vector> #include <iostream> using namespace std;vector<int > odd,even; bool cmp (int &a,int &b) { return a>b; } int main () { int t; while (cin>>t){ if (t%2 ) odd.push_back (t); else even.push_back (t); } sort (odd.begin (),odd.end (),cmp); sort (even.begin (),even.end ()); for (auto x:odd){ cout<<x<<" " ; } for (auto x:even){ cout<<x<<" " ; } return 0 ; }
3508 最长公共子串 :exclamation: 求的是公共子串!!!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <iostream> #include <cstring> using namespace std;const int N = 1e4 +10 ;int f[N]; char a[N],b[N];int main () { scanf ("%s%s" ,a+1 ,b+1 ); int a_length = strlen (a+1 ); int b_length = strlen (b+1 ); int mx = 0 ; for (int i = 1 ;i<=a_length;++i){ for (int j = b_length;j>=1 ;--j){ if (a[i]==b[j] && a[i]>='a' ) f[j] = f[j-1 ]+1 ; else f[j] = 0 ; mx = max (mx,f[j]); } } cout<<mx<<endl; return 0 ; }
3543 三元组 时间复杂度分析:找一个长度为m中的满足条件的三元组。时间复杂度为 m最大为50,n最大为10;所以 暴力做法完全可行啊! 可以做的优化就是将第三重循环做一个二分。这样就可以少一层,但是要先排序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <iostream> using namespace std;const int N = 51 ;int num[N];int main () { int n; cin>>n; while (n--){ int m; int cnt = 0 ; cin>>m; for (int i = 0 ;i<m;++i){ cin>>num[i]; } for (int i = 0 ;i<m;++i){ for (int j = 0 ;j<m;++j){ for (int k = 0 ;k<m;++k){ if (num[i]+num[j] == num[k]) cnt++; } } } cout<<cnt<<endl; } return 0 ; }
3576 分组统计 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include <iostream> #include <unordered_map> #include <vector> #include <algorithm> using namespace std;const int N = 110 ;int main () { int t,n; cin>>t; while (t--){ unordered_map<int ,int > set[N]; int number[N]; int gs[N]; cin>>n; int mx_group = 0 ; for (int i = 0 ;i<n;++i)cin>>number[i]; for (int i = 0 ;i<n;++i) cin>>gs[i]; for (int i = 0 ;i<n;++i){ set[gs[i]][number[i]]++; mx_group = max (mx_group,gs[i]); } sort (number,number+n); int k = unique (number,number+n)-number; for (int g = 1 ;g<=mx_group;++g){ cout<<g<<"={" ; for (int i = 0 ;i<k;++i){ cout<<number[i]<<"=" <<set[g][number[i]]; if (i+1 <k)cout<<"," ; else cout<<"}\n" ; } } } return 0 ; }
简单模拟。
3395 10进制 VS 2进制 这是一道典型的高精度运算的题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <iostream> #include <vector> using namespace std;vector<int > add (vector<int > &A,vector<int > &B) { if (A.size ()<B.size ()) return add (B,A); vector<int > C; int t = 0 ; for (int i = 0 ;i<A.size ();++i){ t+=A[i]; if (i<B.size ()) t+=B[i]; C.push_back (t%10 ); t/=10 ; } if (t) C.push_back (t); return C; } int main () { string a,b; vector<int > A,B,C; cin>>a>>b; for (int i = a.length ()-1 ;i>=0 ;--i) A.push_back (a[i]-'0' ); for (int i = b.length ()-1 ;i>=0 ;--i) B.push_back (b[i]-'0' ); C = add (A,B); for (int i = C.size ()-1 ;i>=0 ;--i)cout<<C[i]; return 0 ; }
没啥好说的,注意输入和输出的数组顺序。add函数在处理加法的时候是从低位处理到高位,所以在输入的时候需要将低位放在前面,这和我们日常的书写顺序是相反的。
和加法差不多(差得不太多)
判断两个数的大小,用大的减去小的。
由于减法并不像加法有交换律所以定义减法的函数中减数和被减数的位置是固定的。
对于前导0 的处理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include <iostream> #include <vector> using namespace std;bool cmp (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]; return true ; } vector<int > sub (vector<int > &a,vector<int > &b) { vector<int > c; int t = 0 ; for (int i = 0 ;i<a.size ();++i){ t = a[i]-t; if (i<b.size ()) t-=b[i]; c.push_back ((t+10 )%10 ); if (t<0 ) t = 1 ; else t = 0 ; } while (c.size ()>1 && c.back ()==0 ) c.pop_back (); return c; } int main () { string a_s,b_s; vector<int > a,b,c; cin>>a_s>>b_s; for (int i = a_s.length ()-1 ;i>=0 ;--i) a.push_back (a_s[i]-'0' ); for (int i = b_s.length ()-1 ;i>=0 ;--i) b.push_back (b_s[i]-'0' ); if (cmp (a,b)){ c = sub (a,b); }else { c = sub (b,a); cout<<"-" ; } for (int i = c.size ()-1 ;i>=0 ;--i) cout<<c[i]; return 0 ; }
需要注意的是:
对于结果的前导0的处理
结果一定会大于原式,如何处理多出原本被乘数size的数位。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <iostream> #include <vector> #include <algorithm> using namespace std;vector<int > multi (vector<int > &a,int b) { vector<int > c; int t = 0 ; for (int i = 0 ;i<a.size ()||t>0 ;++i){ if (i<a.size ()) t += b*a[i]; c.push_back (t%10 ); t/=10 ; } while (c.size ()>1 && c.back ()==0 ) c.pop_back (); return c; } int main () { string a; int b; vector<int > A; cin>>a>>b; if (b==0 ){ cout<<"0" ; return 0 ; } for (int i = a.length ()-1 ;i>-1 ;--i){ A.push_back (a[i]-'0' ); } vector<int > C = multi (A,b); for (int i = C.size ()-1 ;i>-1 ;--i)cout<<C[i]; return 0 ; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include <iostream> #include <vector> #include <algorithm> using namespace std;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]; C.push_back (r / b); r %= b; } reverse (C.begin (), C.end ()); while (C.size () > 1 && C.back () == 0 ) C.pop_back (); return C; } int main () { string a; vector<int > A; int B; cin >> a >> B; for (int i = a.size () - 1 ; i >= 0 ; i -- ) A.push_back (a[i] - '0' ); int r; auto C = div (A, B, r); for (int i = C.size () - 1 ; i >= 0 ; i -- ) cout << C[i]; cout << endl << r << endl; return 0 ; }
题目描述:
对于一个十进制数 A,将 A转换为二进制数,然后按位逆序排列,再转换为十进制数 B,我们称 B为 A 的二进制逆序数。
例如对于十进制数 173173,它的二进制形式为 1010110110101101,逆序排列得到 1011010110110101,其十进制数为 181181,181181 即为 173173 的二进制逆序数。
注意:二进制转十进制的加法表示!!!秦九韶算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 #include <iostream> #include <vector> #include <algorithm> using namespace std;vector<int > div_2 (vector<int > &a,int &r) { vector<int > c; r = 0 ; for (int i = a.size ()-1 ;i>-1 ;--i){ r = r*10 +a[i]; c.push_back (r>>1 ); r%=2 ; } reverse (c.begin (),c.end ()); while (c.size ()>1 && c.back ()==0 ) c.pop_back (); return c; } vector<int > add (vector<int > a,vector<int > b) { if (a.size ()<b.size ()) return add (b,a); vector<int > c; int t = 0 ; for (int i = 0 ;i<a.size ();++i){ t += a[i]; if (i<b.size ()) t+=b[i]; c.push_back (t%10 ); t/=10 ; } if (t) c.push_back (t); return c; } bool cmp (vector<int > a) { if (a.size ()>1 ) return true ; else return a[0 ]; } vector<int > dec_to_bin (vector<int > &a) { vector<int > b; while (cmp (a)){ int r; a = div_2 (a,r); b.push_back (r); } return b; } vector<int > bin_to_dec (vector<int > &b) { vector<int > d; d.push_back (0 ); for (int i = 0 ;i<b.size ();++i){ d = add (add (d,d),{b[i]}); } return d; } int main () { string a_s; vector<int > a,b,d; cin>>a_s; for (int i = a_s.length ()-1 ;i>-1 ;--i) a.push_back (a_s[i]-'0' ); b = dec_to_bin (a); d = bin_to_dec (b); for (int i = d.size () - 1 ; i >= 0 ; i --) cout << d[i]; cout << endl; return 0 ; }
详解一下如何计算大数二进制转大数十进制:
1 2 3 4 5 6 7 8 vector<int > bin_to_dec (vector<int > &b) { vector<int > d; d.push_back (0 ); for (int i = 0 ;i<b.size ();++i){ d = add (add (d,d),{b[i]}); } return d; }
3425 小白鼠排队 很简单的排序题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include <iostream> #include <algorithm> #include <vector> using namespace std;const int N = 110 ;struct mouse { int w; char color[11 ]; bool operator <(mouse &a) const { return w>a.w; } }; mouse m[N]; int n;int main () { cin>>n; for (int i = 0 ;i<n;++i){ cin>>m[i].w>>m[i].color; } sort (m,m+n); for (int i = 0 ;i<n;++i){ cout<<m[i].color<<endl; } return 0 ; }
3451 字符串排序II 很简单的排序,用到了排序的稳定性 用的是插入排序 复杂度卡点过了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include <iostream> #include <algorithm> #include <vector> #include <ctype.h> using namespace std;bool cmp (char a,char b) { a = (isupper (a)?(a-'A' +'a' ):a); b = (isupper (b)?(b-'A' +'a' ):b); return a<b; } void my_sort (vector<char > &t) { for (int i = 1 ;i<t.size ();++i) for (int j = i-1 ;j>=0 ;--j) if (cmp (t[j+1 ],t[j])) swap (t[j+1 ],t[j]); } int main () { string s; while (getline (cin,s)){ vector<char > table; for (int i = 0 ;i<s.length ();++i) if (isalpha (s[i])) table.push_back (s[i]); my_sort (table); for (int i = 0 ,j = 0 ;i<s.length ();++i) if (!isalpha (s[i])) cout<<s[i]; else { cout<<table[j]; j++; } cout<<endl; } return 0 ; }