第一题：守卫(guard)
有n（2<=n<=20）头奶牛在玩飞盘，可是飞盘飞到了高处。现在他们要想办法叠在一起，去取飞盘。飞盘的高度为H（1 <= H <= 1,000,000,000）。给出每头奶牛的重量、高度、强壮度（能够承受的重量），问他们是否够得到，如果能够取到，求它们额外还能承受最多多少重量。（要保证每头奶牛所承受的重量都不超过它的强壮度）。
输入格式：
第一行包含N和H。
接下来N行，每行三个数，分别表示它的高度、重量和强壮度。所有的数都为正整数。
输出格式：
如果奶牛的队伍可以够到飞盘，输出还能承受的最大额外重量；否则输出“Mark is too tall”.
成绩：AC(qwq)
题解：把奶牛按“体重+承重”从大到小排序，然后dfs，每头奶牛上面只能放“体重+承重”比它小的奶牛。
证明：（W表示放在奶牛A,B上的总重）
A在上：ans=min(strong[A]-W,strong[B]-w[A]-W);
B在上：ans=min(strong[B]-W,strong[A]-w[B]-W);
若ansA>ansB：移项=>stron[A]+w[A]>strong[B]+w[B];
分析：以前做过的原题，勉强还记得搜索，按着这个方向，虽然想（回忆）了半天，最后也凭着记忆推出来了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;
const long long inf=0x3f3f3f3f;
inline void getint(long long&num){
char c;long long flag=1;num=0;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
num*=flag;
}
struct node{
long long w,h,s,ws;
bool operator < (const node &x)const{
return ws>x.ws;
}
}cow[25];
long long n,H,ans=-inf,way[25];
bool vis[25];
void dfs(long long now,long long hight,long long cnt){
if(hight>=H){
long long Min=inf;
for(long long i=1;i<=cnt;i++)
Min=min(Min-cow[way[i]].w,cow[way[i]].s);
ans=max(ans,Min);
}
else
for(long long i=now;i<=n;i++)
if(!vis[i]){
vis[i]=1,way[cnt+1]=i;
dfs(i+1,hight+cow[i].h,cnt+1),vis[i]=0;
}
}
int main(){
//freopen("guard.in","r",stdin);
//freopen("guard.out","w",stdout);
getint(n),getint(H);
for(int i=1;i<=n;i++){
getint(cow[i].h),getint(cow[i].w),getint(cow[i].s);
cow[i].ws=cow[i].w+cow[i].s;
}
sort(cow+1,cow+n+1);
dfs(1,0,0);
if(ans>0) printf("%lld\n",ans);
else printf("Mark is too tall\n");
}
第二题：马拉松比赛（marathon）
奶牛贝西给他的小伙伴设计了一条马拉松比赛的线路。这条线路上一共有n(n<=100000)个点，它们分布在一个平面坐标系中。它的小伙伴毅力不够，所以不能跑完全程，于是贝西给他们安排了一条子线路（它是一段连续的点，比如设定子线路为【i，j】,表示奶牛需要从点i开始，经过点i+1，点i+2，……，最后到点j）。即使这样，奶牛们仍然可能跳过中间某个点以节省路程，当然这个点不能是子线路的起点或终点。现在，有Q(Q<100000)个操作：操作分为两种，第一种为”U I X Y”，表示将点I的位置设在坐标（X,Y）处；第二种为QI J，表示设定子线路为点i到点j，需要查询奶牛们从i跑到j的最短路程。（路程是以曼哈顿距离计算的）他们可以跳过中间某个点。
所有的坐标值x,y均在[-1000,+1000]区间。
输入：
第一行包含N和Q。接下来N行，每行两个数（X,Y），表示每个点的坐标，按照编号从小到大的顺序给出。
接下来Q行，每行表示一个操作。操作如上所述。
输出：对于每一次查询，输出一个整数，表示该子线路的最短路程（曼哈顿距离）。
成绩：根本没写(TAT)
题解：一个dis数组，dis[i][0]表示i到i+1的距离,dis[i][1]表示i到i+2的距离，一颗线段树维护l到r中最大的dis[i][0]+dis[i+1][0]-dis[i][1]，一颗线段树维护l到r不跳过点的距离。
分析：下午考的时候第一遍看没什么思路，就跳过了，结果晚自习回来再看突然灵光乍现2333333333333，然后又把曼哈顿距离搞错了2333333
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<stack>
#include<algorithm>
#include<vector>
#define lson num<<1
#define rson num<<1|1
using namespace std;
const int N=100000+10;
inline void getint(int&num){
char c;int flag=1;num=0;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
num*=flag;
}
struct node{
int x,y;
}point[N];
struct T1{
int l,r,Max;
}tree[N<<2];
struct T2{
int l,r,sum;
}sum[N<<2];
int n,T,pos,x,y,l,r,dis[N][2];
int cut,ans;
char op[3];
int abs(int x){
return x>0?x:-x;
}
int Dist(int i,int j){
return abs(point[i].x-point[j].x)+abs(point[i].y-point[j].y);
}
void updateT1(int num){
tree[num].Max=max(tree[lson].Max,tree[rson].Max);
}
void updateT2(int num){
sum[num].sum=sum[lson].sum+sum[rson].sum;
}
void build(int num,int l,int r){
sum[num].l=tree[num].l=l;
sum[num].r=tree[num].r=r;
sum[num].sum=tree[num].Max=0;
if(l==r) return ;
int mid=(l+r)>>1;
build(lson,l,mid),build(rson,mid+1,r);
}
void insertT1(int num,int pos,int val){
if(pos<tree[num].l||pos>tree[num].r) return ;
else if(pos==tree[num].l&&pos==tree[num].r)
tree[num].Max=val;
else insertT1(lson,pos,val),insertT1(rson,pos,val),updateT1(num);
}
void insertT2(int num,int pos,int val){
if(pos<sum[num].l||pos>sum[num].r) return ;
else if(pos==sum[num].l&&pos==sum[num].r)
sum[num].sum=val;
else{
insertT2(lson,pos,val);
insertT2(rson,pos,val);
updateT2(num);
}
}
void calT1(int num,int l,int r){
if(tree[num].l>r||tree[num].r<l) return ;
else if(tree[num].l>=l&&tree[num].r<=r)
cut=max(cut,tree[num].Max);
else calT1(lson,l,r),calT1(rson,l,r);
}
void calT2(int num,int l,int r){
if(sum[num].l>r||sum[num].r<l) return ;
else if(sum[num].l>=l&&sum[num].r<=r)
ans+=sum[num].sum;
else calT2(lson,l,r),calT2(rson,l,r);
}
int main(){
getint(n),getint(T);
for(int i=1;i<=n;i++)
getint(point[i].x),getint(point[i].y);
for(int i=1;i<n;i++){
dis[i][0]=Dist(i,i+1);
if(i<n-1) dis[i][1]=Dist(i,i+2);
}
build(1,1,n);
for(int i=1;i<=n;i++){
if(i<n-1)
insertT1(1,i,dis[i][0]+dis[i+1][0]-dis[i][1]);
insertT2(1,i,dis[i][0]);
}
while(T--){
scanf("%s",op);
if(op[0]=='U'){
getint(pos),getint(x),getint(y);
point[pos].x=x,point[pos].y=y;
if(pos>1) dis[pos-1][0]=Dist(pos-1,pos);
if(pos>2) dis[pos-2][1]=Dist(pos-2,pos);
if(pos<n) dis[pos][0]=Dist(pos,pos+1);
if(pos<n-1) dis[pos][1]=Dist(pos,pos+2);
if(pos>1||pos<n) insertT1(1,pos-1,dis[pos-1][0]+dis[pos][0]-dis[pos-1][1]);
if(pos>2) insertT1(1,pos-2,dis[pos-2][0]+dis[pos-1][0]-dis[pos-2][1]);
if(pos<n-1) insertT1(1,pos,dis[pos][0]+dis[pos+1][0]-dis[pos][1]);
insertT2(1,pos,dis[pos][0]);
if(pos>1) insertT2(1,pos-1,dis[pos-1][0]);
if(pos>2) insertT2(1,pos-2,dis[pos-2][0]);
}
else{
getint(l),getint(r);
cut=0,ans=0,calT1(1,l,r-2),calT2(1,l,r-1);
printf("%d\n",ans-cut);
}
}
}
第三题：奶牛慢跑（cowjog）
有n（n<=100000）头奶牛在一个无穷长的小道上慢跑。每头奶牛的起点不同，速度也不同。小道可以被分成多条跑到。奶牛只能在属于自己的跑道上慢跑，不允许更换跑道，也不允许改变速度。如果要慢跑t（t<=1000000000）分钟，要保证在任何时候不会有同一跑道上的奶牛相遇，请问最少需要多少条跑道。奶牛开始在哪条跑道是可以随意设置的。
输入格式：第一行两个整数n，t。
接下来的n行，每行包含两个整数，表示奶牛的位置和速度。位置是非负整数，速度是正整数。所有的奶牛的起点都不相同，按起点递增的顺序给出。
输出格式：最少的跑道数。
成绩：2333333333（拒绝写出）（其实并不知道，应该是全WA =_=）
题解：按距离排序，然后最长下降子序列（同拦截导弹）
分析：其实考试时想出了正解，然后只剩下十几分钟了，一时脑残，用树状数组把最长下降子序列打成了一个倒着的逆序对还找了半天错（233333333，被自己傻b到），然后后来过题时有放弃了这个思路，想了个诡异的：用一个dp数组记录，每一组的最远距离，新加入一个人是二分查找放在哪一组里（尽量前放）（就是查找一组的dp值小于新加入的人跑的距离）
正解代码（线段树优化最长下降子序列）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<stack>
#include<algorithm>
#include<vector>
#define lson num<<1
#define rson num<<1|1
using namespace std;
const int N=100000+10;
inline void getLL(long long&num){
char c;int flag=1;num=0LL;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
num*=flag;
}
int n,ans=1,tmp;
long long t;
struct node{
long long pos,v,w;
bool operator < (const node &x)const{
if(pos+t*v==x.pos+t*x.v) return pos>x.pos;
return pos+t*v<x.pos+t*x.v;
}
}cow[100010];
struct T{
int l,r,Max;
T(){Max=1;}
}tree[N<<2];
void update(int num){
tree[num].Max=max(tree[lson].Max,tree[rson].Max);
}
void build(int num,int l,int r){
tree[num].l=l,tree[num].r=r;
if(l==r) return ;
int mid=(l+r)>>1;
build(lson,l,mid),build(rson,mid+1,r);
}
void insert(int num,int pos,int val){
if(pos<tree[num].l||pos>tree[num].r) return ;
else if(tree[num].l==pos&&tree[num].r==pos)
tree[num].Max=val;
else insert(lson,pos,val),insert(rson,pos,val),update(num);
}
void getmax(int num,int l,int r){
if(r<tree[num].l||l>tree[num].r) return ;
else if(tree[num].l>=l&&tree[num].r<=r)
tmp=max(tmp,tree[num].Max);
else getmax(lson,l,r),getmax(rson,l,r);
}
int main(){
scanf("%d",&n),getLL(t);
for(int i=1;i<=n;i++)
getLL(cow[i].pos),getLL(cow[i].v),cow[i].w=i;
sort(cow+1,cow+n+1);
build(1,1,n);
for(int i=2;i<=n;i++){
cow[i].w=n-cow[i].w+1;
tmp=1,getmax(1,1,cow[i].w-1);
insert(1,cow[i].w,tmp+1);
ans=max(ans,tmp);
}
printf("%d\n",ans);
}
解法二：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;
const long long inf=1000000000000000000LL;
const int N=100000+10;
inline void getLL(long long&num){
char c;int flag=1;num=0LL;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
num*=flag;
}
long long n,ans=1LL,t,tree[N],dp[N];
struct node{
long long pos,v,w;
}cow[N];
long long find(long long l,long long r,long long x){
if(l>r) return l;
int mid=(l+r)>>1;
if(x==dp[mid]) return mid+1;
else if(x<dp[mid]) return find(mid+1,r,x);
else return find(l,mid-1,x);
}
int main(){
scanf("%lld",&n),getLL(t);
for(int i=1;i<=n;i++){
getLL(cow[i].pos),getLL(cow[i].v);
cow[i].w=cow[i].pos+cow[i].v*t,dp[i]=inf;
}
dp[1]=cow[1].w;
for(int i=2;i<=n;i++){
long long pos=find(1,ans,cow[i].w);
dp[pos]=cow[i].w,ans=max(ans,pos);
}
printf("%lld\n",ans);
}
总结：因为时间比较短，（非常非常非常非常非常非常非常非常非常非常来不及）第一题耽误的时间比较多（明明A过，却想了很久23333333），如果没做过就并不清楚能不能A了（感觉希望不大），第二题的话，其实并不清楚在完整时间内能否想出来，但后来实现代码时还算没遇到什么困难。（然而好像是oj上最慢的一个@_@）第三题，（2333）是真不知道O（nlogn）的最长下降子序列的算法（223333），但写成“顺序对”表示完全被自己傻B到（233）（样例水得无法直视2333333），至少也应该写一个O（n^2）的骗分（23333）。