连炸两题，身败名裂。
看来不拍暴力就会die。
A题
滑动窗口或什么前缀和二分之类的就行了。
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int maxn=100010; int n,ans1,ans2; ll S[maxn],m; int main() { n=read();m=read(); rep(i,1,n) S[i]=S[i-1]+read(); rep(i,1,n) { int l=1,r=i; while(l<r) { int mid=l+r>>1; if(S[i]-S[mid-1]>m) l=mid+1; else r=mid; } if(S[i]-S[l-1]==m&&!ans1) ans1=l,ans2=i; } printf("%d %d ",ans1,ans2); return 0; }
B题
好像是有奇怪的进制加法可以做。
我的做法是这样的，先计算出{1,2,--,n}变换到A的次数。
然后逐位确定乱搞。
但是要写高精度。
然后我因为构造函数写成了int炸了。
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int maxn=310; struct bign { int s[maxn],len; bign() {len=1;memset(s,0,sizeof(s));} void operator = (ll b) { //嘿嘿嘿考试时写成了int len=0; while(b) s[len++]=b%10,b/=10; } bign operator * (int b) { bign c;c.len=len+10; int last=0; rep(i,0,c.len-1) { int x=s[i]*b+last; c.s[i]+=x%10; last=x/10; } while(c.len>1&&!c.s[c.len-1]) c.len--; return c; } bign operator + (bign b) { bign c;c.len=max(len,b.len)+1; rep(i,0,c.len-1) { c.s[i]+=s[i]+b.s[i]; c.s[i+1]+=c.s[i]/10; c.s[i]%=10; } while(c.len>1&&!c.s[c.len-1]) c.len--; return c; } bool operator >= (bign b) { if(len>b.len) return 1; if(len<b.len) return 0; dwn(i,len-1,0) { if(s[i]>b.s[i]) return 1; if(s[i]<b.s[i]) return 0; } return 1; } bool operator > (bign b) { if(len>b.len) return 1; if(len<b.len) return 0; dwn(i,len-1,0) { if(s[i]>b.s[i]) return 1; if(s[i]<b.s[i]) return 0; } return 0; } void print() { dwn(i,len-1,0) printf("%d",s[i]); printf(" ",len); } }; int n,A[maxn],B[maxn],use[maxn]; bign m,xp[maxn]; int main() { xp[0]=1;rep(i,1,100) xp[i]=xp[i-1]*i; n=read();ll tmp;scanf("%lld",&tmp);m=tmp; rep(i,1,n) A[i]=read(); rep(i,1,n) { int cnt=0; rep(j,i+1,n) if(A[j]<A[i]) cnt++; m=m+(xp[n-i]*cnt); } if(m>=xp[n]) {puts("-1");return 0;} bign cur;cur=0; rep(i,1,n) { rep(j,0,n-1) { if(cur+xp[n-i]>m) {B[i]=j;break;} cur=cur+xp[n-i]; } } rep(i,1,n) { rep(j,1,n) if(!use[j]) { if(B[i]==0) use[j]=1,printf("%d%c",j,i==n?' ':' '); B[i]--; } } return 0; }
C题
大意是对每一行有N条带权线段，对于每个位置计算出覆盖它的线段的最大权值。
扫描线用个堆来维护一下就行了。
然后我想错了用了个单调队列，成功炸掉90分。
#include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) using namespace std; typedef long long ll; inline ll read() { ll x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=110; const int maxm=5010; int n,m; ll D[maxn][maxm],A[maxn][maxm]; int L[maxn][maxm],R[maxn][maxm]; struct Line { int l,r;ll v; bool operator < (const Line& ths) const {return l<ths.l;} }B[maxm]; struct HeapNode { ll d;int u; bool operator < (const HeapNode& ths) const {return d<ths.d;} }; int main() { n=read();m=read(); rep(i,1,n) rep(j,1,m) A[i][j]=read(); rep(i,1,n) rep(j,1,m) L[i][j]=read(); rep(i,1,n) rep(j,1,m) R[i][j]=read(); rep(i,1,n) { rep(j,1,m) A[i][j]+=D[i][j],printf("%lld%c",A[i][j],j==m?' ':' '); rep(j,1,m) B[j]=(Line){L[i][j],R[i][j],A[i][j]}; sort(B+1,B+m+1); int cur=1;priority_queue<HeapNode>Q; //嘿嘿嘿考试时用了一个单调队列 rep(j,1,m) { while(cur<=m&&B[cur].l<=j) Q.push((HeapNode){B[cur].v,cur}),cur++; while(!Q.empty()) { HeapNode x=Q.top(); if(B[x.u].r>=j) { D[i+1][j]=x.d; break; } else Q.pop(); } } } return 0; }
D题
对于每一个交换子树操作，左子树的所有点的答案要加上右子树的size，右子树的所有点的答案要减去左子树的size。
然后找一个支持区间增加单点查询的数据结构如线段树，BIT就行了。
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=100010; int n,clo,l[maxn],r[maxn],A[maxn],in[maxn]; int s[maxn],L[maxn],R[maxn]; int dfs(int x) { A[x]=clo++;L[x]=clo;s[x]=1; if(l[x]) s[x]+=dfs(l[x]); if(r[x]) s[x]+=dfs(r[x]); R[x]=clo; return s[x]; } int addv[maxn*4]; void pushdown(int o) { if(addv[o]) { int lc=o<<1,rc=lc|1; addv[lc]+=addv[o];addv[rc]+=addv[o]; addv[o]=0; } } int pos,ql,qr,val; void update(int o,int l,int r) { if(ql<=l&&r<=qr) addv[o]+=val; else { pushdown(o); int mid=l+r>>1,lc=o<<1,rc=lc|1; if(ql<=mid) update(lc,l,mid); if(qr>mid) update(rc,mid+1,r); } } void query(int o,int l,int r) { if(l==r) printf("%d ",addv[o]); else { pushdown(o); int mid=l+r>>1,lc=o<<1,rc=lc|1; if(pos<=mid) query(lc,l,mid); else query(rc,mid+1,r); } } int main() { n=read(); rep(i,2,n) { int p=read(),c=read(),t=read();in[c]++; if(t) r[p]=c; else l[p]=c; } rep(i,1,n) if(!in[i]) dfs(i); rep(i,1,n) ql=L[i],qr=L[i],val=A[i],update(1,1,n); dwn(i,read(),1) { int t=read(),x=read(); if(t==1) pos=L[x],query(1,1,n); else { if(!l[x]||!r[x]) continue; ql=L[l[x]];qr=R[l[x]];val=s[r[x]]; update(1,1,n); ql=L[r[x]];qr=R[r[x]];val=-s[l[x]]; update(1,1,n); swap(l[x],r[x]); } } return 0; }
E题
设f[i][j]表示已经走了i步，该匹配j位置的方案数。
然后可以枚举下一位是什么：
f[i+1][to(j,0)]+=f[i][j]
f[i+1][to(j,1)]+=f[i][j]
注意如果to(j,c)=m，则要同时转移到f[i+1][m]，f[i+1][0]。
然后矩阵快速幂即可。
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) using namespace std; typedef long long ll; inline ll read() { ll x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=105; const int mod=1000000007; char s[maxn]; int m,f[maxn]; void KMP() { f[0]=f[1]=0; for(int i=1;s[i];i++) { int j=f[i]; while(j&&s[i]!=s[j]) j=f[j]; f[i+1]=(s[i]==s[j]?j+1:0); } } struct Matrix { ll A[maxn][maxn]; Matrix operator * (const Matrix& b) { Matrix c; rep(i,0,m) rep(j,0,m) { c.A[i][j]=0; rep(k,0,m) (c.A[i][j]+=A[i][k]*b.A[k][j])%=mod; } return c; } void print() { rep(i,0,m) { rep(j,0,m) printf("%lld%c",A[i][j],j==m?' ':' '); } } }; void pow(Matrix& ans,ll n) { Matrix t;t=ans;n--; while(n) { if(n%2) ans=ans*t; t=t*t;n/=2; } } Matrix ans; int main() { ll n=read();scanf("%s",s); m=strlen(s);KMP(); rep(j,0,m-1) rep(c,0,1) { int k=j;while(k&&s[k]!=c+'0') k=f[k]; if(s[k]==c+'0') { ans.A[k+1][j]++; if(k+1==m) ans.A[0][j]++; } else ans.A[0][j]++; } pow(ans,n); printf("%lld ",ans.A[m][0]); return 0; }