试题 A 幸运数 100
学习:
1.填空题，暴力解，用to_string()整数转换成字符串+(int)字符串转换成整数
代码:
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
ll ans;int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);/*for(int i=1e1;i<1e2;i++){string s=to_string(i);ll cnt1=0,cnt2=0;for(int j=0;j<s.size()/2;j++) cnt1+=(int)s[j];for(int j=s.size()/2;j<s.size();j++) cnt2+=(int)s[j];if(cnt1==cnt2) ans++; }cout<<ans<<endl;for(int i=1e3;i<1e4;i++){string s=to_string(i);ll cnt1=0,cnt2=0;for(int j=0;j<s.size()/2;j++) cnt1+=(int)s[j];for(int j=s.size()/2;j<s.size();j++) cnt2+=(int)s[j];if(cnt1==cnt2) ans++; }cout<<ans<<endl;for(int i=1e5;i<1e6;i++){string s=to_string(i);ll cnt1=0,cnt2=0;for(int j=0;j<s.size()/2;j++) cnt1+=(int)s[j];for(int j=s.size()/2;j<s.size();j++) cnt2+=(int)s[j];if(cnt1==cnt2) ans++; }cout<<ans<<endl;for(ll i=1e7;i<1e8;i++){string s=to_string(i);ll cnt1=0,cnt2=0;for(int j=0;j<s.size()/2;j++) cnt1+=(ll)s[j];for(int j=s.size()/2;j<s.size();j++) cnt2+=(ll)s[j];if(cnt1==cnt2) ans++; }cout<<ans<<endl;*/cout<<4430091;return 0;
}
试题 B 有奖问答 100
学习:
1.基础的二维动态规划，记得初始化dp[0][0]=1,确定最终状态答案，然后判断条件再进行相应的状态转移即可
代码:
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
int dp[35][105]; //到第i道题为止，到第j分为止的方案数
ll ans;int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);/*dp[0][0]=1;for(int i=1;i<=30;i++){for(int j=0;j<=100;j+=10){//答对转移if(j>=10){dp[i][j]=dp[i][j]+dp[i-1][j-10];} //答错转移 if(j==0){for(int k=0;k<=90;k+=10){dp[i][j]=dp[i][j]+dp[i-1][k];}}}}for(int i=1;i<=30;i++){ans+=dp[i][70];}cout<<ans;*/cout<<8335366;return 0;
}
试题 C 平方差 90(需优化)
学习:
1.根据x=y^2-z^2=(y+z)(y-z)，再对y和z分奇偶讨论可以得到x是4的倍数或x是奇数，暴力遍历得到90分
2.优化前缀和参考[[Day9 构造#^e1f1cb|100分平方差]]
试题 D 更小的数 100
学习:
1.想不出来好方法直接暴力，子字符串左右各一个指针向中间移动，判断条件ans++即可
代码:
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
ll ans;
string s;int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);getline(cin,s);int n=s.size();//前i后j for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){//找到s[i]!=s[j] int t1=i,t2=j;while(s[t1]==s[t2] && t1<=t2){t1++;t2--;}if(t1>=t2) continue;//s[t1]>s[t2]if(s[t1]>s[t2]){ans++; } }}cout<<ans;return 0;
}
试题 E 颜色平衡树 70->90(超内存,学习树的基础)
学习:
1.因为颜色数量不确定多少，且N较大，选取vector<map<int,ll>> cnt(n+1);来记录以i为根节点，颜色j的结点个数，记得初始化cnt[i][col[i]]++;
2.注意迭代器没有+1,只有++,且没有<,>，只有!=
//注意这里 it2=++it1，不能写it1+1,所以下面还要再恢复it1 auto it1=cnt[i].begin(),it2=++it1;it1=cnt[i].begin();//有>=2种颜色,判断当前结点是否符合条件 for(;it2!=cnt[i].end();it1++,it2++){
代码:
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=2e5+10;
int father[N]; //第i个结点的父结点
int col[N]; //第i个结点的颜色
bool flag[N]; //是否有子结点
int n;
ll ans;int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;vector<map<int,ll>> cnt(n+1); //记录以i为根节点，颜色j的结点个数for(int i=1;i<=n;i++){cin>>col[i]>>father[i];flag[father[i]]=true;//初始化map cnt[i][col[i]]++;}//倒序更新for(int i=n;i>=1;i--){//除第1个结点外,给父结点加上子结点的颜色个数if(i>1){int fid=father[i]; for(auto &x:cnt[i]){ //x为map<int,ll> cnt[fid][x.first]+=x.second;}} //没有子结点肯定成立if(!flag[i]){ans++;continue;} //就1种颜色肯定成立if(cnt[i].size()==1){ans++;continue;} bool t=true;//注意这里 it2=++it1，不能写it1+1,所以下面还要再恢复it1 auto it1=cnt[i].begin(),it2=++it1;it1=cnt[i].begin();//有>=2种颜色,判断当前结点是否符合条件 for(;it2!=cnt[i].end();it1++,it2++){//有两种颜色数量不同直接breakif(it1->second!=it2->second){t=false;break;} } if(t){ans++;}} cout<<ans;return 0;
}
学习结构体表示树+dfs+子结点颜色数量传递给父结点写法:
1.基础概念:
子树:以某个结点为根结点的树
2.结构体表示树:
struct tree{int c,f;vector<int> child;
}t[N];
3.dfs:
(1)确定输入参数:
第i个结点，以它为根节点的子树
(2)确定返回类型，为了判断颜色平不平衡，向下搜索的目的就是获取子结点各个颜色的数量，即map<int,int>型，故返回这个,因此在dfs中刚开始就得初始化
//初始化return结果map<int,int> cnt
map<int,int> cnt;
//初始化cnt[t[i].c]=1
cnt[t[i].c]=1;
最后return
//返回cnt
return cnt;
(3)确定遍历范围:
遍历第i个结点的子结点，获取他们的map<int,int> cnt,从而更新当前第i个结点的map<int,int> cnt,此题递归中止条件是隐式的，无需判断return,因为遍历完子结点就结束
//遍历子结点
for(auto &x:t[i].child){//获取子结点的map<int,int>auto tmp=dfs(x);//更新父结点的map<int,int> cntfor(auto &[col,num]:tmp){cnt[col]+=num;}
}
学习auto遍历map型:
for(auto &[col,num]:tmp){cnt[col]+=num;
}
(4)更新ans
//判断父结点的cnt来判断是不是颜色平衡树，从而更新ans
//其中一个颜色的数量作为基准
int sum=cnt[t[i].c];
bool flag=true;
for(auto &[col,num]:cnt){if(num!=sum){flag=false;break;}
}
if(flag) ans++;
代码:
#include <bits/stdc++.h>using namespace std;
const int N=2e5+10;
int ans,n;//结构体树
struct tree{int c,f;vector<int> child;
}t[N]; //参数为第i个结点，返回map<int,int>,<颜色id，数量>
map<int,int> dfs(int i){//初始化return结果map<int,int> cntmap<int,int> cnt;//初始化cnt[t[i].c]=1cnt[t[i].c]=1;//遍历子结点for(auto &x:t[i].child){//获取子结点的map<int,int>auto tmp=dfs(x);//更新父结点的map<int,int> cntfor(auto &[col,num]:tmp){cnt[col]+=num;} } //判断父结点的cnt来判断是不是颜色平衡树，从而更新ans//其中一个颜色的数量作为基准 int sum=cnt[t[i].c]; bool flag=true;for(auto &[col,num]:cnt){if(num!=sum){flag=false;break;}}if(flag) ans++;//返回cntreturn cnt;
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>t[i].c>>t[i].f;if(t[i].f!=0) t[t[i].f].child.emplace_back(i);}//dfs第i个结点对应的子树，更新第i个结点的颜色dfs(1); cout<<ans;return 0;
}
试题 F 买瓜 10->100(dfs还得练)
尽量不要用恢复现场的那种dfs，用剪枝+记忆化
学习:
(1)三种情况搜索:
1不买当前的瓜
2劈一半
3买一整个瓜
(2)确定dfs参数,dfs(当前买到的瓜总重量，第i个瓜，劈瓜次数)
(3)递归结束条件:
i>=n || s>=m || s+sum[i]<m return
(4)更新答案:
if(s=m) ans=min(ans,cnt)
(4)剪枝(最开始):
cnt>=ans return
(5)优化:
1.因为有一半，所有一开始全乘以2，避免小数
2.对重量降序排列，且用sum数组记录i-最后瓜的重量，如果s+sum[i]<m,直接return
(6)对ans判断，进行结果输出
代码:
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=35;
ll a[N],m,sum[N];//要乘2和要加，开long long
int n,ans=50; //ans不会超过30，最小值开大数 //s:总重量，i:序号,cnt:劈瓜次数
void dfs(ll s,int i,int cnt){//剪枝if(ans<=cnt) return;//更新答案if(s==m) ans=min(ans,cnt);//递归结束if(i>n || s>=m || s+sum[i]<m) return;//继续dfs//不买 dfs(s,i+1,cnt); //买，不劈dfs(s+a[i],i+1,cnt); //买，劈dfs(s+a[i]/2,i+1,cnt+1);
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;//乘2 m<<=1;for(int i=1;i<=n;i++){cin>>a[i];a[i]<<=1;}//排序 sort(a+1,a+1+n,greater<int>());//算i-n瓜的重量和for(int i=n;i>=1;i--){sum[i]=sum[i+1]+a[i]; //sum[n+1]=0} //dfsdfs(0,1,0);if(ans==50) cout<<-1;else cout<<ans;return 0;
}
加练:
[[Day 19 加练dfs]]
试题 G 网络稳定性 0->40->70(学一下基础图论)
1.暴力floyd得了40分，N开5010
代码:
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=5010;
ll dp[N][N]; //i-j之间的稳定性
int n,m,q; int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m>>q;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){//初始化 if(i!=j) dp[i][j]=-1;}}for(int i=1;i<=m;i++){int u,v;ll w;cin>>u>>v>>w;//u-v有多条路，取稳定性最高的 dp[u][v]=max(dp[u][v],w);dp[v][u]=max(dp[v][u],w);}//floydfor(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){//i-k-j比i-j好，说明min(dp[i][k],dp[k][j])>dp[i][j]if(min(dp[i][k],dp[k][j])>dp[i][j]){dp[i][j]=min(dp[i][k],dp[k][j]);} }}}while(q--){int x,y;cin>>x>>y;cout<<dp[x][y]<<endl;}return 0;
}
70分:kruskal最大生成树+dfs
1.此题比较综合，因为定义这条路径的稳定性为其经过所有连接中稳定性最低的那个，要让最低值尽量大，且能连接所有结点，考虑构建最大生成树(利用最小生成树的性质:最大边权是所有生成树中最小的,这里是最小边权是所有生成树中最大的),利用kruskal+并查集构建最大生成树，然后要找树中两个结点的路径，然后更新稳定性，就是基本的DFS遍历树即可
代码:
#include <bits/stdc++.h>using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
struct Edge{int u,v,w;Edge(int tu,int tv,int tw):u(tu),v(tv),w(tw){}//用vector，先取出边权最大的，所以按边权降序bool operator<(const Edge &e)const{return w>e.w;}
};
int n,m,q;
int pre[N]; //父亲,用于并查集
vector<Edge> es; //边数组
vector<PII> g[N]; //最大生成树的邻接表 //找根
int root(int x){if(pre[x]==x) return x;pre[x]=root(pre[x]);return pre[x];
}//构建最大生成树
void kruskal(){//遍历边for(const auto &e:es){//连通则跳过if(root(e.u)==root(e.v)) continue;//不连通则连通 pre[root(e.u)]=root(e.v);g[e.u].emplace_back(e.v,e.w);g[e.v].emplace_back(e.u,e.w);}
}//dfs,x为当前搜索结点，y为目标结点,tmp为当前路径稳定性的最低值
void dfs(int x,int f,const int &y,int &ans,int tmp){//递归结束 if(x==y){ans=tmp;return;}//遍历儿子for(const auto &child:g[x]){if(child.first==f) continue;dfs(child.first,x,y,ans,min(tmp,child.second));}
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m>>q;//初始化pre for(int i=1;i<=n;i++) pre[i]=i;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;es.emplace_back(u,v,w);}//es按边权升序sort(es.begin(),es.end());//变成最大生成树kruskal(); while(q--){int x,y;cin>>x>>y;//并查集查是否有路径 if(root(x)!=root(y)){cout<<-1<<endl;continue;}//dfs遍历最大生成树 int ans=0;dfs(x,0,y,ans,1e9);cout<<ans<<endl;}return 0;
}
试题 H 异或和之和 90(优化)
学习:
1.求[l,r]的异或和，联系前缀和，以及异或的运算性质，可以参考前缀和求pre数组，得到区间异或和pre[r]^pre[l-1]
代码:
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=1e5+10;
int a[N],n;
ll pre[N],ans;//1-i异或和 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){pre[i]=pre[i-1]^a[i]; //0^a[i]=a[i]}for(int l=1;l<=n;l++){for(int r=l;r<=n;r++){ans+=pre[r]^pre[l-1]; //l-r异或和 }}cout<<ans;return 0;
}
试题 I 像素放置 0->100(dfs还得练)
学习:
1.典型的DFS放东西
2.选取遍历顺序，从左到右，从上到下放
3.每放置一个，会对之前已经放完的左方，左上方和上方产生影响，而check函数的逻辑是判断是不是等于数字，所以一定要保证判断的(x,y)此时的九宫格都已经放完
4.所有根据上述逻辑，左方不用判断，左上方必判断，而上方只有在最后一列再判断(因为右侧没有了),同时最后一列也正好换行，需要单独判断
5.判断左上方和上方涉及x-1和y-1，因此需要单独判断x==1或者y==1
6.考验基本代码功底
代码:
#include <bits/stdc++.h>using namespace std;
//地图
char mp[12][12];
//结果
int ans[12][12];
int n,m; //检查九宫格是否符合要求(此时x,y的九宫格已经填完)
bool check(int x,int y){//_跳过if(mp[x][y]=='_') return true;int cnt=0;//默认是0 for(int i=-1;i<=1;i++){for(int j=-1;j<=1;j++){cnt+=ans[x+i][y+j];}} //符合要求(一定是等于) if(cnt==mp[x][y]-'0') return true;//不符合要求return false;
} //从左到右，从上到下遍历
void dfs(int x,int y){//结束if(x==n+1){//看最后1行行不行for(int j=1;j<=m;j++){//不满足条件回溯 if(!check(n,j)) return;} //满足条件输出结果for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<ans[i][j];}cout<<endl;} return;} //最后一列要换行if(y==m){ //放置该棋子会对上方，左上方和左方产生影响，但是最后一列只有上方和左上方都已经填完九宫格,需检查//放0ans[x][y]=0; //x=1无上方和左上方，y=1无左上方 if( x==1 || ( y==1 && check(x-1,y) ) || ( check(x-1,y-1) && check(x-1,y) ) ){//能放置继续DFS,换行 dfs(x+1,1); }//0不行则放1ans[x][y]=1; if( x==1 || ( y==1 && check(x-1,y) ) || ( check(x-1,y-1) && check(x-1,y) ) ){//能放置继续DFS,换行 dfs(x+1,1); } }//不是最后一列 else{//放置该棋子会对上方，左上方和左方产生影响，但是不是最后一列只有左上方填完九宫格，需检查 //放0ans[x][y]=0; //x=1无上方和左上方，y=1无左上方 if( x==1 || y==1 || check(x-1,y-1) ){//能放置继续DFS dfs(x,y+1); }//0不行则放1ans[x][y]=1; if( x==1 || y==1 || check(x-1,y-1) ){//能放置继续DFS dfs(x,y+1); } }
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>mp[i][j];}}//开始填充 dfs(1,1);return 0;
}
试题 J 翻转硬币 5->15(太难放弃，用最小值1得到5分)
学习:
1.15分暴力枚举
2.理解暴力逻辑
(1)因为选取一次操作数i，使得满足 jmodi=0 的位置 j 的硬币翻转。所有就是看用了几个操作数i，即操作数i用或不用(用两次就等于不用),i从1-n,所以操作组合mask共有1-2^n-1次方种可能,然后暴力枚举即可，需要用到右移+&得到1
代码:
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
ll n;int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;ll ans=1e18;//枚举操作组合,[1,2^n-1)for(ll mask=1;mask<(1<<n);mask++){//硬币状态vector<bool> coins(n+1,false);//第一个硬币朝下coins[1]=true; //当前操作组合的总操作次数(共有几个1)ll cnt=0;//模拟翻硬币for(int i=1;i<=n;i++){//选取i,即右移i-1位，最低位是1 if((mask>>(i-1))&1){cnt++;//jmodi==0翻转 for(int j=i;j<=n;j+=i){coins[j]=!coins[j];}}}//判断经过当前操作组合硬币是否都朝上 bool allUp=true;for(int i=1;i<=n;i++){if(coins[i]){allUp=false;break;}}if(allUp){ans=min(ans,cnt);}} cout<<ans;return 0;
}
_今日的最新消息_长沙官网seo收费标准)
