目录
1065 A+B and C (64bit) （20 分）（巧用溢出概念）
1066 Root of AVL Tree （25 分）（平衡二叉树裸题）
1067 Sort with Swap(0, i) （25 分）（我觉得它是连通图）
1068 Find More Coins （30 分）（01背包）
1065 A+B and C (64bit) （20 分）（巧用溢出概念）
【题意】给你三个数a,b,c，问a+b>c？
【分析】64位，所以用long long。分几种情况：
- 两数均正，和为负，溢出，则必满足
- 两数均负和为正，溢出，不满足
- 未溢出，则正常的长整型运算，比较即可
【代码】
#include<bits/stdc++.h>
using namespace std;typedef long long ll;int main()
{int t;scanf("%d",&t);int ca=0;while(t--){ll a,b,c;scanf("%lld%lld%lld",&a,&b,&c);int f;ll sum=a+b;if(a>0 && b>0 && sum<=0)f=1;else if(a<0 && b<0 && sum>=0)f=0;else if(sum>c)f=1;else f=0;printf("Case #%d: ",++ca);if(!f)puts("false");else puts("true");}
}1066 Root of AVL Tree （25 分）（平衡二叉树裸题）
【题意】建立平衡二叉树，输出根节点
【代码】
#include<bits/stdc++.h>
using namespace std;typedef struct node{struct node *lchild;struct node *rchild;int val,height;
}*tree,node;int getHeight(tree &T)
{if(T==NULL)return -1;return T->height;
}
void R(tree &T)
{tree L=T->lchild;T->lchild=L->rchild;L->rchild=T;T->height=max(getHeight(T->lchild),getHeight(T->rchild))+1;L->height=max(getHeight(L->lchild),getHeight(L->rchild))+1;T=L;
}
void L(tree &T)
{tree R=T->rchild;T->rchild=R->lchild;R->lchild=T;T->height=max(getHeight(T->lchild),getHeight(T->rchild))+1;R->height=max(getHeight(R->lchild),getHeight(R->rchild))+1;T=R;
}
void LR(tree &T)
{L(T->lchild);R(T);
}
tree RL(tree &T)
{R(T->rchild);L(T);
}
void insert(tree &T,int x)
{if(T==NULL) {T=new node;T->val=x;T->lchild=T->rchild=NULL;T->height=0;}else if(x<T->val) {insert(T->lchild,x);if(getHeight(T->lchild)-getHeight(T->rchild)==2) {if(x<T->lchild->val) R(T);else LR(T);}}else if(x>T->val){insert(T->rchild,x);if(getHeight(T->rchild)-getHeight(T->lchild)==2){if(x>T->rchild->val) L(T);else RL(T);}}T->height=max(getHeight(T->lchild),getHeight(T->rchild))+1;
}
int main()
{tree T=NULL;int n;scanf("%d",&n);for(int i=0;i<n;++i){int x;scanf("%d",&x);insert(T,x);}cout<<T->val<<endl;return 0;
}1067 Sort with Swap(0, i) （25 分）（我觉得它是连通图）
【题意】给你一个序列，每次只能与0互换，求使得各个位置的下标与值相等最少需要的步数
【分析】对于序列中的每个数，有一个数对，(值，下标)，那么根据这个来进行图的连通。在根据0是否在连通块中以及所在连通块的个数来求得
【代码】
#include<bits/stdc++.h>
using namespace std;const int maxn=1e5+10;
int a[maxn],vis[maxn];
int n;int main()
{memset(vis,0,sizeof(vis));scanf("%d",&n);for(int i=0;i<n;++i){int x;scanf("%d",&x);a[x]=i;}vector<int>v;int cnt=0,now=0,f=0,num=0;for(int now=0;now<n;++now){if(vis[now])continue;cnt=0;while(!vis[now] && a[now]!=now){vis[now]=1;now=a[now];cnt++;}// cout<<cnt<<endl;if(cnt)v.push_back(cnt);if(now==0){if(cnt==0)f=1;else num++; }}int sum=0;
// cout<<"size="<<v.size()<<endl;for(int i=0;i<v.size();++i)sum+=v[i];//cout<<sum<<endl;if(f==1)sum+=v.size();else sum=sum-num+v.size()-num;printf("%d\n",sum);
}1068 Find More Coins （30 分）（01背包）
【题意】用拥有的硬币凑成给定的面值且输出最小序列（序列尽可能长）
【分析】
- 01背包求dp[]数组，然后利用choice数组遍历获得ans数组
- dp[i]：容量为i时，可以凑成的最大面值
- choice[i][j]：第i个物品在容量为j时是否被选择
- ans[i]：存答案
【代码】
#include<bits/stdc++.h>
using namespace std;const int maxn=1e4+10;
int dp[maxn];//容量为i时最大值
int choice[maxn][110];//第i个物品在容量为j时是否被选择
int ans[maxn];
int a[maxn];bool cmp(int x,int y){ return x>y; }int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;++i)scanf("%d",&a[i]);sort(a,a+n,cmp);dp[0]=0;for(int i=0;i<n;++i)for(int j=m;j>=a[i];--j)if(dp[j]<=dp[j-a[i]]+a[i])//注意有等号！！{dp[j]=dp[j-a[i]]+a[i];choice[i][j]=1;}if(dp[m]!=m)puts("No Solution");else{int cnt=0;for(int i=n-1;i>=0;--i){if(choice[i][m])ans[cnt++]=a[i],m-=a[i];if(m<=0)break;}for(int i=0;i<cnt;++i)(i==cnt-1)?printf("%d\n",ans[i]):printf("%d ",ans[i]);}} 小结：
- 要巧用概念来解决问题，第一题一开始就用字符串来写然后写了半天写不出来…？？
- 模板还是要记记，今天又做到平衡二叉树
- 转换思维呀 第三题转换成图还是挺好做的呀(毕竟自己推了好一会呢！)
- 贪心问题又忘了…之前明明整理过的，01背包却又理解好半天，第4题还是搞了很久