edward_mj

[ZOJ3335 Filtering]矩阵维护类型的题目

【题目大意】
给出一个a[i][j]。
然后ans[i][j]=以(i , j)为中心的一个m*n的矩形内所有数字的中位数。
如果m*n超出了边框。那么ans[i][j]=a[i][j]。
0<=a[i][j]<256。
【算法分析】
首先，注意到键值的范围为[0，255]。
我们容易想到弄一个桶来维护。或许桶里还可以搞个线段树什么的。
然后显然ans[i][j]和ans[i][j-1]所包含的数里，只有两列不同。于是我们可以在O(p*q*n)里维护一个所包含数字的桶。
有这个桶呢，暴力找中位数，那么复杂度是O(p*q*(n+256))。
但是依然MS可能超时。
于是我们可以加入一个优化：
ans[i][j]和ans[i][j-1]一般相差不是很远。
那么我们就在ans[i][j]的基础上，先前滑动和向后滑动，一般而言就可以很快出解了。
【时间复杂度】O(p*q*(n+256)) 一般达不到。
【CODE】
#include #include #include const int N=505;
int a[N][N],b[N][N],T[256];
int m,n,p,q,L;

void input(){
int i,j;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
scanf("%d",&a[i][j]);
scanf("%d%d",&p,&q);
L=p*q/2+1;
}

int Cal(int x,int y){
int i,j;
for (i=x-p;i<=x+p;i++)
for (j=y-q;j<=y+q;j++)
T[a[i][j]]++;
j=0;
for (i=0;i<256;i++){
j+=T[i];
if (j>=L) return i;
}
}

