算法设计与分析讨论班上机作业

2018年4月2日8,6120

凸包

A:Wall POJ1113

求凸包周长加一个圆

#include<map>
#include<deque>
#include<ctime>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 2000000000
using namespace std;
int n,R,top;
struct P{
    double x,y;
}p[1005],s[1005];
double dis(P a,P b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
P operator-(P a,P b)
{
    P t;t.x=a.x-b.x;t.y=a.y-b.y;return t;
}
double operator*(P a,P b)
{
    return a.x*b.y-a.y*b.x;
}
bool operator<(P a,P b)
{
    double t=(a-p[1])*(b-p[1]);
    if(t==0)return dis(a,p[1])<dis(b,p[1]);
    return t<0;
}
void graham()
{
    int k=1;
    for(int i=2;i<=n;i++)
        if(p[k].y>p[i].y||(p[k].y==p[i].y&&p[k].x>p[i].x))
            k=i;
    swap(p[1],p[k]);
    sort(p+2,p+n+1);
    s[++top]=p[1];s[++top]=p[2];
    for(int i=3;i<=n;i++)
    {
        while(top>1&&(p[i]-s[top-1])*(s[top]-s[top-1])<=0)
            top--;
        s[++top]=p[i];
    }
}
int main()
{
    scanf("%d%d",&n,&R);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&p[i].x,&p[i].y);
    graham();
    double ans=0;
    s[0]=s[top];
    for(int i=1;i<=top;i++)
        ans+=sqrt(dis(s[i],s[i-1]));
    ans=ans+2*acos(-1)*R;
    printf("%d\n",(int)round(ans));
    return 0;
}

#include<map>

#include<deque>

#include<ctime>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 2000000000

using namespace std;

int n,R,top;

struct P{

double x,y;

}p[1005],s[1005];

double dis(P a,P b)

{

return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

}

P operator-(P a,P b)

{

P t;t.x=a.x-b.x;t.y=a.y-b.y;return t;

}

double operator*(P a,P b)

{

return a.x*b.y-a.y*b.x;

}

bool operator<(P a,P b)

{

double t=(a-p[1])*(b-p[1]);

if(t==0)return dis(a,p[1])<dis(b,p[1]);

return t<0;

}

void graham()

