[关闭]
@ivorysi 2018-01-02T08:46:27.000000Z 字数 43681 阅读 789

常用算法学习笔记

笔记

二分

POJ 1064 Cable master

Description

Inhabitants of the Wonderland have decided to hold a regional programming contest. The Judging Committee has volunteered and has promised to organize the most honest contest ever. It was decided to connect computers for the contestants using a "star" topology - i.e. connect them all to a single central hub. To organize a truly honest contest, the Head of the Judging Committee has decreed to place all contestants evenly around the hub on an equal distance from it.
To buy network cables, the Judging Committee has contacted a local network solutions provider with a request to sell for them a specified number of cables with equal lengths. The Judging Committee wants the cables to be as long as possible to sit contestants as far from each other as possible.
The Cable Master of the company was assigned to the task. He knows the length of each cable in the stock up to a centimeter,and he can cut them with a centimeter precision being told the length of the pieces he must cut. However, this time, the length is not known and the Cable Master is completely puzzled.
You are to help the Cable Master, by writing a program that will determine the maximal possible length of a cable piece that can be cut from the cables in the stock, to get the specified number of pieces.

Input

The first line of the input file contains two integer numb ers N and K, separated by a space. N (1 = N = 10000) is the number of cables in the stock, and K (1 = K = 10000) is the number of requested pieces. The first line is followed by N lines with one number per line, that specify the length of each cable in the stock in meters. All cables are at least 1 meter and at most 100 kilometers in length. All lengths in the input file are written with a centimeter precision, with exactly two digits after a decimal point.

Output

Write to the output file the maximal length (in meters) of the pieces that Cable Master may cut from the cables in the stock to get the requested number of pieces. The number must be written with a centimeter precision, with exactly two digits after a decimal point.
If it is not possible to cut the requested number of pieces each one being at least one centimeter long, then the output file must contain the single number "0.00" (without quotes).

Sample Input

4 11
8.02
7.43
4.57
5.39

Sample Output

2.00

题解

很明显的二分，然而精度卡的很恶心，只能转换成longlong来做……

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define esp 1e-8
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. int n;
  17. double c[20005];
  18. ll cable[20005];
  19. ll sum=0,k;
  20. bool check(ll mid) {
  21.     ll cnt=0;
  22.     siji(i,1,n) {
  23.     cnt+=cable[i]/mid;
  24.     if(cnt>=k) return true;
  25.     }
  26.     return false;
  27. }
  28. void solve() {
  29.     scanf("%d%lld",&n,&k);
  30.     siji(i,1,n) {
  31.     scanf("%lf",&c[i]);
  32.     cable[i]=(c[i]+0.005)*100;
  33.     sum+=cable[i];
  34.     }
  35.     if(k>sum) {puts("0.00");return;}
  36.     ll l=0,r=sum;
  37.     while(l<r) {
  38.     ll mid=(l+r+1)>>1;
  39.     if(check(mid)) l=mid;
  40.     else r=mid-1;
  41.     }
  42.     printf("%.2f\n",(double)l/100.0);
  43. }
  44. int main() {
  45. #ifdef ivorysi
  46.     freopen("f1.in","r",stdin);
  47. #endif
  48.     solve();
  50.     return 0;
  52. }

POJ 3273 Monthly Expense

Description

Farmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤ moneyi ≤ 10,000) that he will need to spend each day over the next N (1 ≤ N ≤ 100,000) days.
FJ wants to create a budget for a sequential set of exactly M (1 ≤ M ≤ N) fiscal periods called "fajomonths". Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.
FJ's goal is to arrange the fajomonths so as to minimize the expenses of the fajomonth with the highest spending and thus determine his monthly spending limit.

Input

Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 contains the number of dollars Farmer John spends on the ith day

Output

Line 1: The smallest possible monthly limit Farmer John can afford to live with.

Sample Input

7 5
100
400
300
100
500
101
400

Sample Output

500

题解

下边界是最大花钱的那天的钱数，上边界是所有钱的总和，然后二分
每次O(N)判断是否合法

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define esp 1e-8
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. int n,m;
  17. ll budget[1000005];
  18. bool check(ll mid) {
  19.     int cnt=0;
  20.     ll all=budget[1];
  21.     siji(i,2,n) {
  22.     if(all+budget[i]>mid) {
  23.         ++cnt;
  24.         all=budget[i];
  25.     }
  26.     else {
  27.         all+=budget[i];
  28.     }
  29.     }
  30.     ++cnt;
  31.     return cnt<=m;
  32. }
  33. void solve() {
  34.     scanf("%d%d",&n,&m);
  35.     ll l=0,r=0;
  36.     siji(i,1,n) {
  37.     scanf("%lld",&budget[i]);
  38.     r+=budget[i];
  39.     l=max(l,budget[i]);
  40.     }
  41.     while(l<r) {
  42.     ll mid=(l+r)>>1;
  43.     if(check(mid)) r=mid;
  44.     else l=mid+1;
  45.     }
  46.     printf("%lld\n",r);
  47. }
  48. int main() {
  49. #ifdef ivorysi
  50.     freopen("f1.in","r",stdin);
  51. #endif
  52.     solve();
  54.     return 0;
  56. }

Codeforces 549 H. Degenerate Matrix

The determinant of a matrix 2 × 2 is defined as follows:
A matrix is called degenerate if its determinant is equal to zero.
The norm ||A|| of a matrix A is defined as a maximum of absolute values of its elements.
You are given a matrix . Consider any degenerate matrix B such that norm ||A - B|| is minimum possible. Determine ||A - B||.

Input

The first line contains two integers a and b (|a|, |b| ≤ 109), the elements of the first row of matrix A.
The second line contains two integers c and d (|c|, |d| ≤ 109) the elements of the second row of matrix A.

Output

Output a single real number, the minimum possible value of ||A - B||. Your answer is considered to be correct if its absolute or relative error does not exceed 10 - 9.

Examples

Input

1 2
3 4

Output

0.2000000000

Input

1 0
0 1

Output

0.5000000000

题解

这道题本来想看题解
但是题解加载不出来，然后就自己想出来了
因为精度又被卡了，但是在网上学到一个小技巧，对于浮点数的二分直接确定枚举次数，例如1000000次，就很秒了

我们观察一下我们枚举一个绝对值k
ad的取值是一个区间，bc的取值是一个区间
我们区间求交，如果有交的话那么k一定是合法的，然后r=k 否则l=k

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define esp 1e-6
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. double a,b,c,d;
  17. double tmp[8];
  18. void make_data(double p,double q,double k) {
  19.     tmp[1]=(p+k)*(q+k);
  20.     tmp[2]=(p+k)*(q-k);
  21.     tmp[3]=(p-k)*(q+k);
  22.     tmp[4]=(p-k)*(q-k);
  23. }
  24. bool check(double mid) {
  25.     make_data(a,d,mid);
  26.     double r1=tmp[1],l1=tmp[1];
  27.     siji(i,2,4) {
  28.     r1=max(r1,tmp[i]);
  29.     l1=min(l1,tmp[i]);
  30.     }
  31.     make_data(b,c,mid);
  32.     double r2=tmp[1],l2=tmp[1];
  33.     siji(i,2,4) {
  34.     r2=max(r2,tmp[i]);
  35.     l2=min(l2,tmp[i]);
  36.     }
  37.     if(l1<r2 && l2<r1) return true;
  38.     else return false;
  39. }
  40. void solve() {
  41.     scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
  42.     double l=0.0,r=1000000000.0;
  43.     int num=1000000;
  44.     while(num--) {
  45.     double mid=(l+r)/2.0;
  46.     if(check(mid)) r=mid;
  47.     else l=mid;
  48.     }
  49.     printf("%.9lf\n",r);
  50. }
  51. int main() {
  52. #ifdef ivorysi
  53.     freopen("f1.in","r",stdin);
  54. #endif
  55.     solve();
  57.     return 0;
  59. }

BZOJ 1857: [Scoi2010]传送带

Description

在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在lxhgww想从A点走到D点，他想知道最少需要走多长时间

Input

输入数据第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By 第二行是4个整数，表示C和D的坐标，分别为Cx，Cy，Dx，Dy 第三行是3个整数，分别是P，Q，R

Output

输出数据为一行，表示lxhgww从A点走到D点的最短时间，保留到小数点后2位

Sample Input

0 0 0 100
100 0 100 100
2 2 1

Sample Output

136.60

HINT

对于100%的数据，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
1<=P，Q，R<=10

题解

