又偷懒了。。。用了STL中的std::lower_bound
速度好慢。。。#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) #define N 3010 typedef long long LL; using namespace std; int n,m,T,k; LL f[N]; int Time[N]; struct node{int t;LL p2,p1;}; node s[N]; int find(int x) { int *p=lower_bound(Time+1,Time+1+k,x); return p-Time; } int main() { scanf("%d%d%d%d",&n,&m,&T,&k);
Views:
477
|
Added by:
dhy0077
|
Date:
10.11.2013
|
SPOJ 上有，4月份做的，贪心var ans:qword;n,i,b1,t:longint; a,a1:array[0..100000] of longint; procedure qsort(l,r:longint); var i,j,t,m:longint; begin i:=l;j:=r;m:=a[(l+r) div 2]; repeat while a[i]>m do inc(i); while a[j]<m do dec(j); if i<=j then begin t:=a[i];a[i]:=a[j];a[j]:=t; inc(i);dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end; begin readln(n); a[0]:=0;b1:=0; for i:=1 to n do begin readln(a1[i]); b1:=b1+a1[i]; end; b1:=b1 div n; for i:=1 to n do begin
...
Read more »
Views:
259
|
Added by:
dhy0077
|
Date:
10.11.2013
|
这题想了一会就想出来了其实可以在n^2上做一些优化方程:f[i]=min(f[j]+1)(j<i)(time[j]>=time[i]+dis(p[i],p[j]))
#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define M 100001 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; int x[M],y[M],t[M],a[M],f[M],n,m; int dis(int i,int j) { return fabs(x[i]-x[j])+fabs(y[i]-y[j]); } int main() { cin>>n>>m; int i,j; FOR(i,1,m)
Views:
530
|
Added by:
dhy0077
|
Date:
10.11.2013
|
想了半天，越看越像二分图
ps:就是二分图，傻了
#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define N 100010 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; int pre[N],last[N],e[N],size[N],n,len=0,V[N],d[N]; void add(int x,int y) { pre[++len]=last[x]; last[x]=len;e[len]=y; size[x]++; } int DFS(int x) { int pos=last[x],i;
Views:
433
|
Added by:
dhy0077
|
Date:
10.11.2013
|
数据太水了
可以做到nlogn的
Views:
430
|
Added by:
dhy0077
|
Date:
10.11.2013
|
Views:
405
|
Added by:
dhy0077
|
Date:
10.11.2013
|
Views:
426
|
Added by:
dhy0077
|
Date:
10.11.2013
|
这个贪心写起来好麻烦#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define N 5010 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; struct node{int d,p;}; int cmp(node a,node b){return a.d<b.d;} node P[N]; string st; int n,k; void doit1() { int w=n/P[0].d; int y=n-P[0].d*w; st=""; int i,j; FOR(i,1,w) st+=('0'+P[0].p); int maxp=0,pos; FOR(i,0,w-1)
Views:
449
|
Added by:
dhy0077
|
Date:
10.11.2013
|
数组模拟链表+ST-RMQ#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) #define N 300010 #define M 40 typedef long long LL; using namespace std; int dep,L,pre[N],last[N],size[N],e[N],len=0,f[N],D[N],p[N],dp[N][M],n,flag[N]; void add(int u,int v) { pre[++len]=last[u]; last[u]=len;e[len]=v; size[u]++; } void RMQ_init(int n) { int i,j; for (i=1;i<=n;i++) dp[i][0]=D[i];
Views:
329
|
Added by:
dhy0077
|
Date:
10.11.2013
| |