|
|
2010年4月8日
方法：建两个堆，同时维护一个大根堆和一个小根堆
用一对指针就行卡位
弹出的时候如果在这个区间就记录下来，如果不在区间内就扔掉。
#include<iostream>
using namespace std;
int a[1000010];
int minout[1000010],maxout[1000010];
int n,k;
struct node{
int key;
int pla;
};
struct heap//堆
{
int size;
struct node elem[2000010];
}minh,maxh;
void insertmin(int x,int p)
{
int i= ++minh.size;
while(minh.elem[i/2].key > x)
{
minh.elem[i]=minh.elem[i/2];
i /=2;
}
minh.elem[i].key=x;
minh.elem[i].pla=p;
}
void deletemin()
{
int i,child,last,place;
last=minh.elem[minh.size].key;
place=minh.elem[minh.size].pla;
minh.size--;
for(i=1;i*2 <= minh.size;i = child)
{
child=2*i;
if(child != minh.size && minh.elem[child+1].key < minh.elem[child].key )
child++;
if( last > minh.elem[child].key )
minh.elem[i] = minh.elem[child];
else break;
}
minh.elem[i].key=last;
minh.elem[i].pla=place;
}
void insertmax(int x,int p)
{
int i= ++maxh.size;
while(maxh.elem[i/2].key < x)
{
maxh.elem[i]=maxh.elem[i/2];
i /=2;
}
maxh.elem[i].key=x;
maxh.elem[i].pla=p;
}
void deletemax()
{
int i,child,last,place;
last=maxh.elem[maxh.size].key;
place=maxh.elem[maxh.size].pla;
maxh.size--;
for(i=1;i*2 <= maxh.size;i = child)
{
child=2*i;
if(child != maxh.size && maxh.elem[child+1].key > maxh.elem[child].key )//
child++;
if( last < maxh.elem[child].key )//
maxh.elem[i] = maxh.elem[child];
else break;
}
maxh.elem[i].key=last;
maxh.elem[i].pla=place;
}
void cal()
{
int i;
minh.size=0;
minh.elem[0].key=-INT_MAX;
maxh.size=0;
maxh.elem[0].key=INT_MAX;
for(i=1;i<=k;i++)
{
insertmin(a[i],i);
insertmax(a[i],i);
}
int p1=1,p2=k;
while(p2<=n)
{
while(minh.elem[1].pla < p1 || minh.elem[1].pla>p2)
deletemin();
while(maxh.elem[1].pla < p1 || maxh.elem[1].pla>p2)
deletemax();
minout[p1]=minh.elem[1].key;
maxout[p1]=maxh.elem[1].key;
p1++;
p2++;
insertmin(a[p2],p2);
insertmax(a[p2],p2);
}
}
int main()
{
int i;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
cal();
for(i=1;i<=n-k;i++)
printf("%d ",minout[i]);
printf("%d\n",minout[n-k+1]);
for(i=1;i<=n-k;i++)
printf("%d ",maxout[i]);
printf("%d\n",maxout[n-k+1]);
}
134. Centroid
time limit per test: 0.50 sec.
memory limit per test: 4096 KB
You are given an undirected connected graph, with N vertices and N-1 edges (a tree). You must find the centroid(s) of the tree.
In order to define the centroid, some integer value will be assosciated to every vertex. Let's consider the vertex k. If we remove the vertex k from the tree (along with its adjacent edges), the remaining graph will have only N-1 vertices and may be composed of more than one connected components. Each of these components is (obviously) a tree. The value associated to vertex k is the largest number of vertices contained by some connected component in the remaining graph, after the removal of vertex k. All the vertices for which the associated value is minimum are considered centroids.
Input
The first line of the input contains the integer number N (1<=N<=16 000). The next N-1 lines will contain two integers, a and b, separated by blanks, meaning that there exists an edge between vertex a and vertex b.
Output
You should print two lines. The first line should contain the minimum value associated to the centroid(s) and the number of centroids. The second line should contain the list of vertices which are centroids, sorted in ascending order.
Sample Input
7
1 2
2 3
2 4
1 5
5 6
6 7
Sample Output
3 1
1
给一棵n个节点的树，求这棵树的重心。
树的重心就是是指删掉它以后，
剩下的最大的连通子树的节点数是最少的点。
因为树是保证连通的，所以从任何一个节点都可以把这棵树拎起来。
所以可以从任何一个点去DFS（返回子节点个数+1）
#include<iostream>
#include<algorithm>
#include<vector>
#define pk(x) push_back(x)
using namespace std;
const int N=16010;
vector<int>g[N];
int n,value=0x7fffffff,num;//n为边数，value为最小权值，num为重心个数
int res[N],vis[N];
int dfs(int u)//
{
vis[u]=1;
int sum=0,k=0,tmp;//k是节点u的value.Sum是u的所有子节点的个数
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(!vis[v]){
tmp=dfs(v);
sum += tmp;
if(k<tmp) k=tmp;//k(f[u])=max{sum[v]+1}sum[v]是v的所有子节点个数+v自己
}
}
tmp=n-1-sum;//k(f[u])=max{k,n-1-sum}//将该节点和该节点的所有子节点划去的剩余部分
if(k<tmp) k=tmp;
if(value>k){//求所有节点中最小的权值
value=k;
num=1;//发现更小的，置num为1
res[1]=u;
}
else if(value==k){
res[++num]=u;
}
return sum+1;
}
int main()
{
scanf("%d",&n);
int i,a,b;
for(i=1;i<n;i++){
scanf("%d%d",&a,&b);
g[a].pk(b);
g[b].pk(a);
}
dfs(1);
printf("%d %d\n",value,num);
sort(res+1,res+num+1);
if(num>0)
printf("%d",res[1]);
for(i=2;i<=num;i++)
printf(" %d",res[i]);
printf("\n");
}
2010年4月5日
对于一套导弹拦截系统，它要不可以拦截上升序列，要不可以拦截下降序列，现在问最少需要多少套系统。 很自然的想到LIS算法，可惜在这里不能用，如果这样贪心的话 每套系统拦截最多的导弹和系统的数量最少没有什么直接联系，应该不会正确 而LIS中，最核心的思想在于能否将一个元素加入到序列中，只与这个序列目前的最后一个元素有关 这道题就用了这个关键的思想。 用up[k]和down[k]记录第k套上升（下降）系统目前所拦截的最后一个导弹 dfs(u,v,t)意味着已有u个上升，v个下降，正在处理第t个数 按理说，每拿到一个新的数字应该将它所有能放入的序列都放一遍的 但扩展节点时却存在一个贪心策略，大大节省了时间。 假设现在要把一个数放入一个上升序列，那么一定是所有能放入的上升序列中，最后一个元素最大的那一个。 其实想想也是，既然每个数字都要放到一个序列中， 对于上升序列，肯定是目前越小越有用，既然能放入大的里面，何必浪费一个小的呢 注意到其实up[i]按这种策略已经是排好序的了，所以只用找最先碰到的一个就行了 这样将深搜的树从一个多叉树变成了二叉树，时间效率提升很大。
#include<iostream>
using namespace std;
#define max(a,b) a>b?a:b
int n,res,a[60];
int up[60],down[60];
void dfs(int u,int v,int t)
{
if(u+v>=res)return;
if(t>n)
{
if(u+v<res)res=u+v;
return;
}//找到更好的结果
int i,tmp;
//UP
for(i=1;i<=u;i++)
if(up[i]<a[t]) break;
tmp=up[i];
up[i]=a[t];
dfs(max(i,u),v,t+1);
up[i]=tmp;
//DOWN
for(i=1;i<=v;i++)
if(down[i]>a[t]) break;
tmp=down[i];
down[i]=a[t];
dfs(u,max(i,v),t+1);
down[i]=tmp;
}
int main()
{
int i;
while(scanf("%d",&n) && n)
{
res=100;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
dfs(0,0,1);
printf("%d\n",res);
}
}
Heap
|
Time Limit: 5000MS
|
|
Memory Limit: 131072K
|
|
Total Submissions: 1965
|
|
Accepted: 392
|
Description
A (binary) heap is an array that can be viewed as a nearly complete binary tree. In this problem, we are talking about max-heaps.
A max-heap holds the property that for each node than the root, it’s key is no greater than its parent’s. Upon this we further require that for every node that has two children, key of any node in the subtree rooted at its left child should be less than that of any node in the subtree rooted at its right child.
Any array can be transformed into a max-heap satisfying the above requirement by modifying some of its keys. Your task is find the minimum number of keys that have to be modified.
Input
The input contains a single test case. The test case consists of nonnegative integers distributed on multiple lines. The first integer is the height of the heap. It will be at least 1 and at most 20. Then follow the elements of the array to be transformed into a heap described above, which do not exceed 109. Modified elements should remain integral though not necessarily nonnegative.
Output
Output only the minimum number of elements (or keys) that have to be modified.
Sample Input
3
1
3 6
1 4 3 8
Sample Output
4
Hint
1 10
/ \ / \
3 6 =====> 3 9
/ \ / \ / \ / \
1 4 3 8 1 2 4 8
Source
POJ Monthly--2007.04.01, czh
题意理解：在原树上改变部分数字，使之满足以下两个条件：
1所有的节点的值都不会比他的父亲节点大
2左子树的所有节点的值都比对应的右子树小
所以，这里要求，左<右<=中
算法思想：递归后续遍历+最长上升字串算法nlogn
算法设计：用数组来存储树
后续遍历找到合适的排序
最长上升子序列，找到了最多的可利用部分
改动自然是最小的了。
注意的地方：为了使<和<=保持一致
每次从左到右的时候要减去1，后面所有的节点都受影响
这样只做一次不降子序列就行了。
源代码：(已AC)
1 #include<iostream>
2 using namespace std;
3 int h,n,p,tmp,SIZE;
4 int *a,*tre;
5 void maketre(int k)
6 {
7 if(2*k<=n)
8 maketre(2*k);
9 if(2*k+1<=n){tmp++;
10 maketre(2*k+1);
11 }
12 tre[++p]=a[k]-tmp;
13 }
14 int solve()
15 {
16 int l,r,mid,len=1;
17 a[1]=tre[1];
18 for(int i=2;i<=n;i++)//
19 {
20 l=1,r=len;
21 while(l<=r)
22 {
23 mid=(l+r)>>1;
24 if(a[mid]<=tre[i]) l=mid+1;//上升或不降
25 else r=mid-1;//二分查找
26 }
27 a[l]=tre[i];//插入
28 if(l>len) len++;//增加长度
29 }
30 return len;
31 }
32 int main()
33 {
34 scanf("%d",&h);
35 SIZE=1 << h;
36 a=new int[SIZE+100];
37 tre=new int[SIZE+100];
38 int t;
39 while(scanf("%d",&t)!=EOF)
40 a[++n]=t;
41 maketre(1);
42 cout<<n-solve()<<endl;
43 }
44
45
错误之处：
树不一定是满的，也就是说若只有左孩子的时候，左孩子是可以与父亲相等的……这个地方错了很多次
只能使用不降子序列，无法使用上升子序列？
2010年4月3日
Intervals
|
Time Limit: 2000MS
|
|
Memory Limit: 65536K
|
|
Total Submissions: 8965
|
|
Accepted: 3318
|
Description
You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.
Write a program that:
reads the number of intervals, their end points and integers c1, ..., cn from the standard input,
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n,
writes the answer to the standard output.
Input
The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.
Output
The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.
Sample Input
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
Sample Output
6
思路：
题目的转换真的非常非常巧妙，让我再来梳理一下。本题的题意是给了我们一些区间，然后告诉每个区间中至少需要取Ci个数。求出满足n个条件的集合C的最少的元素个数。
首先第一个转化，是找到一个合理的表示。用ti表示每一个数，如果有用就是1，否则是0。吧S(i+1)定义成S(i+1)=sigma(tj)(1<=j<=i)也就是。S[i+1]表示从0到i有多少个数是需要的。
因此，题目中的条件可以表示成S[bi+1]>=S[ai]+Ci//至少要Ci个
这与bellman中的松弛操作时很像的。因此可以看成一些点
有D[v]>=D[u]+w(u,v)
上式对任何u成立，所以v应该是里面最大的，若D[v]<D[u]+w(u,v)则D[v]=D[u]+w(u,v)
于是。可以从ai和bi+1连一条线，它的长度是ci
这里只有这些条件还是不够的，还要加上两个使其满足整数性质的条件
1>=s[i+1]-s[i]>=0
有了这么多条件，使其自然构成了一个差分约束系统。
用spfa算法得到一个最长路，第一个到最后一个节点的最长路即是需要求的值。
Source Code
1 #include<iostream>
2 #include<vector>//for map
3 #include<queue>//for spfa
4 using namespace std;
5 #define MAXN 50010
6 #define pb push_back
7 int dis[MAXN],used[MAXN];
8 int aa=INT_MAX,bb=-1;//aa最小bb最大
9 struct edge
10 {
11 int p;
12 int len;
13 }tmp;
14 vector<edge>map[MAXN];
15
16 void spfa()
17 {
18 int i,t;
19 queue<int>Q;
20 for(i=aa;i<=bb;i++)
21 dis[i]=-INT_MAX;
22 dis[aa]=0;
23 used[aa]=1;//先进一个
24 Q.push(aa);
25 while(!Q.empty())
26 {
27 t=Q.front();
28 Q.pop();
29 used[t]=0;//出队列过后,还可能再进
30 int nt=map[t].size();
31 for(i=0;i<nt;i++)
32 {
33 if(dis[map[t][i].p]<dis[t]+map[t][i].len)//求最长路
34 {
35 dis[map[t][i].p]=dis[t]+map[t][i].len;
36 if(!used[map[t][i].p])
37 {
38 used[map[t][i].p]=1;
39 Q.push(map[t][i].p);
40 }
41 }
42 }
43 }
44 }
45 int main()
46 {
47 int i,n;
48 scanf("%d",&n);
49 int u,v,w;
50 for(i=1;i<=n;i++)
51 {
52 scanf("%d%d%d",&u,&v,&w);
53 if(u<aa) aa=u;
54 if(v+1>bb) bb=v+1;
55 tmp.len=w;
56 tmp.p=v+1;
57 map[u].pb(tmp);
58 }//添加ci边
59 for(i=aa;i<=bb;i++)
60 {
61 tmp.len=0;
62 tmp.p=i+1;
63 map[i].pb(tmp);
64 tmp.len=-1;
65 tmp.p=i;
66 map[i+1].pb(tmp);
67 }//添加0边和-1边
68 spfa();
69 printf("%d\n",dis[bb]);
70 return 0;
71 }
72
技术总结：技术上使用了STL的vector让存储图的邻接表非常方便。spfa的时候省事用了STL的queue。基本的操作就是pop(),push(),front(),size(),empty()
还有一个贪心算法：先按后端点排序，把前面的要求越往后放越好，这样后面放的时候就可以利用前面放的结果。贪心为什么是正确的？
2010年3月7日
水题开路了，若x是丑数，则2x,3x,5x都是丑数，本想直接开数组，再数一次
结果发现丑数十分稀疏，空间完全不够，只好对 2x,3x,5x 数列的大小进行判断
把最小的放入a[]
1 #include<iostream>
2 using namespace std;
3 int a[1550];
4 int min(int x,int y,int z)
5 {
6 int t;
7 t= x<y ? x:y;
8 t= t<z ? t:z;
9 return t;
10 }
11 int main()
12 {
13 a[1]=1;
14 int i,x=1,y=1,z=1;
15 for(i=2;i<=1500;i++)
16 {
17 a[i]=min(2*a[x],3*a[y],5*a[z]);
18 if(2*a[x]==a[i])x++;
19 if(3*a[y]==a[i])y++;
20 if(5*a[z]==a[i])z++;
21 }
22 while(cin>>i&&i)
23 cout<<a[i]<<endl;
24 }
25
2010年2月16日
Description
给定两个整数M，N，生成一个M*N的矩阵，矩阵中元素取值为A至Z的26个字母中的一个，A在左上角，其余各数按顺时针方向旋转前进，依次递增放置，当超过26时又从A开始填充。例如，当M=5，N=8时，矩阵中的内容如下：
A B C D E F G H
V W X Y Z A B I
U J K L M N C J
T I H G F E D K
S R Q P O N M L
Input
M为行数，N为列数，其中M，N都为大于0的整数。
Output
分行输出相应的结果
Sample Input
4 9
Sample Output
A B C D E F G H I
V W X Y Z A B C J
U J I H G F E D K
T S R Q P O N M L
#include<iostream>
#include<cmath>
using namespace std;
int m,n;
char p[1300][1300];
int goi[4]={0,1,0,-1};
int goj[4]={1,0,-1,0};
int main()
{
cin>>m>>n;
int i=0,j,k=0,x=1,y=1;
memset(p,'0',sizeof(p));
while(1)
{
if(p[x][y]=='0'&&x<=m&&x>=1&&y<=n&&y>=1)
{
p[x][y]='A'+i%26;
i++;
if(i==m*n)break;
x += goi[k];y += goj[k];
}
else
{
x -=goi[k];y -= goj[k];
k=(k+1)%4;
x += goi[k];y += goj[k];
}
}
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(j==n) cout<<" "<<p[i][j]<<endl;
else cout<<" "<<p[i][j];}
} 阅读全文
类别：Poj 查看评论
2010年2月15日
这个题是2506的加强版，思路是一样的。
独立的可递推情况变得更多。
独立2列时有3种，而独立4列，6列，8列……所有偶数列都有两种
于是这个递推公式复杂一些
f(n)=3*f(n-2)+2*f(n-4)+2*f(n-6)+2*f(n-8)…………
这两个题f(0)都是1，很有意思~。一开始就这里WA了。
#include<iostream>
using namespace std;
//f(n)=3*f(n-2)+2*f(n-4)+2*f(n-6)……
int f[50];
int main()
{
int i,j,t;
f[0]=1;
f[1]=0;
f[2]=3;
for(i=4;i<=30;i++)
{
f[i]=3*f[i-2];
for(j=2; ;j++)
{
t=i-2*j;
if(t<0)break;
else
f[i]+=2*f[t];
}
}
while(cin>>t)
{
if(t==-1)break;
cout<<f[t]<<endl;
}
} 阅读全文
类别：Poj 查看评论
给看似复杂的题找到了合适的规律就会变得简单。
这个题就是这样。对于n列来说，可以在n-1列的基础上加上一块，或者是在n-2列的基础上加上2块
而2块独立的，不依赖于1块的情况有两种，所以得到递推公式f(n)=f(n-1)+2f(n-2)
看样例，要用到高精。
#include<iostream>
//f(n)=f(n-1)+2f(n-2)
using namespace std;
int f[251][300];
void HPprint(int *a)
{
for (int i=a[0];i>=1;i--) cout<<a[i];
cout<<endl;
}
void HPplus(int *a,int *b,int *c)
{
int i,j;
j=0;
for(i=1;i<=min(a[0],b[0]);i++)
{
c[i]=a[i]+b[i]+j;
j=c[i]/10;
c[i]%=10;
}
if(j!=0) c[i]=j;
c[0]=a[0]>b[0]?a[0]+2:b[0]+2;
while(c[c[0]]==0 && c[0]>1) c[0]--;
}
void HPmultyNUM(int *a,int b,int *c)
{
int i,j,k;
for (i=1;i<=a[0];i++)
c[i]+=a[i]*b;
k=0;
for (j=1;j<=a[0];j++)
{
c[j]+=k;
k=c[j]/10;
c[j]%=10;
}//进位
if(k!=0) c[j]=k;
c[0]=a[0]+3;
while (c[c[0]]==0 && c[0]>1) c[0]--;
}
int main()
{
int i,j,t[300],test;
f[0][0]=1;f[0][1]=1;
f[1][0]=1;f[1][1]=1;f[2][0]=1;f[2][1]=3;
for(i=3;i<=250;i++)
{
memset(t,0,sizeof(t));
HPmultyNUM(f[i-2],2,t);
HPplus(t,f[i-1],f[i]);
}
while(cin>>test)
HPprint(f[test]);
return 0;
} 阅读全文
类别：Poj 查看评论
|