目录
1112 Stucked Keyboard （20 分）（字符串模拟）
1113 Integer Set Partition （25 分）（排序）
1114 Family Property （25 分）（并查集）
1115 Counting Nodes in a BST （30 分）（二叉搜索树）
1112 Stucked Keyboard （20 分）（字符串模拟）
【题意】求键盘上坏掉的键并输出本来要输出的串
【分析】先把坏掉的键存起来，然后遍历字符串边遍历边判断并输出（注意空格是可以坏掉的！！）
【代码】
#include<bits/stdc++.h>
using namespace std;vector<int>v[40];
vector<char>vv;
int book[40];int main()
{int k;scanf("%d",&k);string s;cin>>s;int len=s.length();char c;int cnt=0;c=s[0];int num=1;for(int i=1;i<=len;++i){num=1;while(c==s[i] && i<len)num++,i++;if(isdigit(c))v[c-'0'+26].push_back(num);else if(isalpha(c))v[c-'a'].push_back(num);else v[36].push_back(num);c=s[i]; }memset(book,0,sizeof(book));for(int i=0;i<len;++i){int f=1,x;if(s[i]=='_')x=36;else x=(isdigit(s[i]))?(s[i]-'0'+26):(s[i]-'a');if(book[x])continue;for(int j=0;j<v[x].size();++j){if(v[x][j]!=0 && v[x][j]%k!=0){f=0;break;}}if(f)vv.push_back(s[i]),book[x]=1;}
// cout<<vv.size()<<endl;int vis[300];memset(vis,0,sizeof(vis));int t=0;for(int i=0;i<vv.size();++i){t=1;printf("%c",vv[i]);vis[vv[i]]=1;}if(t)puts("");for(int i=0;i<len;++i){int num=0;while(vis[s[i]]==1){num++;i++;if(num%k==0)printf("%c",s[i-1]);}printf("%c",s[i]);}puts("");
}1113 Integer Set Partition （25 分）（排序）
【分析】把一个序列尽可能平均分成两个序列，求长度与和之差的绝对值
【代码】
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
const int maxn=1e5+10;
int a[maxn];int main()
{int n;scanf("%d",&n);ll sum=0;for(int i=0;i<n;++i){scanf("%d",&a[i]);sum+=a[i];}sort(a,a+n);int x=n/2;int y=n-x;int sum1=0,sum2=0;for(int i=0;i<x;++i)sum1+=a[i];sum2=sum-sum1;printf("%d %d\n",(n&1)?1:0,abs(sum1-sum2));
}1114 Family Property （25 分）（并查集）
【题意】求每个家族的平均拥有的房产数和人均房产数
【分析】并查集。将有关系的人放在一起，注意join时要分情况讨论
#include<bits/stdc++.h>
using namespace std;const int maxn=1e4+10;
struct node{int id;int sets,areas;double avg_a,avg_s;int num;int f=0;
}a[maxn],b[maxn];
bool cmp(node x,node y){return x.avg_a!=y.avg_a?x.avg_a>y.avg_a:x.id<y.id;}
int vis[maxn];
int pre[maxn];int find(int x)
{while(x!=pre[x])x=pre[x];return x;
}
void join(int x,int y)
{int fx=find(x),fy=find(y);if(fx<fy)pre[fy]=fx;else if(fx>fy)pre[fx]=fy;
}
int main()
{int n;scanf("%d",&n);memset(vis,0,sizeof(pre));for(int i=0;i<maxn;++i)pre[i]=i;for(int i=0;i<n;++i){int id,fa,ma,k;scanf("%d%d%d%d",&id,&fa,&ma,&k);a[i].id=id;vis[id]=1;if(fa!=-1)vis[fa]=1,join(id,fa);if(ma!=-1)vis[ma]=1,join(id,ma);for(int i=0;i<k;++i){int x;scanf("%d",&x);vis[x]=1;join(x,id);}scanf("%d%d",&a[i].sets,&a[i].areas);}for(int i=0;i<n;++i){int x=find(a[i].id);b[x].id=x;b[x].sets+=a[i].sets;b[x].areas+=a[i].areas;b[x].f=1;}int cnt=0;for(int i=0;i<maxn;++i){if(vis[i])b[find(i)].num++;if(b[i].f)cnt++;}for(int i=0;i<maxn;++i){if(b[i].f){b[i].avg_s=b[i].sets*1.0/b[i].num;b[i].avg_a=b[i].areas*1.0/b[i].num;}}sort(b,b+maxn,cmp);printf("%d\n",cnt);for(int i=0;i<cnt;++i)printf("%04d %d %.3lf %.3lf\n",b[i].id,b[i].num,b[i].avg_s,b[i].avg_a);}1115 Counting Nodes in a BST （30 分）（二叉搜索树）
【题意】建立一棵二叉搜索树并输出最后两层的节点数及和
【分析】注意题上给出的BST的定义
【代码】
#include<bits/stdc++.h>
using namespace std;const int maxn=1e3+10;
typedef struct node{struct node *lchild;struct node *rchild;int val;
}node,*tree;int n1,n2;void build(tree &T,int x)
{if(T==NULL){T=new node();T->val=x;T->lchild=T->rchild=NULL;return;}if(x<=T->val)build(T->lchild,x);else if(x>T->val)build(T->rchild,x);
}
void getLevel(tree &T)
{queue<tree>q;q.push(T);while(!q.empty()){n2=n1;n1=q.size();for(int i=0;i<n1;++i){tree t=q.front();q.pop();if(t->lchild!=NULL)q.push(t->lchild);if(t->rchild!=NULL)q.push(t->rchild);}}
}
int main()
{int n;scanf("%d",&n);tree T=NULL;for(int i=0;i<n;++i){int x;scanf("%d",&x);build(T,x);}n1=n2=0;getLevel(T);printf("%d + %d = %d\n",n1,n2,n1+n2);
}