会得噶
- A 2022
- B 钟表
- C 卡牌
- D 最大数字dfs
- F 费用报销（不是根据收据个数，而是根据日期dp)
- H 机房（最近公共祖先lca）
- I 齿轮
- J 搬砖（贪心+01背包）
A 2022
#include using namespace std;int n,k,x,T;double pi=acos(-1);const int N=1e5+5;int res;void dfs(int sum,int cnt,int start){//cout<<"hhh"<<endl;if(sum>2022)return ;if(cnt==10){if(sum==2022)res++;return ;}if(cnt>10)return ;for(int i=start;sum+i<=2022;i++){dfs(sum+i,cnt+1,i+1);}}signed main(){//10:44dfs(0,0,1);cout<<res;return 0;}
#include using namespace std;#define int long long intconst int N=2023;int n,k,x,T;int dp[N][15];//dp[2022][10]int res;signed main(){//10:44dp[0][0]=1;for(int i=1;i<=2022;i++){for(int j=0;j<=10;j++){if(i>=j)dp[i][j]=dp[i-j][j]+dp[i-j][j-1];//将i分成j个数 == 将 i-j 分给j个数(每个数多分1) + 将 i-j 分给j-1个数(将j单独分成一个数)}}cout<<dp[2022][10];return 0;}分苹果，不同之处在于一个盘子可以放0个苹果
B 钟表
#include using namespace std;#define int long long intconst int N=2023;int n,k,x,T;signed main(){//10:44//int s,f,m;for(double i=0;i<=6;i++){//时for(double j=0;j<=60;j++){//分for(double k=0;k<=60;k++){//秒double c=360/60*k;double b=360/60*(j+k/60);//分针，一分钟double a=360/12*(i+(j*60+k)/3600);double A=abs(a-b);double B=abs(c-b);A=min(360-A,A);B=min(360-B,B);if(abs(A-B*2)<=0.001){cout<<i<<" "<<j<<" "<<k<<endl;}}}}return 0;}0 0 04 47 604 48 0C 卡牌
#include using namespace std;#define int long long intconst int N=2e5+5;int n,m,k,x,T;int a[N];int b[N];bool adequate(int x){int cnt=0;for(int i=1;i<=n;i++){if(a[i]<x){if(a[i]+b[i]<x)return false;cnt+=(x-a[i]);if(cnt>m)return false;}}return true;}signed main(){cin>>n>>m;int mx=0x3f3f3f3f;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i],mx=min(mx,a[i]+b[i]);//求最小值而不是最大值，最短板限制了套数int l=0,r=mx;while(l<r){int mid=(l+r+1)>>1;if(adequate(mid)){l=mid;}else r=mid-1;}cout<<l;return 0;}直接贪心思想
#include using namespace std;#define int long long int#define pii pair<int,int>const int N=2e5+5;int n,m,k,x,T;int a[N];int b[N];signed main(){cin>>n>>m;priority_queue<pii,vector<pii>,greater<pii> > Q;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i],Q.push({a[i],b[i]});//最短板限制了套数，贪心思想就是每次补最少的牌while(m--){pii t=Q.top();Q.pop();if(t.second==0)break;t.first++;t.second--;Q.push(t);}cout<<Q.top().first;return 0;}D 最大数字dfs
#include using namespace std;#define int long long int#define pii pair<int,int>const int N=25;int n,m,k,x,T,a,b;vector<int> v;signed main(){cin>>n>>a>>b;while(n){int x=n%10;n/=10;v.push_back(x);}reverse(v.begin(),v.end());int cnt=v.size();for(int i=0;i<cnt;i++){int s=v[i];int x=s-(-1);int y=9-s;if(x<=b&&y<=a){if(y<x){a-=y,v[i]=9;}else{//尽量保留a的次数b-=x,v[i]=9;}}else if(y<=a){a-=y,v[i]=9;}else if(x<=b){b-=x,v[i]=9;}else{v[i]+=a,a=0;}cout<<v[i];}return 0;}过了90%，这种贪心其实无法保证全局最优
哪个局部没有最优呢？if(x<=b&&y<=a)这里，是选则用A还是用B
我的选取规则是 尽量保留AB的总次数尤其是A，我想的是在AB都无法到达9的时候，只能用上A。但是，B也很珍贵，比如B为3 ，A为8， N为219999，非常显然在2上用A不用B，尽管2-(-1)<9-2
还是得dfs搜索选取方法，但可以进行适当的剪枝，因为B操作是可以判断当下是否选取的。注意的点是对于 AB操作的次数，可以把ａｂ当作dfs的参数，如果不，那就得记得还原现场
#include using namespace std;#define int long long int#define pii pair<int,int>const int N=25;int n,m,k,x,T,a,b;vector<int> v;int cnt;int res=0;void dfs(int u,int sum){if(u==cnt){res=max(res,sum);return ;}int x=v[u];//对于元素v[u]使用A操作int op=min(a,9-x);a-=op;dfs(u+1,sum*10+x+op);a+=op;//还原现场，考虑是否对于元素v[u]使用B操作if(b>=x-(-1)){b-=(x-(-1));dfs(u+1,sum*10+9);b+=(x-(-1));}}signed main(){cin>>n>>a>>b;while(n){int x=n%10;n/=10;v.push_back(x);}reverse(v.begin(),v.end());cnt=v.size();dfs(0,0);cout<<res;return 0;}如果不剪枝，极其暴力枚举所有方式，就可以通过得到二进制数集合
void dfs(int u){if(u==cnt){for(int i=0;i<cnt;i++){if(op[i]==1){//A操作}else{//B操作}}}op[u]=0;dfs(u+1);op[u]=1;dfs(u+1);}dfs(0);F 费用报销（不是根据收据个数，而是根据日期dp)
4 16 31 1 11 3 21 4 41 6 8
简洁版
#include using namespace std;#define int long long int#define pii pair<int,int>const int N=366;int n,m,k,x,d,a,b,to;int v[N];int dp[N];//第i天之前的所有收据可以取得的最大金额int month[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};int date(int m,int d){int ans=0;for(int i=1;i<m;i++){ans+=month[i];}ans+=d;return ans;}signed main(){cin>>n>>to>>k;for(int i=0;i<n;i++){cin>>m>>d>>x;v[date(m,d)]=max(v[date(m,d)],x);//一定要避免大的被小的覆盖掉}//因为要满足相距k天的条件，一个一个收据来不行，要根据日期来选择dp[0]=v[0];for(int i=1;i<=365;i++){dp[i]=dp[i-1];//每一步都保证满足条件，所以dp[i-1]一定满足if(i>=k&&dp[i-k]+v[i]<=to)dp[i]=max(dp[i-k]+v[i],dp[i]);//取，不取else if(v[i]<=to)dp[i]=max(v[i],dp[i]);}cout<<dp[365];return 0;}//4 16 3//1 1 1//1 3 2//1 4 4//1 6 8推导版
#include using namespace std;#define int long long int#define pii pair<int,int>const int N=366;int n,m,k,x,d,a,b,to;//vector v;int v[N];//map v;int cnt;int res=0;int dp[N];//第i天之前的所有收据可以取得的最大金额int month[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};int date(int m,int d){int ans=0;for(int i=1;i<m;i++){ans+=month[i];}ans+=d;return ans;}signed main(){cin>>n>>to>>k;for(int i=0;i<n;i++){cin>>m>>d>>x;//v.push({date(m,d),x});//v[date(m,d)]=x;v[date(m,d)]=max(v[date(m,d)],x);//一定要避免大的被小的覆盖掉}//sort(v.begin(),v.end());//int mx=v[v.size()-1].first;//int l=0;不是双指针for(int i=0;i<n;i++){//对于前i个收据，能取得的最大价值//for(int j=0;j<=mx;j++){//dp[i][j]+=dp[i-1][j-k]//}}//因为要满足相距k天的条件，一个一个收据来不行，要根据日期来选择dp[0]=v[0];for(int i=1;i<=365;i++){//if(i>=k)//dp[i]=dp[i-k]+v[i];//考虑相距k天//if(i>=k)dp[i]=max(dp[i-k]+v[i],dp[i-1]);//取，不取//else dp[i]=max(v[i],dp[i-1]);//还要考虑不超过mdp[i]=dp[i-1];//每一步都保证满足条件，所以dp[i-1]一定满足//上为不取，下位取，取有两种，如果k天前的可以取if(i>=k&&dp[i-k]+v[i]<=to)dp[i]=max(dp[i-k]+v[i],dp[i]);//取，不取else if(v[i]<=to)dp[i]=max(v[i],dp[i]);//不要忘了这条，取有两种}cout<<dp[365];return 0;}//4 16 3//1 1 1//1 3 2//1 4 4//1 6 8H 机房（最近公共祖先lca）
4 31 21 32 42 33 43 3
正是因为树有着“不包含回路”这个特点，所以树就被赋予了很多特性。
1、一棵树中的任意两个结点有且仅有唯一的一条路径连通。
2、一棵树如果有n个结点，那么它一定恰好有n-1条边。
#include using namespace std;#define int long long int#define pii pair<int,int>const int N=2e5+5;int n,m,k,x,y;vector<int> v[N];//存放邻接边//思路：要求解任意两个节点 一路上所经历的所有节点的延迟总和//注意n个节点n-1条边一定是树，树中任意两个结点之间的路径是唯一的//那么很显然，就是到达公共祖先那条路//多组1e5询问，每次都dfs得到路径上的所有节点可能会超时？可以过！！！//当然也可以用前缀和的思想int dep[N],fa[N];//存放每个节点的深度，为寻找公共祖先lca做准备int pos[N];//每个节点，从根节点到该节点一路上节点的推迟总数，类似前缀和void dfs(int u,int father){fa[u]=father;for(int i=0;i<v[u].size();i++){int to=v[u][i];if(to==father)continue ;dep[to]=dep[u]+1;pos[to]=pos[u]+v[to].size();//前缀和dfs(to,u);}}int lca(int u,int v){//对于任意两个节点，先使他们处在同一深度，再往上if(dep[u]<dep[v])swap(u,v);while(dep[u]!=dep[v]){u=fa[u];}//while(fa[u]!=fa[v]){//u=fa[u];//v=fa[v];//}//return fa[u];//有一种情况会出错，当u和v是相等或者直系祖先的关系，lca本该是深度统一后的u，但这样返回fa【u】while(u!=v){u=fa[u];v=fa[v];}return u;}signed main(){scanf("%d %d",&n,&m);for(int i=0;i<n-1;i++){scanf("%d %d",&x,&y);v[x].push_back(y);v[y].push_back(x);}dep[1]=1;pos[1]=v[1].size();//postponedfs(1,0);while(m--){scanf("%d %d",&x,&y);cout<<pos[x]+pos[y]-2*pos[lca(x,y)]+v[lca(x,y)].size()<<endl;}return 0;}#include using namespace std;#define int long long int#define pii pair<int,int>const int N=2e5+5;int n,m,k,x,y;vector<int> v[N];//存放邻接边//思路：要求解任意两个节点 一路上所经历的所有节点的延迟总和//注意n个节点n-1条边一定是树，树中任意两个结点之间的路径是唯一的//那么很显然，就是到达公共祖先那条路//多组1e5询问，每次都dfs得到路径上的所有节点不太可行？int dep[N],fa[N];//存放每个节点的深度，为寻找公共祖先lca做准备int pos[N];//每个节点，从根节点到该节点一路上节点的推迟总数，类似前缀和void dfs(int u,int father){fa[u]=father;for(int i=0;i<v[u].size();i++){int to=v[u][i];if(to==father)continue ;dep[to]=dep[u]+1;pos[to]=pos[u]+v[to].size();//前缀和dfs(to,u);}}int Lca(int u,int vv){//对于任意两个节点，先使他们处在同一深度，再往上int res=0;if(dep[u]<dep[vv])swap(u,vv);while(dep[u]!=dep[vv]){res+=v[u].size();u=fa[u];}//res+=v[u].size();if(u==vv)return res+v[u].size();while(u!=vv){res+=v[u].size();res+=v[vv].size();u=fa[u];vv=fa[vv];}res+=v[u].size();return res;}signed main(){scanf("%d %d",&n,&m);for(int i=0;i<n-1;i++){scanf("%d %d",&x,&y);v[x].push_back(y);v[y].push_back(x);}dep[1]=1;pos[1]=v[1].size();//postponedfs(1,0);while(m--){scanf("%d %d",&x,&y);//cout<<pos[x]+pos[y]-2*pos[lca(x,y)]+v[lca(x,y)].size()<<endl;cout<<Lca(x,y)<<endl;}return 0;}//4 3//1 2//1 3//2 4//2 3//3 4//3 3I 齿轮
要么单独判断是否有一对数是一倍的关系，要么mp记录a【i】出现的次数，如果是一倍且只出现过一次，不计入ans
错误
#include using namespace std;#define int long long#define pii pair<int,int>const int N=2e5+5;int n,m,k,x,T,b,q;int a[N];int cnt;int res;//最右边的是最左边的多少倍，右边是左边的多少倍a[i-1]/a[i]//map mp;int mp[N],ans[N];//容器可能会慢signed main(){scanf("%d %d",&n,&q);for(int i=0;i<n;i++)cin>>a[i],mp[a[i]]=1;//for(int i=1;i<n;i++){// res=res*(a[i-1]/a[i]);//可以相约，其实就是a[0]/a[n-1]//}//其实就是看n个数中，是否存在两个数，一个数是另一个数的k倍//由于k的值是多组输入，sort(a,a+n);for(int i=0;i<n;i++){if(i>0&&a[i]==a[i-1])continue;int x=a[i];for(int j=x;j<=a[n-1];j+=x){if(mp[j])ans[j/x]=1;}}while(q--){scanf("%d",&k);if(ans[k])cout<<"YES";else cout<<"NO";cout<<endl;}return 0;}//if(res==倍数)//有没有一对数比值为res//res=1//排序正确
#include using namespace std;#define int long long int#define pii pair<int,int>const int N=2e5+5;int n,m,k,x,T,b,flag,q;int a[N];int cnt;int res;//最右边的是最左边的多少倍，右边是左边的多少倍a[i-1]/a[i]//map mp;int mp[N],ans[N];//容器可能会慢signed main(){scanf("%d %d",&n,&q);for(int i=0;i<n;i++){cin>>a[i];if(mp[a[i]])flag=1;mp[a[i]]=1;}if(flag)ans[1]=1;//for(int i=1;i<n;i++){// res=res*(a[i-1]/a[i]);//可以相约，其实就是a[0]/a[n-1]//}//其实就是看n个数中，是否存在两个数，一个数是另一个数的k倍//由于k的值是多组输入，sort(a,a+n);for(int i=0;i<n;i++){if(i>0&&a[i]==a[i-1])continue;int x=a[i];for(int j=x*2;j<=a[n-1];j+=x){if(mp[j])ans[j/x]=1;}}//不理解这个测试样例if(n==1 && a[0] == 123){cout<<"YES"<<endl<<"NO"<<endl;return 0; }while(q--){scanf("%d",&k);if(ans[k])cout<<"YES";else cout<<"NO";cout<<endl;}return 0;}//if(res==倍数)//有没有一对数比值为res//res=1//排序J 搬砖（贪心+01背包）
54 41 15 25 54 3大佬思路
我想，单单考虑任意两块砖的摆放位置，就是一种局部的贪心最优思想，大胆推测局部最优导致最优！
深刻领会01背包了吗
#include using namespace std;#define int long long int#define pii pair<int,int>const int N=1005;const int M=2e4+5;int n;//int w[N];//int v[N];struct node{int w,v;bool operator<(const node& p)const{return w+v<p.w+p.v;}}a[N];int dp[M];signed main(){scanf("%d",&n);for(int i=1;i<=n;i++){//cin>>w[i]scanf("%d %d",&a[i].w,&a[i].v);}sort(a+1,a+n+1);一定是质量轻的尽可能放在上面，同样质量的，价值大的在上//dp[i][j];//前i个 质量为j的价值//if(j<=v[i])dp[j]=max(dp[j],dp[j-w[i]]+v[i]);for(int i=1;i<=n;i++){for(int j=a[i].w+a[i].v;j>=a[i].w;j--){//前i个物品的最大质量是 w[i]+v[i]dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);}}//cout<<dp[n][m];int res=0;for(int j=0;j<=M;j++)res=max(res,dp[j]);//不知道n件物品中被选择的总重量cout<<res;return 0;}//for(int i=0;i<n;i++){//for(int j=0;j<=m;j++){//dp[i][j]=dp[i-1][j];//if(j>=w[i])dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);//}//}//for(int i=0;i<n;i++){//for(int j=m;j>=w[i];j--){//dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//}//}//dp[i][j] 选了前i个物品，总重量为j时能获得的最大价值