C++博客-CSniper

[DP] PKU 1141 括号序列

yajunw — Thu, 11 Oct 2012 05:57:00 GMT

http://poj.org/problem?id=1141
DP, 记录路径。

# include <stdio.h>
# include <string.h>

# define N 205
# define INF 1000000000
# define Mid (1 << 10)
# define Lft (1 << 9 )
# define Rgt (1 << 8 )

char buf[N];
int f[N][N], p[N][N];

int dp(int x, int y)
{
                int & ans = f[x][y];
                if (ans != -1) return ans;
                if (x > y) return ans = 0;
                ans = INF;
                if ( (buf[x]=='('&&buf[y]==')') ||
                     (buf[x]=='['&&buf[y]==']') )
                {
                                if (ans > dp(x+1, y-1))
                                {
                                                p[x][y] = Mid;
                                                ans = f[x+1][y-1];
                                }
                }
                if ( buf[x]=='(' || buf[x]=='[' )
                {
                                if (ans > dp(x+1, y)+1)
                                {
                                                p[x][y] = Rgt;
                                                ans = f[x+1][y] + 1;
                                }
                }
                if ( buf[y]==')' || buf[y]==']' )
                {
                                if (ans > dp(x, y-1)+1)
                                {
                                                p[x][y] = Lft;
                                                ans = f[x][y-1] + 1;
                                }
                }
                for (int i = x; i < y; ++i)
                {
                                if (ans > dp(x, i)+dp(i+1, y))
                                {
                                                p[x][y] = i;
                                                ans = f[x][i] + f[i+1][y];
                                }
                }
                return ans;
}

void print(int s, int t)
{
                switch(p[s][t])
                {
                                case Mid:
                                {
                                                putchar(buf[s]), print(s+1, t-1), putchar(buf[t]);
                                                break;
                                }
                                case Lft:
                                {
                                                if (buf[t] == ')')
                                                                putchar('('), print(s, t-1), putchar(')');
                                                else
                                                                putchar('['), print(s, t-1), putchar(']');
                                                break;
                                }
                                case Rgt:
                                {
                                                if (buf[s] == '(')
                                                                putchar('('), print(s+1, t), putchar(')');
                                                else
                                                                putchar('['), print(s+1, t), putchar(']');
                                                break;
                                }
                                case 0:
                                {
                                                for (int i = s; i <= t; ++i)
                                                                putchar(buf[i]);
                                                break;
                                }
                                default:
                                {
                                                print(s, p[s][t]), print(p[s][t]+1, t);
                                                break;
                                }
                }
}

int main()
{
                int n;

                buf[0] = 0, scanf("%s", buf+1);
                memset(f, -1, sizeof(f));
                memset(p, 0, sizeof(p));
                n = strlen(buf+1);
                dp(1, n), print(1, n), putchar('\n');

                return 0;
}

yajunw 2012-10-11 13:57 发表评论

[DP] PKU 1181 棋盘分割

yajunw — Thu, 11 Oct 2012 04:14:00 GMT

http://poj.org/problem?id=1191
dp

# include <stdio.h>
# include <string.h>
# include <math.h>

# define M (8 + 3)
# define N (14 + 3)
# define INF 1000000000

int n, m = 8;
int a[M][M];
int s[M][M];
int f[N][M][M][M][M];

int Min(int x, int y) {
                return x<y ? x:y;
}
int cal(int x1, int y1, int x2, int y2)
{
                int ret = s[x2][y2]+s[x1-1][y1-1]-s[x1-1][y2]-s[x2][y1-1];
                return ret * ret;
}
void pre(void)
{
                int i, j, t;
                for (i = 1; i <= m; ++i)
                                for (j = 1; j <= m; ++j)
                                                scanf("%d", &a[i][j]);
                for (i = 0; i < N; ++i)
                                s[i][0] = s[0][i] = 0;
                for (i = 1; i <= m; ++i)
                {
                                t = 0;
                                for (j = 1; j <= m; ++j)
                                {
                                                t += a[i][j];
                                                s[i][j] = t + s[i-1][j];
                                }
                }
                memset(f, -1, sizeof(f));
}

