Problem A: An easy problem

Description

 

Peter Manson owned a small house in an obscure street. It was a weather-beaten tenement of wood, containing some six or eight rooms, all of which, with one exception, were given over to dirt, cobwebs, gloom, and desolation. Peter might readily have let the rooms which he did not require for his own use, but so profound was his distrust of human nature, that not even the prospect of receiving rent for the empty rooms could overcome his apprehension of being robbed by neighbors under the same roof. For Peter trusted not his money to banks or railroads, but wanted to have it directly under his own eye or within his reach. As for investing his gold in the luxuries of life, or even in what were generally considered its absolute necessaries, we have already seen that Peter was no such fool as that. A gold eagle was worth ten times more to him than its equivalent in food or clothing.

    With more than his usual alacrity, old Peter Manson, bearing under his cloak the fresh loaf which he had just procured from the baker on such advantageous terms, hastened to his not very inviting home.

    Drawing from his pocket a large and rusty door-key, he applied it to the door. It turned in the lock with a creaking sound, and the door yielding to Peter’s push he entered.

The room which he appropriated to his own use was in the second story. It was a large room, of some eighteen feet square, and, as it is hardly necessary to say, Was not set off by expensive furniture. The articles which came under this denomination were briefly these — a cherry table which was minus one leg, whose place had been supplied by a broom handle fitted in its place; three hard wooden chairs of unknown antiquity; an old wash-stand; a rusty stove which Peter had picked up cheap at an auction, after finding that a stove burned out less fuel than a fireplace; a few articles of crockery of different[18] patterns, some cracked and broken; a few tin dishes, such as Peter found essential in his cooking; and a low truckle bedstead with a scanty supply of bedclothes.

Are you tired of reading this long passage? Now,I’m giving you a task which is nothing to do with the passage. Ahhh ~Please sort this string “cpteca”,make the first letter be upper-letter.

 

Input

 

Output

 

Sample Input

 

Sample Output

 

HINT

Title links: gdutcode.sinaapp.com/problem.php…

(⊙ O ⊙)… A does not capitalize people do not know what mentality

Here is the AC code:

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #include <iostream> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <set> 10 #include <stack> 11 #include <map> 12 using namespace std; 13 int main() 14 { 15 puts("Accept"); 16 return 0; 17}Copy the code

Problem B: Tmk eats soup and rice

Description

 

It was cold some time ago, so TMK liked to eat soup and rice.

As we all know, the soup and rice on the second floor of the third meal point and take two Windows, a shu shu is responsible for ordering window, a shu shu is responsible for cooking soup, a shu shu is responsible for cooking, ordering takes 1 minute, each need to cook 5 minutes, at the same time can cook up to 4.

One day, TMK came to the second floor of three meals, found no one to take soup rice window, but the ordering window is full of people, the original selling soup rice shu just began to work, TMK bored the number of queue, just N people.

Tmk would like to know how long it will take to get the soup and rice if they are at the end of the line at this time. Because of the high quality of the students in GUANGDONG University of Technology, no one will jump the queue, of course, Tmk will not jump the queue, and they are determined, so they will not fail halfway.

Now, assuming that everything except ordering and cooking time is ignored, TMK wants you to figure out how long he has to wait to get his soup and rice.

Input

 

The first line has a T(0<T<=10000), indicating how many groups of data there are.

Then each line has a N (0<=n<=10000), indicating the number of people in the queue at the ordering window when TMK arrives at the second floor of sanfan.

Output

 

For each n, output an integer to indicate how long it takes TMK to fetch soup and rice.

Sample Input

2

0

4

Sample Output

6

11

HINT

Title links: gdutcode.sinaapp.com/problem.php…

Analysis: a very regular sequence, I did not push the formula but directly hit the table… The formula is n over 4 plus 1 times 5 plus n%4 plus 1.

Here is the AC code:

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #include <iostream> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <set> 10 #include <stack> 11 #include <map> 12 using namespace std; 13 const int maxn = 10050; 14 int a[maxn]; 15 int main() 16 { 17 a[0] = 6; 18 for(int i=1; i<maxn; i++) 19 { 20 a[i] = a[i-1]+1; 21 if(i%4==0) 22 a[i]++; 23 } 24 int t; 25 scanf("%d",&t); 26 while(t--) 27 { 28 int n; 29 scanf("%d",&n); 30 printf("%d\n",a[n]); 31 } 32 return 0; 33}Copy the code

Problem C: The attacking investigative corps

Description

 

