由于不清楚来源，题目乱放：

　　Problem 1: Mirrors [Brian Dean and Travis Hance, 2013]

Farmer John's cows have been causing too much trouble around the farm, and

FJ therefore wants to keep a more watchful eye on them.  By installing N

reflective fences (1 <= N <= 200) at various locations on the farm, he

hopes to be able to see from his house at location (0,0) to the barn at

location (a,b).

On a 2D map of FJ's farm, fence i appears as a short line segment centered

at integer location (x_i, y_i) and tilted 45 degrees (either like '/' or

like '\').  For example, a fence oriented like '/' at position (3,5) could

be described as a line segment from (2.9,4.9) to (3.1,5.1).  Each fence

(and also the location of the barn) lies at a different position with

integer coordinates in the range -1,000,000...1,000,000.  No fence lies at

(0,0) or (a,b).

FJ plans to sit at his house at position (0,0) and look directly to the

right (in the +x direction).  With his gaze bouncing off some of the

reflective fences on his farm, he hopes to be able to see the point (a,b).

Unfortunately, FJ thinks he oriented one of his fences incorrectly (e.g.,

'\' instead of '/').  Please output the index of the first fence in FJ's

list such that by toggling its direction (between '/' and '\' or vice

versa), FJ will be able to see the point (a,b).  

If FJ can already see the point (a,b) without toggling any fence, please

output 0.  If it is still impossible for him to see (a,b) even after

toggling up to a single fence, output -1.

PROBLEM NAME: mirrors

INPUT FORMAT:

* Line 1: Three space-separated integers, N, a, and b.

* Lines 2..1+N: Line i+1 describes fence i and contains either "x_i

        y_i /" or "x_i y_i \", where (x_i, y_i) is the location of the

        center of the fence, and \ or / refers to its orientation.

SAMPLE INPUT (file mirrors.in):

5 6 2

3 0 /

0 2 /

1 2 /

3 2 \

1 3 \

INPUT DETAILS:

A map of the farm looks like this (with H denoting FJ's house and B

denoting the barn):

3 .\.....

2 //.\..B

1 .......

0 H../...

  0123456

OUTPUT FORMAT:

* Line 1: The index of the first fence for which toggling that fence

        allows FJ to see the point (a,b).  If FJ can already see the

        point (a,b), please output 0, or if there is no way he can see

        (a,b) even after toggling up to one fence, please output -1.

SAMPLE OUTPUT (file mirrors.out):

4

OUTPUT DETAILS:

By toggling the fence at position (3,2), FJ can see the point (a,b).  On

the map:

3 .\.....

2 //./--B

1 ...|...

0 H--/...

  0123456

　　Problem 2: Liars and Truth Tellers [Brian Dean, 2013]

After spending so much time around his cows, Farmer John has started to

understand their language.  Moreover, he notices that among his N cows

(2 <= N <= 1000), some always tell the truth while others always lie.

FJ carefully listens to M statements (1 <= M <= 10,000) from his cows, each

of the form "x y T", meaning that "cow x claims cow y always tells the

truth" or "x y L", meaning that "cow x claims cow y always tells lies".

Each statement involves a pair of different cows, and the same pair of cows

may appear in multiple statements.  

Unfortunately, FJ believes he might have written down some entries in his

list incorrectly, so there may not be a valid way to designate each cow as

a truth teller or a liar that is consistent with all the M statements on

FJ's list.  To help FJ salvage as much of his list as possible, please

compute the largest value of A such that there exists a valid way to

designate each cow as a truth teller or a liar in a manner that is

consistent with the first A entries in FJ's list.

PROBLEM NAME: truth

INPUT FORMAT:

* Line 1: Two space-separated integers, N and M.

* Lines 2..1+M: Each line is of the form "x y L" or "x y T",

        describing a statement made by cow x about cow y.

SAMPLE INPUT (file truth.in):

4 3

1 4 L

2 3 T

4 1 T

INPUT DETAILS:

There are 4 cows and 3 statements.  Cow 1 says that cow 4 lies, cow 2 says

that cow 3 tells the truth, and cow 4 says that cow 1 tells the truth.

OUTPUT FORMAT:

* Line 1: The maximum value of A such that the first A entries in FJ's

        list can be consistent with some assignment of "truth teller"

        or "liar" to the N cows.

SAMPLE OUTPUT (file truth.out):

2

OUTPUT DETAILS:

Statements 1 and 3 cannot both be satisfied at the same time, but

statements 1 and 2 can be, if we let cows 1..3 tell the truth and cow 4 be

a liar.

　　Problem 3: Painting the Fence [Brian Dean, 2012]

Farmer John has devised a brilliant method to paint the long fence next to

his barn (think of the fence as a one-dimensional number line).  He simply

attaches a paint brush to his favorite cow Bessie, and then retires to

drink a cold glass of water as Bessie walks back and forth across the

fence, applying paint to any segment of the fence that she walks past.

Bessie starts at position 0 on the fence and follows a sequence of N

moves (1 <= N <= 100,000).  Example moves might be "10 L", meaning

Bessie moves 10 units to the left, or "15 R", meaning Bessie moves 15

units to the right.  Given a list of all of Bessie's moves, FJ would

like to know what area of the fence gets painted with at least K coats

of paint.  Bessie will move at most 1,000,000,000 units away from the

origin during her walk.

PROBLEM NAME: paint

INPUT FORMAT:

* Line 1: Two space-separated integers: N and K.

* Lines 2..1+N: Each line describes one of Bessie's N moves (e.g., "15

        L").

SAMPLE INPUT (file paint.in):

6 2

2 R

6 L

1 R

8 L

1 R

2 R

INPUT DETAILS:

Bessie starts at position 0 and moves 2 units to the right, then 6 to the

left, 1 to the right, 8 to the left, and finally 3 to the right.  FJ wants

to know the area covered by at least 2 coats of paint.

OUTPUT FORMAT:

* Line 1: The total area covered by at least K coats of paint.

SAMPLE OUTPUT (file paint.out):

6

OUTPUT DETAILS:

6 units of area are covered by at least 2 coats of paint.  This includes

the intervals [-11,-8], [-4,-3], and [0,2].

             Problem 4: Square Overlap [Brian Dean, 2013]

Farmer John is planning to build N (2 <= N <= 50,000) square fenced-in

pastures on his farm, each of size exactly K x K (1 <= K <= 1,000,000).

Pasture i is centered at point (x_i, y_i) with integer coordinates in the

range -1,000,000...1,000,000.  However, in his haste to complete his plans,

FJ realizes that he may have accidentally placed two pastures in locations

that overlap (by overlap, this means the two pastures share a positive area

in common).  No two pastures share the exact same center point.

Given the locations of each of the planned square pastures, please help FJ

compute the area shared by the two overlapping pastures.  Output zero if no

two squares overlap, and -1 if overlap occurs between more than a single

pair of pastures.  

PROBLEM NAME: squares

INPUT FORMAT:

* Line 1: Two space-separated integers, N and K.  K is guaranteed to

        be even.

* Lines 2..1+N: Line i+1 contains the integers x_i and y_i, describing

        the center of the ith pasture.

SAMPLE INPUT (file squares.in):

4 6

0 0

8 4

-2 1

0 7

INPUT DETAILS:

There are 4 squares, each of size 6 x 6.  The first square is centered at

(0,0), and so on.

OUTPUT FORMAT:

* Line 1: The area shared by the two overlapping squares.  Output zero

        if no two squares overlap, and -1 if overlap occurs between

        more than a single pair of pastures.

SAMPLE OUTPUT (file squares.out):

20

OUTPUT DETAILS:

Pastures #1 and #3 overlap in 20 units of area.

          Problem 5: Party Invitations [Travis Hance, 2012]

Farmer John is throwing a party and wants to invite some of his cows to

show them how much he cares about his herd.  However, he also wants to

invite the smallest possible number of cows, remembering all too well the

disaster that resulted the last time he invited too many cows to a party.

Among FJ's cows, there are certain groups of friends that are hard to

separate.  For any such group (say, of size k), if FJ invites at least k-1

of the cows in the group to the party, then he must invite the final cow as

well, thereby including the entire group.  Groups can be of any size and

may even overlap with each-other, although no two groups contain exactly

the same set of members.  The sum of all group sizes is at most 250,000.

Given the groups among FJ's cows, please determine the minimum number of

cows FJ can invite to his party, if he decides that he must definitely

start by inviting cow #1 (his cows are conveniently numbered 1..N, with N

at most 1,000,000).

PROBLEM NAME: invite

INPUT FORMAT:

* Line 1: Two space-separated integers: N (the number of cows), and G

        (the number of groups).

* Lines 2..1+G: Each line describes a group of cows.  It starts with

        an integer giving the size S of the group, followed by the S

        cows in the group (each an integer in the range 1..N).

SAMPLE INPUT (file invite.in):

10 4

2 1 3

2 3 4

6 1 2 3 4 6 7

4 4 3 2 1

INPUT DETAILS:

There are 10 cows and 4 groups.  The first group contains cows 1 and 3, and

so on.

OUTPUT FORMAT:

* Line 1: The minimum number of cows FJ can invite to his party.

SAMPLE OUTPUT (file invite.out):

4

OUTPUT DETAILS:

In addition to cow #1, FJ must invite cow #3 (due to the first group

constraint), cow #4 (due to the second group constraint), and also cow #2