int dp(int k, int x1, int y1, int x2, int y2)
{
                int i, j;
                int & ans = f[k][x1][y1][x2][y2];
                if (ans != -1)return ans;
                if (k == 1) return ans = cal(x1, y1, x2, y2);
                ans = INF;
                for (i = x1; i < x2; ++i)
                                ans = Min( ans, Min( dp(k-1, x1, y1, i, y2)+cal(i+1, y1, x2, y2),
                                                     dp(k-1, i+1, y1, x2, y2)+cal(x1, y1, i, y2) ) );
                for (j = y1; j < y2; ++j)
                                ans = Min( ans, Min( dp(k-1, x1, y1, x2, j)+cal(x1, j+1, x2, y2),
                                                     dp(k-1, x1, j+1, x2, y2)+cal(x1, y1, x2, j) ) );
                return ans;
}

void solve(void)
{
                double ans;
                ans = ( 1.0*dp(n, 1, 1, 8, 8) )/( 1.0*n )
                      - (1.0*s[8][8]/n)*(1.0*s[8][8]/n);
                printf("%.3f\n", sqrt(ans) );
}

int main()
{
                scanf("%d", &n);
                pre();
                solve();

                return 0;
}

yajunw 2012-10-11 12:14 发表评论

problem 1008 Chengdu

yajunw — Sun, 16 Sep 2012 09:06:00 GMT

1008

# include <cstdio>
# include <algorithm>

# define N 100005

typedef __int64 LL;

int n;
int a[N], b[N], r[N];
bool cmp(int x, int y)
{
                return a[x]-b[y] == a[y]-b[x] ? a[x]>a[y] : a[x]-b[y]>a[y]-b[x];
}
int main()
{
                freopen("in.txt", "r", stdin);

                int i;
                LL w, ans;
                while (~scanf("%d", &n))
                {
                                for (i = 0; i < n; ++i)
                                                scanf("%d%d", &a[i], &b[i]), r[i] = i;
                                std::sort(r, r+n, cmp);
                                w = a[ r[n-1] ];
                                ans = 0;
                                for (i = n-2; i >= 0; --i)
                                {
                                                if (ans < w-(LL)b[ r[i] ]) ans = w - (LL)b[ r[i] ];
                                                w += (LL)a[ r[i] ];
                                }
                                printf("%I64d\n", ans);
                }

                return 0;
}

yajunw 2012-09-16 17:06 发表评论

2011 South Pacific Regional Contest E -- RealPhobia

yajunw — Sat, 15 Sep 2012 09:26:00 GMT

# include

typedef long long int LL;

/***************************************/
LL Min(LL x, LL y)
{
                return x < y ? x : y;
}
LL Max(LL x, LL y)
{
                return x > y ? x : y;
}
LL gcd(LL x, LL y)
{
                if (!y) return x;
                return gcd(y, x%y);
}
LL ex_gcd(LL a,LL b,LL &x,LL &y)
{
                if(b==0)
                {
                                x=1;
                                y=0;
                                return a;
                }
                LL g,t;
                g=ex_gcd(b,a%b,x,y);
                t=x;
                x=y;
                y=t-a/b*y;
                return g;
}
LL niyuan(LL b,LL p)
{
                LL x,y;
                ex_gcd(b,p,x,y);
                return x=(x%p+p)%p;
}
/***************************************/
struct frac
{
                LL n, d;
} ;
LL A, B, C, D;
LL LLabs(LL x)
{
                return x>0 ? x:-x;
}
void slim(frac &x)
{
                LL tmp = LLabs(gcd(x.d, x.n));
                x.d /= tmp;
                x.n /= tmp;
}
frac dif(frac x, frac y)
{
                frac z;
                z.d = x.d * y.d;
                z.n = LLabs(x.n*y.d-x.d*y.n);
                slim(z);
                return z;
}
int cmp(frac x, frac y)
{
                return x.n*y.d - x.d*y.n>0 ? 1:0;
}
frac cal(frac x, frac y, frac BA)
{
                return cmp(dif(x, BA), dif(y, BA)) ? y:x;
}
void solve(void)
{
                frac BA;
                BA.n = A, BA.d = B;
                LL n1 = niyuan(B, A);
                if (n1 == 0) n1 = A;
                LL d1 = (B*n1-1) / A;
                LL d2 = niyuan(A, B);
                if (d2 == 0) d2 = B;
                LL n2 = (A*d2-1) / B;
                frac a, b;
                a.n = n1, a.d = d1;
                b.n = n2, b.d = d2;
                slim(a), slim(b);
                frac ans = cal(a, b, BA);
                printf("%lld/%lld\n", ans.n, ans.d);
}
/***************************************/
int main()
{
                freopen("in.txt", "r", stdin);

                int T;
                scanf("%d", &T);
                while (T--)
                {
                                scanf("%lld/%lld", &A, &B);
                                LL tmp = gcd(A, B);
                                if (tmp != 1)
                                {
                                                printf("%lld/%lld\n", A/tmp, B/tmp);
                                }
                                else solve();
                }

                return 0;
}

