首页 > 代码库 > USACO2013January（乱做）
USACO2013January（乱做）
由于不清楚来源，题目乱放：
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<set> 2 #include<queue> 3 #include<vector> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<iostream> 8 #include<algorithm> 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<set> 59 #include<queue> 60 #include<vector> 61 #include<cstdio> 62 #include<cstring> 63 #include<cstdlib> 64 #include<iostream> 65 #include<algorithm> 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<B.x; 78 } 79 80 points seg[2*N]; 81 int n,k,Temp,tx,cur; 82 char op; 83 long long ans; 84 85 void init(){ 86 freopen("paint.in","r",stdin); 87 freopen("paint.out","w",stdout); 88 scanf("%d%d", &n,&k); 89 For(i,n){ 90 int dist; 91 scanf("\n"); 92 scanf("%d %c", &dist,&op); 93 if(op==‘L‘) tx = cur - dist; 94 else tx = cur + dist; 95 seg[2*i-1].x = min(cur, tx); seg[2*i-1].kind = 1; 96 seg[2*i].x = max(cur, tx); seg[2*i].kind = -1; 97 cur = tx; 98 } 99 }100 101 void work(){102 sort(seg+1,seg+2*n+1,cmp);103 For(i,2*n){104 if ((i>1)&&Temp>=k) ans+=seg[i].x-seg[i-1].x;105 Temp += seg[i].kind;106 }107 cout<<ans<<endl;108 }109 110 int main() {111 init();112 work();113 return 0;114 }115 ---------------------------------------以上是C题-------------------------------116 #include<set>117 #include<queue>118 #include<vector>119 #include<cstdio>120 #include<cstring>121 #include<cstdlib>122 #include<iostream>123 #include<algorithm>124 using namespace std;125 const int N = 50100;126 typedef pair<int,int> 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<int> 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<s[i].y+k)){146 T[i].push_back(j);147 }148 else if(s[i].x + k <= s[j].x && s[i].y + k <= s[j].y) break;149 if(T[i].size() > 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<<ans<<endl;165 return 0;166 }167 ------------------------------------以上是D题----------------------------------168 #include<set>169 #include<queue>170 #include<vector>171 #include<cstdio>172 #include<cstring>173 #include<cstdlib>174 #include<iostream>175 #include<algorithm>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<int> > G;184 vector<int> A[N];queue<int> Q;185 set<int> 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<int>::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题等会儿补上。。
USACO2013January（乱做）