T1 洛希极限
上来一道大数据结构或者单调队列优化$dp$
真就没分析出来正解复杂度
正解复杂度$O(q+nm)$，但是据说我的复杂度是假的
考虑一个点转移最优情况是从它上面的一个反$L$形转移过来
然后维护一个冰茶姬，处理出$le,dw$数组就可以单调队列优化$dp$了
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 #define int long long
6 using namespace std;
7 namespace AE86{
8 inline int read(){
9 int x=0,f=1;char ch=getchar();
10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
12 }inline void write(int x,char opt='\n'){
13 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
14 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
15 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
16 }using namespace AE86;
17
18 const int NN=2005,mod=1e9+7,inf=0x7fffffff;
19 int T,n,m,q;
20 struct Ma{int r1,c1,r2,c2;}a[500005];
21
22 int f[NN][NN],g[NN][NN];
23 int le[NN][NN],dw[NN][NN];
24 int nxt[NN][NN];
25
26 struct Queue{
27 #define hang 1
28 #define lie 0
29 int q[NN],h,t,bin,pos; bool opt;
30 inline void calc_h(){
31 if(h==t) return bin=0,void();
32 if(opt==hang){
33 if(f[q[h]][pos]==f[q[h+1]][pos]) bin=(bin-g[q[h]][pos]+mod)%mod;
34 else{
35 bin=0; int i=h+1;
36 while(f[q[i]][pos]==f[q[h+1]][pos]&&i<=t) bin=(bin+g[q[i]][pos])%mod,++i;
37 }
38 }else{
39 if(f[pos][q[h]]==f[pos][q[h+1]]) bin=(bin-g[pos][q[h]]+mod)%mod;
40 else{
41 bin=0; int i=h+1;
42 while(f[pos][q[i]]==f[pos][q[h+1]]&&i<=t) bin=(bin+g[pos][q[i]])%mod,++i;
43 }
44 }
45 }
46 inline void calc_t(int val){
47 if(opt==hang)
48 bin=(bin+g[q[t]][pos]*(f[q[t]][pos]==f[q[h]][pos])*val+mod)%mod;
49 else
50 bin=(bin+g[pos][q[t]]*(f[pos][q[t]]==f[pos][q[h]])*val+mod)%mod;
51 }
52 inline void clear(){h=1; t=0; bin=0;} inline bool empty(){return h>t;}
53 inline int front(){return h>t?0:q[h];} inline int back(){return h>t?0:q[t];} inline int sum(){return bin;}
54 inline void pop_front(){calc_h();++h;} inline void pop_back(){calc_t(-1);--t;}
55 inline void push_back(int v){q[++t]=v;calc_t(1);}
56 }r[NN],c[NN];
57
58 int ans1,ans2;
59 inline int gx(int x,int y){return nxt[x][y]==x?x:nxt[x][y]=gx(nxt[x][y],y);}
60 inline int gy(int x,int y){return nxt[x][y]==y?y:nxt[x][y]=gy(x,nxt[x][y]);}
61
62 inline void prework(){
63 ans1=ans2=0;
64 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[i][j]=g[i][j]=0,le[i][j]=dw[i][j]=inf;
65 for(int i=1;i<=n;i++) r[i].clear(),f[i][1]=g[i][1]=1;
66 for(int i=1;i<=m;i++) c[i].clear(),f[1][i]=g[1][i]=1;
67 sort(a+1,a+q+1,[](Ma a,Ma b)->bool{return a.r1<b.r1;});
68 for(int i=1;i<=n+1;i++) for(int j=1;j<=m+1;j++) nxt[i][j]=i;
69 for(int i=1;i<=q;i++)
70 for(int j=a[i].c1+1;j<=a[i].c2;j++)
71 for(int k=gx(a[i].r1+1,j);k<=a[i].r2;k=gx(k+1,j))
72 le[k][j]=a[i].r1,nxt[k][j]=gx(k+1,j);
73 sort(a+1,a+q+1,[](Ma a,Ma b)->bool{return a.c1<b.c1;});
74 for(int i=1;i<=n+1;i++) for(int j=1;j<=m+1;j++) nxt[i][j]=j;
75 for(int i=1;i<=q;i++)
76 for(int j=a[i].r1+1;j<=a[i].r2;j++)
77 for(int k=gy(j,a[i].c1+1);k<=a[i].c2;k=gy(j,k+1))
78 dw[j][k]=a[i].c1,nxt[j][k]=gy(j,k+1);
79 }
80
81 namespace WSN{
82 inline short main(){
83 freopen("roche.in","r",stdin); freopen("roche.out","w",stdout);
84 T=read(); for(int i=1;i<NN;i++) r[i].opt=lie,c[i].opt=hang,r[i].pos=c[i].pos=i;
85 while(T--){
86 n=read();m=read();q=read();
87 for(int i=1;i<=q;i++) a[i].r1=read(),a[i].c1=read(),a[i].r2=read(),a[i].c2=read();
88 prework();
89 for(int i=2;i<=n;i++) for(int j=2;j<=m;j++){
90 while(!r[i-1].empty()&&f[i-1][r[i-1].back()]<f[i-1][j-1]) r[i-1].pop_back();
91 r[i-1].push_back(j-1);
92 while(!r[i-1].empty()&&r[i-1].front()<dw[i][j]) r[i-1].pop_front();
93 f[i][j]=f[i-1][r[i-1].front()]+1; g[i][j]=max(1ll,r[i-1].sum());
94
95 while(!c[j-1].empty()&&f[c[j-1].back()][j-1]<f[i-2][j-1]) c[j-1].pop_back();
96 c[j-1].push_back(i-2);
97 while(!c[j-1].empty()&&c[j-1].front()<le[i][j]) c[j-1].pop_front();
98 if(f[i][j]==f[c[j-1].front()][j-1]+1) g[i][j]=(g[i][j]+c[j-1].sum())%mod;
99 else if(f[i][j]<f[c[j-1].front()][j-1]+1) f[i][j]=f[c[j-1].front()][j-1]+1,g[i][j]=max(1ll,c[j-1].sum());
100 }
101 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans1=max(ans1,f[i][j]);
102 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(f[i][j]==ans1) ans2=(ans2+g[i][j])%mod;
103 write(ans1,' '); write(ans2);
104 }
105 return 0;
106 }
107 }
108 signed main(){return WSN::main();}
View Code
T2 特立独行的图
咕咕咕，没学过差分约束，正在学习
T3 玩游戏
又要写流水账了。。。。
毕竟考试的时候狂肝$3$小时，不写一写也对不住自己
但还是以后不要刚题了，会出事的。。。。会$\huge{爆蛋蛋！！}$
发现给的样例都不能手玩，于是就自己在纸上玩了$n=1,2,3,4$的样例，
刚开始发现像$LIS$，后来打完发现$n=4$的唯一一组数据不对$1,3,4,2$
然后就蒙了，然后就开始杠了，然后就死了。就是没发现他是个单调栈的操作。。。
先说说怎么玩，比如$2,3,1$这种情况是剩下来一个人的
第二个人不知道自己拿$3$，但是他发现前面是个$2$，自己后面是有$1,3$两个数字的
那么他肯定是想要保底留下一个$2$，不至于被后面的$1$换走
按照这个思路手玩发现单调找然后出来调和级数是可以的
但是打表他更快，但不推荐使用
题解上的证明始终觉得过于麻烦了，而且不知道有没有问题，看到那个关键时刻就转不过来弯了
所以口胡一下自己的理解：
题目里说每个人绝顶聪明，那么他们一定不会去干一些可能亏本的买卖
如果当他前面的出现的数字的最大值大于后面出现的（包括自己）数字的最小值时，
他就会觉得有一定风险自己会被后面的那个最小值换掉，因为不难发现这个前面数字的最大值是单调递减的，
他如果不换，他就有可能会死，就是这样，那么他肯定不会去冒风险去赌自己会不会更好，而是选择保底
这样的话就有一个结论，设$maxP$为出现数字的集合里的最大值，$minR$为未出现数字集合的最小值
当$maxP<minR$时，选择操作$1$，否则操作$2$
设$suf_i$表示从$i$开始的后缀中的元素最小值
那么进一步推导(或者说发现）得出执行操作一的条件实际上是$[a_i=suf_i]$
所以题目转化为求所有排列中$\sum[a_i=suf_i]$，然后可以推出调和级数
然后用我们看不懂的求导式子化简出一种$S_k(n)$的求解式。
和直接给出一种想不到的答案式，可以用归纳法证明（听说）
然后题解说啥我干啥
1 #include<cmath>
2 #include<algorithm>
3 #include<iostream>
4 #define int long long
5 typedef long double D;
6 using namespace std;
7 const D r=0.57721566490153286060651209;
8 int k,n;
9 inline D H(int n){return log(n)+r+1.0/(2.0*n);}
10 double S[51][1000005];
11 D h[51];
12 D getans(int k,int n){
13 if(n<=1e6){
14 for(int i=1;i<=n;i++) S[0][i]=S[0][i-1]+1.0/i;
15 for(int i=1;i<=k;i++){
16 double res=0.0;
17 for(int j=1;j<=n;j++){
18 res+=S[i-1][j];
19 S[i][j]=res;
20 }
21 }
22 return S[k][n];
23 }
24 if(n>1e6 && k==0) return log(n)+r+1.0/(2.0*n);
25 for(int i=1;i<=k;i++) h[i]=h[i-1]+1.0/i;
26 D ans=(H(n)-h[k]);
27 for(int i=k;i;i--) ans=ans*(1.0*n)/(1.0*i);
28 return ans;
29 }
30 namespace WSN{
31 inline short main(){
32 freopen("game.in","r",stdin);
33 freopen("game.out","w",stdout);
34 cout.unsetf(ios::fixed);
35 cout.setf(ios::scientific);
36 cout.precision(9);
37 cin>>k>>n;
38 cout<<getans(k,n)<<endl;
39 return 0;
40 }
41 }
42 signed main(){return WSN::main();}
View Code
T4 骆驼
大模拟构造题，没啥好说的，
暴力建矩阵，脑洞造方案，切题有快感，给题解点赞
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 int n,m;
5 int g[8][6][6]={
6 {
7 {0,0,0,0,0,0},
8 {0,0,0,0,0,0},
9 {0,0,0,0,0,0},
10 {0,0,0,0,0,0},
11 {0,0,0,0,0,0},
12 {0,0,0,0,0,0},
13 },
14 {
15 {0, 0, 0, 0, 0, 0},
16 {0, 2, 9, 6, 3,10},
17 {0,16,21,24,13,18},
18 {0, 7, 4, 1, 8, 5},
19 {0,23,12,17,22,11},
20 {0,15,20,25,14,19},
21 },//从上往下 1
22 {
23 {0, 0, 0, 0, 0, 0},
24 {0, 2,18,25, 3,17},
25 {0,23,12,15,20,11},
26 {0, 7, 4, 1, 8, 5},
27 {0,14,19,24,13,16},
28 {0,22, 9, 6,21,10},
29 },//从下往上 2
30 {
31 {0, 0, 0, 0, 0, 0},
32 {0, 2,12,15, 3,11},
33 {0, 7,20,23, 8,17},
34 {0,14, 4, 1,13,25},
35 {0,22, 9,16,21,10},
36 {0, 6,19,24, 5,18},
37 },//从左往右 3
38 {
39 {0, 0, 0, 0, 0, 0},
40 {0, 2,15, 6, 3,14},
41 {0, 8,20,23,11,19},
42 {0,25, 4, 1,16, 5},
43 {0,22,12, 7,21,13},
44 {0, 9,17,24,10,18},
45 },//从右往左 4
46 {
47 {0, 0, 0, 0, 0, 0},
48 {0,22, 3, 9,23, 2},
49 {0,16,25,20,17, 7},
50 {0,10,13, 1, 4,12},
51 {0,21,18, 8,24,19},
52 {0,15, 5,11,14, 6},
53 },//奇数右下角 5
54 {
55 {0, 0, 0, 0, 0, 0},
56 {0, 1,19, 7, 4,20},
57 {0,14,11,22,17,12},
58 {0, 8, 5, 0, 9, 6},
59 {0, 2,18,13, 3,21},
60 {0,15,10,23,16, 0},
61 },//奇数起点 6
62 {
63 {0, 0, 0, 0, 0, 0},
64 {0, 1, 6,13,16, 5},
65 {0,11,18, 3, 8,19},
66 {0,23,15, 0,22,14},
67 {0, 2, 7,12,17, 4},
68 {0,10,21,24, 9,20},
69 }
70 //偶数起点 7
71 };
72 const int NN=1005;
73 int ans[NN][NN],sum;
74 inline void update(int x,int y,int id,int sum){
75 for(int i=x;i<=x+4;i++)
76 for(int j=y;j<=y+4;j++)
77 ans[i][j]=g[id][i-x+1][j-y+1]+sum;
78 }
79 inline void print(){
80 for(int i=1;i<=n;i++){
81 for(int j=1;j<=n;j++){
82 printf("%3d ",ans[i][j]);
83 } puts("");
84 }
85 }
86 inline void even(){
87 update(1,1,7,0); sum=24;
88 for(int i=2;i<m;i++) update(1+5*(i-1),1,1,sum),sum+=25;
89 for(int i=1;i<m;i++) update(1+5*(m-1),1+5*(i-1),3,sum),sum+=25;
90 update(1+5*(m-1),1+5*(m-1),2,sum); sum+=25;
91 for(int i=m-1;i>=1;i--){
92 if(i&1){
93 for(int j=m;j>1;j--){
94 if(i==1&&j==2) update(1+5*(i-1),1+5*(j-1),4,sum);
95 else if(j==2) update(1+5*(i-1),1+5*(j-1),2,sum);
96 else update(1+5*(i-1),1+5*(j-1),4,sum);
97 sum+=25;
98 }
99 }else{
100 for(int j=2;j<=m;j++){
101 if(j==m) update(1+5*(i-1),1+5*(j-1),2,sum);
102 else update(1+5*(i-1),1+5*(j-1),3,sum);
103 sum+=25;
104 }
105 }
106 }
107 ans[3][3]=n*n;
108 print();
109 }
110 inline void odd(){
111 update(1,1,6,0); sum=23;
112 for(int i=2;i<m;i++) update(1+5*(i-1),1,1,sum),sum+=25;
113 for(int i=1;i<m;i++) update(1+5*(m-1),1+5*(i-1),3,sum),sum+=25;
114 update(1+5*(m-1),1+5*(m-1),2,sum); sum+=25;
115 for(int i=m-1;i>2;i--){
116 if(i&1){
117 for(int j=2;j<=m;j++){
118 if(j==m) update(1+5*(i-1),1+5*(j-1),2,sum);
119 else update(1+5*(i-1),1+5*(j-1),3,sum);
120 sum+=25;
121 }
122 }else{
123 for(int j=m;j>1;j--){
124 if(j==2) update(1+5*(i-1),1+5*(j-1),2,sum);
125 else update(1+5*(i-1),1+5*(j-1),4,sum);
126 sum+=25;
127 }
128 }
129 }
130 for(int i=m;i>2;i--){
131 if(i&1){
132 update(6,1+5*(i-1),2,sum);sum+=25;
133 update(1,1+5*(i-1),4,sum);sum+=25;
134 }else{
135 update(1,1+5*(i-1),1,sum);sum+=25;
136 update(6,1+5*(i-1),4,sum);sum+=25;
137 }
138 }
139 update(1,6,1,sum); sum+=25;
140 update(6,6,5,sum); sum+=25;
141 ans[3][3]=n*n; ans[5][5]=n*n-1;
142 print();
143 }
144 namespace WSN{
145 inline short main(){
146 freopen("camel.in","r",stdin);
147 freopen("camel.out","w",stdout);
148 scanf("%d",&n); m=n/5;
149 if(n==5){
150 puts("1 11 18 4 10");
151 puts("16 22 8 13 23");
152 puts("19 5 25 20 6");
153 puts("2 12 17 3 9");
154 puts("15 21 7 14 24");
155 return 0;
156 }
157 if(n&1) return odd(),0;
158 even();
159 return 0;
160 }
161 }
162 signed main(){return WSN::main();}
View Code