F-Partition problem
https://ac.nowcoder.com/acm/contest/882/F
题意：输入一个数n，代表总共有2n个人，然后每个人对所有人有个贡献值，然后问题需要将2n个人分成两组，每组n个人，问如何分组使得两组之间的价值最大，同组人不算价值。
思路：直接dfs暴力分组。
//aeha
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const int inf = 0x3f3f3f3f;
int dir[][]={{,},{,},{,},{,-},{-,},{-,-},{,-},{-,}};
#define pi acos(-1)
#define ls rt<<1
#define rs rt<<1|1
#define me0(s) memset(s,0,sizeof(s))
#define me1(s) memset(s,1,sizeof(s))
#define mef(s) memset(s,-1,sizeof(s))
#define meinf(s) memset(s,inf,sizeof(s))
const int N=;
ll ans;
int n;
int t1[],t2[];
int a[N],b[N],v[N][N];
inline int read() {
char c=getchar(); int x=, f=;
while(c<''|c>'') {if(c=='-') f=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*f;
}
ll q_pow(ll a,ll b,ll mod){
ll anss=;
while(b){
if(b&) anss=anss*a%mod;
a=a*a%mod;
b>>=;
}
return anss;
}
ll q_mul(ll a,ll b,ll mod){
ll anss=;
while(b){
if(b&) anss=(anss+a)%mod;
a=(a+a)%mod;
b>>=;
}
return anss;
}
void dfs(int pos,int cnt1,int cnt2,ll ret){
// pos表示当前搜的人的序号，cnt1表示第一组的人数，cnt2表示第二组的人数，ret表示贡献
if(cnt1==cnt2&&cnt1==n){
ans=max(ans,ret);
return ;
}
ll tmp=;
if(cnt1<n){
for(int i=;i<cnt2;i++){
tmp+=v[pos][t2[i]];
}
t1[cnt1]=pos;
dfs(pos+,cnt1+,cnt2,ret+tmp);
}
tmp=;
if(cnt2<n){
for(int i=;i<cnt1;i++){
tmp+=v[pos][t1[i]];
}
t2[cnt2]=pos;
dfs(pos+,cnt1,cnt2+,ret+tmp);
}
}
int main(int argc, char * argv[])
{
std::ios::sync_with_stdio(false);
cin>>n;
ans=;
for(int i=;i<*n;i++){
for(int j=;j<*n;j++){
cin>>v[i][j];
}
}
dfs(,,,);
cout<<ans<<endl;
return ;
}
H-Second Large Rectangle
https://ac.nowcoder.com/acm/contest/882/H
题意：给定一个n*m的矩阵，其中全由0,1两个数字组成，问找到的第二大的全由1组成的矩阵的面积是多少。
思路：先用单调栈的求第一大矩阵的模板，然后在后面的时候修改一下 ，将各种状态保存下来，注意去重。然后输出第二大的面积就行。
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const int inf = 0x3f3f3f3f;
#define pi acos(-1)
#define ls rt<<1
#define rs rt<<1|1
#define me0(s) memset(s,0,sizeof(s))
#define me1(s) memset(s,1,sizeof(s))
#define mef(s) memset(s,-1,sizeof(s))
#define meinf(s) memset(s,inf,sizeof(s))
const int N=;
char a[][];
int h[];
int L[],R[];
map<int,int> ma;
bool v[][];
inline int read() {
char c=getchar(); int x=, f=;
while(c<''|c>'') {if(c=='-') f=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*f;
}
ll q_pow(ll a,ll b,ll mod){
ll anss=;
while(b){
if(b&) anss=anss*a%mod;
a=a*a%mod;
b>>=;
}
return anss;
}
ll q_mul(ll a,ll b,ll mod){
ll anss=;
while(b){
if(b&) anss=(anss+a)%mod;
a=(a+a)%mod;
b>>=;
}
return anss;
}
int main(int argc, char * argv[])
{
std::ios::sync_with_stdio(false);
int n,m;
while(cin>>n>>m){
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
cin>>a[i][j];
}
}
int maxn=;
for(int i=;i<=n;i++){
me0(v);
for(int j=;j<=m;j++){
if(a[i][j]=='')
h[j]++;
else h[j]=;
}
h[]=h[m+]=-;
stack<int>s;
for(int j=;j<=m;j++){
L[j]=;
if(s.size()==){
s.push(j);
L[j]=j;
}
else{
while(s.size()>&&h[s.top()]>=h[j])
s.pop();
if(s.size()==) L[j]=;
else L[j]=s.top()+;
s.push(j);
}
}
while(!s.empty()){
s.pop();
}
for(int j=m;j>=;j--){
R[j]=m;
if(s.size()==){
s.push(j);R[j]=j;
}
else{
while(s.size()>&&h[s.top()]>=h[j])s.pop();
if(s.size()==)R[j]=m;
else R[j]=s.top()-;
s.push(j);
}
}
for(int j=;j<=m;j++){
if(!v[L[j]][R[j]]){
ma[h[j]*(R[j]-L[j]+)]++;
v[L[j]][R[j]]=;
ma[h[j]*(R[j]-L[j])]++;
ma[(h[j]-)*(R[j]-L[j]+)]++;
}
if(h[j]*(R[j]-L[j]+)>maxn)
maxn=h[j]*(R[j]-L[j]+);
}
}
int flag=,ans,pos;
for(int i=maxn;i>=;i--){
if(ma[i]&&ma[i]>){
ans=i;
flag=;
break;
}
else if(ma[i]&&ma[i]==){
pos=i;
break;
}
}
if(flag) cout<<ans<<endl;
else{
for(int i=pos-;i>=;i--){
if(ma[i]){
ans=i;
break;
}
}
cout<<ans<<endl;
}
}
return ;
}