利用区间序,先排序O(nlgn)再O(n)求解#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #define N 100100 #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 L,R; }; node a[N],ans[N]; int cmp(node a,node b) { if (a.L<b.L) return 1; if (b.L<a.L) return 0; if (b.R<a.R) return 1; if (a.R<b.R) return 0; return 0; } int main() { int n,i;
Views:
467
|
Added by:
dhy0077
|
Date:
09.28.2013
|
四平方和定理#include<cstdio> #include<cstdlib> #include<cmath> #define FOR(i,a,b) for(i=(a);i<=(b);i++) using namespace std; int i,j,n; int c1(int t){int R=(int)sqrt(t);return R*R==t;} int c2(int t){FOR(i,1,(int)sqrt(t)) if (c1(t-i*i)) return 1;return 0;} int c3(int t){FOR(j,1,(int)sqrt(t)) if (c2(t-j*j)) return 1;return 0;} int main() { scanf("%d",&n); if (c1(n)) {printf("1\n");return 0;} if (c2(n)) {printf("2\n");return 0;} if (c3(n)) {printf("3\n");return 0;} printf("4\n"); }
Views:
265
|
Added by:
dhy0077
|
Date:
09.28.2013
|
并查集#include<cstdio> #define N 1001 #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 f[N],g[N]; int getf(int x) {if (f[x]==x) return x;int tf=getf(f[x]);g[x]+=g[f[x]];return (f[x]=tf);} int Main() { int i,F=1,n,m,x,y,z; scanf("%d%d",&n,&m); FOR(i,0,n) {f[i]=i;g[i]=0;} FOR(i,1,m) { scanf("%d%d%d",&x,&y,&z); int u=getf(x-1),v=getf(y); if (u!=v) {f[u]=v;g[u]=g[y]-z-g[x-1];} else if (g[y]-g[x-1]!=z) {F=0;break;} } F?printf("true\n"):printf("false\n"); } int main(){int w,i;scanf("%d",&w);FOR(i,1,w) Main();}
...
Read more »
Views:
292
|
Added by:
dhy0077
|
Date:
09.28.2013
|
set#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #define ittype multiset<int>::iterator #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; multiset<int> S; int main() { int x,n,i; scanf("%d",&n); scanf("%d",&x);S.insert(x); int ans=2E9; FOR(i,2,n) { scanf("%d",&x); ittype it=S.insert(x),it2,it3; if (it!=S.begin())
Views:
309
|
Added by:
dhy0077
|
Date:
09.28.2013
| |