spoj MINSUB - Largest Submatrix 题解

发表于 2017-01-18 | 分类于 ACM题解 |

原题

题目大意

给定一个由非负整数构成的矩阵，要求寻找一个子矩阵，使得该子矩阵中的最小元素尽可能大，并且面积至少为k（k为给定的一个整数）。

分析

我们不妨二分子矩阵中的最大元素，将大于等于二分值的设为1，将小于二分值的设为0，然后就在这个01矩阵中寻找面积最大的子矩阵和k进行比较。问题就转化为在01矩阵上求最大子矩阵面积，可以参考全是1的最大子矩阵，通过这个方法，就能解决了。

参考代码

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
#include<climits>
using namespace std;
int n,m,k;
int a[1005][1005];
int area;
int f[1005][1005];
int U[1005],D[1005];
bool judge(int mid){
	memset(f,0,sizeof f);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(a[i][j]>=mid) f[i][j]=f[i][j-1]+1;
			else f[i][j]=0;
	area=0;
	for(int j=1;j<=m;++j){
		for(int i=1;i<=n;++i){
			int tmp=i-1;
			while(tmp&&f[i][j]<=f[tmp][j]) tmp=U[tmp];
			U[i]=tmp;
		}
		for(int i=n;i>0;--i){
			int tmp=i+1;
			while(tmp!=n+1&&f[i][j]<=f[tmp][j]) tmp=D[tmp];
			D[i]=tmp;
		}
		for(int i=1;i<=n;++i)
			area=max(area,(D[i]-U[i]-1)*f[i][j]);
	}
	return area>=k;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d %d %d",&n,&m,&k);
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				scanf("%d",&a[i][j]);
			}
		}
		int l=0,r=INT_MAX,pos;
		while(l<=r){
			int mid=(l+r)>>1;
			if(judge(mid)){
				pos=mid;
				l=mid+1;
			} else
				r=mid-1;
		}
		judge(pos);
		printf("%d %d\n",pos,area);
	}
	return 0;
}

51nod 1158 全是1的最大子矩阵题解

发表于 2017-01-17 | 分类于 ACM题解 |

原题

传送门

题目大意

给一个矩阵，这个矩阵中的每个元素不是1就是0，问在这个矩阵中元素全是1的子矩阵的最大面积。

分析

首先，预处理每个元素向左有多少个1，这样的话，就得到了一个新的数组，不妨记为a[i][j]，通过这个数组可以快速查找以该列为右边界的最大矩形面积了。
对于每个元素（可以成为基准元素），我们以它所在列为右边界，通过a数组，知道它左边有多少个1，就以这个作为矩形的宽，那么就只要寻找上下边界就可以了，因为要构成矩形，所以，沿着右边界上下寻找，要求找到元素的a值要大于基准元素，因为只有这样才能保证矩形的完整。
通过上面的方法，只要枚举每个元素，这个问题就解决了。（在寻找上下边界时，要充分利用已经计算过的值，加快寻找，具体看代码）

参考代码

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<vector>
#include<map>
using namespace std;
int a[505][505];
int U[505],D[505];
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	memset(a,0,sizeof a);
	for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%d",&a[i][j]);
            if(a[i][j]){
                //统计向左有多少个1
                a[i][j]=a[i][j-1]+1;
            }
        }
	}
	int ans=0;
	for(int j=1;j<=m;++j){
        //j就是矩形的右边界
        for(int i=1;i<=n;++i){
            int tmp=i-1;
            //向上寻找对于这个i的上边界
            while(tmp&&a[i][j]<=a[tmp][j]) tmp=U[tmp];//加速过程
            U[i]=tmp;
        }
        for(int i=n;i>0;--i){
            int tmp=i+1;
            //向下寻找对于这个i的下边界
            while(tmp!=n+1&&a[i][j]<=a[tmp][j]) tmp=D[tmp];//加速过程
            D[i]=tmp;
        }
        for(int i=1;i<=n;++i){
            ans=max(ans,(D[i]-U[i]-1)*a[i][j]);
        }
	}
	printf("%d\n",ans);
	return 0;
}

spoj INTSUB - Interesting Subset 题解

发表于 2017-01-15 | 分类于 ACM题解 |

原题

传送门

题目大意