Since Wall.Rose was once again captured by the Iron Giant, the anthroposphere has only Wall.Sina as its last line of defense. Commander finally according to bear, decided to issue general Sanli directly from 105 and 106 training corps called a group of graduates into the investigation corps of the giant counterattack.

There are N graduates in class 105 and M graduates in class 106. In order to facilitate general Mikasin’s selection, the instructors of both regiments submitted the graduation grades of their current graduates, ranked in order of grade from junior to senior. That is, the grade of the 105 I graduates with A small grade is A[I], and the grade of the 106 J graduates with A small grade is B[j], satisfying A[0]<A[1]<… < < A [N – 2] A [N – 1], [1] [0] < B < B… B [M – 2] < B [M – 1]. And in order to reflect the differences of previous graduates, to ensure A[I]! = B[j]{0<=i<N, 0<=j<m}.

Now General Mikasin is picking Q out of A’s and B’s. In each selection, the graduate with the KTH lowest grade is chosen from A[L1..R1] and B[L2..R2]. Samin’s picks are purely for fun, so it’s possible that there are duplicates in those Q picks.

In order to expedite the selection of counterattack personnel, the commander has decided to send you to the list of personnel as soon as possible.

 

Input

 

Enter an integer T on the first line to indicate that there are T groups of data, for each group of data

The first line contains 3 integers, the number of 105 graduates N(<=10^5), the number of 106 graduates M(<=10^5), and the number of picks of the three hats Q(<=10^4).

The second line contains N integers A[I](0<=A[I]<2^31),

The third line contains M integers B[I](0<=B[I]<2^31).

4.. Q + 3 lines, each line has five integers, L1, R1, L2, R2, k (0 < = L1 < = R1 < N, 0 < = L2 < = R2 < M, 1 < = k < = R1 – L1 + L2 + R2 2).

Output

 

For each pick, output an integer representing the KTH smallest result in A[L1..R1] and B[L2..R2].

Sample Input

1

5 5 4

One, three, five, seven, eight

2, 4, 6, 9, 10

0, 4, 0, 4, 7

3, 4, 1, 3, 2

2, 2, 1, 1, 1

0, 3, 0, 3, 6

Sample Output

7

6

4

6

HINT

Title links: gdutcode.sinaapp.com/problem.php…

Analysis:

The binary answer, the binary answer comes out and you look at the binary answer and find out how many are less than or equal to it in each sequence, and the STL is a good thing

Here is the AC code:

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #include <iostream> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <set> 10 #include <stack> 11 #include <map> 12 using namespace std; 13 const int maxn = 1e5+100; 14 int a[maxn]; 15 int b[maxn]; 16 int main() 17 { 18 int t; 19 scanf("%d",&t); 20 while(t--) 21 { 22 int n,m,q; 23 scanf("%d %d %d",&n,&m,&q); 24 for(int i=0; i<n; i++) 25 scanf("%d",&a[i]); 26 for(int i=0; i<m; i++) 27 scanf("%d",&b[i]); 28 while(q--) 29 { 30 int l1,r1,l2,r2,k; 31 scanf("%d %d %d %d %d",&l1,&r1,&l2,&r2,&k); 32 int l = min(a[l1],b[l2]),r = max(a[r1],b[r2]); 33 while(l<r) 34 { 35 int mid = l+((r-l)/2); 36 int pos1 = lower_bound(a+l1,a+r1+1,mid)-a; 37 if(a[pos1]==mid) 38 pos1++; 39 int pos2 = lower_bound(b+l2,b+r2+1,mid)-b; 40 if(b[pos2]==mid) 41 pos2++; 42 if(pos1+pos2<k+l1+l2) 43 l = mid+1; 44 else 45 r = mid; 46 } 47 printf("%d\n",l); 48 } 49 } 50 return 0; 51}Copy the code

Problem D: Aerial image of TMK

Description

This is too bad, TMK he actually got a chance to play with the drone, TMK excited like a child, with the drone to play.

So TMK’s drone went up and flew very high, but the weather was fine today, and the aerial shot of the drone was very clear. TMK flew his drone as high as he could, took a picture from God’s perspective, and ended his young drone career.

TMK found that in this photo, all the buildings turned into points, which could be described as points on a two-dimensional plane, and some points would be on the same straight line. Therefore, TMK wanted to figure out how many different straight lines could be drawn on this photo so that the lines would pass through at least two points. TMK threw the problem at Maple, and Maple threw the problem at YFQQ. Now, YFQQ throws the question at you.

Input

 

The first line has an integer T, representing T sets of data (1<=T<=50)

Each set of data starts with an integer n, indicating that there are n two-dimensional coordinate points on the photo (0<=n<=200)

