Codeforces Round #401 (Div. 2)

和FallDream dalao一起从学长那借了个小号打Div2,他切ABE我做CD,我这里就写下CD题解,剩下的戳这里

AC:All Rank:33 小号Rating:1539+217->1756

C.Alyona and Spreadsheet

题目大意:给出一个n*m的数字矩阵a,k次询问,每次给li,ri,求是否有一列的a[li][j],a[li+1][j],...a[ri][j]组成一个不下降序列。(n*m<=100,000,k<=100,000)

思路:O(n*m)扫一遍可以预处理出每个ri最小的li,我菜,写了线段树。

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
inline int read()
{
int x=;char c;
while((c=getchar())<''||c>'');
for(;c>=''&&c<='';c=getchar())x=(x<<)+(x<<)+c-'';
return x;
}
#define MN 100000
#define N 131072
#define INF 0x7FFFFFFF
vector<int> v[MN+];
vector<pair<int,int> > q[MN+];
int t[N*+],ans[MN+];
void change(int k,int x){for(t[k+=N]=x;k>>=;)t[k]=min(t[k<<],t[(k<<)+]);}
int main()
{
int n,m,k,i,j;
n=read();m=read();
for(i=;i<=m;++i)v[].push_back(INF);
for(i=;i<=n;++i)v[i].push_back();
for(i=;i<=n;++i)for(j=;j<=m;++j)v[i].push_back(read());
for(k=read(),i=;i<k;++i)j=read(),q[read()].push_back(make_pair(j,i));
memset(t,,sizeof(t));
for(i=;i<=n;++i)
{
for(j=;j<=m;++j)if(v[i][j]<v[i-][j])change(j,i);
for(j=;j<q[i].size();++j)ans[q[i][j].second]=(t[]<=q[i][j].first);
}
for(i=;i<k;++i)puts(ans[i]?"Yes":"No");
}

D.

题目大意:给N个字符串,从中删掉最少的字符使得字符串按字典序排序。(字符数量<=500,000)

思路:我写了个分治……solve(l,r,p)表示第l个到第r个前p-1个都一样,从后往前找到第一个s[i][p]>s[i+1][p],把第l个到第i个p以后都截掉,然后按第p个字符分成几块继续分治。其实只要从最后一个往前贪心删掉就可以了。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define MN 500000
#define INF 0x7FFFFFFF
string s[MN+];
int L[MN+];
int C(int x,int y){return y<=L[x]?s[x][y]:;}
void solve(int l,int r,int p)
{
int i,j,mn=INF;
for(i=r;i>=l;--i)
{
if(C(i,p)>mn)L[i]=p-;
mn=min(mn,C(i,p));
}
for(i=l;i<=r;i=j)
{
for(j=i;j<=r&&C(i,p)==C(j,p);++j);
if(C(i,p))solve(i,j-,p+);
}
}
int main()
{
int n,i,j;
cin>>n;
for(i=;i<=n;++i)
{
cin>>s[i];
L[i]=s[i].size()-;
}
solve(,n,);
for(i=;i<=n;++i,puts(""))for(j=;j<=L[i];++j)putchar(s[i][j]);
}
上一篇:53. Maximum Subarray


下一篇:NSString / NSMutableString 字符串处理,常用代码 (实例)