{

int k=1;

for(int i=2;i<=n;i++)

if(p[k].y>p[i].y||(p[k].y==p[i].y&&p[k].x>p[i].x))

k=i;

swap(p[1],p[k]);

sort(p+2,p+n+1);

s[++top]=p[1];s[++top]=p[2];

for(int i=3;i<=n;i++)

{

while(top>1&&(p[i]-s[top-1])*(s[top]-s[top-1])<=0)

top--;

s[++top]=p[i];

}

int main()

{

scanf("%d%d",&n,&R);

for(int i=1;i<=n;i++)

scanf("%lf%lf",&p[i].x,&p[i].y);

graham();

double ans=0;

s[0]=s[top];

for(int i=1;i<=top;i++)

ans+=sqrt(dis(s[i],s[i-1]));

ans=ans+2*acos(-1)*R;

printf("%d\n",(int)round(ans));

return 0;

}

B:Scrambled Polygon POJ2007

排序凸包上的点

#include<set>
#include<map>
#include<deque>
#include<ctime>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 2000000000
using namespace std;
int n;
struct P{
    int x,y;
}p[10005];
int dis(P a,P b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
P operator-(P a,P b)
{
    P t;t.x=a.x-b.x;t.y=a.y-b.y;return t;
}
int operator*(P a,P b)
{
    return a.x*b.y-a.y*b.x;
}
bool operator<(P a,P b)
{
    int t=(a-p[1])*(b-p[1]);
    return t>0;
}
int main()
{
    n=1;
    while(scanf("%d%d",&p[n].x,&p[n].y)!=EOF)
        n++;
    n--;
    sort(p+2,p+n+1);
    for(int i=1;i<=n;i++)
        printf("(%d,%d)\n",p[i].x,p[i].y);
    return 0;
}

#include<set>

#include<map>

#include<deque>

#include<ctime>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 2000000000

using namespace std;

int n;

struct P{

int x,y;

}p[10005];

int dis(P a,P b)

{

return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

}

P operator-(P a,P b)

{

P t;t.x=a.x-b.x;t.y=a.y-b.y;return t;

}

int operator*(P a,P b)

{

return a.x*b.y-a.y*b.x;

}

bool operator<(P a,P b)

{

int t=(a-p[1])*(b-p[1]);

return t>0;

}

int main()

{

n=1;

while(scanf("%d%d",&p[n].x,&p[n].y)!=EOF)

n++;

n--;

sort(p+2,p+n+1);

for(int i=1;i<=n;i++)

printf("(%d,%d)\n",p[i].x,p[i].y);

return 0;

}

动态规划 G 题真的坑

A:Fourier’s Lines POJ1923

#include<set>
#include<map>
#include<deque>
#include<ctime>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 10000000000
#define ll long long
using namespace std;
int n, m;
int f[105][10005];
int check(int n, int m)
{
        if(m && (m < n - 1 || m > n * (n - 1) / 2))
                return 0;
        if(m == 0)return 1;
        if(f[n][m] != -1)return f[n][m];        
        f[n][m] = 0;
        for(int i = 1; i <= n; i++)
                f[n][m] |= check(n - i, m - i * (n - i));
        return f[n][m];
}
int main()
{
        memset(f, -1, sizeof(f));
        int T = 0;
        while(scanf("%d%d", &n, &m))
        {
                T++;
                if(n == 0)break;
                if(check(n, m))
                        printf("Case %d: %d lines with exactly %d crossings can cut the plane into %d pieces at most.\n", T, n, m, n + m + 1);
                else
                        printf("Case %d: %d lines cannot make exactly %d crossings.\n", T, n, m);                        
        }                
        return 0;
}

#include<set>

#include<map>

#include<deque>

#include<ctime>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 10000000000

#define ll long long

using namespace std;

int n, m;

int f[105][10005];

int check(int n, int m)

{

if(m && (m < n - 1 || m > n * (n - 1) / 2))

return 0;

if(m == 0)return 1;

if(f[n][m] != -1)return f[n][m];

f[n][m] = 0;

for(int i = 1; i <= n; i++)

f[n][m] |= check(n - i, m - i * (n - i));

return f[n][m];

}

int main()

{

memset(f, -1, sizeof(f));

int T = 0;

while(scanf("%d%d", &n, &m))

{

T++;

if(n == 0)break;

if(check(n, m))

printf("Case %d: %d lines with exactly %d crossings can cut the plane into %d pieces at most.\n", T, n, m, n + m + 1);

else

printf("Case %d: %d lines cannot make exactly %d crossings.\n", T, n, m);

}

return 0;

}

B:Tour POJ2677

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define inf 1000000000
using namespace std;
int n;
double f[55][55];
struct data{
    int x, y;
}p[55];
double dis(data a, data b)
{
    return sqrt((a.x - b.x)*(a.x - b.x)+(a.y - b.y)*(a.y - b.y));
}
int main()
{
    while(cin >> n)
    {
        for(int i = 1; i <= n; i++)
            cin >> p[i].x >> p[i].y;
        memset(f, 127, sizeof(f));
        f[1][1] = 0;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j < i; j++)
            {
                f[i][j] = min(f[i][j], f[i - 1][j] + dis(p[i - 1], p[i]));
                f[i][i - 1] = min(f[i][i - 1], f[i - 1][j] + dis(p[j], p[i]));
            }
        printf("%.2lf\n", f[n][n-1] + dis(p[n-1], p[n]));
    }
    return 0;
}

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#define inf 1000000000

using namespace std;

int n;

double f[55][55];

struct data{

int x, y;

}p[55];

double dis(data a, data b)

{

return sqrt((a.x - b.x)*(a.x - b.x)+(a.y - b.y)*(a.y - b.y));

}

int main()

{

while(cin >> n)

{

for(int i = 1; i <= n; i++)

cin >> p[i].x >> p[i].y;

memset(f, 127, sizeof(f));

f[1][1] = 0;

for(int i = 1; i <= n; i++)

for(int j = 1; j < i; j++)

{

f[i][j] = min(f[i][j], f[i - 1][j] + dis(p[i - 1], p[i]));

f[i][i - 1] = min(f[i][i - 1], f[i - 1][j] + dis(p[j], p[i]));

}

printf("%.2lf\n", f[n][n-1] + dis(p[n-1], p[n]));

}

return 0;

}

C:Increasing Sequences POJ1239

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#define inf 1000000000
using namespace std;
int n;
char s[105];
int f[105][105]; // 某个数是[l, r], 其能获得的最小的末尾数是[f[l][r], n]
vector<string> ans;
bool cmp(int l1, int r1, int l2, int r2) // 1 > 2?
{
   int p1 = l1, p2 = l2;
    while(s[p1] == '0' && p1 <= r1)p1++;
    while(s[p2] == '0' && p2 <= r2)p2++;
    if(r1 - p1 - 1 != r2 - p2 - 1)
        return (r1 - p1) > (r2 - p2);
    if(r1 - p1 + 1 == 0)return 0;
    while(p1 <= r1){
        if(s[p1] > s[p2])return 1;
        if(s[p1] < s[p2])return 0;
        p1++;
        p2++;
    }
    return 0;
}
int dp(int l, int r)
{
    if(r == n)f[l][r] = l;
    if(f[l][r])return f[l][r];
    f[l][r] = l;
    for(int i = r + 1; i <= n; i++)
        if(dp(r + 1, i) && cmp(r + 1, i, l, r))            
            f[l][r] = max(f[l][r], f[r + 1][i]);
    return f[l][r];
}
 
void print(int last, int x)
{
    if(x == n)return;
    string dig = "";
    int pos = n;
    for(int i = x + 1; i <= n; i++)
        if((!last || cmp(x + 1, i, last, x))
           &&
           (!cmp(f[x + 1][i], n, f[x + 1][pos], n)))
            pos = i;
           // 下一段是 [x + 1, pos]
    for(int i = x + 1; i <= pos; i++)
        dig = dig + s[i];
    ans.push_back(dig);
    print(x + 1, pos);
}
int main()
{    
    while(scanf("%s", s + 1))
    {
        n = strlen(s + 1);
        if(n == 1 && s[1] == '0')break;
        memset(f, 0, sizeof(f));
        for(int i = 1; i <= n; i++)
            for(int j = i; j <= n; j++)
                dp(i, j);
        ans.clear();
        print(1, 0);
        cout << ans[0];
        for(int i = 1; i < ans.size(); i++)
            cout << "," << ans[i];
        printf("\n");
    }
    return 0;
}

#include <cmath>

#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

#define inf 1000000000

using namespace std;

int n;

char s[105];

int f[105][105]; // 某个数是[l, r], 其能获得的最小的末尾数是[f[l][r], n]

vector<string> ans;

bool cmp(int l1, int r1, int l2, int r2) // 1 > 2?

{

int p1 = l1, p2 = l2;

while(s[p1] == '0' && p1 <= r1)p1++;

while(s[p2] == '0' && p2 <= r2)p2++;

if(r1 - p1 - 1 != r2 - p2 - 1)

return (r1 - p1) > (r2 - p2);

if(r1 - p1 + 1 == 0)return 0;

while(p1 <= r1){

if(s[p1] > s[p2])return 1;

if(s[p1] < s[p2])return 0;

p1++;

p2++;

}

return 0;

}

int dp(int l, int r)

{

if(r == n)f[l][r] = l;

if(f[l][r])return f[l][r];

f[l][r] = l;

for(int i = r + 1; i <= n; i++)

if(dp(r + 1, i) && cmp(r + 1, i, l, r))

f[l][r] = max(f[l][r], f[r + 1][i]);

return f[l][r];

}

void print(int last, int x)

{

if(x == n)return;

string dig = "";

int pos = n;

for(int i = x + 1; i <= n; i++)

if((!last || cmp(x + 1, i, last, x))

(!cmp(f[x + 1][i], n, f[x + 1][pos], n)))

pos = i;

// 下一段是 [x + 1, pos]

for(int i = x + 1; i <= pos; i++)

dig = dig + s[i];

ans.push_back(dig);

print(x + 1, pos);

}

int main()

{

while(scanf("%s", s + 1))

{

n = strlen(s + 1);

if(n == 1 && s[1] == '0')break;

memset(f, 0, sizeof(f));

for(int i = 1; i <= n; i++)

for(int j = i; j <= n; j++)

dp(i, j);

ans.clear();

print(1, 0);

cout << ans[0];

for(int i = 1; i < ans.size(); i++)

cout << "," << ans[i];

printf("\n");

}

return 0;

}

D:Charlie’s Change POJ1787

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#define inf 1000000000
using namespace std;
int P;
int f[5][10005], g[5][10005];
int w[5] = {0, 1, 5, 10, 25}, num[5];
int ans[5];
int main()
{
        while(scanf("%d", &P))
        {
                if(P == 0)return 0;
                memset(f, -1, sizeof(f));
                memset(g, 0, sizeof(g));
                for(int i = 1; i <= 4; i++)
                        scanf("%d", &num[i]);
                f[0][0] = 1;
                for(int i = 1; i <= 4; i++)
                        for(int j = 0; j <= P; j++)
                        {
                                f[i][j] = f[i - 1][j];
                                if(j >= w[i] && f[i][j - w[i]] != -1 && f[i][j - w[i]] + 1 > f[i][j] && g[i][j - w[i]] + 1 <= num[i])
                                {
                                        f[i][j] = f[i][j - w[i]] + 1;
                                        g[i][j] = g[i][j - w[i]] + 1;
                                }
                        }
                if(f[4][P] == -1)
                {
                        puts("Charlie cannot buy coffee.");
                        continue;
                }
                for(int i = 4; i >= 1; i--)
                {
                        ans[i] = g[i][P];
                        P -= ans[i] * w[i];
                }
                printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", ans[1], ans[2], ans[3], ans[4]);
        }
        return 0;
}

#include <cmath>

#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

#define inf 1000000000

using namespace std;

int P;

int f[5][10005], g[5][10005];

int w[5] = {0, 1, 5, 10, 25}, num[5];

int ans[5];

int main()

{

while(scanf("%d", &P))

{

if(P == 0)return 0;

memset(f, -1, sizeof(f));

memset(g, 0, sizeof(g));

for(int i = 1; i <= 4; i++)

scanf("%d", &num[i]);

f[0][0] = 1;

for(int i = 1; i <= 4; i++)

for(int j = 0; j <= P; j++)

{

f[i][j] = f[i - 1][j];

if(j >= w[i] && f[i][j - w[i]] != -1 && f[i][j - w[i]] + 1 > f[i][j] && g[i][j - w[i]] + 1 <= num[i])

{

f[i][j] = f[i][j - w[i]] + 1;

g[i][j] = g[i][j - w[i]] + 1;

}

if(f[4][P] == -1)

{

puts("Charlie cannot buy coffee.");

continue;

}

for(int i = 4; i >= 1; i--)

{

ans[i] = g[i][P];

P -= ans[i] * w[i];

}

printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", ans[1], ans[2], ans[3], ans[4]);

}

return 0;

}

E:Strange Towers of Hanoi POJ1958

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#define inf 1000000000
using namespace std;
int f[15];
int main()
{
        f[1] = 1;
        for(int i = 2; i <= 12; i++)
        {
                f[i] = 10000;
                for(int k = 1; k <= i; k++)
                        f[i] = min(f[i], 2 * f[i - k] + (int)pow(2, k) - 1);
        }
        for(int i = 1; i <= 12; i++)
                printf("%d\n", f[i]);
        return 0;
}

#include <cmath>

#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

#define inf 1000000000

using namespace std;

int f[15];

int main()

{

f[1] = 1;

for(int i = 2; i <= 12; i++)

{

f[i] = 10000;

for(int k = 1; k <= i; k++)

f[i] = min(f[i], 2 * f[i - k] + (int)pow(2, k) - 1);

}

for(int i = 1; i <= 12; i++)

printf("%d\n", f[i]);

return 0;

}

F:Balanced Lineup POJ3274

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,q,x,y,a[50001],mn[50001][16],mx[50001][16];
void pre()
{
    for(int i=1;i<=n;i++)
        mx[i][0]=mn[i][0]=a[i];
    int t=log(n)/log(2);
    for(int i=1;i<=t;i++)
        for(int j=n;j>0;j--)
        {
            mx[j][i]=mx[j][i-1];
            if(j+(1<<(i-1))<=n)
                mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);
        }
    for(int i=1;i<=t;i++)
        for(int j=n;j>0;j--)
        {
            mn[j][i]=mn[j][i-1];
            if(j+(1<<(i-1))<=n)
                mn[j][i]=min(mn[j][i],mn[j+(1<<(i-1))][i-1]);
        }
}
int rmq(int l,int r)
{
    int m=log(r-l+1)/log(2);
    int a=max(mx[l][m],mx[r-(1<<m)+1][m]);
    int b=min(mn[l][m],mn[r-(1<<m)+1][m]);
    return a-b;
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    pre();
    while(q--)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",rmq(x,y));
    }
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

int n,q,x,y,a[50001],mn[50001][16],mx[50001][16];

void pre()

{

for(int i=1;i<=n;i++)

mx[i][0]=mn[i][0]=a[i];

int t=log(n)/log(2);

for(int i=1;i<=t;i++)

for(int j=n;j>0;j--)

{

mx[j][i]=mx[j][i-1];

if(j+(1<<(i-1))<=n)

mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);

}

for(int i=1;i<=t;i++)

for(int j=n;j>0;j--)

{

mn[j][i]=mn[j][i-1];

if(j+(1<<(i-1))<=n)

mn[j][i]=min(mn[j][i],mn[j+(1<<(i-1))][i-1]);

}

int rmq(int l,int r)

{

int m=log(r-l+1)/log(2);

int a=max(mx[l][m],mx[r-(1<<m)+1][m]);

int b=min(mn[l][m],mn[r-(1<<m)+1][m]);

return a-b;

}

int main()

{

scanf("%d%d",&n,&q);

for(int i=1;i<=n;i++)

scanf("%d",&a[i]);

pre();

while(q--)

{

scanf("%d%d",&x,&y);

printf("%d\n",rmq(x,y));

}

return 0;

}

G:Banal Tickets POJ1608

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#define inf 1000000000
#define rad 100000000
#define ll long long
using namespace std;
int n;
char str[100];
ll f[2][55][40][20][20], g[55][40][20][20]; // i 2 3 5 7 0?
  
struct data{
    int l;ll v[20];
    data(){
        l=1;
        memset(v,0,sizeof(v));
    }
    data(ll x){
        memset(v,0,sizeof(v));
        l=0;
        while(x)
        {
            v[++l]=x%rad;
            x/=rad;
        }
    }
    ll& operator[](int x){
        return v[x];
    }
    friend data operator+(data a,data b){
        if(a.l<b.l)swap(a,b);
        for(int i=1;i<=b.l;i++)
            a[i]+=b[i];
        for(int i=1;i<=a.l;i++)
            if(a[i]>=rad)
            {
                if(i==a.l)a.l++;
                a[i+1]+=a[i]/rad;
                a[i]%=rad;
            }
        return a;
    }
    friend data operator-(data a,data b){
        for(int i=1;i<=b.l;i++)
            a[i]-=b[i];
        for(int i=1;i<=a.l;i++)
            if(a[i]<0)
            {
                a[i]+=rad;
                a[i+1]--;
            }
        while(!a[a.l]&&a.l>1)a.l--;
        return a;
    }
    friend data operator*(data a,ll b){
        for(int i=1;i<=a.l;i++)
            a[i]*=b;
        for(int i=1;i<=a.l;i++)
            if(a[i]>=rad)
            {
                a[i+1]+=a[i]/rad;
                a[i]%=rad;
                if(i==a.l)a.l++;
            }
        return a;
    }
    friend data operator*(data a,data b){
        data c;
        for(int i=1;i<=a.l;i++)
            for(int j=1;j<=b.l;j++)
                c[i+j-1]+=a[i]*b[j];
        for(int i=1;i<=a.l+b.l;i++)
        {
            if(c[i]>=rad)
            {
                c[i+1]+=c[i]/rad;
                c[i]%=rad;
            }
            if(c.v[i])c.l=i;
        }
        return c;
    }
    friend void print(data a){
        printf("%lld",a[a.l]);
        for(int i=a.l-1;i;i--)printf("%.8lld",a[i]);
        puts("");
    }
};
  
void dp(int L, int R)
{
    memset(f, 0, sizeof(f));        
    int p = 0, q = 1;
    f[0][0][0][0][0] = 1;
    for(int x = L - 1; x <= R - 1; x++)
    {
        int l = x - L + 1;
        char ch = str[x + 1];
        for(int a = 0; a <= 3 * l; a++)
            for(int b = 0; b <= 2 * l; b++)
                for(int c = 0; c <= l; c++)
                    for(int d = 0; d <= l; d++)
                        if(f[p][a][b][c][d])
                        {
                            if(ch == '1' || ch == '?')
                                f[q][a][b][c][d] += f[p][a][b][c][d];
                            if(ch == '2' || ch == '?')
                                f[q][a+1][b][c][d] += f[p][a][b][c][d];
                            if(ch == '3' || ch == '?')
                                f[q][a][b+1][c][d] += f[p][a][b][c][d];
                            if(ch == '4' || ch == '?')
                                f[q][a+2][b][c][d] += f[p][a][b][c][d];
                            if(ch == '5' || ch == '?')
                                f[q][a][b][c+1][d] += f[p][a][b][c][d];
                            if(ch == '6' || ch == '?')
                                f[q][a+1][b+1][c][d] += f[p][a][b][c][d];
                            if(ch == '7' || ch == '?')
                                f[q][a][b][c][d+1] += f[p][a][b][c][d];
                            if(ch == '8' || ch == '?')
                                f[q][a+3][b][c][d] += f[p][a][b][c][d];
                            if(ch == '9' || ch == '?')
                                f[q][a][b+2][c][d] += f[p][a][b][c][d];
                        }                
        memset(f[p], 0, sizeof(f[p]));
        swap(p, q);
    }
}
data qpow(ll t, ll b)
{
    data ans = data(1);
    data a = (data)(t);
    for(ll i = b; i; i >>= 1, a = a * a)
        if(i & 1)ans = ans * a;
    return ans;
}
data calzero()
{
    int ans1 = 0, ans2 = 0;
    for(int i = 1; i <= n; i++)
        if(str[i] == '?')ans1++;
    for(int i = n + 1; i <= 2 * n; i++)
        if(str[i] == '?')ans2++;
    data t1 = qpow(10, ans1) - qpow(9, ans1);
    data t2 = qpow(10, ans2) - qpow(9, ans2);
    return t1 * t2;
}
int main()
{
    scanf("%d", &n);
    scanf("%s", str+1);
    ll t1 = 0, t2 = 0, zl = 0, zr = 0;
    for(int i = 1; i <= 2 * n; i++)
        if(str[i] == '?')
        {
            if(i <= n)t1++;
            else t2++;
        }
        else if(str[i] == '0')
        {
            if(i <= n)zl = 1;
            else zr = 1;
        }
    data ans;
    if(zl || zr)
    {
        if(zl && zr)
            ans = qpow(10, t1 + t2);
        else if(zl)
            ans = qpow(10, t1) * (qpow(10, t2) - qpow(9, t2));
        else ans = (qpow(10, t1) - qpow(9, t1)) * qpow(10, t2);
    }
    else
    {
        dp(1, n);
        memcpy(g, f[n&1], sizeof(f[n&1]));
        dp(n + 1, 2 * n);
        for(int a = 0; a <= 3 * n; a++)
            for(int b = 0; b <= 2 * n; b++)
                for(int c = 0; c <= n; c++)
                    for(int d = 0; d <= n; d++)
                        ans = ans + (data)(g[a][b][c][d]) * (data)(f[n&1][a][b][c][d]);
        ans = ans + calzero();
    }
    print(ans);
    print(qpow(10, t1 + t2) - ans);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

#include <cmath>

#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

#define inf 1000000000

#define rad 100000000

#define ll long long

using namespace std;

int n;

char str[100];

ll f[2][55][40][20][20], g[55][40][20][20]; // i 2 3 5 7 0?

struct data{

int l;ll v[20];

data(){

l=1;

memset(v,0,sizeof(v));

}

data(ll x){

memset(v,0,sizeof(v));

l=0;

while(x)

{

v[++l]=x%rad;

x/=rad;

}

ll& operator[](int x){

return v[x];

}

friend data operator+(data a,data b){

if(a.l<b.l)swap(a,b);

for(int i=1;i<=b.l;i++)

a[i]+=b[i];

for(int i=1;i<=a.l;i++)

if(a[i]>=rad)

{

if(i==a.l)a.l++;

a[i+1]+=a[i]/rad;

a[i]%=rad;

}

return a;

}

friend data operator-(data a,data b){

for(int i=1;i<=b.l;i++)

a[i]-=b[i];

for(int i=1;i<=a.l;i++)

if(a[i]<0)

{

a[i]+=rad;

a[i+1]--;

}

while(!a[a.l]&&a.l>1)a.l--;

return a;

}

friend data operator*(data a,ll b){

for(int i=1;i<=a.l;i++)

a[i]*=b;

for(int i=1;i<=a.l;i++)

if(a[i]>=rad)

{

a[i+1]+=a[i]/rad;

a[i]%=rad;

if(i==a.l)a.l++;

}

return a;

}

friend data operator*(data a,data b){

data c;

for(int i=1;i<=a.l;i++)

for(int j=1;j<=b.l;j++)

c[i+j-1]+=a[i]*b[j];

for(int i=1;i<=a.l+b.l;i++)

{

if(c[i]>=rad)

{

c[i+1]+=c[i]/rad;

c[i]%=rad;

}

if(c.v[i])c.l=i;

}

return c;

}

friend void print(data a){

printf("%lld",a[a.l]);

for(int i=a.l-1;i;i--)printf("%.8lld",a[i]);

puts("");

}

};

void dp(int L, int R)

{

memset(f, 0, sizeof(f));

int p = 0, q = 1;

f[0][0][0][0][0] = 1;

for(int x = L - 1; x <= R - 1; x++)

{

int l = x - L + 1;

char ch = str[x + 1];

for(int a = 0; a <= 3 * l; a++)

for(int b = 0; b <= 2 * l; b++)

for(int c = 0; c <= l; c++)

for(int d = 0; d <= l; d++)

if(f[p][a][b][c][d])

{

if(ch == '1' || ch == '?')

f[q][a][b][c][d] += f[p][a][b][c][d];

if(ch == '2' || ch == '?')

f[q][a+1][b][c][d] += f[p][a][b][c][d];

if(ch == '3' || ch == '?')

f[q][a][b+1][c][d] += f[p][a][b][c][d];

if(ch == '4' || ch == '?')

f[q][a+2][b][c][d] += f[p][a][b][c][d];

if(ch == '5' || ch == '?')

f[q][a][b][c+1][d] += f[p][a][b][c][d];

if(ch == '6' || ch == '?')

f[q][a+1][b+1][c][d] += f[p][a][b][c][d];

if(ch == '7' || ch == '?')

f[q][a][b][c][d+1] += f[p][a][b][c][d];

if(ch == '8' || ch == '?')

f[q][a+3][b][c][d] += f[p][a][b][c][d];

if(ch == '9' || ch == '?')

f[q][a][b+2][c][d] += f[p][a][b][c][d];

}

memset(f[p], 0, sizeof(f[p]));

swap(p, q);

}

data qpow(ll t, ll b)

{

data ans = data(1);

data a = (data)(t);

for(ll i = b; i; i >>= 1, a = a * a)

if(i & 1)ans = ans * a;

return ans;

}

data calzero()

{

int ans1 = 0, ans2 = 0;

for(int i = 1; i <= n; i++)

if(str[i] == '?')ans1++;

for(int i = n + 1; i <= 2 * n; i++)

if(str[i] == '?')ans2++;

data t1 = qpow(10, ans1) - qpow(9, ans1);

data t2 = qpow(10, ans2) - qpow(9, ans2);

return t1 * t2;

}

int main()

{

scanf("%d", &n);

scanf("%s", str+1);

ll t1 = 0, t2 = 0, zl = 0, zr = 0;

for(int i = 1; i <= 2 * n; i++)

if(str[i] == '?')

{

if(i <= n)t1++;

else t2++;

}

else if(str[i] == '0')

{

if(i <= n)zl = 1;

else zr = 1;

}

data ans;

if(zl || zr)

{

if(zl && zr)

ans = qpow(10, t1 + t2);

else if(zl)

ans = qpow(10, t1) * (qpow(10, t2) - qpow(9, t2));

else ans = (qpow(10, t1) - qpow(9, t1)) * qpow(10, t2);

}

else

{

dp(1, n);

memcpy(g, f[n&1], sizeof(f[n&1]));

dp(n + 1, 2 * n);

for(int a = 0; a <= 3 * n; a++)

for(int b = 0; b <= 2 * n; b++)

for(int c = 0; c <= n; c++)

for(int d = 0; d <= n; d++)

ans = ans + (data)(g[a][b][c][d]) * (data)(f[n&1][a][b][c][d]);

ans = ans + calzero();

}

print(ans);

print(qpow(10, t1 + t2) - ans);

return 0;

}

H:Stock Exchange POJ3903

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 1000000000
using namespace std;
int n;
int a[100005], f[100005];
int main()
{
        while(scanf("%d", &n) != EOF)
        {
                memset(f, 127, sizeof(f));
                for(int i = 1; i <= n; i++)
                        scanf("%d", &a[i]);
                for(int i = 1; i <= n; i++)
                        *lower_bound(f, f + n, a[i]) = a[i];
                printf("%d\n", lower_bound(f, f + n, inf) - f);
        }
        return 0;
}

#include <cmath>

#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

#define inf 1000000000

using namespace std;

int n;

int a[100005], f[100005];

int main()

{

while(scanf("%d", &n) != EOF)

{

memset(f, 127, sizeof(f));

for(int i = 1; i <= n; i++)

scanf("%d", &a[i]);

for(int i = 1; i <= n; i++)

*lower_bound(f, f + n, a[i]) = a[i];

printf("%d\n", lower_bound(f, f + n, inf) - f);

}

return 0;

}

« 「百度之星2017」程序设计大赛初赛(B) 【LOJ】小奇 NOIP 练习题 »

hzwer.com _ Home | http://hzwer.com

算法设计与分析讨论班上机作业

凸包

A:Wall POJ1113

B:Scrambled Polygon POJ2007

动态规划 G 题真的坑

A:Fourier’s Lines POJ1923

B:Tour POJ2677

C:Increasing Sequences POJ1239

D:Charlie’s Change POJ1787

E:Strange Towers of Hanoi POJ1958

F:Balanced Lineup POJ3274

G:Banal Tickets POJ1608

H:Stock Exchange POJ3903

分类目录

热门文章

Myfriends

近期评论