首先今天参加的考试，也不知道对不对，但是也不会改了。拿出来就是分享一下。wa了别怪我哈。嘻嘻~~~~~~
第一题求相邻两数的最大差的绝对值
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 10000
int num[maxn];
int main(){
int n;
scanf("%d",&n);
int ans = 0;
for(int i = 0;i < n; i++){
scanf("%d",&num[i]);
}
for(int i = 1;i < n; i++){
ans = max(ans,abs(num[i]-num[i-1]));
}
printf("%d\n",ans);
return 0;
}
第二题；模拟火车票售票，
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int num[1000];
int total[200];
int main(){
int n,u;
for(int i = 1;i <= 100 ;i++)
num[i] = total[i] = 0;
cin>>n;
for(int i = 0;i < n; i++){
vector<int>ans;
cin>>u;
int flag = 0;
for(int j = 1;j <= 20; j++){
if(5 - total[j] >= u){
flag = j;
break;
}
}
if(flag > 0){
for(int j = 1;j <= u; j++){
ans.push_back(5*flag-5+j+total[flag]);
}
}
else {
for(int j = 1;j <= 100 && ans.size() < u;j++){
if(num[j] == 0)
ans.push_back(j);
}
}
for(int j = 0;j < ans.size(); j++){
if(j > 0)printf(" ");
cout<<ans[j];
num[ans[j]] = 1;
int v = ans[j]-1;
total[1+v/5]++;
}
cout<<endl;
}
return 0;
}
第三题：还是模拟题
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
struct Node{
int health,attack;
Node(){
}
Node(int h,int a){
health = h;
attack = a;
}
};
struct Role{
Node card[10];
int health;
int num;
Role(){}
};
void add(Role &x,Node b,int p){
x.num++;
for(int i = x.num; i > p; i--)
x.card[i] = x.card[i-1];
x.card[p] = b;
}
void del(Role &x,int p,int d){
x.card[p].health -= d;
if(x.card[p].health <= 0){
for(int i = p;i < x.num; i++)
x.card[i] = x.card[i+1];
x.num--;
}
}
int main(){
Role role[2];
string ope;
int p,a,h,d;
role[0].health = role[1].health = 30;
role[0].num = role[1].num = 0;
int n,now=0;
cin>>n;
while(n--){
cin>>ope;
if(ope == "summon"){
cin>>p>>a>>h;
add(role[now],Node(h,a),p);
}
else if(ope == "attack"){
cin>>a>>d;
if(d == 0){
role[now^1].health -= role[now].card[a].attack;
}
else{
int x1 = role[now].card[a].attack;
int x2 = role[now^1].card[d].attack;
del(role[now],a,x2);
del(role[now^1],d,x1);
}
}
else if(ope == "end"){
now ^= 1;
}
}
if(role[0].health <= 0) cout<<-1<<endl;
else if(role[1].health <= 0)cout<<1<<endl;
else cout<<0<<endl;
cout<<role[0].health<<endl;
cout<<role[0].num;
for(int i = 1;i <= role[0].num; i++)
cout<<" "<<role[0].card[i].health;
cout<<endl;
cout<<role[1].health<<endl;
cout<<role[1].num;
for(int i = 1;i <= role[1].num; i++)
cout<<" "<<role[1].card[i].health;
cout<<endl;
return 0;
}
第四题：求到起点的满足最短路径的最小生成树
我的做法是求最短路，然后在这个过程，满足最短路的情况下，为每个点选择最小的边作为到达该点的路径。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<set>
using namespace std;
#define maxn 10007
struct Node{
int v,c;
Node(){}
Node(int vv,int cc){
v = vv;
c = cc;
}
};
vector<Node> head[maxn];
int dist[maxn];
int cost[maxn];
int flag[maxn];
bool operator < (Node a,Node b){
if(a.c == b.c) return a.v < b.v;
return a.c < b.c;
}
int dif(int s,int n){
memset(flag,0,sizeof(flag));
dist[s] = 0;
cost[s] = 0;
Node be,en;
be.v = s;
be.c = 0;
set<Node> haha;
haha.insert(be);
while(haha.size() > 0){
be = *haha.begin();
haha.erase(haha.begin());
if(flag[be.v]) continue;
flag[be.v] = 1;
for(int i = 0;i < head[be.v].size(); i++){
en.v = head[be.v][i].v;
en.c = be.c + head[be.v][i].c;
if(flag[en.v] == 0 && dist[en.v] >= en.c){
dist[en.v] = en.c;
haha.insert(en);
cost[en.v] = min(cost[en.v],head[be.v][i].c);
}
}
}
int ans = 0;
for(int i = 1;i <= n; i++)
ans += cost[i];
return ans;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1;i <= n; i++)
head[i].clear();
for(int i = 1;i <= n; i++)
cost[i] = dist[i] = 10000007;
int u,v,c;
for(int i = 0;i < m; i++){
scanf("%d%d%d",&u,&v,&c);
head[u].push_back(Node(v,c));
head[v].push_back(Node(u,c));
}
cout<<dif(1,n)<<endl;
return 0;
}
第五题：四边形满足以下条件，对角线与x,y平行，交点位置不能存在输入的点。四边形可以存在包含关系，
求能包含的最大层数。或者求包含最大层数的情况数。
60%的小数据课可以n^2暴力过的。
然后求最大的可以n*logn过的。
求情况数不会，主要还没想清楚求区间大于某一个数的数字个数。当时没想到，也想错了。
我的思路：离散化，保留坐标的相对大小不影响结果。然后y轴每条直线建立一个集合，
然后从下到上扫描。想通一件事就行，任何一点能镶嵌的最大层数是这个点上、下、左、右
方向上点数最小的那个值。所以用线段树维护区间最值就行了。
</pre><pre>
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<vector>#include<set>#include<map>using namespace std;#define maxn 2000007struct Point {int x,y;Point(){}};struct Node{int num,v,c;Node(){}};#define maxv 500007Point point[maxv];vector<int> headx[maxv];vector<int> heady[maxv];Node node[maxn];//初始化线段树void build(int root,int l,int r){node[root].num = 0;node[root].v = 0;node[root].c = 0;if(l == r){node[root].num = 1;return ;}int mid = (l+r)/2;build(root*2+1,l,mid);build(root*2+2,mid+1,r);}//获取区间内得到层数最大值以及情况数Node get(int root,int l,int r,int L,int R,int lim){if(r < l){Node a;a.v = 0;a.num = 0;return a;}if(l == L && R == r){Node a = node[root];if(a.v > lim) a.v = lim;return a;}int mid = (L+R)/2;if(mid >= r) {Node a = get(root*2+1,l,r,L,mid,lim);a.v = min(a.v,lim);return a;}else if(mid < l) {Node a = get(root*2+2,l,r,mid+1,R,lim);a.v = min(a.v,lim);return a;}else {Node a = get(root*2+1,l,mid,L,mid,lim);Node b = get(root*2+2,mid+1,r,mid+1,R,lim);if(a.v == b.v){a.num += b.num;}else if(a.v < b.v){a = b;}return a;}}//更新线段树，加入新点int maxAns = 10000000; //取一个最大值第一次执行算法的时候是不会有影响的void add(int root,int p,int L,int R){if(L == R){node[root].c ++;node[root].num = 1;node[root].v = min(node[root].c,(int)headx[L].size()-node[root].c);/*node[root].v = min(node[root].v,maxAns);//此处为求第二问新加的*/return ;}int mid = (L+R)/2;if(p <= mid) add(root*2+1,p,L,mid);else add(root*2+2,p,mid+1,R);Node a = node[root*2+1];Node b = node[root*2+2];if(a.v == b.v) a.num += b.num;else if(a.v < b.v) a = b;node[root] = a;}int main(){int n,q;scanf("%d%d",&n,&q);map<int,int>mapx;map<int,int>mapy;for(int i = 0;i < n; i++){scanf("%d%d",&point[i].x,&point[i].y);mapx[point[i].x] = 0;mapy[point[i].y] = 0;}int cntx = 0,cnty = 0;map<int,int>::iterator it;for(it = mapx.begin(); it != mapx.end(); it++){it->second = cntx++;}for(it = mapy.begin(); it != mapy.end(); it++){it->second = cnty++;}int x,y;for(int i = 0;i < n; i++){x = point[i].x = mapx[point[i].x];y = point[i].y = mapy[point[i].y];headx[x].push_back(y);heady[y].push_back(x);}map<int,int> ans;build(0,0,cntx-1);for(int i = 0;i < cnty; i++){sort(heady[i].begin(),heady[i].end());for(int j = 1;j < heady[i].size(); j++){Node p = get(0,heady[i][j-1]+1,heady[i][j]-1,0,cntx-1,min(j,(int)heady[i].size()-j));ans[p.v] += p.num;}for(int j = 0;j < heady[i].size(); j++){add(0,heady[i][j],0,cntx-1);}}it = ans.end();it--;if(q == 1){cout<<it->first<<endl;}else{ /* 这段代码新加的用来求第二问的 maxAns = it->first; ans.clear(); build(0,0,cntx-1); for(int i = 0;i < cnty; i++){ sort(heady[i].begin(),heady[i].end()); for(int j = 1;j < heady[i].size(); j++){ Node p = get(0,heady[i][j-1]+1,heady[i][j]-1,0,cntx-1,min(j,(int)heady[i].size()-j)); ans[p.v] += p.num; } for(int j = 0;j < heady[i].size(); j++){ add(0,heady[i][j],0,cntx-1); } } it = ans.end(); it--; */cout<<it->second<<endl;}return 0;}
=================================2016年9月14日更新
今天收到电子证书0.28%,大概15名吧。有满分的，也在预料之中！只怪当时太自信，没有想清楚问题。
前四题100，第五题40分。数据说了50%是求最值，我感觉能拿450的，复杂度是没问题的，具体就不深究哪里错了了。
对于第五题的第二问，我已经想好了处理方法了。看评论这么多，我就更新一下代码了
先求出最大值，然后知道最大值maxv以后，重新计算一遍，此时的目标是求数量。
方法是对于线段树中记录的v值球min（v,maxv）.这样就能把最大值都统计出来，并且不用担心少算了。
对于第四题错误的同学，我想用邻接表或者vector是不会爆内存的。请考虑一下问题
1. if(flag[be.v]) continue; 这个判断添加了吗 这个是为了防止计算cost得到偏小值
2.if(flag[en.v] == 0 && dist[en.v] >= en.c) 这个判断呢 = 号是必须加的哦。