(due to the final group constraint).

 

题解：

A题：没看懂，就没做，听同学说改一个镜子就行了。。草草草。。英文太渣木有办法。。  （10%）

B题：并查集，“对手”并查集，不过我不知道怎么就WA了两个点。。如果有大神看到。。麻烦和我说下。。谢谢。。（80%）

C题：离散+前缀和直接搞   （100%）

D题：sb题。。O(n^2)的暴力。。优化就是如果有>两个的正方形就直接return            (100%)

E题：被卡了4个点QAQ。。显然是教师机太渣= =.. stl直接搞。。内置红黑树真流弊。。(100%)

Codes:

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 using namespace std; 10 const int N = 100010; 11 #define For(i,n) for(int i=1;i<=n;i++) 12 #define Rep(i,l,r) for(int i=l;i<=r;i++) 13 14 int n,m,x,y;char op; 15 int fa[N],enemy[N]; 16 17 int find(int i){ 18 if(fa[i]==i) return i; 19 else return find(fa[i]); 20 } 21 22 void merge(int x,int y){ 23 int fx = find(x) , fy = find(y); 24 fa[fx] = fy; 25 } 26 27 int main(){ 28 freopen("truth.in","r",stdin); 29 freopen("truth.out","w",stdout); 30 scanf("%d%d",&n,&m); 31 For(i,n) fa[i] = i; 32 For(i,m){ 33 scanf("\n"); 34 scanf("%d%d %c",&x,&y,&op); 35 int fx = find(x) , fy = find(y); 36 if(op=='L'){ 37 if(fx==fy) { 38 printf("%d\n",i-1); 39 return 0; 40 } 41 else{ 42 if(enemy[x]) merge(enemy[x],y); 43 if(enemy[y]) merge(enemy[y],x); 44 enemy[x] = y; enemy[y] = x; 45 } 46 }else{ 47 if(find(enemy[x])==find(y)||find(enemy[y])==find(x)){ 48 printf("%d\n",i-1); 49 return 0; 50 } 51 fa[fx] = fy; 52 } 53 } 54 printf("%d\n",m); 55 return 0; 56 } 57 -------------------------------------以上是B题--------------------------------- 58 #include
              
                59 #include
               
                 60 #include
                
                  61 #include
                 
                   62 #include
                  
                    63 #include
                   
                     64 #include
                    
                      65 #include
                     
                       66 using namespace std; 67 const int N = 100010; 68 #define For(i,n) for(int i=1;i<=n;i++) 69 #define Rep(i,l,r) for(int i=l;i<=r;i++) 70 71 struct points{ 72 int x; 73 int kind; 74 }; 75 76 bool cmp(points A,points B){ 77 return A.x
                      
                       1)&&Temp>=k) ans+=seg[i].x-seg[i-1].x;105 Temp += seg[i].kind;106 }107 cout<
                       
                        <
                        
                         117 #include
                         
                          118 #include
                          
                           119 #include
                           
                            120 #include
                            
                             121 #include
                             
                              122 #include
                              
                               123 #include
                               
                                124 using namespace std;125 const int N = 50100;126 typedef pair
                                
                                  points;127 #define x first128 #define y second129 #define For(i,n) for(int i=1;i<=n;i++)130 #define Rep(i,l,r) for(int i=l;i<=r;i++)131 points s[N];132 using namespace std;133 vector
                                 
                                   T[N];134 int n,k,Ans[N*100];135 long long ans,minx,miny,maxx,maxy;136 137 int main(){138 freopen("squares.in","r",stdin);139 freopen("squares.out","w",stdout);140 scanf("%d%d",&n,&k);141 For(i,n) scanf("%d%d",&s[i].x,&s[i].y);142 sort(s+1,s+n+1);143 For(i,n-1){144 Rep(j,i+1,n)145 if((s[i].x+k>s[j].x)&&(s[j].y+k>s[i].y)&&(s[j].y
                                  
                                    0) Ans[++Ans[0]] = i;150 if(T[i].size() > 1) Ans[++Ans[0]] = i;151 if(T[i].size() > 1) break;152 } 153 if(Ans[0] > 1) {154 printf("%d\n",-1);155 return 0;156 }157 else if(Ans[0]==1){158 int id = Ans[Ans[0]];159 int a = id , b = T[id].back();160 minx = max(s[a].x,s[b].x); miny = max(s[a].y,s[b].y);161 maxx = min(s[a].x+k,s[b].x+k); maxy = min(s[a].y+k,s[b].y+k);162 ans = (maxx-minx) * (maxy-miny);163 }164 cout<
                                   
                                    <
                                    
                                     169 #include
                                     
                                      170 #include
                                      
                                       171 #include
                                       
                                        172 #include
                                        
                                         173 #include
                                         
                                          174 #include
                                          
                                           175 #include
                                           
                                            176 using namespace std;177 const int N = 1000010;178 #define For(i,n) for(int i=1;i<=n;i++)179 #define Rep(i,l,r) for(int i=l;i<=r;i++)180 181 bool inv[N]={ false,true};182 int n,q,ans,tot,k;183 vector< set
                                            
                                              > G;184 vector
                                             
                                               A[N];queue
                                              
                                                Q;185 set
                                               
                                                 small;186 187 int read(){188 int num = 0;189 char ch = getchar();190 while(ch>'9'||ch<'0') ch = getchar();191 while(ch>='0'&&ch<='9'){192 num = num * 10 + ch - '0';193 ch = getchar();194 } 195 return num;196 }197 198 void init(){199 n = read(); q = read();200 Q.push(1);201 For(i,q){ 202 small.clear();203 tot = read();204 For(j,tot){205 k = read();206 small.insert(k);A[k].push_back(i);207 }208 G.push_back(small);209 }210 }211 212 void Work(){213 while (!Q.empty()){214 int Front=Q.front();215 Q.pop();ans++;216 Rep(j,0,A[Front].size()-1){217 int x=A[Front][j];218 G[x-1].erase(Front);219 if (G[x-1].size()==1){220 set
                                                
                                                 ::iterator top = G[x-1].begin();221 if (!inv[*top]){222 inv[*top]=true;Q.push(*top);223 }224 }225 }226 }227 printf("%d\n",ans);228 }229 230 int main(){231 freopen("invite.in","r",stdin);232 freopen("invite.out","w",stdout);233 init();234 Work();235 }236 ------------------------------------以上是E题-----------------------------------
                                                
                                               
                                              
                                             
                                            
                                           
                                          
                                         
                                        
                                       
                                      
                                     
                                    
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

A题等会儿补上。。