void solve(){
p/=2; q/=2;
int i,j,k,pre,next;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
b[i][j]=-10000;
bool first;
for (i=1+p;i+p<=m;i++){
memset(T,0,sizeof(T));
first=true;
for (j=1+q;j+q<=n;j++)
if (first){
first=false;
b[i][j]=Cal(i,j);
pre=0; next=0;
for (k=0;k for (k=b[i][j]+1;k<256;k++) next+=T[k];
}else{
int &t=b[i][j];
t=b[i][j-1];
for (k=i-p;k<=i+p;k++){
T[a[k][j-q-1]]–;
if (a[k][j-q-1] if (a[k][j-q-1]>t) next–;
T[a[k][j+q]]++;
if (a[k][j+q] if (a[k][j+q]>t) next++;
}
while (pre>=L){
next+=T[t];
t–;
pre-=T[t];
}
while (next>=L){
pre+=T[t];
t++;
next-=T[t];
}
}
}
}

void output(){
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++){
if (b[i][j]<0) b[i][j]=a[i][j];
printf("%d",b[i][j]);
if (j==n) putchar(‘n’);
else putchar(‘ ‘);
}
putchar(‘n’);
}

int main(){
while (scanf("%d%d",&m,&n)!=EOF){
input();
solve();
output();
}
}

[ZOJ3338 Map]爬山法

【题目大意】
给出两个矩形，让你求一个点，使之满足在两个矩形里的比例位置是一样的。
【算法分析】
Orz。。。比赛时想爬山。但是弄成直接爬那个重合点，然后以他们比例差作为估价函数。
于是果断写不出，然后挂了。
然后赛后问师傅。。。师傅说直接爬外面的，再算在里面的对应位置就可以了。
当时当场Orz自己的傻×无限次。

然后其中一种正确的做法是：
在外面爬，然后算在里面的对应位置，估价函数就设为这两个对应点的距离。

于是一爬就过。。。Orz。。。
【CODE】
#include #include #include #include #include using namespace std;
const double eps=1e-5;
struct Point{double x,y;}a[5],st,xXL,yXL;
double ratex,ratey;

inline double sqr(double x){return x*x;}
inline double dis(Point A,Point B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}

void input(){
scanf("%lf%lf",&st.x,&st.y);
for (int i=1;i<=4;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
ratex=dis(a[1],a[2])/st.x;
ratey=dis(a[1],a[4])/st.y;

xXL.x=a[2].x-a[1].x;
xXL.y=a[2].y-a[1].y;

yXL.x=a[4].x-a[1].x;
yXL.y=a[4].y-a[1].y;
}

double w(double x,double y){
if (x<0 || x>st.x || y<0 || y>st.y) return 1e50;
double rx=x/st.x,ry=y/st.y;
Point m,tmp;
tmp.x=x; tmp.y=y;

m.x=rx*xXL.x+ry*yXL.x+a[1].x;
m.y=rx*xXL.y+ry*yXL.y+a[1].y;
return dis(m,tmp);
}

void work(){
double step=1.0,x=0,y=0;
bool flag;
for (;step>eps;step/=2){
for (flag=true;flag;){
flag=false;
if (w(x+step,y) if (w(x-step,y) if (w(x,y+step) if (w(x,y-step) }
}
printf("%.2lf %.2lfn",x,y);
}

int main(){
int Tc,i;
scanf("%d",&Tc);
for (i=1;i<=Tc;i++){
input();
work();
}
}

[FOJ1902 Graduate]动态规划

【题目大意】
给出N个人，他们高度各不相同，让他们站两排，满足：
1、同一个位置的人中，前面的比后面的矮。
2、最终没有一排是空的，而且后面那排的人数<=前面那排。
3、如果i站在j的左边，那么i比j矮。
问有多少种方案。
结果mod 20100501
【算法分析】
dp
F[i][j]表示前面那排排了i个人，后面那排排了j个人。
那么方程就是F[i][j]=F[i-1][j]+F[i,j-1]。（i>=j && i+j<=n）
初始F[0][0]=1。
【时间复杂度】O(n^2)
【CODE】
#include #include #include int a[105];
int f[105][105];

void init(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
}

void dp(){
memset(f,0,sizeof(f));
f[0][0]=1;
int i,j;
for (i=0;i<=n;i++)
for (j=0;i+j<=n && j<=i;j++)
if (i+j>0){
if (i) f[i][j]+=f[i-1][j];
if (j) f[i][j]+=f[i][j-1];
f[i][j]%=20100501;
}
int ans=0;
for (i=1;i<=n/2;i++){
ans+=f[n-i][i];
ans%=20100501;
}
printf("%dn",ans);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
printf("Case #%d: ",i);
init();
dp();
}
}

[FOJ1903 Regular Brackets]贪心、无权修改括号序列、O(n)

【题目大意】
给定一个括号序列，让你修改最少的次数，使之成为一个合法的括号序列。
输出这个修改次数，并输出最终字典序最小的修改后的结果。
【算法分析】
Orz。。。这类题是我最不擅长的。。。应该说直觉不够好么。。。
下面引用lcc大牛的做法：

先从左向右扫一旦扫到一个失配的’)’就将左边第一个’）’强转‘（’ 然后反过来做一遍这样得到的一定是最小转化而且是最小字典序

一开始我也想到个类似的，然后我居然去想，这第一个’)’会不会不能转呢。。。
= =，晕，在正向枚举的时候，stack本来就可以超过0。本就不需要考虑失配。
太SB了。。。然后就这样。
【复杂度】O(n)
【CODE】
#include #include #include const int N=1000005;
int Tc,n,ans;
int Q[N];
char S[N];

void solve1(){
int stack=0,h=1,t=0,i;
for (i=1;i<=n;i++)
if (S[i]=='(‘) stack++;
else{
Q[++t]=i;
if (!stack){
S[Q[h++]]='(‘;
ans++;
stack++;
}
else stack–;
}
}

void solve2(){
int stack=0,h=1,t=0,i;
for (i=n;i>=1;i–)
if (S[i]==’)’) stack++;
else{
Q[++t]=i;
if (!stack){
S[Q[h++]]=’)’;
ans++;
stack++;
}
else stack–;
}
}

int main(){
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
scanf("%s",S+1);
n=strlen(S+1);
ans=0;
solve1();
solve2();
printf("Case #%d: %dn",i,ans);
puts(S+1);
}
}

[FOJ1898 Cows Arrangement]超Orz的差分约束系统~

【题目大意】
有一个数组d[1..n]
d[1]=0，d[i]然后给出一些限制，
第一种：x,y,w，d[y]-d[x]<=w（数据保证x第二种：x,y,w，d[y]-d[x]>=w（数据保证x一个d[i]=k满足条件当且仅当存在一组d[1..n]满足限制，而且d[i]=k。
【算法分析】
完全没想到。。。一开始写了个二分+差分判可行了。。。完全超时到天荒地老。。。
后来看正解。
非常Orz。就是按题目的这些不等式建图。
第一次，按最短路来建图，d[1]设为0，然后其他全设为无穷大。跑一遍最短路的spfa。
第二次，按最长路来建图，d[1]设为0，然后其他也全设为0。跑一遍最长路的spfa。

然后、然后、很Orz地他就解决了。。。

最短路跑出的是最大值。
最长路跑出的是最小值。

为什么呢？
因为他都是按照那个不等式最贴边的方式解得。
所以最短路就是刚好<=那个上界。
而最长路则是刚好>=那个下界。

So，Orz。。。。
【CODE】
#include #include #include #include #include using namespace std;
const int N=5005;
const int INF=100000000;
int n;
int L[N],R[N],d[N],Q[N],v[N],Inn[N];
bool flag;
struct edge{int x,y,w;edge *next;};
struct Link_t{
edge sp[N],*ls[N];
int e;
void init(){
e=0;
for (int i=1;i<=n;i++) ls[i]=NULL;
}

void addedge(int x,int y,int w){
e++;
sp[e].x=x; sp[e].y=y; sp[e].w=w;
sp[e].next=ls[x]; ls[x]=&sp[e];
}
}Hate,Love,G;

void input(){
int ml,mh,i,x,y,w;
scanf("%d%d%d",&n,&ml,&mh);
Hate.init();
Love.init();
for (i=1;i<=ml;i++){
scanf("%d%d%d",&x,&y,&w);
Love.addedge(x,y,w);
}
for (i=1;i<=mh;i++){
scanf("%d%d%d",&x,&y,&w);
Hate.addedge(x,y,w);
}
}

void build1(){
G.init();
int i;
for (i=1;i<=Love.e;i++){
edge *t=&Love.sp[i];
G.addedge(t->x,t->y,t->w);
}
for (i=1;i<=Hate.e;i++){
edge *t=&Hate.sp[i];
G.addedge(t->y,t->x,-t->w);
}
for (i=1;i G.addedge(i+1,i,-1);
G.addedge(1,n,INF);
}

void spfa1(){
for (int i=1;i<=n;i++){
Inn[i]=0;
v[i]=0;
d[i]=INF+22;
}
int head=0,tail=1;
d[1]=0; Q[1]=1; v[1]=1;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=G.ls[Q[head]];t;t=t->next)
if (d[t->x]+t->w d[t->y]=d[t->x]+t->w;
if (d[t->y]<0){
flag=false;
return;
}
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
Q[tail]=t->y;
Inn[t->y]++;
if (Inn[t->y]>n){
flag=false;
return;
}
}
}
v[Q[head]]=0;
}
}

void build2(){
G.init();
int i;
for (i=1;i<=Love.e;i++){
edge *t=&Love.sp[i];
G.addedge(t->y,t->x,-t->w);
}
for (i=1;i<=Hate.e;i++){
edge *t=&Hate.sp[i];
G.addedge(t->x,t->y,t->w);
}
for (i=1;i G.addedge(i,i+1,1);
G.addedge(n,1,-INF);
}

void spfa2(){
for (int i=1;i<=n;i++){
v[i]=0;
d[i]=0;
}
int head=0,tail=1;
d[1]=0; Q[1]=1; v[1]=1;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=G.ls[Q[head]];t;t=t->next)
if (d[t->x]+t->w>d[t->y]){
d[t->y]=d[t->x]+t->w;
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
Q[tail]=t->y;
}
}
v[Q[head]]=0;
}
}

void output(){
puts("Exist!");
for (int i=1;i<=n;i++)
printf("%d %dn",L[i],R[i]);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
printf("Case #%d: ",i);
input();
flag=true;
build1();
spfa1();
if (!flag){
puts("Not Exist!");
continue;
}
for (int j=1;j<=n;j++) R[j]=d[j];
build2();
spfa2();
for (int j=1;j<=n;j++) L[j]=d[j];
output();
}
}