Bert is a programmer with a real fear of floating point arithmetic. Bert has quite successfully used rational numbers to write his programs but he does not like it when the denominator grows large.

Your task is to help Bert by writing a program that decreases the denominator of a rational number, whilst introducing the smallest error possible. For a rational number A/B, where B > 2 and 0 < A < B, your program needs to identify a rational number C/D such that:

0 < C < D < B, and
the error | A/B - C/D| is the minimum over all possible values of C and D, and
D is the smallest such positive integer.

Input

The input starts with an integer K ( 1K1000) that represents the number of cases on a line by itself. Each of the following K lines describes one of the cases and consists of a fraction formatted as two integers, A and B, separated by `/' such that:

B is a 32 bit integer strictly greater than 2, and
0 < A < B

Output

For each case, the output consists of a fraction on a line by itself. The fraction should be formatted as two integers separated by `/'.

Sample Input

Sample Output

1/3
1/2
8/13

yajunw 2012-09-15 17:26 发表评论

HDOJ 3641 Treasure Hunting

yajunw — Sat, 08 Sep 2012 08:01:00 GMT

给出 2n 个数，求最大的 x 满足 x!%M = 0 ，其中 M = a1^b1*a2^b2*a3^b3…*an^bn 。

Input

In the first line is an integer T (1<=T<=50) indicating the number of test cases.
Each test case begins with an integer n (1<=n<=100), then followed n lines. Each line contains two numbers ai and bi (1 <= ai <= 100, 1<=bi<=10000000000000)

Output

For each test case output the result x in one line.

Source
2010 Asia Regional Hangzhou Site Online Contest

# include <stdio.h>
# include <string.h>
# include <math.h>

# define N 101
typedef long long int LL;

int n;
/*******************************************************/
int p[50], top = 0;
int isPrime(int x)
{
                int i;
                if (x%2==0) return x==2;
                if (x%3==0) return x==3;
                if (x%5==0) return x==5;
                for (i = 7; i < x; i += 5)
                                if (x%i == 0) return 0;
                return 1;
}

void pre(void)
{
                int i;
                for (i = 2; i < N; ++i)
                                if (isPrime(i)) p[top++] = i;
}
/*******************************************************/
LL pn[50];
void init(void)
{
                int i, j, x;
                LL cnt;
                LL num;
                memset(pn, 0, sizeof(pn));
                scanf("%d", &n);
                for (i = 0; i < n; ++i)
                {
                                scanf("%d%I64d", &x, &num);
                                for (j = 0; j < top; ++j)
                                {
                                                if (x%p[j] == 0)
                                                {
                                                                cnt = 0;
                                                                while (x%p[j]==0) ++cnt, x/=p[j];
                                                                pn[j] += cnt*num;
                                                }
                                }
                }
}
LL Max(LL x, LL y)
{
                return x>y ? x:y;
}

LL mypow(int pr, int cnt)
{
                LL ret = 1;
                while (cnt > 0) --cnt, ret *= pr;
                return ret;
}

