A 2022
#include <bits/stdc++.h>
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:44
dfs(0,0,1);
cout<<res;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long int
const int N=2023;
int n,k,x,T;
int dp[N][15];//dp[2022][10]
int res;
signed main(){//10:44
dp[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個數(shù) == 將 i-j 分給j個數(shù)(每個數(shù)多分1) + 將 i-j 分給j-1個數(shù)(將j單獨分成一個數(shù))
}
}
cout<<dp[2022][10];
return 0;
}
分蘋果，不同之處在于一個盤子可以放0個蘋果
B 鐘表
#include <bits/stdc++.h>
using namespace std;
#define int long long int
const 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 0
4 47 60
4 48 0
C 卡牌
#include <bits/stdc++.h>
using namespace std;
#define int long long int
const 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]);
//求最小值而不是最大值，最短板限制了套數(shù)
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 <bits/stdc++.h>
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]});
//最短板限制了套數(shù)，貪心思想就是每次補最少的牌
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 最大數(shù)字dfs
#include <bits/stdc++.h>
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的次數(shù)
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%，這種貪心其實無法保證全局最優(yōu)
哪個局部沒有最優(yōu)呢？if(x<=b&&y<=a)這里，是選則用A還是用B
我的選取規(guī)則是 盡量保留AB的總次數(shù)尤其是A，我想的是在AB都無法到達9的時候，只能用上A。但是，B也很珍貴，比如B為3 ，A為8， N為219999，非常顯然在2上用A不用B，盡管2-(-1)<9-2
還是得dfs搜索選取方法，但可以進行適當?shù)募糁?，因為B操作是可以判斷當下是否選取的。注意的點是對于 AB操作的次數(shù)，可以把ａｂ當作dfs的參數(shù)，如果不，那就得記得還原現(xiàn)場
#include <bits/stdc++.h>
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;//還原現(xiàn)場，考慮是否對于元素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;
}
如果不剪枝，極其暴力枚舉所有方式，就可以通過得到二進制數(shù)集合
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 費用報銷（不是根據(jù)收據(jù)個數(shù)，而是根據(jù)日期dp)
4 16 3
1 1 1
1 3 2
1 4 4
1 6 8
簡潔版
#include <bits/stdc++.h>
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天之前的所有收據(jù)可以取得的最大金額
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天的條件，一個一個收據(jù)來不行，要根據(jù)日期來選擇
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 <bits/stdc++.h>
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<pii> v;
int v[N];
//map<int,int> v;
int cnt;
int res=0;
int dp[N];//第i天之前的所有收據(jù)可以取得的最大金額
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個收據(jù)，能取得的最大價值
// for(int j=0;j<=mx;j++){
// dp[i][j]+=dp[i-1][j-k]
// }
}
// 因為要滿足相距k天的條件，一個一個收據(jù)來不行，要根據(jù)日期來選擇
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]);
//還要考慮不超過m
dp[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 8
H 機房（最近公共祖先lca）
4 3
1 2
1 3
2 4
2 3
3 4
3 3
正是因為樹有著“不包含回路”這個特點，所以樹就被賦予了很多特性。
1、一棵樹中的任意兩個結(jié)點有且僅有唯一的一條路徑連通。
2、一棵樹如果有n個結(jié)點，那么它一定恰好有n-1條邊。
#include <bits/stdc++.h>
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];//存放鄰接邊
//思路：要求解任意兩個節(jié)點 一路上所經(jīng)歷的所有節(jié)點的延遲總和
//注意n個節(jié)點n-1條邊一定是樹，樹中任意兩個結(jié)點之間的路徑是唯一的
//那么很顯然，就是到達公共祖先那條路
//多組1e5詢問，每次都dfs得到路徑上的所有節(jié)點可能會超時？可以過！??！
//當然也可以用前綴和的思想
int dep[N],fa[N];//存放每個節(jié)點的深度，為尋找公共祖先lca做準備
int pos[N];//每個節(jié)點，從根節(jié)點到該節(jié)點一路上節(jié)點的推遲總數(shù)，類似前綴和
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){//對于任意兩個節(jié)點，先使他們處在同一深度，再往上
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是相等或者直系祖先的關(guān)系，lca本該是深度統(tǒng)一后的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();//postpone
dfs(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 <bits/stdc++.h>
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];//存放鄰接邊
//思路：要求解任意兩個節(jié)點 一路上所經(jīng)歷的所有節(jié)點的延遲總和
//注意n個節(jié)點n-1條邊一定是樹，樹中任意兩個結(jié)點之間的路徑是唯一的
//那么很顯然，就是到達公共祖先那條路
//多組1e5詢問，每次都dfs得到路徑上的所有節(jié)點不太可行？
int dep[N],fa[N];//存放每個節(jié)點的深度，為尋找公共祖先lca做準備
int pos[N];//每個節(jié)點，從根節(jié)點到該節(jié)點一路上節(jié)點的推遲總數(shù)，類似前綴和
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){//對于任意兩個節(jié)點，先使他們處在同一深度，再往上
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();//postpone
dfs(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 3
I 齒輪
要么單獨判斷是否有一對數(shù)是一倍的關(guān)系，要么mp記錄a【i】出現(xiàn)的次數(shù)，如果是一倍且只出現(xiàn)過一次，不計入ans
錯誤
#include <bits/stdc++.h>
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<int,int> 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個數(shù)中，是否存在兩個數(shù)，一個數(shù)是另一個數(shù)的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==倍數(shù))
//有沒有一對數(shù)比值為res
//res<1取倒數(shù)，使得res>=1
//排序
正確
#include <bits/stdc++.h>
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<int,int> 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個數(shù)中，是否存在兩個數(shù)，一個數(shù)是另一個數(shù)的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==倍數(shù))
//有沒有一對數(shù)比值為res
//res<1取倒數(shù)，使得res>=1
//排序
J 搬磚（貪心+01背包）
5
4 4
1 1
5 2
5 5
4 3
大佬思路
我想，單單考慮任意兩塊磚的擺放位置，就是一種局部的貪心最優(yōu)思想，大膽推測局部最優(yōu)導致最優(yōu)！
貪心證明
深刻領會01背包了嗎文章來源：http://www.zghlxwxcb.cn/news/detail-467512.html
#include <bits/stdc++.h>
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);
一定是質(zhì)量輕的盡可能放在上面，同樣質(zhì)量的，價值大的在上
//dp[i][j];//前i個 質(zhì)量為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個物品的最大質(zhì)量是 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時能獲得的最大價值
暴力， 不一定能想出dp
大部分樣例是超時
改變排序方式只會得到更低的分數(shù)文章來源地址http://www.zghlxwxcb.cn/news/detail-467512.html
#include <bits/stdc++.h>
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{
if(w==p.w)return v>p.v;
else return w<p.w;//我只會這樣貪！
// return w+v<p.w<p.v;
}
}a[N];
vector<int> arrange;
int res=0;
void dfs(int u,int start){
if(u==n){
// for(int i=0;i<arrange.size();i++)cout<<arrange[i]<<" ";
// cout<<endl;
// res++;經(jīng)過測試可知，這種暴力枚舉會有重復的，但不是計算種數(shù)而是最大值 不影響
int sum=0;//總重量 前i個的
int ans=0;//最大價值
for(int i=0;i<arrange.size();i++){
if(sum>a[arrange[i]].v)break;//不符條件
sum+=a[arrange[i]].w;
ans+=a[arrange[i]].v;
if(i==arrange.size()-1)res=max(res,ans);
}
return ;
}
dfs(u+1,start);//對于n塊磚,n塊里面選若干塊，方案不得重復
for(int i=start;i<=n;i++){
arrange.push_back(i);
dfs(u+1,i+1);
arrange.pop_back();
}
}
//買我的優(yōu)雅
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d",&a[i].w,&a[i].v);
}
sort(a+1,a+n+1);
//一定是質(zhì)量輕的盡可能放在上面，同樣質(zhì)量的，價值大的在上(我只會這樣貪)
dfs(0,1);
cout<<res;
return 0;
}
//5
//4 4
//1 1
//5 2
//5 5
//4 3
到了這里，關(guān)于十三屆藍橋杯國賽2022的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
