连炸两题，身败名裂。
看来不拍暴力就会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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int maxn=;
int n,ans1,ans2;
ll S[maxn],m;
int main() {
n=read();m=read();
rep(i,,n) S[i]=S[i-]+read();
rep(i,,n) {
int l=,r=i;
while(l<r) {
int mid=l+r>>;
if(S[i]-S[mid-]>m) l=mid+;
else r=mid;
}
if(S[i]-S[l-]==m&&!ans1) ans1=l,ans2=i;
}
printf("%d %d\n",ans1,ans2);
return ;
}
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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int maxn=;
struct bign {
int s[maxn],len;
bign() {len=;memset(s,,sizeof(s));}
void operator = (ll b) { //嘿嘿嘿考试时写成了int
len=;
while(b) s[len++]=b%,b/=;
}
bign operator * (int b) {
bign c;c.len=len+;
int last=;
rep(i,,c.len-) {
int x=s[i]*b+last;
c.s[i]+=x%;
last=x/;
}
while(c.len>&&!c.s[c.len-]) c.len--;
return c;
}
bign operator + (bign b) {
bign c;c.len=max(len,b.len)+;
rep(i,,c.len-) {
c.s[i]+=s[i]+b.s[i];
c.s[i+]+=c.s[i]/;
c.s[i]%=;
}
while(c.len>&&!c.s[c.len-]) c.len--;
return c;
}
bool operator >= (bign b) {
if(len>b.len) return ;
if(len<b.len) return ;
dwn(i,len-,) {
if(s[i]>b.s[i]) return ;
if(s[i]<b.s[i]) return ;
}
return ;
}
bool operator > (bign b) {
if(len>b.len) return ;
if(len<b.len) return ;
dwn(i,len-,) {
if(s[i]>b.s[i]) return ;
if(s[i]<b.s[i]) return ;
}
return ;
}
void print() {
dwn(i,len-,) printf("%d",s[i]);
printf("\n",len);
}
};
int n,A[maxn],B[maxn],use[maxn];
bign m,xp[maxn];
int main() {
xp[]=;rep(i,,) xp[i]=xp[i-]*i;
n=read();ll tmp;scanf("%lld",&tmp);m=tmp;
rep(i,,n) A[i]=read();
rep(i,,n) {
int cnt=;
rep(j,i+,n) if(A[j]<A[i]) cnt++;
m=m+(xp[n-i]*cnt);
}
if(m>=xp[n]) {puts("-1");return ;}
bign cur;cur=;
rep(i,,n) {
rep(j,,n-) {
if(cur+xp[n-i]>m) {B[i]=j;break;}
cur=cur+xp[n-i];
}
}
rep(i,,n) {
rep(j,,n) if(!use[j]) {
if(B[i]==) use[j]=,printf("%d%c",j,i==n?'\n':' ');
B[i]--;
}
}
return ;
}
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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxm=;
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,,n) rep(j,,m) A[i][j]=read();
rep(i,,n) rep(j,,m) L[i][j]=read();
rep(i,,n) rep(j,,m) R[i][j]=read();
rep(i,,n) {
rep(j,,m) A[i][j]+=D[i][j],printf("%lld%c",A[i][j],j==m?'\n':' ');
rep(j,,m) B[j]=(Line){L[i][j],R[i][j],A[i][j]};
sort(B+,B+m+);
int cur=;priority_queue<HeapNode>Q; //嘿嘿嘿考试时用了一个单调队列
rep(j,,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+][j]=x.d;
break;
}
else Q.pop();
}
}
}
return ;
}
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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
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]=;
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*];
void pushdown(int o) {
if(addv[o]) {
int lc=o<<,rc=lc|;
addv[lc]+=addv[o];addv[rc]+=addv[o];
addv[o]=;
}
}
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>>,lc=o<<,rc=lc|;
if(ql<=mid) update(lc,l,mid);
if(qr>mid) update(rc,mid+,r);
}
}
void query(int o,int l,int r) {
if(l==r) printf("%d\n",addv[o]);
else {
pushdown(o);
int mid=l+r>>,lc=o<<,rc=lc|;
if(pos<=mid) query(lc,l,mid);
else query(rc,mid+,r);
}
}
int main() {
n=read();
rep(i,,n) {
int p=read(),c=read(),t=read();in[c]++;
if(t) r[p]=c;
else l[p]=c;
}
rep(i,,n) if(!in[i]) dfs(i);
rep(i,,n) ql=L[i],qr=L[i],val=A[i],update(,,n);
dwn(i,read(),) {
int t=read(),x=read();
if(t==) pos=L[x],query(,,n);
else {
if(!l[x]||!r[x]) continue;
ql=L[l[x]];qr=R[l[x]];val=s[r[x]];
update(,,n);
ql=L[r[x]];qr=R[r[x]];val=-s[l[x]];
update(,,n);
swap(l[x],r[x]);
}
}
return ;
}
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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int mod=;
char s[maxn];
int m,f[maxn];
void KMP() {
f[]=f[]=;
for(int i=;s[i];i++) {
int j=f[i];
while(j&&s[i]!=s[j]) j=f[j];
f[i+]=(s[i]==s[j]?j+:);
}
}
struct Matrix {
ll A[maxn][maxn];
Matrix operator * (const Matrix& b) {
Matrix c;
rep(i,,m) rep(j,,m) {
c.A[i][j]=;
rep(k,,m) (c.A[i][j]+=A[i][k]*b.A[k][j])%=mod;
}
return c;
}
void print() {
rep(i,,m) {
rep(j,,m) printf("%lld%c",A[i][j],j==m?'\n':' ');
}
}
};
void pow(Matrix& ans,ll n) {
Matrix t;t=ans;n--;
while(n) {
if(n%) ans=ans*t;
t=t*t;n/=;
}
}
Matrix ans;
int main() {
ll n=read();scanf("%s",s);
m=strlen(s);KMP();
rep(j,,m-) rep(c,,) {
int k=j;while(k&&s[k]!=c+'') k=f[k];
if(s[k]==c+'') {
ans.A[k+][j]++;
if(k+==m) ans.A[][j]++;
}
else ans.A[][j]++;
}
pow(ans,n);
printf("%lld\n",ans.A[m][]);
return ;
}