首先今天參加的考試，也不知道對不對，但是也不會改了。拿出來就是分享一下。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 2000007
struct Point {
int x,y;
Point(){
}
};
struct Node{
int num,v,c;
Node(){
}
};
#define maxv 500007
Point 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) 這個判斷呢 = 号是必須加的哦。
![201903-1小中大[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)