UVa 11572 - Unique Snowflakes
问一个数组中，无重复数字的最长子串长度是多少。
用map维护某数字上次出现的位置。另外用变量last表示上次出现数字重复的位置。
如果出现重复数字，且map[val]>last时，计算当前区间长度，然后last变为map[val]+1。
其他时候增长区间长度即可。
每次遍历一个元素都要更新map[val]，用区间长度更新最优解。
#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<string>
#define INF 1000000000LL
#define ll long long
using namespace std;
map<int,int> mp;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
mp.clear();
int n;
scanf("%d",&n);
,res=,last=;
; i<=n; ++i)
{
int v;
scanf("%d",&v);
int &u=mp[v];
if(!u||u<last) res++;
else
{
res=i-u;
last=u+;
}
u=i;
ans=max(ans,res);
}
printf("%d\n",ans);
}
;
}
UVa 1152 - 4 Values whose Sum is 0
中途相遇法。重点在于写哈希的部分。
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<string>
#define ll long long
using namespace std;
struct Hash_map
{
static const int mask=0x7fffff;
],q[];
void clear()
{
; i<=mask; ++i)
q[i]=;
}
int& operator [](int k)
{
int i;
)&mask);
p[i]=k;
return q[i];
}
};
][];
Hash_map hash;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
hash.clear();
; i<n; ++i)
scanf(][i],&arr[][i],&arr[][i],&arr[][i]);
; i<n; ++i)
; j<n; ++j)
hash[arr[][i]+arr[][j]]++;
;
; i<n; ++i)
; j<n; ++j)
ans+=hash[-(arr[][i]+arr[][j])];
printf("%d\n",ans);
if(T)putchar('\n');
}
;
}
ZOJ 3278 8G Island
给两个数组，A和B，求第k大个Ai*Bj的数字。这里要注意是求第k大，不是第k小。相当于求第n*m-k小数字。
二分答案，统计比该答案小的结果有多少个。这样问题就变成了求一个满足比它小的数超过（n*m-k)的最小数。
需要快速求比该数小的元素个数，这样枚举Ai，再计算b=val/Ai，快速统计比不超过b的Bj有多少个，这样可以求得。可以用二分也可以用前缀和的性质。
注意要用longlong。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
#define LL long long
using namespace std;
LL n,m,K;
const LL maxn= 1e10;
;
vector<int> a,b;
],bsum[];
LL judge(LL val)
{
LL cnt=;
if(a.size()<b.size())
{
; i<a.size(); ++i)
{
LL p=min(val/a[i],maxm);
cnt+=bsum[p];
}
}
else
{
; i<b.size(); ++i)
{
LL p=min(val/b[i],maxm);
cnt+=asum[p];
}
}
return cnt;
}
LL BinSearch(LL low,LL high)
{
LL mid=(low+high)/;
while(low<high)
{
if(judge(mid)>=K) high=mid;
;
mid=(low+high)/;
}
return mid;
}
int main()
{
while(cin>>n>>m>>K)
{
int u;
a.clear();
b.clear();
; i<n; ++i)
{
cin>>u;
a.push_back(u);
}
; i<m; ++i)
{
cin>>u;
b.push_back(u);
}
memset(asum,,sizeof(asum));
memset(bsum,,sizeof(bsum));
; i<a.size(); ++i)
asum[a[i]]++;
; i<=maxm; ++i)
asum[i]+=asum[i-];
; i<b.size(); ++i)
bsum[b[i]]++;
; i<=maxm; ++i)
bsum[i]+=bsum[i-];
K=n*m-K+;
cout<<BinSearch(,maxn)<<endl;
}
;
}
UVa 11491 Erasing and Winning
给一个长度为n的数字，问删掉d个数字后可能取得的最大数字是多少？
思路比较好想，考虑留下的n-d个数字，每次在保证最终可以选到n-d-i个数字的前提下，选最大的数字，这个选数的过程可以用线段树完成，同时维护区间最大值和最大值下标，注意优先选最左边的。复杂度n*logn。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
#define inf -100000000
#define LL long long
#define MAXN 100001<<2
using namespace std;
struct SegmentTree
{
int maxv[MAXN],pos[MAXN];
void push_up(int o)
{
]>=maxv[o<<|])
{
maxv[o]=maxv[o<<];
pos[o]=pos[o<<];
}
else
{
maxv[o]=maxv[o<<|];
pos[o]=pos[o<<|];
}
}
void build(int o,int L,int R)
{
if(L==R)
{
char c=getchar();
maxv[o]=c-';
pos[o]=L;
}
else
{
;
build(o<<,L,M);
build(o<<|,M+,R);
push_up(o);
}
}
int query(int o,int L,int R,int ql,int qr,int &p,int &maxn)
{
if(ql<=L&&R<=qr)
{
if(maxv[o]>maxn)
{
maxn=maxv[o];
p=pos[o];
}
return maxn;
}
else
{
;
,b=;
,L,M,ql,qr,p,maxn);
|,M+,R,ql,qr,p,maxn);
return max(a,b);
}
}
};
SegmentTree tree;
int N,D;
int main()
{
while(scanf("%d%d",&N,&D)!=EOF)
{
if(!N&&!D) break;
getchar();
tree.build(,,N);
getchar();
,pos;
; i<=N-D; ++i)
{
;
,,N,p,d,pos,maxn);
printf("%d",r);
p=pos+;
}
printf("\n");
}
;
}
UVa 787 Maximum Sub-sequence Product
问最大子数组乘积是多少。数据量不大，n^2可做。要用大数，所以写了java。
import java.math.BigInteger;
import java.util.Scanner;
public class Main
{
public static void main(String[] args) {
BigInteger[] a = new BigInteger[101];
for (int i = 0; i <= 100; ++i)
a[i] = new BigInteger("0");
BigInteger maxnBigInteger = new BigInteger("-999999");
Scanner inScanner = new Scanner(System.in);
while (inScanner.hasNextBigInteger()) {
int n = 0;
while (true) {
a[n] = inScanner.nextBigInteger();
if (a[n].compareTo(maxnBigInteger) == 0)
break;
n++;
}
BigInteger ansBigInteger = new BigInteger("1");
ansBigInteger = ansBigInteger.multiply(a[0]);
for (int i = 0; i < n; ++i) {
BigInteger resBigInteger = new BigInteger("1");
for (int j = i; j < n; ++j) {
resBigInteger = resBigInteger.multiply(a[j]);
ansBigInteger = ansBigInteger.max(resBigInteger);
}
}
System.out.println(ansBigInteger);
}
}
}
UVa 11536 Smallest Sub-Array
求一个出现全部1-K的数字的最小数组长度。
分别用一个首、尾指针维护一个区间，使区间内出现要求的全部k个数字。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
#define ll long long
#define INF 2139062143
#define inf -2139062144
#define MOD 20071027
using namespace std;
int N,M,K;
];
],cnt;
bool judge(int a)
{
<=a&&a<=K;
}
int main()
{
;
//freopen("out.txt","w",stdout);
scanf("%d",&T);
a[]=;
a[]=;
a[]=;
while(T--)
{
scanf("%d%d%d",&N,&M,&K);
; i<=N; ++i)
a[i]=(a[i-]+a[i-]+a[i-])%M+;
memset(vis,,sizeof(vis));
cnt=;
;
;
; i<=N; ++i)
{
if(judge(a[i]))
{
) cnt++;
vis[a[i]]++;
}
while(j<=i&&cnt==K)
{
if(!judge(a[j])) j++;
!=)
{
vis[a[j]]--;
j++;
}
else break;
}
if(cnt==K)
{
) ans=i-j+;
);
}
}
printf("Case %d: ",++kase);
) puts("sequence nai");
else printf("%d\n",ans);
}
;
}
与最大子序列和相关的一些题型。
最经典的是1维的最大连续数组和，O（n）DP可做。2维就要用前缀和+DP。
此类题可变形为求值小于K的最大连续数组和，1维则用尺取法维护区间，同步维护区间和和最短区间长度。2维同样利用这个思想，再加前缀和。
UVa 11951 Area
求小于给定数值的最大面积子矩阵，而且权值尽量小。
属于上面的变形题的2维。用滑动窗口维护即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
#define LL long long
#define INF 2139062143
#define inf -2139062144
#define MOD 20071027
using namespace std;
][];
][];
LL K;
void maintain(int ta,LL ts,int &area,LL &cost)
{
if(ta>area) cost=ts;
else if(ta==area) cost=min(cost,ts);
area=max(area,ta);
}
int main()
{
;
//freopen("out.txt","w",stdout);
scanf("%d",&T);
while(T--)
{
int N,M;
scanf("%d%d%lld",&N,&M,&K);
; i<=N; ++i)
; j<=M; ++j)
scanf("%d",&mat[i][j]);
LL cost=;
;
; i<=N; ++i)
; j<=M; ++j)
sum[i][j]=sum[i][j-]+mat[i][j];
; i<=M; ++i)
for(int j=i; j<=M; ++j)
{
;
LL s=;
,ed=;
while(ed<=N)
{
];
if(a>K)
{
ed=st=ed+;
s=;
continue;
}
while(st<ed&&s+a>K)
{
];
s-=b;
st++;
}
while(ed<=N&&s+a<=K)
{
s+=a;
ed++;
];
}
if(s<=K)
maintain((ed-st)*L,s,area,cost);
}
}
printf("Case #%d: %d %lld\n",++kase,area,cost);
}
;
}
UVa 10667 Largest Block
求最大空白矩形。前缀和求连续和，预处理一个数组判断某个区间是否为空。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
][];
][];
bool isEmpty(int c,int L,int R)
{
==sum[c][R]-sum[c][L-];
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int s,b;
scanf("%d%d",&s,&b);
int r1,c1,r2,c2;
memset(grid,,sizeof(grid));
;i<b;++i)
{
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
for(int j=r1;j<=r2;++j)
for(int k=c1;k<=c2;++k)
grid[j][k]=false;
}
memset(sum,,sizeof(sum));
;i<=s;++i)
;j<=s;++j)
sum[i][j]=sum[i][j-]+(int)grid[i][j];
;
;i<=s;++i)
for(int j=i;j<=s;++j)
{
;
;
;k<=s;++k)
{
;
else {
res+=L;
ans=max(ans,res);
}
}
}
printf("%d\n",ans );
}
;
}