我们用光的折射原理，AB上任意一点到D一定有一个极小值
然后我们将平面和D作为同一种介质，我们可以也以为AB上到D的距离也一定有一个极小值
三分套三分
要在必要的时候用sqrt否则会被卡精度啊！！！！

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define esp 1e-8
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. struct Point {
  17.     double x,y;
  18.     Point() {}
  19.     Point(double _x,double _y) {
  20.     x=_x;y=_y;
  21.     }
  22.     friend Point operator + (const Point &a,const Point &b) {
  23.     return Point(a.x+b.x,a.y+b.y);
  24.     }
  25.     friend Point operator - (const Point &a,const Point &b) {
  26.     return Point(a.x-b.x,a.y-b.y);
  27.     }
  28.     friend double operator * (const Point &a,const Point &b) {
  29.     return a.x*b.y-a.y*b.x;
  30.     }
  31.     friend Point operator * (const Point &a,const double &b) {
  32.     return Point(a.x*b,a.y*b);
  33.     }
  34.     friend Point operator / (const Point &a,const double &b) {
  35.     return Point(a.x/b,a.y/b);
  36.     }
  37.     double norm() {
  38.     return sqrt(x*x+y*y);
  39.     }
  40. }A,B,C,D;
  41. double p,q,r;
  42. double dist(Point Z,Point L) {
  43.     return (L-D).norm()/q+(L-Z).norm()/r;
  44. }
  45. double calc(Point mid) {
  46.     Point ll=D,rr=C;
  47.     int num=500;
  48.     while(num--) {
  49.     Point m1=ll+(rr-ll)/3.0;
  50.     Point m2=rr-(rr-ll)/3.0;
  51.     if(dist(mid,m1)-dist(mid,m2)>= -esp) ll=m1;
  52.     else rr=m2;
  53.     }
  54.     return dist(mid,rr)+(mid-A).norm()/p;
  55. }
  56. void solve() {
  57.     scanf("%lf%lf",&A.x,&A.y);
  58.     scanf("%lf%lf",&B.x,&B.y);
  59.     scanf("%lf%lf",&C.x,&C.y);
  60.     scanf("%lf%lf",&D.x,&D.y);
  61.     scanf("%lf%lf%lf",&p,&q,&r);
  62.     Point ll=A,rr=B;
  63.     int num=500;
  64.     while(num--) {
  65.     Point m1=ll+(rr-ll)/3.0;
  66.     Point m2=rr-(rr-ll)/3.0;
  67.     if(calc(m1)-calc(m2)>= esp) ll=m1;
  68.     else rr=m2;
  69.     }
  70.     printf("%.2lf\n",calc(ll));
  71. }
  72. int main() {
  73. #ifdef ivorysi
  74.     freopen("f1.in","r",stdin);
  75. #endif
  76.     solve();
  78.     return 0;
  79. }

578 C. Weakness and Poorness

You are given a sequence of n integers a1, a2, ..., an.
Determine a real number x such that the weakness of the sequence a1 - x, a2 - x, ..., an - x is as small as possible.
The weakness of a sequence is defined as the maximum value of the poorness over all segments (contiguous subsequences) of a sequence.
The poorness of a segment is defined as the absolute value of sum of the elements of segment.

Input

The first line contains one integer n (1 ≤ n ≤ 200 000), the length of a sequence.
The second line contains n integers a1, a2, ..., an (|ai| ≤ 10 000).

Output

Output a real number denoting the minimum possible weakness of a1 - x, a2 - x, ..., an - x. Your answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

Examples

Input

3
1 2 3

Output

1.000000000000000

Input

4
1 2 3 4

Output

2.000000000000000

Input

10
1 10 2 9 3 8 4 7 5 6

Output

4.500000000000000

Note

For the first case, the optimal value of x is 2 so the sequence becomes  - 1, 0, 1 and the max poorness occurs at the segment "-1" or segment "1". The poorness value (answer) equals to 1 in this case.
For the second sample the optimal value of x is 2.5 so the sequence becomes  - 1.5,  - 0.5, 0.5, 1.5 and the max poorness occurs on segment "-1.5 -0.5" or "0.5 1.5". The poorness value (answer) equals to 2 in this case.

题解

这道题我们可以认为每个区间的值都是一个绝对值函数，这些函数复合起来求最大值是一个单峰函数，或者说是单谷函数
然后我们可以三分
如何求函数值呢，我们处理出一个前缀和，一个区间和是sum[r]-sum[l],我们固定一个r，然后找sum[l]的最大值和最小值，对每个函数值取一个max就是这个地方的函数值

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define esp 1e-8
  13. #define MAXN 2000005
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. int n;
  18. double a[MAXN];
  19. double tmp[MAXN];
  20. double calc(double mid) {
  21.     siji(i,1,n) tmp[i]=a[i]-mid;
  22.     tmp[0]=0;
  23.     siji(i,1,n) tmp[i]+=tmp[i-1];
  24.     double mi=min(0.0,tmp[1]),ma=max(0.0,tmp[1]);
  25.     double ans=fabs(tmp[1]);
  26.     siji(i,2,n) {
  27.     ans=max(ans,fabs(tmp[i]-mi));
  28.     ans=max(ans,fabs(tmp[i]-ma));
  29.     mi=min(mi,tmp[i]);
  30.     ma=max(ma,tmp[i]);
  31.     }
  32.     return ans;
  33. }
  34. void solve() {
  35.     scanf("%d",&n);
  36.     double l=100000.0,r=0;
  37.     siji(i,1,n) {
  38.     scanf("%lf",&a[i]);
  39.     r=max(a[i],r);
  40.     l=min(a[i],l);
  41.     }
  42.     int num=200;
  43.     while(num--) {
  44.     double m1=l+(r-l)/3.0;
  45.     double m2=r-(r-l)/3.0;
  46.     if(calc(m1)>=calc(m2)) l=m1;
  47.     else r=m2;
  48.     }
  49.     printf("%.9lf\n",calc(l));
  50. }
  51. int main() {
  52. #ifdef ivorysi
  53.     freopen("f1.in","r",stdin);
  54. #endif
  55.     solve();
  57.     return 0;
  59. }

Constellations

Description

The starry sky in the summer night is one of the most beautiful things on this planet. People imagine that some groups of stars in the sky form so-called constellations. Formally a constellation is a group of stars that are connected together to form a figure or picture. Some well-known constellations contain striking and familiar patterns of bright stars. Examples are Orion (containing a figure of a hunter), Leo (containing bright stars outlining the form of a lion), Scorpius (a scorpion), and Crux (a cross).
In this problem, you are to find occurrences of given constellations in a starry sky. For the sake of simplicity, the starry sky is given as a N × M matrix, each cell of which is a '*' or '0' indicating a star in the corresponding position or no star, respectively. Several constellations are given as a group of T P × Q matrices. You are to report how many constellations appear in the starry sky.
Note that a constellation appears in the sky if and only the corresponding P × Q matrix exactly matches some P × Q sub-matrix in the N × M matrix.

Input

The input consists of multiple test cases. Each test case starts with a line containing five integers N, M, T, P and Q(1 ≤ N, M ≤ 1000, 1 ≤ T ≤ 100, 1 ≤ P, Q ≤ 50).
The following N lines describe the N × M matrix, each of which contains M characters '*' or '0'.
The last part of the test case describe T constellations, each of which takes P lines in the same format as the matrix describing the sky. There is a blank line preceding each constellation.
The last test case is followed by a line containing five zeros.

Output

For each test case, print a line containing the test case number( beginning with 1) followed by the number of constellations appearing in the sky.

Sample Input

3 3 2 2 2
00
0*
*00

**
00

0
*
3 3 2 2 2
00
0*
*00

**
00

0
0
0 0 0 0 0

Sample Output

Case 1: 1
Case 2: 2

题解