The next n rows, each with two integers x and y, represent the coordinates of the points, ensuring that the points do not overlap (-10000<=x,y<=10000)

Output

 

Each set of data outputs an integer number of different lines

Sample Input

1

4

1 1

2 1

3 1

2 2

Sample Output

4

HINT

Title links: gdutcode.sinaapp.com/problem.php…

Analysis:

There’s no point, so all possible line segments are n times n minus 1 over 2, and since we’re asking for a line, let’s enumerate the two points, see if they intersect with other points and if they intersect with ans —

Here is the AC code:

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #include <iostream> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <set> 10 #include <stack> 11 #include <map> 12 using namespace std; 13 const int maxn = 2e5+10; 14 struct point 15 { 16 int x,y; 17 }a[maxn]; 18 int n,m; 19 int x_mul(point p0,point p1,point p2) 20 { 21 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); 22 } 23 int main() 24 { 25 //freopen("a.in","r",stdin); 26 int t; 27 scanf("%d",&t); 28 while(t--) 29 { 30 int n; 31 scanf("%d",&n); 32 for(int i=0; i<n; i++) 33 scanf("%d %d",&a[i].x,&a[i].y); 34 int ans = n*(n-1)/2; 35 for(int i=0; i<n; i++) 36 { 37 for(int j=i+1; j<n; j++) 38 { 39 for(int k=0; k<n; k++) 40 { 41 if(k>=i && k<=j) 42 continue; 43 if(x_mul(a[k],a[i],a[j])==0) 44 ans--; 45 } 46 } 47 } 48 printf("%d\n",ans); 49 } 50 return 0; 51}Copy the code

Problem E: Go the long way around

Description

 

TMK he was late again, although YFQQ has been used to it, but Maple still resolutely ran to the laboratory to walk back to the dormitory.

Maple came downstairs and decided to walk just long enough to get back to the dormitory. Maple numbers the n points he can walk from 1 to n, where the lab is at point 1 and the dorm is at point N. These n points are connected by m two-way roads.

Maple states that when he reaches a certain point, he will not go to any point less numbered than that point, but when he chooses a path, he will go straight down that path until he reaches the end of that path. There are some paths that are connected to themselves from one point, which means that Maple can start at that point and go around and come back, and there might be several different paths at two o ‘clock. Maple wants to walk these roads until he gets to the dorm, and when he gets to the dorm, he stops right away. However, because of Maple’s physical limitations, the total length of his walk cannot exceed K, or he will be exhausted to death.

Now given the points where these two-way paths connect and its length, we’re asking how long Maple can walk from the lab to the dormitory without tiring himself to death.

Input

 

The first line is an integer T, representing T sets of data (1<=T<=20).

Each set of data starts with three integers n,m,k, which means there are n points and m paths, and the maximum length Maple can take is K

Then there are m rows, each of which is three integers u,v,l, representing a two-way path from point u to point v, length L

(2 < = n < = 2000, 0 < = m < = 3000, 1 < = k < = 3000) (1 < = u, v < = n, 1 < = m < = 6000)

Output

 

Each set of data outputs an integer, which is what they want.

If Maple can’t get back to the dormitory or is bound to die before returning to the dormitory, then output -1.

Sample Input

2

5 6 7

1 2 1

3 2 2

5 1

3, 4, 4

4, 5, 4

1 4 2

3 3, 999

1, 2, 4

2 2 10

2, 3, 3

Sample Output

6

997

HINT

Title links: gdutcode.sinaapp.com/problem.php…

Analysis:

Dp, dp [I] [n] said to point I of length n is feasible, the equation of state for: dp/TMP) v (tt) | = dp [I] [tt – TMP. W], TMP. Between v and I have a length of TMP. W

