T1 贪吃蛇
题目大意：给定地图大小，障碍坐标和蛇一开始坐标。蛇一开始长度为$1$。$q$次询问，每次有两种操作：1.向上、下、左、右伸长一格；2.尾巴缩短一格。当蛇越界或撞到障碍物或自己身体时游戏结束。问游戏结束的时间。
STL::deque模拟即可。
代码：
#include<cstdio> #include<iostream> #include<queue> using namespace std; const int N=105; int a[N][N],vis[N][N],n,m,t,Q; int nowx,nowy; deque< pair<int,int> > q; inline int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } inline bool judge(int x,int y) { if (x<1||x>n||y<1||y>m) return 0; if (vis[x][y]||a[x][y]) return 0; return 1; } int main() { // freopen("snake18.in","r",stdin); n=read();m=read();t=read();Q=read(); for (int i=1;i<=t;i++) { int x=read(),y=read(); a[x][y]=1; } nowx=read();nowy=read(); vis[nowx][nowy]=1; q.push_back(make_pair(nowx,nowy)); for (int i=1;i<=Q;i++) { int opt=read(); if (opt==1) { char c;cin>>c; int xx,yy; if (c=='U') xx=nowx-1,yy=nowy; if (c=='D') xx=nowx+1,yy=nowy; if (c=='L') xx=nowx,yy=nowy-1; if (c=='R') xx=nowx,yy=nowy+1; if (!judge(xx,yy)){ cout<<i; return 0; } q.push_back(make_pair(xx,yy)); vis[xx][yy]=1; nowx=xx,nowy=yy; // printf("%d %d ",xx,yy); } else { pair<int,int> tmp=q.front();q.pop_front(); vis[tmp.first][tmp.second]=0; } } cout<<-1; return 0; }
T2 分糖果
原题目：皇后游戏
先说$cmp$：$min(a_i,b_j)<min(b_i,a_j)$
我的思路跟高赞题解的不同，欢迎探讨。（参考自2014年北京高考理科数学第20题）
我们可以尝试用数学归纳法证明贪心策略。
当$n=2$时，假设现有两个数对数列$P(a,b)(c,d)$和$P'(c,d)(a,b)$。
$T_1(P)=a+b,T_2(P)=max(a+b,a+c)+d=a+d+max(b,c)$
$T_1(P')=c+d,T_2(P')=max(c+a,c+d)+b$
当$min=a$时，$T_2(P')=c+d+b$。因为有$aleq max(b,c)$，所以$T_2(P)leq T_2(p')$；
当$min=d$时，$T_2(P')=c+a+b$。因为有$dleq max(b,c)$，所以此时有$T_2(P)leq T_2(p')$。
综上，$n=2$时贪心策略成立。$n>2$时，因为满足局部最优子结构的性质，由数学归纳法得到贪心策略是正确的。
以上说明了$min(a_i,b_j)$严格小于$min(b_i,a_j)$的情况。对于相等的情况，我们怎么处理？事实上，我们有$a_i<a_j$。考虑讨论$min$的取值：
1.如果$min$取值在$a$，那么显然成立，符合贪心策略意图。
2.如果$min$取值在$b$，那么考虑这个式子：$max(sumlimits a+a_i,c)$。现然我们要让这个式子尽量取值小，把较小的$a$放到前面是比把较大的$a$放到前面是更优的。
综上，$a_i<a_j$成立。
Upd:然而这个证明存在问题QAQ，各位看官就随便看看吧……
代码：
#include<cstdio> #include<iostream> #include<algorithm> #define int long long using namespace std; const int N=50005; int T,n,ans,c[N],sum; struct node{ int a,b; }a[N]; bool cmp(node a,node b){ return min(a.a,b.b)==min(b.a,a.b)?a.a<b.a:min(a.a,b.b)<min(b.a,a.b); } inline int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } signed main() { T=read(); while(T--) { n=read(); for (int i=1;i<=n;i++) a[i].a=read(),a[i].b=read(); sort(a+1,a+n+1,cmp); c[1]=a[1].a+a[1].b; ans=c[1];sum=a[1].a; for (int i=2;i<=n;i++) { sum+=a[i].a; c[i]=max(c[i-1],sum)+a[i].b; ans=max(ans,c[i]); } printf("%lld ",ans); } return 0; }
T3 排序
题目大意：给定长度为$n$的序列$a$和$m$个修改位置$p$。每次将$p$之后且小于等于$a_p$的数拿出来升序排序再按次序放回原位置。问每次操作过后逆序对数。
考虑每个数的贡献。通常用树状数组维护逆序对数是考虑每个$i$的贡献：$j<i$且$a_j>a_i$。我们变换一下思路，求$j>i$且$a_j<a_i$的数对个数。一个显然的二维偏序问题。这样我们可以通过预处理逆序对然后逐一减去每个数的贡献。
对于快速求出满足题目条件的数，我们可以使用线段树，维护一个$pair$类型的线段树，每次返回最小值的下标。均摊复杂度是$O(1)$的。总时间复杂度$O((n+m)log n)$。
代码：
#include<cstdio> #include<iostream> #include<algorithm> #define lowbit(x) x&(-x) #define int long long using namespace std; const int N=500005; const int inf=1e18; int tree[N],a[N],b[N],ans[N],num[N],n,m,now; pair<int,int> mi[N*4]; inline int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void add(int x){ for (int i=x;i<=n;i+=lowbit(i)) tree[i]++; } inline int sum(int x){ int res=0; for (int i=x;i;i-=lowbit(i)) res+=tree[i]; return res; } inline void build(int index,int l,int r) { mi[index]=make_pair(inf,inf); if (l==r) return; int mid=(l+r)>>1; build(index*2,l,mid); build(index*2+1,mid+1,r); } inline void update(int index,int l,int r,int x,pair<int,int> k) { if (l==r){ mi[index]=k; return; } int mid=(l+r)>>1; if (x<=mid) update(index*2,l,mid,x,k); else update(index*2+1,mid+1,r,x,k); mi[index]=min(mi[index*2],mi[index*2+1]); } inline pair<int,int> query(int index,int l,int r,int ql,int qr) { if (ql<=l&&r<=qr) return mi[index]; int mid=(l+r)>>1;pair<int,int> res=make_pair(inf,inf); if (ql<=mid) res=min(res,query(index*2,l,mid,ql,qr)); if (qr>mid) res=min(res,query(index*2+1,mid+1,r,ql,qr)); return res; } signed main() { n=read();m=read(); for (int i=1;i<=n;i++) a[i]=read(),b[i]=a[i]; sort(b+1,b+n+1); int len=unique(b+1,b+n+1)-b-1; for (int i=n;i>=1;i--) { num[i]=lower_bound(b+1,b+len+1,a[i])-b; add(num[i]);ans[i]=sum(num[i]-1); now+=ans[i]; update(1,1,n,i,make_pair(num[i],i)); } while(m--) { int p=read(); while(1) { pair<int,int> tmp=query(1,1,n,p,n); if (tmp.first>num[p]) break; now-=ans[tmp.second]; update(1,1,n,tmp.second,make_pair(inf,inf)); } printf("%lld ",now); } return 0; }
T4 眼泪
改了改，然而懒得写题解了。咕咕咕……