这道题hash没有暴力跑得快
把每一行的q个都给二进制，然后子方格二进制压起来，然后一行行暴力匹配

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define ba  823
  13. #define ha 99994711
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. int n,m,t,p,q;
  18. char map[1005][1005];
  19. ll hash[1005][1005],h[105];
  20. int ans;
  21. bool check() {
  22.     siji(i,1,n-p+1) {
  23.     siji(j,1,m-q+1) {
  24.         if(hash[i][j]==h[1]) {
  25.         siji(k,2,p) {
  26.             if(hash[i+k-1][j]!=h[k]) goto fail;
  27.         }
  28.         return true;
  29.         }
  30.         fail:;
  31.     }
  32.     }
  33.     return false;
  34. }
  35. void solve() {
  36.     if(n<p || m<q) {puts("0");return;}
  37.     memset(hash,0,sizeof(hash));
  38.     siji(i,1,n) {
  39.     scanf("%s",map[i]+1);
  40.     siji(k,1,q) {
  41.         if(map[i][k]=='*') {
  42.         hash[i][1]|=((ll)1<<(k-1));
  43.         }
  44.     }
  45.     siji(j,2,m-q+1) {
  46.         hash[i][j]=hash[i][j-1]>>1;
  47.         if(map[i][j+q-1]=='*') {
  48.         hash[i][j]|=((ll)1<<(q-1));
  49.         }
  50.     }
  51.     }
  52.     ans=0;
  53.     while(t--) {
  54.     memset(h,0,sizeof(h));
  55.     siji(i,1,p) {
  56.         scanf("%s",map[i]+1);
  57.         siji(j,1,q) {
  58.         if(map[i][j]=='*') {
  59.             h[i]|=((ll)1<<(j-1));
  60.         }
  61.         }
  62.     }
  63.     if(check()) ++ans;
  64.     }
  65.     printf("%d\n",ans);
  66. }
  67. int main() {
  68. #ifdef ivorysi
  69.     freopen("f1.in","r",stdin);
  70. #endif
  71.     int c=0;
  72.     while(scanf("%d%d%d%d%d",&n,&m,&t,&p,&q)!=EOF) {
  73.     if(n==0 && m==0 && t==0 && p==0 && q==0) break;
  75.     ++c;
  76.     printf("Case %d: ",c);
  77.     solve();
  78.     }
  80.     return 0;
  82. }

双hash大法

好啊！

lzlj

机房这个神奇的地方总是存在这一些神奇的字符串
就拿lzlj来说吧，就有着许多意思
泸州老窖
龙章麟角
老子垃圾
连战连捷
当然还有**垃圾
然而机房里某位具有毒奶的人却不愿听到lzlj，而胡小兔和其他一群菜鸡总喜欢讲话.
所以她现在交给你一个任务，让你判断讲话内容中什么时候出现了她不喜欢的词汇
(如果你不想完成这个任务的话，请你输出lzlj，并准备接受毒奶)

输入

第一行一个正整数n(1<=n<=1000)，表示她一共有n个不想听到的词汇
接下来第2到n+1行，每行一个字符串S[i]表示该词汇(|S|<=20)
第n+2行一个正整数m(m<=1000000)，表示机房讲话内容的长度
第n+3行一个长度为m的字符串T

输出

一个长度为m的数字串，第i位输出1表示存在以T[i]开头的不喜欢的词汇，0则为不存在

样例输入

1
lzlj
50
lzljlinzhihaoalzllzljllzjjlzljpleasedontmilkmelzlj

样例输出

10000000000000000100000000100000000000000000001000

题解

这个题出的
好啊！
因为hash不擅长比较长度不相同的字符串，所以我们按照长度进行插入，每次清空一遍哈希表，然后检查这个位置的串是不是合法，我们可以用单变量从后往前扫来得到m串固定长度的哈希值
这道题由于太随机了，一个普通的模数会被卡死，所以我们要写双哈希

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. int n,m;
  16. char s[1005][55];
  17. char str[1000005];
  18. vector<int> v[55];
  19. bool lz[1000005];
  20. ll e[2][25];
  21. ll ha[2]={99994711,1274436047};
  22. int ba[2]={823,757};
  23. struct node {
  24.     ll val;
  25.     int next;
  26. }edge[2][2000005];
  27. int head[2][MOD+5],sumedge[2];
  28. void add(int id,int u,ll x) {
  29.     edge[id][++sumedge[id]].val=x;
  30.     edge[id][sumedge[id]].next=head[id][u];
  31.     head[id][u]=sumedge[id];
  32. }
  33. void ins(int id,ll x) {
  34.     x%=ha[id];
  35.     int u=(int)x%MOD;
  36.     for(int i=head[id][u];i;i=edge[id][i].next) {
  37.     if(edge[id][i].val==x) return ;
  38.     }
  39.     add(id,u,x);
  40. }
  41. bool find(int id,ll x) {
  42.     x%=ha[id];
  43.     int u=(int)x%MOD;
  44.     for(int i=head[id][u];i;i=edge[id][i].next) {
  45.     if(edge[id][i].val==x) return true;
  46.     }
  47.     return false;
  48. }
  49. ll calc(int pos,int id) {
  50.     int l=strlen(s[id]+1);
  51.     ll res=0;
  52.     siji(i,1,l) {
  53.     res+=e[pos][i-1]*(s[id][i]-'a'+1)%ha[pos];
  54.     res%=ha[pos];
  55.     }
  56.     return res;
  57. }
  58. ll change(int id,ll x,int pos,int k) {
  59.     x-=(str[pos]-'a'+1)*e[id][k-1]%ha[id];
  60.     x=(x%ha[id]+ha[id])%ha[id];
  61.     x=x*e[id][1]%ha[id];
  62.     x+=(str[pos-k]-'a'+1);
  63.     x%=ha[id];
  64.     return x;//忘记return 了， gg
  65. }
  66. void solve() {
  67.     e[0][0]=1;e[1][0]=1;
  68.     siji(i,1,20) {
  69.     e[0][i]=e[0][i-1]*ba[0]%ha[0];
  70.     e[1][i]=e[1][i-1]*ba[1]%ha[1];
  71.     }
  72.     scanf("%d",&n);
  73.     siji(i,1,n) {
  74.     scanf("%s",s[i]+1);
  75.     v[strlen(s[i]+1)].push_back(i);
  76.     }
  77.     scanf("%d",&m);
  78.     scanf("%s",str+1);
  79.     siji(j,1,20) {
  80.     if(m<j) break;
  81.     memset(head,0,sizeof(head));
  82.     memset(sumedge,0,sizeof(sumedge));
  83.     int si=v[j].size();
  84.     if(si==0) continue;
  85.     xiaosiji(k,0,si) {
  86.         ins(0,calc(0,v[j][k]));
  87.         ins(1,calc(1,v[j][k]));
  88.     }
  90.     ll now0=0,now1=0;
  91.     int t=0;
  92.     siji(i,m-j+1,m) {
  93.         now0+=(str[i]-'a'+1)*e[0][t]%ha[0];
  94.         now1+=(str[i]-'a'+1)*e[1][t]%ha[1];
  95.         ++t;
  96.         now0%=ha[0];
  97.         now1%=ha[1];
  98.     }
  99.     gongzi(i,m,j) {
  100.         if(find(0,now0)&&find(1,now1)) {
  101.         lz[i-j+1]=1;
  102.         }
  103.         now0=change(0,now0,i,j);
  104.         now1=change(1,now1,i,j);
  105.     }
  106.     }
  107.     siji(i,1,m) {
  108.     if(lz[i]) printf("1");
  109.     else printf("0");
  110.     }
  111.     puts("");
  112. }
  114. int main() {
  115. #ifdef ivorysi
  116.     freopen("f1.in","r",stdin);
  117. #endif
  118.     solve();
  120.     return 0;
  122. }

codeforces 25 E. Test

Sometimes it is hard to prepare tests for programming problems. Now Bob is preparing tests to new problem about strings — input data to his problem is one string. Bob has 3 wrong solutions to this problem. The first gives the wrong answer if the input data contains the substring s1, the second enters an infinite loop if the input data contains the substring s2, and the third requires too much memory if the input data contains the substring s3. Bob wants these solutions to fail single test. What is the minimal length of test, which couldn't be passed by all three Bob's solutions?

Input

There are exactly 3 lines in the input data. The i-th line contains string si. All the strings are non-empty, consists of lowercase Latin letters, the length of each string doesn't exceed 105.

Output

Output one number — what is minimal length of the string, containing s1, s2 and s3 as substrings.

Examples

Input

ab
bc
cd

Output

4

Input

abacaba
abaaba
x

Output

11

题解

