有的考试表面上自称NOIP模拟，背地里却是绍兴一中NOI模拟

吓得我直接文件打错

T1 Skip

---

设状态$f_i$为最后一次选$i$在$i$时的最优解。有$f_i=max_{j<i}[f_j+a_i-\frac{(j-i)\times (j-i-1)}{2}]$

设$j<k$，对$i$来说，$k$优于$j$，当且仅当$2\times i>\frac{2\times(f_j-f_k)+k^2+k-j^2-j}{k-j}$

斜率优化，$CDQ$分治，先按$a$排序，分治中按$id$排序满足限制，然后维护右下凸包更新答案。

$code:$

 1 #include<bits/stdc++.h>

 2 #define int long long

 3 using namespace std;

 4

 5 namespace IO{

 6     inline int read(){

 7         char ch=getchar(); int x=0,f=1;

 8         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

 9         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

10         return x*f;

11     }

12     inline void write(int x,char sp){

13         char ch[20]; int len=0;

14         if(x<0){ putchar('-'); x=~x+1; }

15         do{ ch[len++]=x%10+(1<<4)+(1<<5); x/=10; }while(x);

16         for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);

17     }

18     inline int max(int x,int y){ return x<y?y:x; }

19     inline int min(int x,int y){ return x<y?x:y; }

20     inline void swap(int &x,int &y){ x^=y^=x^=y; }

21     inline void chmax(int &x,int y){ x=x<y?y:x; }

22     inline void chmin(int &x,int y){ x=x<y?x:y; }

23 } using namespace IO;

24

25 const int NN=1e5+5;

26 int n,ans,h,t,tmp,q[NN];

27 inline int calc(int x){ return x*(x+1)/2; }

28 struct node{

29     int a,pre,id,f;

30 }f[NN];

31 bool cmp1(node x,node y){ return x.id<y.id; }

32 bool cmp2(node x,node y){ return x.a==y.a?x.id<y.id:x.a<y.a; }

33 bool cmp3(int x,int y,int z){ return (2*(f[z].f-f[x].f)+f[x].pre-f[z].pre)*(f[y].id-f[z].id)>=(2*(f[z].f-f[y].f)+f[y].pre-f[z].pre)*(f[x].id-f[z].id); }

34 bool cmp4(int x,int y,int a){ return 2*(f[y].f-f[x].f)+f[x].pre-f[y].pre>=2*a*(f[x].id-f[y].id); }

35

36 void solve(int l,int r){

37     if(l>=r) return;

38     int mid=l+r>>1;

39     solve(l,mid); h=1; t=0; tmp=l;

40     sort(f+l,f+mid+1,cmp1); sort(f+mid+1,f+r+1,cmp1);

41     for(int i=mid+1;i<=r;i++){

42         while(f[tmp].id<f[i].id&&tmp<=mid){

43             while(h<t&&!cmp3(tmp,q[t],q[t-1])) --t;

44             q[++t]=tmp++;

45         }

46         while(h<t&&!cmp4(q[h+1],q[h],f[i].id)) ++h;

47         if(h>t) continue;

48         chmax(f[i].f,f[q[h]].f+f[i].a-calc(f[i].id-f[q[h]].id-1));

49     }

50     sort(f+mid+1,f+r+1,cmp2);

51     solve(mid+1,r);

52 }

53

54 signed main(){

55     freopen("skip.in","r",stdin);

56     freopen("skip.out","w",stdout);

57     n=read(); ans=-calc(n);

58     for(int i=1;i<=n;i++) f[i].a=read(), f[i].f=f[i].a-calc(i-1), f[i].id=i, f[i].pre=i*i+i;

59     sort(f+1,f+n+1,cmp2); solve(1,n);

60     for(int i=1;i<=n;i++) chmax(ans,f[i].f-calc(n-f[i].id));

61     write(ans,'\n');

62     return 0;

63 }

T1

T2 String

---

爆搜，记忆化方案数。

参考学长博

$code:$

 1 #include<bits/stdc++.h>

 2 #define int long long

 3 using namespace std;

 4

 5 namespace IO{

 6     inline int read(){

 7         char ch=getchar(); int x=0,f=1;

 8         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

 9         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

10         return x*f;

11     }

12     inline void write(int x,char sp){

13         char ch[20]; int len=0;

14         if(x<0){ putchar('-'); x=~x+1; }

15         do{ ch[len++]=x%10+(1<<4)+(1<<5); x/=10; }while(x);

16         for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);

17     }

18     inline int max(int x,int y){ return x<y?y:x; }

19     inline int min(int x,int y){ return x<y?x:y; }

20     inline void swap(int& x,int& y){ x^=y^=x^=y; }

