http://vjudge.net/vjudge/contest/view.action?cid=54562#overview
H B. Polygons http://codeforces.com/problemset/problem/166/B
目前已知两种解法，先贴一个凸包的。算法是把两个多边形的点一起做一个凸包，看这个凸包是否包含b的点，包含说明b不是严格在a内，凸包要包括边上的点。复杂度nlogn，n为两个凸包点的和n=m+n=120000。nlogn=2024720。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-;
const int M=;
struct point{
double x,y;
bool type;
}a[M],b[M];
bool operator < (const point &l, const point &r) {
return l.y < r.y || (fabs(l.y- r.y)<eps && l.x < r.x);
}
class ConvexHull { //凸包
bool mult(point sp, point ep, point op) {//>包括凸包边上的点,>=不包括
return (sp.x - op.x) * (ep.y - op.y)> (ep.x - op.x) * (sp.y - op.y);
}
public:
int graham(int n,point p[],point res[]) {//多边形点个数和点数组，凸包存res
sort(p, p + n);
if (n == ) return ;
res[] = p[];
if (n == ) return ;
res[] = p[];
if (n == ) return ;
res[] = p[];
int top=;
for (int i = ; i < n; i++) {
while (top && mult(p[i], res[top], res[top-])) top--;
res[++top] = p[i];
}
int len = top;
res[++top] = p[n - ];
for (int i = n - ; i >= ; i--) {
while (top!=len && mult(p[i], res[top],res[top-])) top--;
res[++top] = p[i];
}
return top; // 返回凸包中点的个数
}
} gx;
int main(){
int n,m;
while(~scanf("%d",&n)){
for(int i=;i<n;i++){
scanf("%lf%lf",&a[i].x,&a[i].y);
a[i].type=true;
}
scanf("%d",&m);
for(int i=;i<m;i++){
scanf("%lf%lf",&a[i+n].x,&a[i+n].y);
a[i+n].type=false;
}
int lb=gx.graham(n+m,a,b);
bool flag=true;
for(int i=;i<lb;i++){
if(!b[i].type){
flag=false;
break;
}
}
if(flag) puts("YES");
else puts("NO");
}
return ;
}
还有就是直接on判断b的点是否在a内。复杂度mlogn，m是b的点，n是a的点。mlogn=332192.
#include<cstdio>
const int M=;
struct point{
double x,y;
}a[M],p;
class PinConvexHull{//判断点严格在凸包内(logn)
double mult(point sp,point ep,point op){
return (sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y);
}
public:
bool solve(point p,point a[],int n){//传入待判断点，凸包点数组，凸包点个数
int L=,R=n-;
while(L<=R){
int mid=(L+R)>>;
if(mult(a[mid],p,a[])>=){
R=mid-;
}
else{
L=mid+;
}
}
if(L<||mult(a[n-],p,a[])<=||mult(a[L-],p,a[L])<=) {
return false;
}
return true;
}
}gx;
int main(){
int n,m;
while(~scanf("%d",&n)){
for(int i=;i<n;i++){
scanf("%lf%lf",&a[i].x,&a[i].y);
}
scanf("%d",&m);
bool flag=true;
while(m--){
scanf("%lf%lf",&p.x,&p.y);
if(!gx.solve(p,a,n)) flag=false;
}
if(flag) puts("YES");
else puts("NO");
}
return ;
}
F Minimal Ratio Tree http://acm.hdu.edu.cn/showproblem.php?pid=2489
最小生成树克鲁斯卡尔，二进制枚举，浮点数比较加eps，输出格式不要多余空格，边的数组大小要注意，最大能n^2
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const double eps=1e-;
const int inf=0x7fffffff;
const int M=;
class Kruskal { //最小生成树 kruskal 算法
class UnionFindSet {//并查集
int par[M];
public:
void init() {
mt(par,-);
}
int getroot(int x) {
int i=x,j=x,temp;
while(par[i]>=) i=par[i];
while(j!=i) {
temp=par[j];
par[j]=i;
j=temp;
}
return i;
}
bool unite(int x,int y) {
int p=getroot(x);
int q=getroot(y);
if(p==q)return false;
if(par[p]>par[q]) {
par[q]+=par[p];
par[p]=q;
} else {
par[p]+=par[q];
par[q]=p;
}
return true;
}
} f;
struct E {
int u,v,w;
friend bool operator < (E a,E b) {
return a.w<b.w;
}
} e[M];
int le,res,num,n;
public:
void init(int x) {
n=x;
le=res=;
f.init();
num=;
}
void add(int u,int v,int w) {
e[le].u=u;
e[le].v=v;
e[le].w=w;
le++;
}
void solve() {
sort(e,e+le);
for(int i=; i<le&&num<n; i++) {
if(f.unite(e[i].u,e[i].v)) {
num++;
res+=e[i].w;
}
}
if(num<n) res=inf;
}
int getvalue() {
return res;
}
}gx;
int one(int x){
int res=;
while(x){
if(x&){
res++;
}
x>>=;
}
return res;
}
int val[M],tmp[M],ans[M],dist[M][M];
int main(){
int n,m;
while(~scanf("%d%d",&n,&m),n|m){
for(int i=;i<n;i++){
scanf("%d",&val[i]);
}
for(int i=;i<n;i++){
for(int j=;j<n;j++){
scanf("%d",&dist[i][j]);
}
}
int big=<<n;
double sma=inf;
for(int i=;i<big;i++){
if(one(i)==m){
int lt=;
int sumnode=;
for(int j=;j<n;j++){
if((i>>j)&){
tmp[lt++]=j;
sumnode+=val[j];
}
}
gx.init(m);
for(int j=;j<m;j++){
for(int k=j+;k<m;k++){
gx.add(j,k,dist[tmp[j]][tmp[k]]);
}
}
gx.solve();
int sumedge=gx.getvalue();
double now=sumedge*1.0/sumnode;
if(sma>now+eps){
sma=now;
for(int j=;j<m;j++){
ans[j]=tmp[j];
}
continue;
}
if(fabs(sma-now)<eps){
bool flag=false;
for(int j=;j<m;j++){
if(tmp[j]>ans[j]) break;
if(tmp[j]<ans[j]){
flag=true;
break;
}
}
if(flag){
for(int j=;j<m;j++){
ans[j]=tmp[j];
}
}
}
}
}
for(int i=;i<m;i++){
if(i) printf(" ");
printf("%d",ans[i]+);
}
puts("");
}
return ;
}
最小生成树prim，一样一样的。
#include<cstdio>
#include<cmath>
const double eps=1e-;
const int inf=0x7fffffff;
const int M=;
class Prim { //无向图最小生成树 prim,邻接阵O(n^2)必须保证图的连通的!
int n,mat[M][M],dis[M],pre[M],v[M],ret,i,j,k;
public: // pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-1
void init(int x) {
n=x;
for(i=; i<n; i++)
for(j=; j<n; j++)
mat[i][j]=i==j?:inf;//不相邻点边权inf
}
void add(int u,int v,int w) {
mat[u][v]=w;
mat[v][u]=w;
}
int solve() {
ret=;
for (i=; i<n; i++) dis[i]=inf,v[i]=,pre[i]=-;
for (dis[j=]=; j<n; j++) {
for (k=-,i=; i<n; i++) if (!v[i]&&(k==-||dis[i]<dis[k])) k=i;
for (v[k]=,ret+=dis[k],i=; i<n; i++) if (!v[i]&&mat[k][i]<dis[i]) dis[i]=mat[pre[i]=k][i];
}
return ret;//返回最小生成树的长度
}
}gx;
int val[M],tmp[M],ans[M],dist[M][M];
int one(int x){
int res=;
while(x){
if(x&){
res++;
}
x>>=;
}
return res;
}
int main(){
int n,m;
while(~scanf("%d%d",&n,&m),n|m){
for(int i=;i<n;i++){
scanf("%d",&val[i]);
}
for(int i=;i<n;i++){
for(int j=;j<n;j++){
scanf("%d",&dist[i][j]);
}
}
int big=<<n;
double sma=inf;
for(int i=;i<big;i++){
if(one(i)==m){
int lt=,sumnode=;
for(int j=;j<n;j++){
if((i>>j)&){
tmp[lt++]=j;
sumnode+=val[j];
}
}
gx.init(m);
for(int j=;j<m;j++){
for(int k=j+;k<m;k++){
gx.add(j,k,dist[tmp[j]][tmp[k]]);
}
}
int sumedge=gx.solve();
double now=sumedge*1.0/sumnode;
if(sma>now+eps){
sma=now;
for(int j=;j<m;j++){
ans[j]=tmp[j];
}
continue;
}
if(fabs(sma-now)<eps){
bool flag=false;
for(int j=;j<m;j++){
if(tmp[j]>ans[j]) break;
if(tmp[j]<ans[j]){
flag=true;
break;
}
}
if(flag){
for(int j=;j<m;j++){
ans[j]=tmp[j];
}
}
}
}
}
for(int i=;i<m;i++){
if(i) printf(" ");
printf("%d",ans[i]+);
}
puts("");
}
return ;
}
G The area http://acm.hdu.edu.cn/showproblem.php?pid=1071
给3个点，两点确定一条直线，三点确定二次函数的方程，分别求区间内的面积，积分，然后相减就是阴影面积。
#include<cstdio>
int main() {
int t;
double x1,x2,x3,y1,y2,y3;
while(~scanf("%d",&t)) {
while(t--) {
scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3);
double a2=(y3-y2)/(x3-x2);
double b2=y2-a2*x2;
double a1=((y2-y1)/(x2-x1)-(y3-y1)/(x3-x1))/(x2-x3);
double b1=(y3-y1)/(x3-x1)-a1*(x3+x1);
double c1=y1-a1*x1*x1-b1*x1;
double s1=a1*x3*x3*x3/+b1*x3*x3/+c1*x3;
double h1=a1*x2*x2*x2/+b1*x2*x2/+c1*x2;
s1-=h1;
double s2=a2*x3*x3/+b2*x3;
double h2=a2*x2*x2/+b2*x2;
s2-=h2;
printf("%.2f\n",s1-s2);
}
}
return ;
}
E Ping pong http://acm.hdu.edu.cn/showproblem.php?pid=2492
用on的预处理出某一个位置之前几个比它小，几个它大，后面同理，前面小乘后面大的个数，是一种，前面大乘后面小的，是一种。预处理中要快速知道前面有几个比我小，那么可以用树状数组把on的求和降到logn。
#include<cstdio>
#include<cstring>
#define mt(a,b) memset(a,b,sizeof(a))
typedef __int64 LL;
const int M=;
class One_Tree_Array { //一维树状数组
typedef int typev;
typev a[M];
public:
void init() {
mt(a,);
}
int lowb(int t) {
return t&(-t);
}
void add(int i,typev v) {
for(; i<M; a[i]+=v,i+=lowb(i));
}
typev sum(int i) {
typev s=;
for(; i>; s+=a[i],i-=lowb(i));
return s;
}
}gx;
int a[M],big[M],sma[M],prebig[M],presma[M];
int main(){
int t,n;
while(~scanf("%d",&t)){
while(t--){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
gx.init();
for(int i=n;i>=;i--){
sma[i]=gx.sum(a[i]);
big[i]=n-i-sma[i];
gx.add(a[i],);
}
gx.init();
for(int i=;i<=n;i++){
presma[i]=gx.sum(a[i]);
prebig[i]=i--presma[i];
gx.add(a[i],);
}
LL ans=;
for(int i=;i<=n;i++){
ans+=prebig[i]*sma[i];
ans+=presma[i]*big[i];
}
printf("%I64d\n",ans);
}
}
return ;
}
当然可以掏出线段树来做树状数组的工作。
#include<cstdio>
#include<cstring>
#define mt(a,b) memset(a,b,sizeof(a))
#define lrrt int L,int R,int rt
#define iall 1,M-1,1
#define imid int mid=(L+R)>>1
#define lson L,mid,rt<<1
#define rson mid+1,R,rt<<1|1
typedef __int64 LL;
const int M=;
int tree[M<<];
int a[M],big[M],sma[M],prebig[M],presma[M];
void pushup(int rt){
tree[rt]=tree[rt<<]+tree[rt<<|];
}
void update(int x,lrrt){
if(L==R){
tree[rt]++;
return ;
}
imid;
if(mid>=x) update(x,lson);
else update(x,rson);
pushup(rt);
}
int query(int x,int y,lrrt){
if(x<=L&&R<=y) return tree[rt];
imid;
int ans=;
if(mid>=x) ans+=query(x,y,lson);
if(mid<y) ans+=query(x,y,rson);
return ans;
}
int main(){
int t,n;
while(~scanf("%d",&t)){
while(t--){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
mt(tree,);
for(int i=n;i>=;i--){
sma[i]=query(,a[i],iall);
big[i]=n-i-sma[i];
update(a[i],iall);
}
mt(tree,);
for(int i=;i<=n;i++){
presma[i]=query(,a[i],iall);
prebig[i]=i--presma[i];
update(a[i],iall);
}
LL ans=;
for(int i=;i<=n;i++){
ans+=prebig[i]*sma[i];
ans+=presma[i]*big[i];
}
printf("%I64d\n",ans);
}
}
return ;
}
A Online Judge http://acm.hdu.edu.cn/showproblem.php?pid=1073
模拟字符串比较
#include<cstdio>
#include<cstring>
const int M=;
char a[M][M],b[M][M],sa[M*M],sb[M*M],op[M];
bool judge(char c) {
if(c==' '||c=='\t'||c=='\n') return false;
return true;
}
int main() {
int t;
while(~scanf("%d",&t)) {
getchar();
while(t--) {
gets(op);
int la=;
while(gets(op)&&strcmp(op,"END")) {
strcpy(a[la++],op);
}
gets(op);
int lb=;
while(gets(op)&&strcmp(op,"END")) {
strcpy(b[lb++],op);
}
if(la==lb) {
bool flag=true;
for(int i=; i<la; i++) {
if(strcmp(a[i],b[i])) {
flag=false;
break;
}
}
if(flag) {
puts("Accepted");
continue;
}
}
int lsa=,lsb=;
for(int i=; i<la; i++) {
for(int j=; a[i][j]; j++) {
if(judge(a[i][j])) {
sa[lsa++]=a[i][j];
}
}
}
sa[lsa]=;
for(int i=; i<lb; i++) {
for(int j=; b[i][j]; j++) {
if(judge(b[i][j])) {
sb[lsb++]=b[i][j];
}
}
}
sb[lsb]=;
if(!strcmp(sa,sb)) puts("Presentation Error");
else puts("Wrong Answer");
}
}
return ;
}
C Box of Bricks http://poj.org/problem?id=1477
水。
#include<cstdio>
#include<cstdlib>
const int M=;
int a[M];
int main(){
int n,cas=;
while(~scanf("%d",&n),n){
int sum=;
for(int i=;i<n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
sum/=n;
int ans=;
for(int i=;i<n;i++){
ans+=abs(a[i]-sum);
}
printf("Set #%d\nThe minimum number of moves is %d.\n\n",cas++,ans/);
}
return ;
}
B X问题 http://acm.hdu.edu.cn/showproblem.php?pid=1573
由于x%a=b ai共10个，并且最大值是10，所以最小公倍数最大是2520，可以暴力。
#include<cstdio>
const int M=;
int a[M],b[M];
int gcd(int a,int b) { //最大公约数
return b?gcd(b,a%b):a;
}
int lcm(int a,int b) { //最小公倍数
return a/gcd(a,b)*b;
}
int main(){
int t,n,m;
while(~scanf("%d",&t)){
while(t--){
scanf("%d%d",&n,&m);
int sumlcm=;
for(int i=;i<m;i++){
scanf("%d",&a[i]);
sumlcm=lcm(sumlcm,a[i]);
}
for(int i=;i<m;i++){
scanf("%d",&b[i]);
}
int ans=-;
for(int i=;i<=sumlcm;i++){
bool flag=true;
for(int j=;j<m;j++){
if(i%a[j]!=b[j]){
flag=false;
break;
}
}
if(flag){
ans=i;
break;
}
}
if(ans==-||ans>n){
puts("");
continue;
}
int sum=(n-ans)/sumlcm+;
printf("%d\n",sum);
}
}
return ;
}
也可以用不要求ai互质的中国剩余定理解模线性方程组。
#include<cstdio>
const int M=;
int a[M],b[M];
int gcd(int a,int b) { //最大公约数
return b?gcd(b,a%b):a;
}
int lcm(int a,int b) { //最小公倍数
return a/gcd(a,b)*b;
}
int ext_gcd(int a,int b,int &x,int &y) { //扩展gcd d=gcd(a,b)=a*x+b*y; return d,x,y;
int t,ret;
if(!b) {
x=;
y=;
return a;
}
ret=ext_gcd(b,a%b,x,y);
t=x;
x=y;
y=t-a/b*y;
return ret;
}
int modular_linear_system(int a[],int b[],int n){//求解模线性方程组(无要求)X mod a[i]=b[i],n个方程
int m1,m2,r1,r2,c,d,t,x,y;
m1=a[];
r1=b[];
for(int i=;i<n;i++){
m2=a[i];
r2=b[i];
c=r2-r1;
d=ext_gcd(m1,m2,x,y);
if(c%d) return -;
t=m2/d;
x=(c/d*x%t+t)%t;
r1=m1*x+r1;
m1=m1*m2/d;
}
return r1;
}
int main() {
int t,n,m;
while(~scanf("%d",&t)) {
while(t--) {
scanf("%d%d",&n,&m);
int sumlcm=;
for(int i=; i<m; i++) {
scanf("%d",&a[i]);
sumlcm=lcm(sumlcm,a[i]);
}
for(int i=; i<m; i++) {
scanf("%d",&b[i]);
}
int ans=modular_linear_system(a,b,m);
if(ans==-||ans>n) {
puts("");
continue;
}
if(ans==) ans+=sumlcm;
int sum=(n-ans)/sumlcm+;
printf("%d\n",sum);
}
}
return ;
}
end