这道题我们用hash暴力就好
我们先忽略所有串是另一个串子串
然后前后链接这么匹配，找前后链接的最大长度用暴力去找
然后生成一个新的串，求新的hash，然后再和下一个进行匹配
有特殊情况是一个串包含了剩下所有的串

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define ba 823
  13. #define ha 99994711
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. char s[10][300005];
  18. ll e[300010];
  19. ll h[10][300005];
  20. int now[10],cnt,ans;
  21. bool used[10];
  22. bool check(int a,int l1,int r1,int b ,int l2,int r2) {
  23.     ll res=e[200000-l1]*(h[a][r1]-h[a][l1-1])%ha-e[200000-l2]*(h[b][r2]-h[b][l2-1])%ha;
  24.     res=(res%ha+ha)%ha;
  25.     return res==0;
  26. }
  27. void calc() {
  28.     int len=0;
  29.     siji(i,2,cnt) {
  30.     int la=strlen(s[now[i-1]]+1),lb=strlen(s[now[i]]+1);
  31.     int l=min(la,lb);
  32.     for(len=l;len>=1;--len) {
  33.         if(check(now[i-1],la-len+1,la,now[i],1,len)) break;
  34.     }
  35.     siji(j,1,la-len) {
  36.         s[4][j]=s[now[i-1]][j];
  37.     }
  38.     siji(j,1,lb) {
  39.         s[4][j+la-len]=s[now[i]][j];
  40.     }
  41.     s[4][lb+la-len+1]='\0';
  42.     now[i]=4;
  43.     siji(j,1,lb+la-len) {
  44.         h[4][j]=h[4][j-1]+e[j-1]*(s[4][j]-'a'+1)%ha;
  45.         h[4][j]%=ha;
  46.     }
  47.     }
  48.     ans=min(ans,(int)strlen(s[4]+1));
  49.     ans=max(ans,(int)strlen(s[now[1]]+1));
  50. }
  51. void dfs(int dep) {
  52.     if(dep>cnt) {
  53.     calc();
  54.     return;
  55.     }
  56.     siji(i,0,2) {
  57.     if(used[i]) {
  58.         used[i]=0;
  59.         now[dep]=i;
  60.         dfs(dep+1);
  61.         used[i]=1;
  62.     }
  63.     }
  64. }
  65. void solve() {
  66.     e[0]=1;
  67.     siji(i,1,200000) {
  68.     e[i]=e[i-1]*ba%ha;
  69.     }
  70.     scanf("%s%s%s",s[0]+1,s[1]+1,s[2]+1);
  71.     ans=strlen(s[0]+1)+strlen(s[1]+1)+strlen(s[2]+1);
  72.     if(strlen(s[0]+1)<strlen(s[1]+1)) swap(s[0],s[1]);
  73.     if(strlen(s[0]+1)<strlen(s[2]+1)) swap(s[0],s[2]);
  74.     if(strlen(s[1]+1)<strlen(s[2]+1)) swap(s[1],s[2]);
  75.     siji(i,0,2) {
  76.     int len=strlen(s[i]+1);
  77.     siji(j,1,len) {
  78.         h[i][j]=h[i][j-1]+e[j-1]*(s[i][j]-'a'+1)%ha;
  79.         h[i][j]%=ha;
  80.     }
  81.     }
  82.     memset(used,1,sizeof(used));
  83.     siji(i,1,2) {
  84.     siji(j,0,i-1) {
  85.         if(!used[j]) continue;
  86.         int l=strlen(s[j]+1),z=strlen(s[i]+1);
  87.         siji(k,1,l-z+1) {
  88.         if(check(j,k,k+z-1,i,1,z)) {used[i]=0;break;}
  89.         }
  90.         if(!used[i]) break;
  91.     }
  92.     }
  93.     siji(i,0,2) if(used[i]) ++cnt;
  94.     dfs(1);
  95.     printf("%d\n",ans);
  96. }
  98. int main() {
  99. #ifdef ivorysi
  100.     freopen("f1.in","r",stdin);
  101. #endif
  102.     solve();
  104.     return 0;
  106. }

二分图

二分图有一些很秒的公式啊

|最大匹配数|=|最小顶点覆盖|
最小顶点覆盖的意思是我们选择个数最少的点然后覆盖所有的边
我们考虑每一条边一定连着一个被匹配的点，如果一条边连着一个未匹配的点，那么这条边也一定连着一条被匹配的点，否则匹配可以增加

|最大独立集|+|最小顶点覆盖|=顶点个数
最大独立集就是选出一些点，这些点之间没有边相连
我们把最小顶点覆盖去除了，那么剩下的顶点就没有边了啊

|最大匹配|+|最小边覆盖|=顶点个数
我们往最大匹配中加边，就可以覆盖所有顶点了，所以这个式子告诉我们，最小边覆盖就是选择最大匹配的那些边，然后加入新的边将未匹配点链接起来

POJ 2724 Purifying Machine

Description

Mike is the owner of a cheese factory. He has 2N cheeses and each cheese is given a binary number from 00...0 to 11...1. To keep his cheese free from viruses, he made himself a purifying machine to clean virus-infected cheese. As a talented programmer, his purifying machine is built in a special way. His purifying machine has N switches, each switch has three states, 1, 0 and *. An operation of this machine is a cleaning action according to the states of the N switches. During one operation, at most one switch can be turned to state *, which can substitute for either 1 or 0. When the machine is turned to a specific state, an operation will clean all the cheeses with corresponding binary numbers. For example, if N equals 6 and the switches are turned to 01*100, the cheeses numbered 010100 and 011100 are under operation by the machine.
One day, Mike's machine was infected. When Mike found out, he had already done some operations and the cheeses operated by this infected machine were infected too. He cleaned his machine as quickly as he could, and now he needs to clean the infected cheeses with the minimum number of operations. If a cheese is infected, cleaning this cheese with the machine one or more times will make this cheese free from virus again; but if a cheese is not infected, operation on this cheese will make it go bad.
Now given the infected operations Mike has done, you need to find out the minimum number of operations that must be performed to clean all the infected cheeses without making any clean cheese go bad.

Input

There are several test cases. Each test case starts with a line containing two numbers N and M (1 <= N <= 10, 1 <= M <= 1000). N is the number of switches in the machine and M is the number of infected operations Mike has done. Each of the following M lines contains a switch state of the machine. A test case with N = M = 0 ends the input and should not be processed.

Output

For each test case, output one line containing an integer, which is the minimum number of operations Mike needs to do.

Sample Input

3 3
*01
100
011
0 0

Sample Output

2

题解

这道题“at most one switch can be turned to state *”
╮(╯▽╰)╭思考的方向一开始就跑偏了，以为会有很多*其实只有一个
只有一个的话就很好考虑了，我们创造出所有被污染的奶酪编号，然后我们在每两个二进制位只相差一位的奶酪编号连上一条边，然后跑二分图匹配
这道题要求的是最小边覆盖，运用公式|最大匹配数|+|最小边覆盖|=|V|
这道题的from一定需要是-1因为0也是一个点

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define ba 823
  13. #define ha 99994711
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. int n,m;
  18. char s[105];
  19. vector<int> g[2200];
  20. bool used[2200],vis[2200];
  21. int num[3500],now=0,tot,par[3500],ans;
  22. void dfs(int dep) {
  23.     if(dep>n) {
  24.     if(!used[now]) {
  25.         used[now]=1;
  26.         num[++tot]=now;
  27.     }
  28.     return;
  29.     }
  30.     if(s[dep]=='*') {
  31.     now=(now<<1)|1;
  32.     dfs(dep+1);
  33.     now>>=1;
  34.     now=(now<<1);
  35.     dfs(dep+1);
  36.     }
  37.     if(s[dep]=='1') {
  38.     now=(now<<1)|1;
  39.     dfs(dep+1);
  40.     now>>=1;
  41.     }
  42.     if(s[dep]=='0') {
  43.     now=(now<<1);
  44.     dfs(dep+1);
  45.     now>>=1;
  46.     }
  47. }
  48. int lowbit(int x) {
  49.     return x&(-x);
  50. }
  51. bool match(int u) {
  52.     int s=g[u].size();
  53.     xiaosiji(i,0,s) {
  54.     int v=g[u][i];
  55.     if(!vis[v]) {
  56.         vis[v]=1;
  57.         if(par[v]==-1 || match(par[v])) {
  58.         par[v]=u;
  59.         par[u]=v;
  60.         return true;
  61.         }
  62.     }
  63.     }
  64.     return false;
  65. }
  66. void solve() {
  67.     siji(i,0,1024) g[i].clear();
  68.     memset(num,0,sizeof(num));
  69.     memset(used,0,sizeof(used));
  70.     memset(par,-1,sizeof(par));
  71.     tot=0;
  72.     ans=0;
  73.     siji(i,1,m) {
  74.     scanf("%s",s+1);
  75.     now=0;
  76.         dfs(1);
  77.     }
  78.     siji(i,1,tot) {
  79.     siji(j,i+1,tot) {
  80.         int C=num[i]^num[j];
  81.         if(C-lowbit(C)==0) {
  82.         g[num[i]].push_back(num[j]);
  83.         g[num[j]].push_back(num[i]);
  84.         }
  85.     }
  86.     }
  87.     siji(i,0,1024) {
  88.     if(used[i]) {
  89.         if(par[i]==-1) {
  90.         memset(vis,0,sizeof(vis));
  91.         if(match(i)) ++ans;
  92.         }
  93.     }
  94.     }
  95.     printf("%d\n",tot-ans);
  96. }
  98. int main() {
  99. #ifdef ivorysi
  100.     freopen("f1.in","r",stdin);
  101. #endif
  102.     while(scanf("%d%d",&n,&m)!=EOF){
  103.     if(n+m==0) break;
  104.     solve();
  105.     }
  106.     return 0;
  108. }

