T1 嘟嘟噜
上来一看数据范围1e9就蒙蔽，然后不知所措的打了一个 $ O（n）$的无脑算法，由于本人真的脑小，导致O（n）的柿子推了好长时间，导致心态崩了，然后........ 今天能明白了log的算法，算是约瑟夫问题弄明白了，没有想到跳跃式的竟然可以log求。
#include<bits/stdc++.h> using namespace std; #define re register inline int read() { int x=0,f=1;char cc=getchar(); while(cc>'9'||cc<'0'){if(cc=='-')f=-1;cc=getchar();} while(cc>='0'&&cc<='9'){x=(x<<1)+(x<<3)+cc-'0';cc=getchar();} return x*f; } const int maxn=5000005; int n,k,m,S; int ans[maxn]; queue<int>q; set<int>pc,fc; stack<int>s; int main() { n=read(),k=read(),m=read(),S=read(); for(int i=1,u;i<=m;i++) { u=read(); ans[u]=-1; } q.push(S); for(re int i=1;i<=n;++i) if(i!=S&&ans[i]!=-1) { if(i&1)pc.insert(i); else fc.insert(i); } while(q.size()&&(!pc.empty()||!fc.empty())) { int x=q.front();q.pop(); if((x&1)==(k&1)) { for(auto it=pc.lower_bound(max(x-k+1,k-x));it!=pc.end()&&*it<x+k;++it) { int zz=(k-(abs(x-*it)+1))>>1; if(zz>n-max(*it,x))break; q.push(*it); ans[*it]=ans[x]+1; s.push(*it); } while(s.size())pc.erase(s.top()),s.pop(); continue; } for(auto it=fc.lower_bound(max(x-k+1,k-x));it!=fc.end()&&*it<x+k;++it) { int zz=(k-(abs(x-*it)+1))>>1; if(zz>n-max(*it,x))break; ans[*it]=ans[x]+1; q.push(*it); s.push(*it); } while(s.size())fc.erase(s.top()),s.pop(); } for(re int i=1;i<=n;++i) { if(!ans[i]&&(i!=S))ans[i]=-1; printf("%d ",ans[i]); } return 0; }
T2 天才绅士少女助手克里斯蒂娜
看题就发现是原题，然后想到当时自己连题解都没有颓，就崩了，然后想到当时就是wba大神造的数据，我就感到了一丝不妙，其实就是拆一下柿子就出来了！
然后我就怀着爆零的心情去看T3
#include<bits/stdc++.h> using namespace std; #define int long long inline int read() { int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=5000005; const int mod=20170927; int n,m; struct BIT { int tr[maxn]; inline int lowbit(int x){return x&(-x);} inline int query(int x) { int res=0; while(x) { (res+=tr[x]+mod)%=mod; x-=lowbit(x); } return res; } inline void update(int x,int val) { while(x<=n) { (tr[x]+=val+mod)%=mod; x+=lowbit(x); } return ; } }t1,t2,t3; int a1[maxn],a2[maxn],a3[maxn]; struct node { int x,y; inline void make(int _x,int _y){x=_x,y=_y;return ;} }s[maxn]; signed main() { //freopen("inputs2.in","r",stdin); n=read();m=read(); for(int i=1,x,y;i<=n;i++) { x=read(),y=read(); s[i].make(x,y); } for(int i=1;i<=n;i++) { a1[i]=(s[i].x*s[i].x%mod)%mod; a2[i]=(s[i].y*s[i].y%mod)%mod; a3[i]=(s[i].x*s[i].y%mod)%mod; t1.update(i,a1[i]); t2.update(i,a2[i]); t3.update(i,a3[i]); } int opt=0; while(m--) { opt=read(); if(opt==1) { int p=read(),x=read(),y=read(); s[p].x=x,s[p].y=y; int c1=a1[p],c2=a2[p],c3=a3[p]; a1[p]=x*x%mod,a2[p]=y*y%mod;a3[p]=x*y%mod; t1.update(p,a1[p]-c1); t2.update(p,a2[p]-c2); t3.update(p,a3[p]-c3); } else { int l=read(),r=read(); int ans=0; ans=((t1.query(r)-t1.query(l-1)+mod)%mod*(t2.query(r)-t2.query(l-1)+mod)%mod+mod)%mod; int tt=((t3.query(r)-t3.query(l-1)+mod)%mod+mod)%mod; ans=((ans-tt*tt%mod+mod)%mod+mod)%mod; printf("%lld ",ans); } } return 0; }
T3
就是一个LCIS，当时学的时候还被人消费来着（LSC LCIS）然后在看出是dp之后由于剩的时间过少，还想调T2所以直接打的爆搜，按说应该可以20分，但是只有10分，
3
考虑 DP. 设状态 dp(i, j) 表示 a 序列考虑到 i, b 序列考虑到 j 并且必须选 b j 的最
大长度. 当 a i = b j 时, 显然有转移 dp(i, j) = max k<j,b k <b j {dp(i − 1, k)} + 1.
于是从小到大枚举 j, 维护 max k<j,b k <a i {dp(i − 1, k)}, 直接转移即可.
时间复杂度 O(nm).
由于前几场考试T1过于水，导致之前的T1都切了，而且一般20分钟之内就可以A，所以这次T1拖了1个小时，就心态炸了，还是要历练！@……@
#include<bits/stdc++.h> using namespace std; #define re register #define LL long long template<class T> inline void read(T &x) { T f=1;x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x=x*f; } int n,m; const int maxn=5005; LL a[maxn],b[maxn]; bool vis[maxn]; int ch[maxn],tot; int dp[maxn][maxn]; int pre[maxn][maxn]; int sta[maxn],topp; inline void ba(re int x,re int y) { if(x==0||y==0)return; re int qq=pre[x][y]; if(y!=qq)sta[++topp]=b[y]; ba(x-1,qq); } signed main() { //freopen("inputs3.in","r",stdin); read(n); for(re int i=1;i<=n;i++) read(a[i]); read(m); for(re int i=1;i<=m;i++) read(b[i]); for(re int i=1;i<=n;i++) { int res=0,id=0; if(b[0]<b[1])res=dp[i-1][0],id=0; for(re int j=1;j<=m;j++) { if(a[i]==b[j]) { pre[i][j]=id; dp[i][j]=res+1; } else { pre[i][j]=j; dp[i][j]=dp[i-1][j]; } if(b[j]<a[i]) { if(res<=dp[i-1][j]) { res=dp[i-1][j],id=j; } } } } int ans=0,id=0; for(re int i=1;i<=m;i++) { if(dp[n][i]>=ans)ans=dp[n][i],id=i; } printf("%d ",dp[n][id]); ba(n,id); while(topp) { printf("%d ",sta[topp]); topp--; } return 0; }