标签存档：数据结构

【题目】

提交文件：road.pas/.cpp

输入文件：road.in

输出文件：road.out

 

我们知道，每天都有成千上万的车辆在高速公路上行驶。如果一辆装有若干吨货物的卡车通过一段高速公路，就会对这段公路造成一定程度的破坏。

整段高速公路有一个初始的耐久度I。如果一辆装有d吨货物的卡车通过一段高速公路，这段公路的耐久度就会减少d。一旦某段公路的耐久度小于或等于0，这段公路就会永久性地毁坏。卡车无法通过已经毁坏的地方。

有两种维护公路的车辆：T1和T2。T1车可以将一段公路的耐久度增加r。T2车可以将一段公路的耐久度小于p的部分修复至p。虽然维护公路的车辆可以通过已经毁坏的部分，但是已经毁坏的地方仍然无法修复。

你的任务是统计一下一共有多少辆卡车可以成功通行。

 

输入格式:

第一行是三个整数N、M和I，表示高速公路的长度为N，有M辆车依次通过，整段高速公路的初始的耐久度为I。

以下M行每行描述一辆车，格式如下：

1 s t d：一辆装有d吨货物的卡车准备通过区间[s,t]。在此之前先检查区间[s,t]是否完好。如果区间[s,t]里面有任何一个地方毁坏了，这辆卡车就会取消整个通行计划；否则这辆卡车就可以成功通过区间[s,t]，即使通过之后会把某些地方毁坏。

2 s t r：一辆T1车通过区间[s,t]，为这段公路的耐久度增加r。

3 s t p：一辆T2车通过区间[s,t]，为这段公路的耐久度修复至p。

其中：1≤N≤100000，1≤M≤100000，1≤I≤1000，1≤s≤t≤N，1≤d≤1000，1≤r≤1000，1≤p≤1000。

 

输出格式：

输出一个数，表示有多少辆卡车可以成功通行。

 

输入样例：

3 5 2

2 1 3 3

3 1 3 4

1 1 2 3

1 2 3 2

1 1 3 1

 

输出样例：

2

 

样例解释：

第3辆卡车无法通过区间[1,3]。因为虽然区间[1,2)和区间(2,3]的耐久度大于0，但是2这个点的耐久度为0，所以卡车无法通过。

【算法分析】
这个题就牛X了。。。至少对我来说。
块状链表嘛，就是把长度为n的整个数列分成sqrt(n)份，那么每份就有sqrt(n)个元素了。
然后维护三个标记。
1、key，表示这个块里最小的一个数是多少。
2、delta，这个块里的整体增值。
3、cc，这个块 < cc的要先变成cc。
4、low，这个块上一次标记清空之后，如果a[i]<=low,那么这个路就爆了。
然后我们设定cc都是在delta之前。那么维护上就有一点技巧了。
如果想不通的话就看程序吧。。。我觉得还是写得挺清晰地
= =
然后线段树的话，对于“重叠的标记”和“重叠标记”之间的合并无法做到。
于是无法完成这个任务。
【CODE】
#include #include #include #include #define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
const int N=100005;
struct Node{int l,r,key,delta,low,cc;}p[N/100];
int a[N],L;
int n,m,Stw,ans;

void build(){
for (int i=1;i<=n;i++) a[i]=Stw;
L=0;
int part=(int)(sqrt(n));
if (part==0) part=1;
for (int i=1;(i-1)*part+1<=n;i++){
L=i;
p[i].l=(i-1)*part+1;
p[i].r=min(i*part,n);
p[i].key=Stw;
p[i].delta=p[i].low=p[i].cc=0;
}
}

void push(int i){
for (int j=p[i].l;j<=p[i].r;j++){
if (a[j]<=p[i].low){
a[j]=0;
continue;
}
a[j]>?=p[i].cc;
a[j]+=p[i].delta;
}
}

void remake(int i){
p[i].delta=p[i].low=p[i].cc=0;
p[i].key=0x7FFFFFFF;
for (int j=p[i].l;j<=p[i].r;j++)
p[i].key}