POJ 1422 Air Raid

Description

Consider a town where all the streets are one-way and each street leads from one intersection to another. It is also known that starting from an intersection and walking through town's streets you can never reach the same intersection i.e. the town's streets form no cycles.
With these assumptions your task is to write a program that finds the minimum number of paratroopers that can descend on the town and visit all the intersections of this town in such a way that more than one paratrooper visits no intersection. Each paratrooper lands at an intersection and can visit other intersections following the town streets. There are no restrictions about the starting intersection for each paratrooper.

Input

Your program should read sets of data. The first line of the input file contains the number of the data sets. Each data set specifies the structure of a town and has the format:
no_of_intersections
no_of_streets
S1 E1
S2 E2
......
Sno_of_streets Eno_of_streets
The first line of each data set contains a positive integer no_of_intersections (greater than 0 and less or equal to 120), which is the number of intersections in the town. The second line contains a positive integer no_of_streets, which is the number of streets in the town. The next no_of_streets lines, one for each street in the town, are randomly ordered and represent the town's streets. The line corresponding to street k (k <= no_of_streets) consists of two positive integers, separated by one blank: Sk (1 <= Sk <= no_of_intersections) - the number of the intersection that is the start of the street, and Ek (1 <= Ek <= no_of_intersections) - the number of the intersection that is the end of the street. Intersections are represented by integers from 1 to no_of_intersections.
There are no blank lines between consecutive sets of data. Input data are correct.

Output

The result of the program is on standard output. For each input data set the program prints on a single line, starting from the beginning of the line, one integer: the minimum number of paratroopers required to visit all the intersections in the town.

Sample Input

2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

Sample Output

2
1

题解

这道题我们这样考虑，求一个最小路径覆盖
我们把每个点拆成两个点，然后如果u到v有一条边，然后从u到v'连一个点，求最大匹配
n-最大匹配数就是我们的答案
为什么呢……可以这么想，我们有一条路径a->b b->c c->d
我们一定匹配了三条边a->b b->c c->d
经过的节点数是4个，然后需要走的点是4-3=1个
最后呢，其实在代码里不用把点拆开，我们的边都是有向边，from只要更新从谁走过来就可以了，而由于我们不能逆着边走，题里有没有环，所以我们的情况不会发生冲突

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define ba 823
  13. #define ha 99994711
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. int T,n,m;
  18. struct node {
  19.     int to,next;
  20. }edge[10005];
  21. int head[10005],sumedge,from[10005],ans;
  22. bool vis[10005];
  23. void add(int u,int v) {
  24.     edge[++sumedge].to=v;
  25.     edge[sumedge].next=head[u];
  26.     head[u]=sumedge;
  27. }
  28. bool match(int u) {
  29.     for(int i=head[u];i;i=edge[i].next) {
  30.     int v=edge[i].to;
  31.     if(!vis[v]) {
  32.         vis[v]=1;
  33.         if(from[v]==0 || match(from[v])) {
  34.         from[v]=u;
  35.         return true;
  36.         }
  37.     }
  38.     }
  39.     return false;
  40. }
  41. void solve() {
  42.     scanf("%d%d",&n,&m);
  43.     memset(from,0,sizeof(from));
  44.     memset(head,0,sizeof(head));
  45.     sumedge=0;
  46.     ans=0;
  47.     int u,v;
  48.     siji(i,1,m) {
  49.     scanf("%d%d",&u,&v);
  50.     add(u,v);
  51.     }
  52.     siji(i,1,n) {
  53.     memset(vis,0,sizeof(vis));
  54.     if(match(i)) ++ans;
  55.     }
  56.     printf("%d\n",n-ans);
  57. }
  59. int main() {
  60. #ifdef ivorysi
  61.     freopen("f1.in","r",stdin);
  62. #endif
  63.     scanf("%d",&T);
  64.     while(T--) {
  65.     solve();
  66.     }
  67.     return 0;
  69. }

POJ 1486 Sorting Slides

Description

Professor Clumsey is going to give an important talk this afternoon. Unfortunately, he is not a very tidy person and has put all his transparencies on one big heap. Before giving the talk, he has to sort the slides. Being a kind of minimalist, he wants to do this with the minimum amount of work possible.
The situation is like this. The slides all have numbers written on them according to their order in the talk. Since the slides lie on each other and are transparent, one cannot see on which slide each number is written.
Well, one cannot see on which slide a number is written, but one may deduce which numbers are written on which slides. If we label the slides which characters A, B, C, ... as in the figure above, it is obvious that D has number 3, B has number 1, C number 2 and A number 4.
Your task, should you choose to accept it, is to write a program that automates this process.

Input

The input consists of several heap descriptions. Each heap descriptions starts with a line containing a single integer n, the number of slides in the heap. The following n lines contain four integers xmin, xmax, ymin and ymax, each, the bounding coordinates of the slides. The slides will be labeled as A, B, C, ... in the order of the input.
This is followed by n lines containing two integers each, the x- and y-coordinates of the n numbers printed on the slides. The first coordinate pair will be for number 1, the next pair for 2, etc. No number will lie on a slide boundary.
The input is terminated by a heap description starting with n = 0, which should not be processed.

Output

For each heap description in the input first output its number. Then print a series of all the slides whose numbers can be uniquely determined from the input. Order the pairs by their letter identifier.
If no matchings can be determined from the input, just print the word none on a line by itself.
Output a blank line after each test case.

Sample Input

4
6 22 10 20
4 18 6 16
8 20 2 18
10 24 4 8
9 15
19 17
11 7
21 11
2
0 2 0 2
0 2 0 2
1 1
1 1
0

Sample Output

Heap 1
(A,4) (B,1) (C,2) (D,3)

Heap 2
none

题解

又因为没好好读题naive了
Then print a series of all the slides whose numbers can be uniquely determined from the input
这说明了输入不是完全合法的，我们是要找哪些边一定在最大匹配里
求一个最大匹配和边集，然后删除每条边再求一次最大匹配，看看最大匹配的数目有没有减少，有减少的话就证明不是

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define ba 823
  13. #define ha 99994711
  14. #define pii pair<int,int>
  15. #define fi first
  16. #define se second
  17. //#define ivorysi
  18. using namespace std;
  19. typedef long long ll;
  20. int n;
  21. int g[105][105];
  22. char *s="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  23. int xmin[105],xmax[105],ymin[105],ymax[105],ql,num,from[105],ans[105],cnt;
  24. pii que[105];
  25. bool vis[105];
  26. bool match(int u) {
  27.     siji(v,1,60) {
  28.     if(g[u][v]) {
  29.         if(!vis[v]) {
  30.         vis[v]=1;
  31.         if(from[v]==0 || match(from[v])) {
  32.             from[v]=u;
  33.             return true;
  34.         }
  35.         }
  36.     }
  37.     }
  38.     return false;
  39. }
  40. int calc(pii k) {
  41.     g[k.fi][k.se]=0;
  42.     int res=0;
  43.     memset(from,0,sizeof(from));
  44.     siji(i,1,n) {
  45.     memset(vis,0,sizeof(vis));
  46.     if(match(i)) {
  47.         ++res;
  48.     }
  49.     }
  50.     g[k.fi][k.se]=1;
  51.     return res;
  52. }
  53. void solve() {
  54.     memset(from,0,sizeof(from));
  55.     memset(ans,0,sizeof(ans));
  56.     memset(g,0,sizeof(g));
  57.     memset(ans,0,sizeof(ans));
  58.     ql=0;
  59.     cnt=0;
  60.     num=0;
  61.     siji(i,1,n) {
  62.     scanf("%d%d%d%d",&xmin[i],&xmax[i],&ymin[i],&ymax[i]);
  63.     }
  64.     int x,y;
  65.     siji(i,1,n) {
  66.     scanf("%d%d",&x,&y);
  67.     siji(j,1,n) {
  68.         if(xmin[j]<=x && xmax[j]>=x && ymin[j]<=y && ymax[j]>=y) {
  69.         g[j][i+n]=1;
  70.         }
  71.     }
  72.     }
  73.     siji(i,1,n) {
  74.     memset(vis,0,sizeof(vis));
  75.     if(match(i)) ++num;
  76.     }
  77.     siji(i,n+1,2*n) {
  78.     que[++ql]=make_pair(from[i],i);
  79.     }
  80.     siji(i,1,ql) {
  81.     if(calc(que[i])<num) {
  82.         ++cnt;
  83.         ans[que[i].fi]=que[i].se-n;
  84.     }
  85.     }
  86.     if(cnt==0) {
  87.     puts("none");
  88.     return;
  89.     }
  90.     int t=0;
  91.     siji(i,1,n) {
  92.     if(ans[i]!=0) {
  93.         ++t;
  94.         printf("(%c,%d)%c",s[i-1],ans[i]," \n"[t==cnt]);
  95.     }
  96.     }
  97. }
  99. int main() {
  100. #ifdef ivorysi
  101.     freopen("f1.in","r",stdin);
  102. #endif
  103.     int T=0;
  104.     while(1) {
  105.     scanf("%d",&n);
  106.     if(!n) break;
  107.     ++T;
  108.     if(T!=1) puts("");
  109.     printf("Heap %d\n",T);
  110.     solve();
  111.     }
  112.     return 0;
  114. }