21     inline void chmax(int& x,int y){ x=x<y?y:x; }

22     inline void chmin(int& x,int y){ x=x<y?x:y; }

23 } using namespace IO;

24

25 int k,n,base,finl,tim[26],chr[10];

26 char s[1000];

27 map<int,int>f[10];

28

29 inline int bit(int x){ return x?1<<4*x-4:0; }

30 int dfs(int l,int st,int rk,int lst){

31     if(f[lst].find(st)!=f[lst].end()&&f[lst][st]<=rk) return f[lst][st];

32     if(st==finl){

33         if(!rk){ puts(s); exit(0); }

34         return f[lst][st]=1;

35     }

36     int tmp=0,sum=0;

37     for(int i=base;i<26;i++) if(i+'a'!=s[l-1]){

38         ++tim[i]; ++chr[tim[i]]; s[l]=i+'a';

39         if(chr[tim[i]]<=k-tim[i]+1)

40             tmp=dfs(l+1,st+bit(tim[i])-bit(tim[i]-1),rk,tim[i]), rk-=tmp, sum+=tmp;

41         --chr[tim[i]]; --tim[i];

42     }

43     return f[lst][st]=sum;

44 }

45

46 signed main(){

47     freopen("string.in","r",stdin);

48     freopen("string.out","w",stdout);

49     k=read(); n=read();

50     while(k>8){

51         for(int i=1;i<k;i++) putchar(base+'a'), putchar(base+'b');

52         putchar(base+'a'); k-=2; base+=2;

53     }

54     for(int i=1;i<=k;i++) finl|=bit(i);

55     dfs(0,0,n-1,9);

56     puts("-1");

57     return 0;

58 }

T2

T3 Permutation

---

发现题解是错的，于是花了一下午把它改对了。

首先不难发现可以把问题转化为$n=n+m-k$，$k=m$的情况，因为$m$后的串对答案无影响，且对答案有贡献时后面的串是固定的。设$f_{n,k}$为$n=n,k=k$时的答案。

讨论当前考虑区间的第一个数是否不变。当变化时，设前一行第一个数为$x$，后一行为$x+1$，那么前一行$[2\dots k]$是$n − (k − 2)\dots n$。后一行$[i + 1][2\dots k]$是$x + 2\dots x + k$。

于是答案贡献为$n-k-x$。这部分总答案为$\sum_{j=1}^{n-k}n-j-k$，化简即为$\begin{pmatrix}n-k\\ 2\end{pmatrix}$。

注意$n=1$时答案应为$n-1$，这样算是错的。

设$g_{n,k}=\begin{pmatrix}n-k\\ 2\end{pmatrix}$，那么$f_{n,k}=g_{n,k}+\sum_{j=1}^{n-k+1}f_{n-j,k-1}$，相当于每次枚举第一行相同的值，将第一行去掉。$n-j$表示可取数的个数为$n-j$。

发现$\begin{pmatrix}n\\ m\end{pmatrix}$实际意义可以是将$n+1$有顺序地划分为$m+1$个正整数，那么考虑$g_{x,y}$贡献次数，从$f_{n,k}$到$g_{x,y}$迭代了$k-y$次，第一维一共减了$n-x$，那么它的次数应为将$n-x$划分为$k-y$个正整数的方案，即为$\begin{pmatrix}n-x-1\\ k-y-1\end{pmatrix}$。

考虑枚举$g_{x,y}$中的$y$，计算$2\leq y\leq x\leq k$的总贡献。

第一步枚举$x$相当于将$n − y + 1$划分为$n − x$和$x − y + 1$两个正整数，然后将$n-x$划分为$k-y$个正整数是它的系数，将$x-y+1$划分为$3$个正整数是它的值，合起来考虑，$y$的贡献即为将$n-y+1$划分为$k-y+3$个正整数的方案，也就是$\begin{pmatrix}n-y\\k-y-2\end{pmatrix}$。

因为迭代出的$f_{x,1}$要特殊处理，所以刚才枚举$y$从$2$开始。最后再将$f_{x,1}$的贡献加上即可。

$k=1$要特判。

$code:$

 1 #include<bits/stdc++.h>

 2 #define int long long

 3 using namespace std;

 4

 5 namespace IO{

 6     inline int read(){

 7         char ch=getchar(); int x=0,f=1;

 8         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

 9         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

10         return x*f;

11     }

12     inline void write(int x,char sp){

13         char ch[20]; int len=0;

14         if(x<0){ putchar('-'); x=~x+1; }

15         do{ ch[len++]=x%10+(1<<4)+(1<<5); x/=10; }while(x);

16         for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);

17     }

