题目链接 经商 题目思路 并查集构图，再用01背包解决 代码实现 #include<bits/stdc++.h> using namespace std; const int Max=1e6; int n,m,c; int fa[Max],dp[Max],cost[Max],value[Max]; void init() { for(int i=1;i<=n;i++) fa[i]=i; } int find(int x) { if(fa[x]!=x) { fa[x]=find(fa[x]); } retu...

题目链接 食物链 题目思路：带权并查集 设0为a,b同级 a1b为a吃b a2b为b吃a第一次写带权并查集，希望在最近的刷题中能有所提高 代码实现 #include<bits/stdc++.h> using namespace std; #define ll long long const int Max=1e6; int n,k; int ft[Max],d[Max]; void init() { for(int i=1;i<=n;i++) ft[i]=i; } int find(int x) { if(ft[x]==x) return ...

题目链接 扑克牌 题目思路 二分,数据比较大的时候r设的大一些，不然易wa 代码实现 #include<bits/stdc++.h> using namespace std; #define ll long long const int Max=1e5; ll n,m,c[Max]; bool check(ll x) { ll res=0; for(int i=1;i<=n;i++) { res+=(max(c[i],x)-c[i]); } return res<=min(m,x); } int main() { ...

题目链接 聪明的质检员 题目思路 二分+前缀和优化#代码实现 #include<bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define ll long long const int Max=1e6; ll n,m,s; ll v[Max],w[Max],L[Max],R[Max],sum[Max],cnt[Max]; ll check(int x) { ll res=0; for(int i=1;i&l...

题目链接 wyh的物品 题目思路 01分数规划入手题，千万不要把value和weight看反！ 代码实现 #include<bits/stdc++.h> using namespace std; #define ll long long const int Max=1e5+5; int a[Max],b[Max]; int n,k; double p[Max]; bool cmp(double aaa,double bbb) { return aaa>bbb; } bool check(double x) { double res=0; for(int...

题目链接 K-th Number 题目思路 二分＋尺取法 题目大意是从a中找长度大于k的区间中第k大的数放入b中，然后在b中找到第m大的数，即为answer 然后可以这样想，假设第m大的数为x，那么应该有m个区间，其中有k个大于等于x的。当取x，有k大于等于x区间数量>=m时，x肯定是取小了，反之则取大了 区间用尺取法，找x用二分法一直疑问为什么l=mid+1,ans=mid,因为mid刚好为答案ans时，区间数量是等于m的。（多练习二分） 代码实现 #include<bits/stdc++.h> using namespace std; #define ll lon...

题目链接 分数线划定 代码实现 #include<bits/stdc++.h> using namespace std; struct score { int num,scr; }a[5005]; bool cmp(score a,score b) { if(a.scr==b.scr) return a.num<b.num; return a.scr>b.scr; } int main() { int n,m; while(cin>>n>>m){ for(int i=0;i<...

题目链接 小C的记事本 题目思路：对栈的运用 撤销可以通过栈的pop()来实现，str.erase()是新学到的知识，原来字符串还有删除指定部分字符串的函数str.erase(x,y); 删除字符串str从第x开始的y个字符 代码实现 #include<bits/stdc++.h> using namespace std; int t; string tmp,in; int num; int main() { int q; while(cin>>q){ stack<string> str; while(q...

题目链接 题目链接三个拓展 题目思路：前缀和加dp 代码实现 #include<bits/stdc++.h> using namespace std; const int Max=1e6; long long a[Max],s[Max]; int main() { int t; cin>>t; while(t--) { int n,k; long long nmax=-1e18,ans=-1e18; cin>>n>>k; for(int i=1;i&l...

题目链接 The Biggest Water Problem 题目思路 无脑暴力递归 代码实现 #include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; while(n>=10) { int sum=0; while(n) { sum+=(n%10); n/=10; } n=sum; } cout<...

题目链接 逆序数 题目思路：归并排序的典型题 熟练运用归并排序 代码实现 #include<bits/stdc++.h> using namespace std; const int Max=1e5+5; int a[Max],b[Max]; long long sum=0; void _merge(int left,int right) { if(left>=right) return; int mid=left+(right-left)/2,l=left,r=mid+1; _merge(left,mid); _merge(mid+1,rig...

题目链接 老子的全排列呢 题目思路：简单递归 全排列函数 next_permutation()参考博客 实现代码 #include<bits/stdc++.h> using namespace std; int f[10]; int a[8]; void dfs(int n) { if(n==8) { for(int i=0;i<n-1;i++) cout<<a[i]<<' '; cout<<a[n-1]<<endl; } else ...

题目链接 竞赛技巧 题目思路：cmp函数 代码实现 #include<bits/stdc++.h> using namespace std; struct timem { int hr,min,sec; }ti[5005]; bool cmp(timem a,timem b) { if(a.hr==b.hr) { if(a.min==b.min) return a.sec<b.sec; else return a.min<b.min; } else return a.hr&l...

题目链接 栈和排序 题目思路：贪心 假m[i]大于后面所有数的最大值maxm[i+1]，不难发现，如果现在不输出m[i]，那最后出栈的字典序一定小于当前的字典序 代码实现 #include<bits/stdc++.h> using namespace std; int maxm[1000005],m[1000005]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>m[i]; for(int i=n;i>=1;i--) ...