IDDFS

1085: [SCOI2005]骑士精神

Description

在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑
士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空
位上。 给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘： 为了体现出骑士精神，他们必须以最少的步
数完成任务。

Input

第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑
士，*表示空位。两组数据之间没有空行。

Output

对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。

Sample Input

2
10110
01*11
10111
01001
00000
01011
110*1
01110
01010
00100

Sample Output

7
-1

题解

我们的估价函数表示至少要走的步数，值是当前状态和目标状态不同的位置的个数-1
然后逐渐枚举深度，进行搜索

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define ba 823
  13. #define ha 99994711
  14. #define pii pair<int,int>
  15. #define fi first
  16. #define se second
  17. //#define ivorysi
  18. using namespace std;
  19. typedef long long ll;
  20. int T,stx,sty,dep;
  21. char cur[5][5];
  22. char last[5][5]={
  23.     {'1','1','1','1','1'},
  24.     {'0','1','1','1','1'},
  25.     {'0','0','*','1','1'},
  26.     {'0','0','0','0','1'},
  27.     {'0','0','0','0','0'}
  28. };
  29. int dx[]={1,-1,1,-1,2,-2,2,-2};
  30. int dy[]={2,2,-2,-2,1,1,-1,-1};
  31. int H() {
  32.     int res=-1;
  33.     siji(i,0,4) {
  34.     siji(j,0,4) {
  35.         if(last[i][j]!=cur[i][j]) ++res;
  36.     }
  37.     }
  38.     return res;
  39. }
  40. bool check(int x,int y) {
  41.     return x>=0 && x<=4 && y>=0 && y<=4;
  42. }
  43. bool dfs(int step,int x,int y) {
  44.     if(step>dep) {
  45.     if(H()==-1) return true;
  46.     return false;
  47.     }
  48.     if(step+H()-1 > dep) return false;
  49.     siji(i,0,7) {
  50.     int fx=x+dx[i],fy=y+dy[i];
  51.     if(check(fx,fy)) {
  52.         swap(cur[fx][fy],cur[x][y]);
  53.         if(dfs(step+1,fx,fy)) return true;
  54.         swap(cur[fx][fy],cur[x][y]);
  55.     }
  56.     }
  57.     return false;
  58. }
  59. int main() {
  60. #ifdef ivorysi
  61.     freopen("f1.in","r",stdin);
  62. #endif
  63.     scanf("%d",&T);
  64.     while(T--) {
  65.     siji(i,0,4) {
  66.         scanf("%s",cur[i]);
  67.     }
  68.     siji(i,0,4) {
  69.         siji(j,0,4) {
  70.         if(cur[i][j]=='*') stx=i,sty=j;
  71.         }
  72.     }
  73.     siji(i,0,15) {
  74.         dep=i;
  75.         if(dfs(1,stx,sty)) {
  76.         printf("%d\n",dep);
  77.         goto succ;
  78.         }
  79.     }
  80.     puts("-1");
  81.         succ:;
  82.     }
  83.     return 0;
  85. }

POJ 2286 The Rotation Game

Description

The rotation game uses a # shaped board, which can hold 24 pieces of square blocks (see Fig.1). The blocks are marked with symbols 1, 2 and 3, with exactly 8 pieces of each kind.
Initially, the blocks are placed on the board randomly. Your task is to move the blocks so that the eight blocks placed in the center square have the same symbol marked. There is only one type of valid move, which is to rotate one of the four lines, each consisting of seven blocks. That is, six blocks in the line are moved towards the head by one block and the head block is moved to the end of the line. The eight possible moves are marked with capital letters A to H. Figure 1 illustrates two consecutive moves, move A and move C from some initial configuration.

Input

The input consists of no more than 30 test cases. Each test case has only one line that contains 24 numbers, which are the symbols of the blocks in the initial configuration. The rows of blocks are listed from top to bottom. For each row the blocks are listed from left to right. The numbers are separated by spaces. For example, the first test case in the sample input corresponds to the initial configuration in Fig.1. There are no blank lines between cases. There is a line containing a single `0' after the last test case that ends the input.

Output

For each test case, you must output two lines. The first line contains all the moves needed to reach the final configuration. Each move is a letter, ranging from A' toH', and there should not be any spaces between the letters in the line. If no moves are needed, output `No moves needed' instead. In the second line, you must output the symbol of the blocks in the center square after these moves. If there are several possible solutions, you must output the one that uses the least number of moves. If there is still more than one possible solution, you must output the solution that is smallest in dictionary order for the letters of the moves. There is no need to output blank lines between cases.

Sample Input

1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
0

Sample Output

AC
2
DDHH
2

题解

A*函数是还差几个数能构成中间方格的8个数
然后我这个zz
我把格子的长度打成了8
然后自己毫无知觉……wtf……为什么能过样例啊

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define ba 823
  13. #define ha 99994711
  14. #define pii pair<int,int>
  15. #define fi first
  16. #define se second
  17. //#define ivorysi
  18. using namespace std;
  19. typedef long long ll;
  20. int ori[30],dep=0;
  21. int cur[5][10];
  22. int op[10],line[10],d[10],ans[106];
  23. int H() {
  24.     int cnt[4]={0,0,0,0};
  25.     siji(j,0,1) {
  26.     siji(i,2,4) {
  27.         cnt[cur[j][i]]++;
  28.     }
  29.     }
  30.     cnt[cur[2][3]]++;
  31.     cnt[cur[3][3]]++;
  32.     int res=8-cnt[1];
  33.     res=min(res,8-cnt[2]);
  34.     res=min(res,8-cnt[3]);
  35.     return res;
  36. }
  37. void update(int x) {
  38.     if(x==0) {
  39.     cur[2][2]=cur[0][2];
  40.     cur[3][2]=cur[0][4];
  41.     }
  42.     else if(x==1) {
  43.     cur[2][4]=cur[1][2];
  44.     cur[3][4]=cur[1][4];
  45.     }
  46.     else if(x==2) {
  47.     cur[0][2]=cur[2][2];
  48.     cur[1][2]=cur[2][4];
  49.     }
  50.     else {
  51.     cur[0][4]=cur[3][2];
  52.     cur[1][4]=cur[3][4];
  53.     }
  54. }
  55. void change(int id,int dir) {
  56.     int tmp[10];
  57.     memcpy(tmp,cur[id],sizeof(cur[id]));
  58.     siji(i,0,6) {
  59.     cur[id][i]=tmp[(i+dir+7)%7];
  60.     }
  61. }
  62. bool dfs(int step,int prev) {
  63.     if(step>dep) {
  64.     if(H()==0) return true;
  65.     else return false;
  66.     }
  67.     if(step+H()-1 > dep) return false;
  68.     siji(i,0,7) {
  69.     if(i==op[prev]) continue;
  70.     else {
  71.         change(line[i],d[i]);
  72.         update(line[i]);
  73.         ans[step]=i;
  74.         if(dfs(step+1,i)) return true;
  75.         change(line[i],-d[i]);
  76.         update(line[i]);
  77.     }
  78.     }
  79.     return false;
  80. }
  81. int main() {
  82. #ifdef ivorysi
  83.     freopen("f1.in","r",stdin);
  84. #endif
  85.     op[0]=5;op[1]=4;op[2]=7;op[3]=6;
  86.     op[5]=0;op[4]=1;op[7]=2;op[6]=3;
  87.     op[8]=-1;
  88.     line[0]=line[5]=0;
  89.     line[1]=line[4]=1;
  90.     line[2]=line[7]=2;
  91.     line[3]=line[6]=3;
  92.     d[0]=d[1]=d[6]=d[7]=1;
  93.     d[2]=d[3]=d[4]=d[5]=-1;
  94.     while(1) {
  95.     scanf("%d",&ori[1]);
  96.     if(ori[1]==0) break;
  97.     siji(i,2,24) scanf("%d",&ori[i]);
  98.     siji(i,5,11) cur[2][i-5]=ori[i];
  99.     siji(i,14,20) cur[3][i-14]=ori[i];
  100.     cur[0][0]=ori[1];cur[0][1]=ori[3];
  101.     cur[0][2]=ori[7];cur[0][3]=ori[12];
  102.     cur[0][4]=ori[16];cur[0][5]=ori[21];
  103.     cur[0][6]=ori[23];
  104.     cur[1][0]=ori[2];cur[1][1]=ori[4];
  105.     cur[1][2]=ori[9];cur[1][3]=ori[13];
  106.     cur[1][4]=ori[18];cur[1][5]=ori[22];
  107.     cur[1][6]=ori[24];
  108.     dep=0;
  109.     memset(ans,0,sizeof(ans));
  110.     while(!dfs(1,8)) {
  111.         ++dep;
  112.     }
  113.     if(!dep) {
  114.         puts("No moves needed");
  115.     }
  116.     else {
  117.         siji(i,1,dep) {
  118.         printf("%c",ans[i]+'A');
  119.         }
  120.         putchar('\n');
  121.     }
  122.     printf("%d\n",cur[0][2]);
  124.     }
  125.     return 0;
  127. }

