随笔档案

三分

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

struct point { double x,y; };
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);
}

bool operator < (const point &l,const point &r){
    return l.y<r.y || (l.y==r.y && l.x < r.x);
}

int graham(point pnt[],int n,point res[]){ //pnt是图中的所有的点，res是通过判断后在凸边行边上的点，而且这些点都是按逆时针存储的，n是所有点的个数
    int i,len,k = 0,top = 1;
    sort(pnt,pnt+n);
    if(n == 0) return 0; res[0]=pnt[0];
    if(n == 1) return 1; res[1]=pnt[1];
    if(n == 2) return 2; res[2]=pnt[2];
    for(i=2;i<n;i++) {
        while(top && mult(pnt[i],res[top],res[top-1]))
            top--;
        res[++top] = pnt[i];
    }
    len = top; res[++top] = pnt[n-2];
    for(i=n-3;i>=0;i--){
        while(top!=len && mult(pnt[i],res[top],res[top-1]))
            top--;
        res[++top]=pnt[i];
    }
    return top; // 返回凸包中点的个数
}

point res[50001],pnt[50001];

int main() {
    int n;
    while(~scanf("%d",&n) && n) {
        for(int i=0;i<n;i++) scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
        if(graham(pnt,n,res) == n) puts("convex");
        else puts("concave");  
    }
    return 0;   
}

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[7];
int dp[121111];
int v,k;
void ZeroOnePack(int cost,int weight) {
    for(int i=v;i>=cost;i--)
        dp[i] = max(dp[i] , dp[i-cost] + weight);   
}
void CompletePack(int cost,int weight) {
    for(int i=cost;i<=v;i++)
        dp[i] = max(dp[i] , dp[i-cost] + weight);   
}
void MultiplePack(int cost,int weight,int amount) {
    if(cost * amount >= v) CompletePack(cost,weight);
    else {
        for(int k=1;k<amount;) {
            ZeroOnePack(k*cost,k*weight);
            amount -= k;
            k <<= 1;   
        }   
        ZeroOnePack(amount*cost,amount*weight);
    } 
}
int main() {
    int cas = 1;
    while(1) {
        int tot = 0;
        for(int i=1;i<=6;i++) {
            scanf("%d",&a[i]);
            tot += a[i] * i;
        }   
        if(tot == 0) break;
        printf("Collection #%d:\n",cas++);
        if(tot % 2) puts("Can't be divided.");
        else {
            v = tot / 2;
            memset(dp,0,sizeof(dp));
            for(int i=1;i<=6;i++) {
                MultiplePack(i,i,a[i]);   
            }   
            if(dp[v] == v) puts("Can be divided.");
            else puts("Can't be divided.");
        }
        puts("");
    }
    return 0;   
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int t;
double n,a,b;
int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%lf",&n);
        a = n * log10(n);
        b = pow(10 , a - floor(a));
        printf("%d\n",(int)b);
    } 
    return 0;   
}
http://walcl.cn/post/85.html 我承认我以前只会三个人的“田忌赛马”。。。。。。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a[1111] , b[1111];
int s1 , e1 , s2 ,e2;
int n;
bool cmp(int a,int b) {
    return a > b;
}
void solve() {
    s1 = s2 = 0;
    e1 = e2 = n - 1;
    int ans = 0;
    for(;s1 <= e1;) {
        if(a[e1] > b[e2]) ans ++,e1--,e2--;
        else if(a[s1] > b[s2]) ans ++,s1++,s2++;
        else {
            if(a[e1] != b[s2]) ans --;
            e1 -- , s2 ++; 
        }
    }   
    printf("%d\n",ans*200);
}
int main() {
    while(~scanf("%d",&n) && n) {
        for(int i=0;i<n;i++) scanf("%d",a+i);
        for(int i=0;i<n;i++) scanf("%d",b+i);
        sort(a,a+n,cmp);
        sort(b,b+n,cmp);   
        solve();
    }
    return 0;
}

#include <cstdio>
#include <cstring>
using namespace std;
int g[33][33],linky[33];
bool vis[33];
char map[5][5];
int mapl[5][5],mapr[5][5];
int n , m;
bool find(int u) {
    for(int v=1;v<=m;v++)
        if(g[u][v] && !vis[v]) {
            vis[v] = 1;
            if(linky[v]==-1 || find(linky[v])) {
                linky[v] = u;
                return true;   
            }   
        }
    return false;
}
int hungry() {
    int ret = 0;
    memset(linky,-1,sizeof(linky));
    for(int u=1;u<=n;u++) {
        memset(vis,0,sizeof(vis));
        if(find(u)) ret ++;  
    }   
    return ret;
}
int main() {
    int N;
    while(~scanf("%d",&N) && N) {
        memset(mapl,0,sizeof(map));
        memset(mapr,0,sizeof(mapr));
        for(int i=0;i<N;i++) scanf("%s",map[i]);
        n = m = 0;
        for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(map[i][j] == 'X') mapl[i][j] = mapr[i][j] = -1;
        for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) {
            while(mapr[i][j]==-1&&j<N) j++;
            n ++;
            while(mapr[i][j]!=-1&&j<N) mapr[i][j++] = n;   
        }
        for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) {
            while(mapl[j][i]==-1&&j<N) j++;
            m ++;
            while(mapl[j][i]!=-1&&j<N) mapl[j++][i] = m;   
        }
        memset(g,0,sizeof(g));
        for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) {
            if(mapr[i][j]!=-1&&mapl[i][j]!=-1) g[mapr[i][j]][mapl[i][j]] = 1;   
        }
        int ans = hungry();
        printf("%d\n",ans);
    }
    return 0;   
}

http://www.cnblogs.com/ambition/archive/2011/07/25/search_plus.html http://blog.csdn.net/yrc1993/article/details/7841208