Here is the AC code:

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #include <iostream> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <set> 10 #include <stack> 11 #include <map> 12 using namespace std; 13 const int maxn = 5000+40; 14 struct node 15 { 16 int v,w; 17 node() {} 18 node(int _v,int _w) 19 { 20 v = _v; 21 w = _w; 22}}; 24 vector<node>G1[maxn],G2[maxn]; 25 int dp[maxn][maxn]; 26 int main() 27 { 28 int t; 29 scanf("%d",&t); 30 while(t--) 31 { 32 memset(dp,0,sizeof(dp)); 33 int n,m,k; 34 scanf("%d %d %d",&n,&m,&k); 35 for(int i=1; i<=n; i++) 36 G1[i].clear(),G2[i].clear(); 37 while(m--) 38 { 39 int u,v,l; 40 scanf("%d %d %d",&u,&v,&l); 41 if(u! =v) 42 { 43 if(u>v) 44 swap(u,v); 45 G1[u].push_back(node(v,l)); 46 } 47 else 48 G2[u].push_back(node(v,l)); 49 } 50 dp[1][0] = 1; 51 for(int i=1; i<=n; i++) 52 { 53 for(unsigned j=0; j<G2[i].size(); j++) 54 { 55 node tmp = G2[i][j]; 56 for(int tt=tmp.w; tt<=k; tt++) 57 dp[i][tt] |= dp[i][tt-tmp.w]; 58 } 59 for(unsigned j=0; j<G1[i].size(); j++) 60 { 61 node tmp = G1[i][j]; 62 for(int tt=tmp.w; tt<=k; tt++) 63 dp[tmp.v][tt] |= dp[i][tt-tmp.w]; 64 } 65 } 66 int ans = -1; 67 for(int i=0; i<=k; i++) 68 { 69 if(dp[n][i]) 70 ans = i; 71 } 72 printf("%d\n",ans); 73 } 74 return 0; 75}Copy the code

Problem F: Password lock

Description

 

TMK heard that yellow bikes can pack semester, so excited to pack yellow bikes, in order to earn back this, so TMK ride every day.

Recently, yellow car has a new lock. Every time you unlock the lock, you need to rotate the number to the corresponding password position (each position is a cycle of 0~9, the next digit of 9 is 0, which can be turned down or against). For example, if the original number is “1234” and the password is “5678”, then the sum of the number of cells moved in each circle is at least 4+4+4=16 times. Because TMK is smarter, TMK minimizes the total number of squares moved in each turn.

TMK’s memory is also very good. He has memorized the passwords and original numbers of all the yellow bikes he has ridden during this period. He wants to know how many squares he has turned, but TMK is lazy, so this arduous task is handed over to you.

Input

 

The first line is an integer T(0<T<=100), which indicates how many groups of data there are.

The first line of each set of data is an integer n(0<=n<=100), indicating how many times TMK has recently ridden the yellow bike.

Then n times of cycling data:

Ai, Bi, Ci, Di are separated by Spaces to indicate the password of the password lock.

Ai, BI, CI, di are separated by Spaces to indicate the original number of the password lock.

Where 0<= Ai, Bi, Ci, Di, Ai, Bi, Ci, Di <=9, and are integers

Output

 

For each set of data, a number is printed that indicates how many squares the TMK has turned in total.

Sample Input

1

1

3 6 5 3

4 9th September 5

Sample Output

12

HINT

Title links: gdutcode.sinaapp.com/problem.php…

Analysis:

Min ((AI-AI +10)%10,(AI-AI +10)%10)

Here is the AC code:

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #include <iostream> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <set> 10 #include <stack> 11 #include <map> 12 using namespace std; 13 const int maxn = 10050; 14 int a[maxn]; 15 int main() 16 { 17 int t; 18 scanf("%d",&t); 19 while(t--) 20 { 21 int n; 22 scanf("%d",&n); 23 int ans = 0; 24 while(n--) 25 { 26 int a1,b1,c1,d1; 27 int a2,b2,c2,d2; 28 scanf("%d %d %d %d",&a1,&b1,&c1,&d1); 29 scanf("%d %d %d %d",&a2,&b2,&c2,&d2); 30 ans += min((a1-a2+10)%10,(a2-a1+10)%10); 31 ans += min((b1-b2+10)%10,(b2-b1+10)%10); 32 ans += min((c1-c2+10)%10,(c2-c1+10)%10); 33 ans += min((d1-d2+10)%10,(d2-d1+10)%10); 34 } 35 printf("%d\n",ans); 36 } 37 return 0; 38}Copy the code

Problem G: Knowledge comes from decomposition

Description

 

There’s something moving around. I looked down and saw a small white creature, standing on its hind legs and sniffing my torso. It caught my attention.

What are you for?

I analyze the creature. A magenta thermal beam flashed past, raising dust where it had quivered.

Mammals… Nocturnal habits… Impeccable hearing. Incredibly weak. But their reproductive capacity is so strong.

“Well,” I muttered to myself. In the hope of finding more complex objects; I was fascinated by those things.

Digest and learn: this is my purpose. The other visitors I traveled with were primitive: kill and eat, kill and eat. I need to gather all the information available — to harvest more valuable resources.

Finally, we came across a ruined city, with only one primitive tower still intact. The tower seems to be protected… Or they left it there on purpose. I deconstructed the composition of the ruins. My analysis indicates that this region was once a powerful magical kingdom; I’m not surprised that such a destructive force would target it. There’s something interested in this tower. I entered the castle while other visitors were scattered about.