ZOJ 1937 Addition Chains

An addition chain for n is an integer sequence with the following four properties:
a0 = 1
am = n
a0 < a1 < a2 < ... < am-1 < am
For each k (1 <= k <= m) there exist two (not necessarily different) integers i and j (0 <= i, j <= k-1) with ak = ai + aj
You are given an integer n. Your job is to construct an addition chain for n with minimal length. If there is more than one such sequence, any one is acceptable.
For example, <1, 2, 3, 5> and <1, 2, 4, 5> are both valid solutions when you are asked for an addition chain for 5.

Input

The input will contain one or more test cases. Each test case consists of one line containing one integer n (1 <= n <= 100). Input is terminated by a value of zero (0) for n.

Output

For each test case, print one line containing the required integer sequence. Separate the numbers by one blank.

Sample Input

5
7
12
15
77
0

Sample Output

1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77

题解

迭代加深搜索里比较简单的一道题
枚举深度然后搜索就可以，我这里单一的认为下一个数是相邻前一个数和某一个数相加，实际上应该会有别的情况，但是这种情况是大多数，可以简单优化一下不用深搜太多

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. //#define ivorysi
  12. using namespace std;
  13. typedef long long ll;
  14. int n;
  15. int cur[105],dep=0;
  16. bool dfs(int step) {
  17.     if(step>dep) {
  18.         if(cur[dep]==n) return true;
  19.         return false;
  20.     }
  21.     siji(i,0,step-1) {
  22.         if(cur[step-1]+cur[i]<=n) {
  23.             cur[step]=cur[step-1]+cur[i];
  24.             if(dfs(step+1)) return true;
  25.         }
  26.     }
  27.     return false;
  29. }
  30. int main() {
  31. #ifdef ivorysi
  32.     freopen("f1.in","r",stdin);
  33. #endif
  34.     cur[0]=1;
  35.     while(scanf("%d",&n)!=EOF) {
  36.         if(n==0) break;
  37.         dep=0;
  38.         while(!dfs(1)) {
  39.             ++dep;
  40.         }
  41.         siji(i,0,dep) {
  42.             printf("%d%c",cur[i]," \n"[i==dep]);
  43.         }
  44.     }
  45.     return 0;
  47. }

折半搜索

POJ 2549 Sumsets

Description

Given S, a set of integers, find the largest d such that a + b + c = d where a, b, c, and d are distinct elements of S.

Input

Several S, each consisting of a line containing an integer 1 <= n <= 1000 indicating the number of elements in S, followed by the elements of S, one per line. Each element of S is a distinct integer between -536870912 and +536870911 inclusive. The last line of input contains 0.

Output

For each S, a single line containing d, or a single line containing "no solution".

Sample Input

5
2
3
5
7
12
5
2
16
64
256
1024
0

Sample Output

12
no solution

题解

这道题我们可以考虑一半，a+b=d-c
把所有a+b哈希起来
然后枚举d c判断这个值有没有和a+b中的某个数相同

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #include <set>
  9. #include <map>
  10. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  11. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  12. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  13. #define MAXN 100005
  14. #define MOD 994711
  15. //#define ivorysi
  16. using namespace std;
  17. typedef long long ll;
  18. int n;
  19. ll a[2006];
  20. struct node {
  21.     ll val;
  22.     int d,c;
  23.     int next;
  24. }edge[1000005];
  25. int head[MOD+15],sumedge;
  26. void add(int u,ll v,int d,int c) {
  27.     edge[++sumedge].val=v;
  28.     edge[sumedge].next=head[u];
  29.     edge[sumedge].d=d;
  30.     edge[sumedge].c=c;
  31.     head[u]=sumedge;
  32. }
  33. void ins(ll v,int d,int c) {
  34.     int u=(v%MOD+MOD)%MOD;
  35.     add(u,v,d,c);
  36. }
  37. bool find(ll x,int d,int c) {
  38.     int u=(x%MOD+MOD)%MOD;
  39.     for(int i=head[u];i;i=edge[i].next) {
  40.     if(edge[i].val==x) {
  41.         if(d!=edge[i].d && c!=edge[i].c && d!=edge[i].c && c!=edge[i].d) {
  42.         return true;
  43.         }
  44.     }
  45.     }
  46.     return 0;
  47. }
  48. void solve() {
  49.     sumedge=0;
  50.     memset(head,0,sizeof(head));
  51.     siji(i,1,n) {
  52.     siji(j,i+1,n) {
  53.         ins(a[i]+a[j],i,j);
  54.     }
  55.     }
  56.     ll ans=-1000000000;
  57.     siji(i,1,n) {
  58.     siji(j,1,n) {
  59.         if(i==j) continue;
  60.         if(find(a[j]-a[i],j,i)) {
  61.         ans=max(ans,a[j]);
  62.         }
  63.     }
  64.     }
  65.     if(ans!=-1000000000)
  66.     printf("%lld\n",ans);
  67.     else 
  68.     puts("no solution");
  69. }
  70. int main() {
  71. #ifdef ivorysi
  72.     freopen("f1.in","r",stdin);
  73. #endif
  74.     while(scanf("%d",&n)!=EOF) {
  75.     if(!n) break;
  76.     siji(i,1,n) scanf("%lld",&a[i]);
  77.     solve();
  78.     }
  79. }

POJ 3977 Subset

Description

Given a list of N integers with absolute values no larger than 1015, find a non empty subset of these numbers which minimizes the absolute value of the sum of its elements. In case there are multiple subsets, choose the one with fewer elements.

Input

The input contains multiple data sets, the first line of each data set contains N <= 35, the number of elements, the next line contains N numbers no larger than 1015 in absolute value and separated by a single space. The input is terminated with N = 0

Output

For each data set in the input print two integers, the minimum absolute sum and the number of elements in the optimal subset.

Sample Input

1
10
3
20 100 -100
0

Sample Output

10 1
0 2

题解

这道题无限WA……真是够了
我把前18个的2^18个都加进去，并没有去重或者同一值取最小值，直接二分
然而这样我找到了第一个大于等于它的然后用这个下标k-1再去更新
这是不对的，因为排完序之后同一个值数目较大的排在后边，我们需要再一次二分找到最前面等于k-1这个值的

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. //#define ivorysi
  11. using namespace std;
  12. typedef long long ll;
  13. struct node {
  14.     ll val;
  15.     int num;
  16.     node () {};
  17.     node (ll v,int c) {
  18.     val=v;num=c;
  19.     }
  20.     bool operator < (const node &rhs) const {
  21.     if(val!=rhs.val) return val<rhs.val;
  22.     if(num!=rhs.num) return num<rhs.num;
  23.     return false;
  24.     }
  25. }sum[2000005];
  26. int tot,n;
  27. ll a[55],ans;
  28. int idx;
  29. inline ll mabs(ll x) {
  30.     if(x<=0) return -x;
  31.     return x;
  32. }
  33. void update(ll t,int z) {
  34.     if(t<ans) {ans=t;idx=z;}
  35.     else if(t==ans) {idx=min(idx,z);}
  36. }
  37. void solve() {
  39.     int c=min(18,n);
  40.     int all=(1<<c);
  41.     ans=mabs(a[1]);
  42.     idx=1;
  43.     tot=0;
  44.     xiaosiji(i,1,all) {
  45.     ll tmp=0;
  46.     int cnt=0;
  47.     siji(j,1,c) {
  48.         if((i>>(j-1)) & 1){
  49.         tmp+=a[j];
  50.         ++cnt;
  51.         }
  52.     }
  53.     update(mabs(tmp),cnt);
  54.     sum[++tot].val=tmp;
  55.     sum[tot].num=cnt;
  56.     }
  57.     sort(sum+1,sum+tot+1);
  58.     if(n<=18) {
  59.     printf("%lld %d\n",ans,idx);
  60.     return;
  61.     }
  62.     all=(1<<(n-18));
  64.     xiaosiji(i,1,all) {
  65.     ll tmp=0;
  66.     int cnt=0;
  67.     siji(j,1,n-18) {
  68.         if((i>>(j-1)) & 1) {
  69.         tmp+=a[j+18];
  70.         ++cnt;
  71.         }
  72.     }
  73.     update(mabs(tmp),cnt);
  74.     int k1=lower_bound(sum+1,sum+tot+1,node(-tmp,0))-sum;
  75.     int k2=lower_bound(sum+1,sum+tot+1,node(sum[k1-1].val,0))-sum;
  76.     if(k1>tot) k1=tot;
  77.     if(k2>tot) k2=tot;
  78.     if(k1<1) k1=1;
  79.     if(k2<1) k2=1;
  80.     update(mabs(sum[k1].val+tmp),sum[k1].num+cnt);
  81.     update(mabs(sum[k2].val+tmp),sum[k2].num+cnt);
  82.     }
  83.     printf("%lld %d\n",ans,idx);
  84. }
  85. int main() {
  86. #ifdef ivorysi
  87.     freopen("f1.in","r",stdin);
  88. #endif
  89.     while(scanf("%d",&n)!=EOF) {
  90.     if(n==0) break;
  91.     siji(i,1,n) scanf("%lld",&a[i]);
  92.     solve();
  93.     }
  94.     return 0;
  95. }