void Deal1(int l,int r,int w){
int i,j;
for (i=1;i<=L;i++){
if (r if (l<=p[i].l && p[i].r<=r){
if (p[i].key<=0) return;
continue;
}
push(i);
remake(i);
for (j=max(l,p[i].l);j<=min(r,p[i].r);j++)
if (a[j]<=0) return;
}
ans++;
for (i=1;i<=L;i++){
if (r if (l<=p[i].l && p[i].r<=r){
p[i].key-=w;
p[i].delta-=w;
if (p[i].cc+p[i].delta<=0) p[i].low>?=(-p[i].delta);
continue;
}
push(i);
for (j=max(l,p[i].l);j<=min(r,p[i].r);j++) a[j]-=w;
remake(i);
}
}

void Deal2(int l,int r,int w){
int i,j;
for (i=1;i<=L;i++){
if (r if (l<=p[i].l && p[i].r<=r){
if (p[i].key>0) p[i].key+=w;
p[i].delta+=w;
continue;
}
push(i);
for (j=max(l,p[i].l);j<=min(r,p[i].r);j++)
if (a[j]>0) a[j]+=w;
remake(i);
}
}

void Deal3(int l,int r,int w){
int i,j;
for (i=1;i<=L;i++){
if (r if (l<=p[i].l && p[i].r<=r){
if (p[i].key>0) p[i].key>?=w;
p[i].cc>?=w-p[i].delta;
continue;
}
push(i);
for (j=max(l,p[i].l);j<=min(r,p[i].r);j++)
if (a[j]>0) a[j]>?=w;
remake(i);
}
}

void solve(){
int i,op,l,r,w;
scanf("%d%d%d",&n,&m,&Stw);
build();
ans=0;
for (i=1;i<=m;i++){
scanf("%d%d%d%d",&op,&l,&r,&w);
switch (op){
case 1:
Deal1(l,r,w);
break;
case 2:
Deal2(l,r,w);
break;
case 3:
Deal3(l,r,w);
break;
}
}
printf("%dn",ans);
}

int main(){
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
solve();
}

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1047
【算法分析】
先弄一个dmax[i][j]和dmin[i][j]数组分别表示(i,j)这个点往下的n（是题目中的n）个点中，最大值（最小值）是多少。然后这样压缩以后横向再来一次就可以。
【其它】
看到群里说2维单调队列，然后师傅就发了这个链接。。。
难道这就是传说中的2维
还以为是很恐怖的东西。。。
【其它】1Y。
【CODE】
#include #include #include #include using namespace std;
const int N=1005;
int m,n,L,i,j,head,tail;
int w[N][N],dmax[N][N],dmin[N][N],a[N][N],b[N][N],qp[N],qf[N];

int main(){
scanf("%d%d%d",&m,&n,&L);
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
scanf("%d",&w[i][j]);
for (j=1;j<=n;j++){
head=1; tail=0;
for (i=1;i while (head<=tail && w[i][j]>qf[tail]) tail--;
qf[++tail]=w[i][j]; qp[tail]=i;
}
for (i=1;i+L-1<=m;i++){
while (head<=tail && w[i+L-1][j]>qf[tail]) tail--;
qf[++tail]=w[i+L-1][j]; qp[tail]=i+L-1;
while (qp[head] dmax[i][j]=qf[head];
}
}

for (j=1;j<=n;j++){
head=1; tail=0;
for (i=1;i while (head<=tail && w[i][j] qf[++tail]=w[i][j]; qp[tail]=i;
}
for (i=1;i+L-1<=m;i++){
while (head<=tail && w[i+L-1][j] qf[++tail]=w[i+L-1][j]; qp[tail]=i+L-1;
while (qp[head] dmin[i][j]=qf[head];
}
}
int ans=0x7FFFFFFF;
for (i=1;i+L-1<=m;i++){
head=1; tail=0;
for (j=1;j<=n;j++){
while (head<=tail && dmax[i][j]>qf[tail]) tail--;
qf[++tail]=dmax[i][j]; qp[tail]=j;
while (qp[head]<=j-L) head++;
a[i][j]=qf[head];
}
head=1; tail=0;
for (j=1;j<=n;j++){
while (head<=tail && dmin[i][j] qf[++tail]=dmin[i][j]; qp[tail]=j;
while (qp[head]<=j-L) head++;
b[i][j]=qf[head];
}
}
for (i=1;i+L-1<=m;i++)
for (j=L;j<=n;j++)
ans=min(ans,a[i][j]-b[i][j]);
printf("%dn",ans);
}

【算法分析】
据Lost天牛的所有算法总结所说，现在一般人能写得起有两种可合并堆，一种是左偏树，一种是斜堆。
然后斜堆好像算法是平摊的还是啥，单次可能变成O(n)@.@。。。
如果不是平摊只是期望的话。。。那么估计想二叉检索树一样对某些特殊数据会悲剧啊。。。
还是老老实实写左偏树比较好。
然后这题就是左偏树的模板题。
当然还要搞个并查集。
【其它】第一个左偏树。1Y
【CODE】
#include #include #include const int N=105555;
int n,m,fa[N];
struct Node{Node *l,*r;int key,dis;}sp[N],*root[N],*null;

void input(){
null=&sp[0];
for (int i=1;i<=n;i++){
scanf("%d",&sp[i].key);
fa[i]=i;
root[i]=&sp[i];
root[i]->dis=0;
root[i]->l=root[i]->r=null;
}
}

inline void swap(Node *&A,Node *&B){Node *tmp=A; A=B; B=tmp;}

int gf(int k){
if (fa[k]==k) return k;
else return fa[k]=gf(fa[k]);
}

Node* Union(Node *p,Node *q){
if (p==null) return q;
if (q==null) return p;
if (p->key p->r=Union(p->r,q);
if (p->l->dis if (p->r==null) p->dis=0;
else p->dis=p->r->dis+1;
return p;
}

void myself_c(Node *&R){
Node *lc=R->l,*rc=R->r;
R->key>>=1; R->l=R->r=null;
R=Union(R,lc);
R=Union(R,rc);
}

void work(){
scanf("%d",&m);
for (int x,y,i=1;i<=m;i++){
scanf("%d%d",&x,&y);
if (gf(x)==gf(y)) printf("-1n");
else{
myself_c(root[fa[x]]);
myself_c(root[fa[y]]);
root[fa[y]]=Union(root[fa[x]],root[fa[y]]);
fa[fa[x]]=fa[y];
printf("%dn",root[fa[y]]->key);
}
}
}

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

【题目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1819
【算法分析】
Trie+直接暴力枚举那些操作。
【其它】1A。跑得再一次全世界最慢。
【CODE】
#include #include #include int n,m;
struct Trie_t{
Trie_t *son[26];int key;
void Fill(){
for (int i=0;i<26;i++) son[i]=NULL;
key=0;
}
}*root;

void Insert(char *str){
Trie_t *p=root;
while (*str){
if (p->son[*str-‘a’]) p=p->son[*str-‘a’];
else{
p->son[*str-‘a’]=(Trie_t*)malloc(sizeof(Trie_t));
p=p->son[*str-‘a’];
p->Fill();
}
str++;
}
p->key++;
}

void input(){
root=(Trie_t*)malloc(sizeof(Trie_t));
root->Fill();
char str[100];
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%s",str);
Insert(str);
}
}

bool Find(char *str){
Trie_t *p=root;
while (*str){
if (!p->son[*str-‘a’]) return false;
p=p->son[*str-‘a’];
str++;
}
if (p->key) return true;
return false;
}

void solve(){
char str[100],str2[100],Inchar;
for (int i=1,j,k,Inchar;i<=m;i++){
scanf("%s",str);
if (Find(str)) puts("-1");
else{
int Len=strlen(str),tot,ans=0;
for (j=0;j if (str[j]==str[j+1]) continue;
tot=0;
for (k=0;k if (k!=j)
str2[tot++]=str[k];
str2[tot]=0;
if (Find(str2)) ans++;
}

for (j=0;j<=Len;j++)
for (Inchar=’a’;Inchar<='z';Inchar++){
if (str[j]==Inchar) continue;
tot=0;
for (k=0;k str2[tot++]=str[k];
str2[tot++]=Inchar;
for (k=j;k str2[tot++]=str[k];
str2[tot]=0;
if (Find(str2))
ans++;
}

for (j=0;j char tmp=str[j];
for (Inchar=’a’;Inchar<='z';Inchar++){
str[j]=Inchar;
if (Find(str)) ans++;
}
str[j]=tmp;
}
printf("%dn",ans);
}
}
}

int main(){
input();
solve();
}

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1926
【算法分析】
前半部分，直接开200*200个1000的桶，利用经典的O(1)取子矩阵和的那种思想。复杂度做到了
O(Q*1000+R*C*1000)。
后半部分，弄一个线段树然后利用归并的思想把它映射到线性表上，然后二分答案再利用线段树二分线性表上的位置，最终得出ans。
时间复杂度O(Q*lg 1000 * lg c * lg c)。

【其它】
Orz。一开始第一部分用二维线段树做，直接TLE到SB。
线性表的话复杂度达到O(Q * lg 1000 * lg r * lg c * lg r*c)。
桶的话复杂度达到O(Q * lg 1000* lg r * lg c)。但是空间受不了。。。
跑得全世界最慢。
1 23199 root 157204K 4435MS Pascal 3.82K 2010-05-14 14:07:37 2 23435 oimaster 100112K 5574MS G++ 4.15K 2010-05-15 22:54:09 3 24878 edward_mj 164928K 9324MS G++ 4.45K 2010-05-21 20:25:45 【CODE】
#include #include #include const int N=205;
const int rate=8;
int m,n,q,spt,a[N][N],b[500005];
int sp[12000005],Tong[N][N][1001];
int S[ 12000005];
struct Node_t{int l,r,st,ed;}Tr[500005*rate];

struct Solve1_t{
int Sum,Limit,Num,x1,y1,x2,y2,h,Lt;
void input(){
spt=0;
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
memset(Tong,0,sizeof(Tong));
int i,j,k;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++){
if (i+j==2) {Tong[i][j][a[1][1]]++;continue;}
if (i>1){
for (k=1;k<=1000;k++)
Tong[i][j][k]=Tong[i-1][j][k];
for (k=1;k<=j;k++)
Tong[i][j][a[i][k]]++;
}else{
for (k=1;k<=1000;k++)
Tong[i][j][k]=Tong[i][j-1][k];
for (k=1;k<=i;k++)
Tong[i][j][a[k][j]]++;
}
}
}

void solve(){
S[0]=0;
for (int i=1;i<=spt;i++) S[i]=S[i-1]+sp[i];
for (int i=0,j;i scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&h);
int Nt;
Sum=Num=0;
for (j=1000;j>=1;j–){
Nt=0;
Nt+=Tong[x2][y2][j];
Nt-=Tong[x1-1][y2][j];
Nt-=Tong[x2][y1-1][j];
Nt+=Tong[x1-1][y1-1][j];
Sum+=Nt*j;
Num+=Nt;
if (Sum>=h){
Num-=(Sum-h)/j;
printf("%dn",Num);
break;
}
}
if (Sum }
}
}Deal1;

struct Solve2_t{
int x1,y1,x2,y2,Num,h,Limit;
int Sum;

void input(){
spt=0;
for (int i=1;i<=n;i++)
scanf("%d",&b[i]);
}

void Union(Node_t &x,Node_t &y){
for (int i=x.st,j=y.st;i<=x.ed || j<=y.ed;)
if (i<=x.ed && (j>y.ed || sp[i] else sp[++spt]=sp[j++];
}

void build(int p,int l,int r){
Tr[p].l=l; Tr[p].r=r;
if (l==r){
Tr[p].st=Tr[p].ed=++spt;
sp[spt]=b[l];
}else{
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
Tr[p].st=spt+1;
Union(Tr[p*2],Tr[p*2+1]);
Tr[p].ed=spt;
}
S[Tr[p].ed]=sp[Tr[p].ed];
for (int i=Tr[p].ed-1;i>=Tr[p].st;i–)
S[i]=S[i+1]+sp[i];
}

void Try(int p){
if (y1<=Tr[p].l && Tr[p].r<=y2){
if (Limit>sp[Tr[p].ed]) return;
int l=Tr[p].st,r=Tr[p].ed,mid;
while (l mid=(l+r)/2;
if (sp[mid] else r=mid;
}
Sum+=S[l];
Num+=Tr[p].ed-l+1;
}else{
int mid=(Tr[p].l+Tr[p].r)/2;
if (y1<=mid) Try(p*2);
if (y2>mid) Try(p*2+1);
}
}

bool can(int tmp){
Limit=tmp;
Sum=Num=0;
Try(1);
if (Sum return true;
}

void solve(){
int l,r,mid;
for (int i=0;i scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&h);
l=1,r=1000;
while (l+1 mid=(l+r)/2;
if (can(mid)) l=mid;
else r=mid-1;
}
if (can(r)) l=r;
if (!can(l)) puts("Poor QLW");
else{
Num-=(Sum-h)/l;
printf("%dn",Num);
}
}
}
}Deal2;

int main(){
freopen("susu.in","r",stdin);
freopen("susu.out","w",stdout);
scanf("%d%d%d",&m,&n,&q);
if (m>1){
Deal1.input();
Deal1.solve();
}
else{
Deal2.input();
Deal2.build(1,1,n);
Deal2.solve();
}
return 0;
}