一个由1，2，3……2n组成的集合，问它由多少个子集满足以下条件：该子集包含a、b，其中a是该子集中最小的元素，b是a的倍数

分析

首先考虑，显然可以枚举最小元素k（1……n），对于任意一个k，它的倍数的个数为2n/k-1，对于这些倍数，至少要取一个，那么一共有2^（（2n/k-1）-1）（就是所有的可能减去一个空集的可能），剩下的元素可取可不取，那么一共有2^(2n-i-2*n/i+1)，再根据乘法原理，相乘就是答案。

参考代码

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
const int mod=1000000007;
long long f[2010];
void getf(){
	f[0]=1;
	for(int i=1;i<2010;++i){
		f[i]=(f[i-1]<<1)%mod;
	}
}
int main(){
	int T;
	scanf("%d",&T);
	int icase=0;
	getf();
	while(T--){
		int n;
		scanf("%d",&n);
		long long ans=0;
		for(int i=1;i<=n;++i){
			ans=(ans+(f[2*n/i-1]-1)*(f[2*n-i-2*n/i+1])%mod)%mod;
		}
		printf("Case %d: %lld\n",++icase,ans);
	}
	return 0;
}

spoj STARSBC - Star 题解

发表于 2017-01-15 | 分类于 ACM题解 |

原题

传送门

题目大意

一个圆上有n等分点，选定一个为起点后，每隔k个点连一条边，要求所有点都经过的不同图形有多少个。

分析

首先，所有和n有公因数的k是不可行的，当然1除外。
此时的答案显然是n的欧拉函数+1（即1），但还要去除图案重复的。
其次，通过顺时针和逆时针观察，发现k和n-k的图案是相同的，所以，最终的答案是欧拉函数+1的一半

参考代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<vector>
using namespace std;
long long eular(long long n)
{
    long long ans=n;
    for(int i=2;i<=n/i;i++)
    {
        if(n%i==0)
        {
            ans-=ans/i;
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1) ans-=ans/n;
    return ans;
}
int main()
{
    long long n;
    while(scanf("%lld",&n)!=EOF)
    {
        long long ans=(eular(n)+1)/2;
        printf("%lld\n",ans);
    }
	return 0;
}

spoj KAOS - Kaos 题解

发表于 2017-01-15 | 分类于 ACM题解 |

原题

传送门

题目大意

给定一些字符串，要求找出符合要求的(s1,s2)的对数。
1、按照字典序，s1>s2
2、按照字典序，s1翻转后小于s2翻转后（若s1=”abc”，则翻转后为”cba”）

分析

一个要求很好满足，将字符串排序后，那么排在s1前面的字符串都会和s1满足要求一，只要在其中找到满足要求二的即可。
我们很容易想到trie树，将排序后的字符串，翻转后插入字典树中，并一遍统计满足要求二的，就能得到答案。

参考代码

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
const int maxn=100000+10;
struct node{
	int next[26];
	int cnt;
	void init(){
		cnt=0;
		memset(next,0,sizeof next);
	}
}T[maxn*20];
int tot;
void insert(string s){
    reverse(s.begin(),s.end());
	int i=0,p=0;
	while(s[i]){
		int x=s[i]-'a';
		if(T[p].next[x]==0){
			T[tot].init();
			T[p].next[x]=tot++;
		}
		p=T[p].next[x];
		T[p].cnt++;
		i++;
	}
}
int getans(string s)
{
    reverse(s.begin(),s.end());
    int now=0,ans=0;
    int i=0;
    while(s[i])
    {
        int x=s[i]-'a';
        for(int j=x+1;j<26;++j)
        {
            ans+=T[T[now].next[j]].cnt;
        }
        now=T[now].next[x];
        i++;
    }
    for(int j=0;j<26;++j)
    {
        ans+=T[T[now].next[j]].cnt;
    }
    return ans;
}
string s[maxn];
int main(){
	int n;
	scanf("%d",&n);
	tot=1;
	for(int i=0;i<n;++i)
    {
        cin>>s[i];
    }
    sort(s,s+n);
    long long ans=0;
    T[0].init();
    for(int i=0;i<n;++i)
    {
        insert(s[i]);
        ans+=getans(s[i]);
    }
    printf("%lld\n",ans);
	return 0;
}