codeforces 585 D. Lizard Era: Beginning

In the game Lizard Era: Beginning the protagonist will travel with three companions: Lynn, Meliana and Worrigan. Overall the game has n mandatory quests. To perform each of them, you need to take exactly two companions.
The attitude of each of the companions to the hero is an integer. Initially, the attitude of each of them to the hero of neutral and equal to 0. As the hero completes quests, he makes actions that change the attitude of the companions, whom he took to perform this task, in positive or negative direction.
Tell us what companions the hero needs to choose to make their attitude equal after completing all the quests. If this can be done in several ways, choose the one in which the value of resulting attitude is greatest possible.

Input

The first line contains positive integer n (1 ≤ n ≤ 25) — the number of important tasks.
Next n lines contain the descriptions of the tasks — the i-th line contains three integers li, mi, wi — the values by which the attitude of Lynn, Meliana and Worrigan respectively will change towards the hero if the hero takes them on the i-th task. All the numbers in the input are integers and do not exceed 107 in absolute value.

Output

If there is no solution, print in the first line "Impossible".
Otherwise, print n lines, two characters is each line — in the i-th line print the first letters of the companions' names that hero should take to complete the i-th task ('L' for Lynn, 'M' for Meliana, 'W' for Worrigan). Print the letters in any order, if there are multiple solutions, print any of them.

Examples

Input

3
1 0 0
0 1 0
0 0 1

Output

LM
MW
MW

Input

7
0 8 9
5 9 -2
6 -8 -7
9 4 5
-4 -9 9
-4 5 2
-6 8 -7

Output

LM
MW
LM
LW
MW
LM
LW

Input

2
1 0 0
1 1 0

Output

Impossible

题解

折半搜索意图很明显，注意一下要求最大的，而且特判一下n==1的情况

先dfs前一半把所有可能达到的值记到一个set里（记的是查分，方便查找）
然后dfs后一半去set里查有没有对应的差分
最后找到答案了再重新dfs前一半把答案还原出来

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. int n;
  16. int l[35],m[35],w[35];
  17. struct node {
  18.     int l,m,w;
  19.     node() {}
  20.     node(int li,int mi,int wi) {
  21.         l=li;m=mi;w=wi;
  22.     }
  23.     bool operator < (const node &rhs) const {
  24.         if(l!=rhs.l) return l<rhs.l;
  25.         if(m!=rhs.m) return m<rhs.m;
  26.         if(w!=rhs.w) return w<rhs.w;
  27.         return false;
  28.     }
  29.     bool operator == (const node &rhs) const {
  30.         return l==rhs.l && m==rhs.m && w==rhs.w;
  31.     }
  32. }now;
  33. set<node> s;
  34. map<node,int> mmm;
  35. char ans[35][3],tmpans[35][3];
  36. int maxmum;
  37. node rec;
  38. bool dfs1(int dep,bool on,node cal) {
  39.     if(dep>n/2) {
  40.         if(on) {
  41.             if(cal==now) return 1;
  42.         }
  43.         else {
  44.             node k=node(0,now.m-now.l,now.w-now.m);
  45.             if(mmm.count(k)) {
  47.                 mmm[k]=max(mmm[k],now.l);
  48.             }
  49.             else {
  50.                 s.insert(k);
  51.                 mmm[k]=now.l;
  52.             }
  53.         }
  54.         return 0;
  55.     }
  56.     now.l+=l[dep];
  57.     now.m+=m[dep];
  58.     if(on) {ans[dep][0]='L';ans[dep][1]='M';}
  59.     if(dfs1(dep+1,on,cal)) return true;
  60.     now.l-=l[dep];
  61.     now.m-=m[dep];
  63.     now.l+=l[dep];
  64.     now.w+=w[dep];
  65.     if(on) {ans[dep][0]='L';ans[dep][1]='W';}
  66.     if(dfs1(dep+1,on,cal)) return true;
  67.     now.l-=l[dep];
  68.     now.w-=w[dep];
  70.     now.m+=m[dep];
  71.     now.w+=w[dep];
  72.     if(on) {ans[dep][0]='M';ans[dep][1]='W';}
  73.     if(dfs1(dep+1,on,cal)) return true;
  74.     now.m-=m[dep];
  75.     now.w-=w[dep];
  76.     return false;
  77. }
  78. bool dfs2(int dep) {
  79.     if(dep<=n/2) {
  80.         node k=node(0,-now.m+now.l,-now.w+now.m);
  81.         set<node>::iterator iter=s.lower_bound(k);
  82.         if(iter!=s.end() && (*iter)==k) {
  83.             if(mmm[k]+now.l>maxmum) {
  84.                 memcpy(ans,tmpans,sizeof(ans));
  85.                 maxmum=mmm[k]+now.l;
  86.                 rec.l=mmm[k];
  87.                 rec.m=rec.l+k.m;
  88.                 rec.w=rec.m+k.w;
  89.             }
  90.             return true;
  91.         }
  92.         return false;
  93.     }
  94.     bool res=0;
  95.     now.l+=l[dep];
  96.     now.m+=m[dep];
  97.     tmpans[dep][0]='L';tmpans[dep][1]='M';
  98.     if(dfs2(dep-1)) res=1;
  99.     now.l-=l[dep];
  100.     now.m-=m[dep];
  102.     now.l+=l[dep];
  103.     now.w+=w[dep];
  104.     tmpans[dep][0]='L';tmpans[dep][1]='W';
  105.     if(dfs2(dep-1)) res=1;
  106.     now.l-=l[dep];
  107.     now.w-=w[dep];
  109.     now.m+=m[dep];
  110.     now.w+=w[dep];
  111.     tmpans[dep][0]='M';tmpans[dep][1]='W';
  112.     if(dfs2(dep-1)) res=1;
  113.     now.m-=m[dep];
  114.     now.w-=w[dep];
  115.     return res;
  116. }
  117. int main() {
  118. #ifdef ivorysi
  119.     freopen("f1.in","r",stdin);
  120. #endif
  122.     scanf("%d",&n);
  123.     maxmum=-100000000;
  124.     siji(i,1,n) {
  125.         scanf("%d%d%d",&l[i],&m[i],&w[i]);
  126.     }
  127.     if(n==1) {
  128.         int cnt=0;
  129.         if(l[1]==0) ans[1][cnt++]='L';
  130.         if(m[1]==0) ans[1][cnt++]='M';
  131.         if(w[1]==0) ans[1][cnt++]='W';
  132.         if(cnt<2) puts("Impossible");
  133.         else {
  134.             printf("%c%c\n",ans[1][0],ans[1][1]);
  135.         }
  136.         return 0;
  137.     }
  138.     now=node(0,0,0);
  139.     dfs1(1,0,(node){0,0,0});
  140.     now=node(0,0,0);
  141.     if(!dfs2(n)) {
  142.         puts("Impossible");
  143.         return 0;
  144.     }
  145.     else {
  146.         now=node(0,0,0);
  147.         dfs1(1,1,rec);
  148.         siji(i,1,n) {
  149.             printf("%c%c\n",ans[i][0],ans[i][1]);
  150.         }
  151.     }
  152.     return 0;
  153. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注