LL cal(int pr, LL tot)
{
                int tmp;
                LL ppow = 0, temp;
                while (tot > 0)
                {
                                tmp = (int)floor(log(tot*(pr-1)+1)/log(pr))+1;
                                while ((mypow(pr, tmp)-1)/(pr-1) > tot) --tmp;
                                temp = mypow(pr, tmp);
                                ppow += temp;
                                tot -= (temp-1)/(pr-1);
                }
                return ppow;
}
void solve(void)
{
                int i;
                LL ans = 0;
                for (i = 0; i < top; ++i) if (pn[i] != 0)
                                                ans = Max(ans, cal(p[i], pn[i]));
                printf("%I64d\n", ans);
}

int main()
{
                int T;
                pre();
                scanf("%d", &T);
                while (T--) init(), solve();

                return 0;
}

yajunw 2012-09-08 16:01 发表评论

[树状数组] PKU 2299 Ultra-QuickSort

yajunw — Sun, 02 Sep 2012 09:53:00 GMT

维护名次即可（不需要离散化）。

# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;

# define N 500005

typedef long long int LL;
int n;
LL a[N];
int r[N], s[N], c[N];
/***************************************************/
int getsum(int x)
{
                int ret = 0;
                while (x > 0) ret += c[x], x  -= x&(-x);
                return ret;
}
void inc(int x)
{
                while (x <= n) ++ c[x], x += x&(-x);
}
/***************************************************/
bool cmp(int x, int y)
{
                return a[x] > a[y];
}
int main()
{
                LL ans;
                int i;
                while (scanf("%d", &n), n)
                {
                                memset(c+1, 0, sizeof(c[0])*n);
                                for (i = 0; i < n; ++i)
                                                r[i] = i, scanf("%lld", &a[i]);
                                sort(r, r+n, cmp);
                                for (i = 0; i < n; ++i) s[r[i]] = i;
                                ans = 0;
                                for (i = 0; i < n; ++i)
                                                ans += getsum(s[i]+1), inc(s[i]+1);
                                printf("%lld\n", ans);
                }

                return 0;
}

yajunw 2012-09-02 17:53 发表评论

[树状数组] PKU 2155 Matrix

yajunw — Sun, 02 Sep 2012 09:29:00 GMT

树状数组，inc(x,y)表示对[x-n][y-n]的区域执行一次反转操作，这样，getsum(x,y)将总会包含对[x][y]的操作，即为[x][y]的反转总次数，根据奇偶性判断当前状态。

# include <stdio.h>
# include <string.h>

# define N 1005

int n, c[N][N];
void clr(int nn)
{
                int i;
                for (i = 1; i <= nn; ++i)
                                memset(c[i]+1, 0, sizeof(c[0][0])*nn);
}
/******************************************************************/
void inc(int x, int y)
{
                int t;
                while (x <= n)
                {
                                t = y;
                                while (t <= n) ++ c[x][t], t += t&(-t);// printf("%d\n", t);
                                x += x&(-x);
                }
}
int getsum(int x, int y)
{
                int t, ret = 0;
                while (x > 0)
                {
                                t = y;
                                while (t > 0) ret += c[x][t], t -= t&(-t);// printf("%d\n", t);
                                x -= x&(-x);
                }
                return ret;
}
/******************************************************************/
int main()
{
                char ins[3];
                int X, T, x0, y0, x1, y1;
                scanf("%d", &X);
                while (X--)
                {
                                scanf("%d%d", &n, &T), clr(n);
                                while (T--)
                                {
                                                scanf("%s%d%d", ins, &x0, &y0);
                                                switch(ins[0])
                                                {
                                                                case 'C':
                                                                {
                                                                                scanf("%d%d", &x1, &y1);
                                                                                inc(x0, y0);
                                                                                inc(x0, y1+1);
                                                                                inc(x1+1, y0);
                                                                                inc(x1+1, y1+1);
                                                                                break;
                                                                }
                                                                case 'Q': puts((getsum(x0, y0)&0x1) ? "1":"0"); break;
                                                }
                                }
                                if (X) putchar('\n');
                }

                return 0;
}

yajunw 2012-09-02 17:29 发表评论

[树状数组] PKU 3067 Japan

yajunw — Sun, 02 Sep 2012 05:53:00 GMT

结果用 long long。

# include <stdio.h>
# include <string.h>
# include <algorithm>

using namespace std;

