比赛总结：
看错F题意@byf
要勇于打表找规律
题解(不定更新)
A EddyWalker
B EddyWalker2
C Go on Strike!
D Kth Minimum Clique
E MAZE
F Partition problem
题解：https://blog.csdn.net/liufengwei1/article/details/96729137
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 int n;
5 long long ans;
6 int aa[30],bb[30];
7 int v[30][30];
8 long long f[30][1<<18];
9 long long sum[30];
10 int num[1<<18];
11
12 inline void prework()
13 {
14 for(int i=0,x=1;i<18;i++,x<<=1)
15 num[x]=i;
16 scanf("%d",&n);
17 for(int i=0;i<2*n;i++)
18 for(int j=0;j<2*n;j++)
19 scanf("%d",&v[i][j]),sum[i+1]+=v[i][j];
20 for(int i=1;i<=2*n;i++)
21 sum[i]=sum[i-1]+sum[i];
22 int l,s,d;
23 for(int i=0;i<2*n;i++)
24 {
25 l=1<<(min(2*n,18));
26 for(int j=1;j<l;j++)
27 {
28 s=j;
29 while(s)
30 {
31 d=s&-s;
32 f[i][j]+=v[i][num[d]];
33 s-=d;
34 }
35 }
36 }
37 }
38
39 inline void dfs(int k,int as,int bs,int acnt,long long w)
40 {
41 if(acnt+2*n-1-k+1<n || k-acnt+2*n-1-k+1<n)
42 return;
43 if(w+sum[2*n]-sum[k+1-1]<ans)
44 return;
45 if(w>ans)
46 ans=w;
47 if(k>=2*n)
48 return;
49 long long tmp=0;int tas,tbs;
50 if(k>=18)
51 {
52 aa[++aa[0]]=k;
53 tmp=w+f[k][bs];
54 for(int i=1;i<=bb[0];i++)
55 tmp+=v[k][bb[i]];
56 dfs(k+1,as,bs,acnt+1,tmp);
57 aa[aa[0]--]=0;
58
59 bb[++bb[0]]=k;
60 tmp=w+f[k][as];
61 for(int i=1;i<=aa[0];i++)
62 tmp+=v[k][aa[i]];
63 dfs(k+1,as,bs,acnt,tmp);
64 bb[bb[0]--]=0;
65 }
66 else
67 {
68 dfs(k+1,as|(1<<k),bs,acnt+1,w+f[k][bs]);
69 dfs(k+1,as,bs|(1<<k),acnt,w+f[k][as]);
70 }
71 }
72
73 inline void mainwork()
74 {
75 dfs(0,0,0,0,0);
76 }
77
78 inline void print()
79 {
80 printf("%lld",ans);
81 }
82
83 int main()
84 {
85 prework();
86 mainwork();
87 print();
88 return 0;
89 }
View Code
G Polygons
H Second Large Rectangle
题解：https://blog.csdn.net/liufengwei1/article/details/96730426
1 #include<bits/stdc++.h>
2 #define maxl 1010
3
4 using namespace std;
5
6 int n,m,top,mx,mx1,my1,mx2,my2,secmx;
7 int s[maxl],h[maxl],l[maxl],r[maxl];
8 int a[maxl][maxl];
9 char ch[maxl];
10
11 inline void prework()
12 {
13 scanf("%d%d",&n,&m);
14 for(int i=1;i<=n;i++)
15 {
16 scanf("%s",ch+1);
17 for(int j=1;j<=m;j++)
18 a[i][j]=ch[j]-'0';
19 }
20 }
21
22 inline void solve1()
23 {
24 mx=0;int tmp;
25 for(int i=1;i<=m;i++)
26 h[i]=0;
27 for(int i=1;i<=n;i++)
28 {
29 for(int j=1;j<=m;j++)
30 if(a[i][j]==1)
31 h[j]++;
32 else
33 h[j]=0;
34 top=0;
35 for(int j=1;j<=m;j++)
36 {
37 while(top>0 && h[s[top]]>h[j])
38 r[s[top]]=j-1,--top;
39 l[j]=s[top]+1;
40 s[++top]=j;
41 }
42 while(top>0)
43 r[s[top]]=m,--top;
44 for(int j=1;j<=m;j++)
45 if(h[j])
46 {
47 tmp=h[j]*(r[j]-l[j]+1);
48 if(tmp>mx)
49 {
50 mx=tmp;
51 mx1=i-h[j]+1;my1=l[j];
52 mx2=i;my2=r[j];
53 }
54 }
55 }
56 }
57
58 inline void solve2()
59 {
60 secmx=0;int tmp,tx1,tx2,ty1,ty2;
61 for(int i=1;i<=m;i++)
62 h[i]=0;
63 for(int i=1;i<=n;i++)
64 {
65 for(int j=1;j<=m;j++)
66 if(a[i][j]==1)
67 h[j]++;
68 else
69 h[j]=0;
70 top=0;
71 for(int j=1;j<=m;j++)
72 {
73 while(top>0 && h[s[top]]>h[j])
74 r[s[top]]=j-1,--top;
75 l[j]=s[top]+1;
76 s[++top]=j;
77 }
78 while(top>0)
79 r[s[top]]=m,--top;
80 for(int j=1;j<=m;j++)
81 if(h[j])
82 {
83 tx1=i-h[j]+1;ty1=l[j];
84 tx2=i;ty2=r[j];
85 tmp=h[j]*(r[j]-l[j]+1);
86 if(mx1!=tx1 || my1!=ty1 || mx2!=tx2 || my2!=ty2)
87 secmx=max(tmp,secmx);
88 secmx=max(secmx,(h[j]-1)*(r[j]-l[j]+1));
89 secmx=max(secmx,h[j]*(r[j]-l[j]));
90 }
91 }
92 }
93
94 inline void mainwork()
95 {
96 solve1();
97 solve2();
98 }
99
100 inline void print()
101 {
102 printf("%d\n",secmx);
103 }
104
105 int main()
106 {
107 prework();
108 mainwork();
109 print();
110 return 0;
111 }
View Code
I Inside A Rectangle
J Subarray
题解：https://blog.csdn.net/liufengwei1/article/details/96836978
1 //牛逼网友的J
2 #include<bits/stdc++.h>
3 using namespace std;
4 typedef long long ll;
5 const int INF = 0x3f3f3f3f;
6 const int MAXN = 10000000, MAXM = 1000000;
7
8 int l[MAXM + 5], r[MAXM + 5], f[MAXM + 5], g[MAXM + 5];
9 int sum[MAXN * 3 + 5], b[MAXN * 3 + 5], c[MAXN * 3 + 5];
10
11 int main()
12 {
13 int n;
14 scanf("%d",&n);
15 for(int i=1;i<=n;i++)
16 scanf("%d%d",&l[i],&r[i]);
17 f[1]=r[1]-l[1]+1;
18 //f[i]以i段右端点为结尾的能构造出的最大的前缀和
19 for(int i=2;i<=n;i++)
20 f[i]=max(0,f[i-1]-(l[i]-r[i-1]-1))+r[i]-l[i]+1;
21 //0：以i-1段右端点结尾的能构造出的最大的前缀和都不足够跨过[i-1,i]之间的-1
22 //f[i - 1] - (l[i] - r[i - 1] - 1)：跨过之后还剩下多少贡献给这段
23 g[n]=r[n]-l[n]+1;
24 //g[i]以i段左端点为开头的能构造出的最大的前缀和
25 for(int i=n-1;i>=1;i--)
26 g[i]=max(0,g[i+1]-(l[i+1]-r[i]-1))+r[i]-l[i]+1;
27 //ERR1(f, n);
28 //ERR1(g, n);
29 int i=1,base=10000000;
30 ll ans=0;
31 while(i<=n)
32 {
33 int j=i+1;
34 while(j<=n && g[j]+f[j-1]>=l[j]-r[j - 1]-1) {
35 //说明这个[j-1,j]之间的-1段可以因为两侧的f[j-1]和g[j]足够大而连接起来
36 j++;
37 }
38 j--;
39 //此时j是从i开始最远能够连接到的区间
40 int left=max(0,l[i]-g[i]),right=min(1000000000-1,r[j]+f[j]);
41 //left,right是至少会产生一个贡献的范围
42 //ERR(left, right);
43 int t=i,mi=INF,mx=0;
44 sum[0]=0;
45 for(int k=left;k<=right;k++)
46 {
47 //统计这一整段可连接区间的前缀和
48 if(k>=l[t] && k<=r[t])
49 sum[k-left+1]=sum[k-left]+1;
50 else
51 sum[k-left+1]=sum[k-left]-1;
52 if(k==r[t])
53 t++;
54 mi=min(mi,sum[k-left+1]+base);
55 mx=max(mx,sum[k-left+1]+base);
56 //b记录前缀和出现过的次数
57 b[sum[k-left+1]+base]++;
58 }
59 //ERR1(sum, right);
60 //b记录前缀和出现过的次数的后缀和
61 for(int k=mx-1;k>=mi;k--)
62 b[k]+=b[k+1];
63 //包含最左侧点的贡献
64 ans+=b[base+1];
65 for(int k=left;k<=right;k++) {
66 t=sum[k-left+1]+base;
67 //t表示k位置sum的值
68 //b[t+1]比t大的值的个数
69 //c[t+1]比在k位置左侧的比t大的值的个数的lazy
70 b[t+1]-=c[t+1]; //把lazy加上去
71 c[t]+=c[t+1]+1; //lazy标记下移
72 c[t+1] = 0; //清空lazy
73 ans+=b[t+1];
74 }
75 for(int k=mi;k<=mx;k++)
76 b[k]=0,c[k]=0;
77 i=j+1;
78 }
79 printf("%lld", ans);
80 return 0;
81 }
View Code