18     inline int max(int x,int y){ return x<y?y:x; }

19     inline int min(int x,int y){ return x<y?x:y; }

20     inline void swap(int &x,int &y){ x^=y^=x^=y; }

21     inline void chmax(int &x,int y){ x=x<y?y:x; }

22     inline void chmin(int &x,int y){ x=x<y?x:y; }

23 } using namespace IO;

24

25 const int NN=1e6+5,p=1e9+7;

26 int n,k,m,fac[NN],inv[NN],ans;

27 inline int C(int x,int y){ return x<0||y<0||x<y?0:fac[x]*inv[y]%p*inv[x-y]%p; }

28 inline int qpow(int a,int b){

29     int res=1;

30     while(b){

31         if(b&1) res=res*a%p;

32         a=a*a%p;

33         b>>=1;

34     }

35     return res;

36 }

37

38 signed main(){

39     freopen("perm.in","r",stdin);

40     freopen("perm.out","w",stdout);

41     n=read(); k=read(); m=read(); n=n-k+m; k=m; fac[0]=inv[0]=1;

42

43     for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%p; inv[n]=qpow(fac[n],p-2);

44     for(int i=n-1;i;i--) inv[i]=inv[i+1]*(i+1)%p;

45

46     if(k==1){ write(n-1,'\n'); return 0; }

47     for(int i=2;i<=k;i++) (ans+=C(n-i,k-i+2))%=p;//cout<<ans<<endl;

48     for(int i=2;i<=n;i++){

49         int num=C(n-i-1,k-2);

50         int tmp=i-1;

51         (ans+=num*tmp%p)%=p;//cout<<i<<' '<<num<<' '<<tmp<<endl;

52     }

53     write(ans,'\n');

54     return 0;

55 }

T3

T4 小P的生成树

---

发现在最后加和的负数的方向向量确定的情况下，每条边的权值是固定的。于是

注意题解里算$tan$式子列反了。。

$code:$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3

 4 namespace IO{

 5     inline int read(){

 6         char ch=getchar(); int x=0,f=1;

 7         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

 8         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

 9         return x*f;

10     }

11     inline void write(int x,char sp){

12         char ch[20]; int len=0;

13         if(x<0){ putchar('-'); x=~x+1; }

14         do{ ch[len++]=x%10+(1<<4)+(1<<5); x/=10; }while(x);

15         for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);

16     }

17     inline int max(int x,int y){ return x<y?y:x; }

18     inline int min(int x,int y){ return x<y?x:y; }

19     inline void swap(int &x,int &y){ x^=y^=x^=y; }

20     inline void chmax(int &x,int y){ x=x<y?y:x; }

21     inline void chmin(int &x,int y){ x=x<y?x:y; }

22 } using namespace IO;

23

24 const int NN=210;

25 int n,m,f[NN];

26 vector<double>arr;

27 double ans,aa,bb;

28 struct eg{

29     int u,v,a,b;

30     double val;

31     bool operator<(const eg& x)const{ return val>x.val; }

32 }e[NN];

33 int getf(int x){ return f[x]==x?x:f[x]=getf(f[x]); }

34

35 void kruscal(){

36     sort(e+1,e+m+1);

37     aa=0; bb=0;

38     for(int i=1;i<=n;i++) f[i]=i;

39     for(int i=1;i<=m;i++){

40         int fu=getf(e[i].u),fv=getf(e[i].v);

41         if(fu==fv) continue;

42         f[fv]=fu;

43         aa+=e[i].a; bb+=e[i].b;

44     }

45     ans=max(ans,sqrt(aa*aa+bb*bb));

46 }

47 signed main(){

48     freopen("mst.in","r",stdin);

49     freopen("mst.out","w",stdout);

50     n=read(); m=read();

51     for(int i=1;i<=m;i++)

52         e[i].u=read(),e[i].v=read(),e[i].a=read(),e[i].b=read();

53     for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) if(i!=j){

54         double tn=1.0*(e[i].a-e[j].a)/(e[i].b-e[j].b);

55         double ar=atan(tn);

56         arr.push_back(ar), arr.push_back(ar+acos(-1));

57     }

58     sort(arr.begin(),arr.end());

59     for(int i=0;i<arr.size()-1;i++){

60         int j=i+1;

61         double mid=(arr[i]+arr[j])/2;

62         for(int k=1;k<=m;k++) e[k].val=1.0*e[k].a*cos(mid)+1.0*e[k].b*sin(mid);

63         kruscal();

64     }

65     printf("%.6lf",ans);

66     return 0;

67 }

T4

2021.9.17考试总结[NOIP模拟55]的相关教程结束。