# define B 1005
# define N 1000005

int n, m, k, a[B];
int r[N], x[N], y[N];
bool cmp(int i, int j)
{
                return x[i]^x[j] ? x[i]>x[j] : y[i]>y[j];
}
/********************************************************/
int getsum(int x)
{
                int ret = 0;
                while (x > 0) ret += a[x], x -= x&(-x);
                return ret;
}
void inc(int x)
{
                while (x <= m) ++ a[x], x += x&(-x);
}
/********************************************************/
int main()
{
                int ii, T, i, xx;
                long long int ans;

                scanf("%d", &T);
                for (ii = 1; ii <= T; ++ii)
                {
                                scanf("%d%d%d", &n, &m, &k);
                                memset(a+1, 0, sizeof(a[0])*m);
                                for (i = 0; i < k; ++i)
                                                r[i] = i, scanf("%d%d", &x[i], &y[i]);
                                sort(r, r+k, cmp);
                                ans = 0;
                                for (i = 0; i < k; ++i)
                                                ans += getsum(y[r[i]]-1), inc(y[r[i]]);
                                printf("Test case %d: %lld\n", ii, ans);
                }

                return 0;
}

yajunw 2012-09-02 13:53 发表评论

[树状数组] PKU 2481 Cows

yajunw — Sun, 02 Sep 2012 03:51:00 GMT

1 # include <cstdio>
2 # include <cstring>
3 # include <algorithm>
4 using namespace std;
5
6 # define B 100005
7 # define N 100005
8
9 struct Intv {int s, e;};
10
11 Intv c[N];
12 int n, a[B], r[N], le[N];
13
14 bool cmp(const int x, const int y)
15 {
16                 if (c[x].s == c[y].s) return c[x].e > c[y].e;
17                 return c[x].s < c[y].s;
18 }
19 /**************************************************/
20 int getsum(int x)
21 {
22                 int ret = 0;
23                 while (x > 0) ret += a[x], x -= x&(-x);
24                 return ret;
25 }
26 void inc(int x)
27 {
28                 while (x <= B) ++a[x], x += x&(-x);
29 }
30 /**************************************************/
31 int main()
32 {
33                 int i, n, x;
34
35                 while (scanf("%d", &n), n)
36                 {
37                                 memset(a, 0, sizeof(a));
38                                 for (i = 0; i < n; ++i)
39                                                 r[i] = i, scanf("%d%d", &c[i].s, &c[i].e);
40                                 sort(r, r+n, cmp);
41                                 for (i = 0; i < n; ++i)
42                                 {
43                                                 x = c[r[i]].e + 1, inc(x);
44                                                 if (i && c[r[i]].e==c[r[i-1]].e && c[r[i]].s==c[r[i-1]].s)
45                                                                 le[r[i]] = le[r[i-1]];
46                                                 else
47                                                                 le[r[i]] = i-getsum(x-1);
48                                 }
49                                 for (i = 0; i < n; ++i)
50                                 {
51                                                 if (i) putchar(' ');
52                                                 printf("%d", le[i]);
53                                 }
54                                 putchar('\n');
55                 }
56
57                 return 0;
58 }
59

yajunw 2012-09-02 11:51 发表评论

[树状数组] PKU 3252 Star

yajunw — Sun, 02 Sep 2012 02:21:00 GMT

# include < stdio.h >

int a[ 32005 ], le[ 15005 ], n;
/* ********************************************************* */
int getsum( int x)
{
                 int ret = 0 ;
                 while (x > 0 ) ret += a[x], x -= (x & ( - x));
                 return ret;
}
void inc( int x)
{
                 while (x <= 32005 ) ++ a[x], x += (x & ( - x));
}
/* ********************************************************* */
int main()
{
                 int i, x, y;
                scanf( " %d " , & n);
                 for (i = 0 ; i < n; ++ i)
                {
                                scanf( " %d%d " , & x, & y), ++ x;
                                 ++ le[getsum(x)];
                                inc(x);
                }
                 for (i = 0 ; i < n; ++ i) printf( " %d\n " , le[i]);

                 return 0 ;
}

yajunw 2012-09-02 10:21 发表评论