Mysterious instruments are scattered everywhere. I tested one. Another magenta thermal beam flashes by, and the dust rises again.

Time machine… Starting requires solving puzzles… Oh, my God. I need to take a closer look.

“Given a string s of length n, and integer k, Return the length of the longest substring that contains exactly k distinct characters.”

T group data… String contains only upper and lower case letters… Can’t find return 0. This problem successfully attracted me.

Input

 

 

Enter an integer T on the first line to indicate that there are T groups of data,

 

Next T lines, each line is a string s and an integer k(T<=666, length(s)<=10^6, 0=<k<=52)

 

 

 

Output

For each set of data, output an answer.

Sample Input

3

abcd 2

aaabbbcc 2

aa 3

Sample Output

2

6

0

HINT

Title links: gdutcode.sinaapp.com/problem.php…

Analysis: ruler take maintenance answer

Here is the AC code:

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #include <iostream> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <set> 10 #include <stack> 11 #include <map> 12 using namespace std; 13 const int maxn = 1e6+10; 14 char a[maxn]; 15 int vis[100]; 16 int main() 17 { 18 int t; 19 cin>>t; 20 while(t--) 21 { 22 int n,k; 23 scanf("%s %d",a,&k); 24 n = strlen(a); 25 int ans = 0; 26 int l = 0,r = 0,cnt = 0; 27 memset(vis,0,sizeof(vis)); 28 while(n-l>ans) 29 { 30 while(r<n) 31 { 32 if(vis[a[r]-'A']) 33 vis[a[r]-'A']++; 34 else 35 { 36 if(cnt+1>k) 37 break; 38 else 39 cnt++; 40 vis[a[r]-'A']++; 41 } 42 r++; 43 } 44 if(cnt == k) 45 ans = max(ans,r-l); 46 vis[a[l]-'A']--; 47 if(vis[a[l]-'A']==0) 48 cnt--; 49 l++; 50 } 51 printf("%d\n",ans); 52 } 53 return 0; 54}Copy the code

Problem H: Find the square

Description

 

In a character map, can you find squares surrounded by #? If YES, print NO. (The square does not need to be filled with # inside, the area should be at least 4, and the map size should not exceed 20*20)

Legal Situation 1:

# # # #

# # $$

# $# #

# # # #

Legal Situation 2:

# # # #

# # $$

$$$$

$$$$

Legal Situation 3

# # # #

# # $$

# # $$

# # # #

Illegality

# # # #

# # $$

# $$$

# # # #

Input

 

The first line is an integer T, which tells you how many sets of data there are

For each set of data:

The first line is two integers n, where m represents the map size n rows and m columns (0<n,m<=20).

Output

 

If found, print “YES” (without quotes), otherwise print “NO” (without quotes)

Sample Input

2

4 4

# # # #

# # $$

# $# #

# # # #

4 4

# # # #

# # $$

# $$$

# # # #

Sample Output

YES

NO

HINT

Title links: gdutcode.sinaapp.com/problem.php…

Analysis: find a point ‘#’, enumerate the square length, determine whether it is valid

Here is the AC code:

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #include <iostream> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <set> 10 #include <stack> 11 #include <map> 12 using namespace std; 13 const int maxn = 1e6+10; 14 char a[25][25]; 15 bool slove(int x,int y,int n) 16 { 17 for(int i=x; i<=x+n; i++) 18 { 19 if(a[i][y]! ='#') 20 return false; 21 if(a[i][y+n]! ='#') 22 return false; 23 } 24 for(int i=y; i<=y+n; i++) 25 { 26 if(a[x][i]! ='#') 27 return false; 28 if(a[x+n][i]! ='#') 29 return false; 30 } 31 return true; 32 } 33 int main() 34 { 35 int t; 36 scanf("%d",&t); 37 while(t--) 38 { 39 int n,m; 40 scanf("%d %d",&n,&m); 41 for(int i=0; i<n; i++) 42 scanf("%s",a[i]); 43 int flag = 0; 44 for(int i=0; i<n; i++) 45 { 46 for(int j=0; j<m; j++) 47 { 48 if(a[i][j]=='#') 49 { 50 for(int k=1; k<=n-1-i; k++) 51 { 52 if(i+k>=n || j+k>=n) 53 break; 54 if(slove(i,j,k)) 55 flag = 1; 56 } 57 } 58 } 59 } 60 if(flag) 61 puts("YES"); 62 else 63 puts("NO"); 64 } 65 return 0; 66}Copy the code