7454 Parentheses
A bracket is a punctuation mark, which is used in matched pairs, usually used within articles or programs. Brackets include round brackets, square brackets, curly brackets, angle brackets, and various other pairs of symbols. Let’s focus on the round brackets, also called parentheses. A sequence of parentheses is said to be well-formed if the parentheses are properly nested. For example, A = a1a2 . . . a18 = “(()())()()()(())()” is well-formed, but B = b1b2 . . . b18 = “(()())))(((((())((” is not. (See Figure 1.) More formally, a sequence of parentheses P = p1p2 . . . pn is well-formed
if (1) when scanning it from p1 to pn, the number of right parentheses does not exceed the number of left parentheses at any state, and
(2) the numbers of left and right parentheses are equal.
Figure 1. Two sequences of parentheses.AutoText is a company, which is developing a text editor for programmers. The new editor willprovide many powerful functions to automatically correct typing errors. On a keyboard, the left andright parentheses are adjacent. Thus, it is often that “)” is mistyped as “(” or vice versa. And therefore,one of the functions AutoText wants to provide is to automatically convert a sequence of parenthesesP(that may not be well-formed) into a wellformed sequenceP′. In the conversion, the only allowedoperation is to reverse a parenthesis (i.e., either to replace a “(” with a “)” or to replace a “)” witha “(”). For example, in Figure 1, we can convertBinto the well-formed sequenceAby performing 4reverse operations onb7,b10,b12,b18. Of course, there may be several ways to convert a sequence intoa well-formed sequence. A conversion is optimal if it uses the minimum number of reverse operations.Please write a program to compute the minimum number of reverse operations that make a givensequence of parenthesesP=p1p2:::pnwell-formed.InputThe first line contains an integerT10indicating the number of test cases. The first line of each testcase contains an even integern,2n100, indicating the length ofP. Next, the second line givesthe sequenceP.
Output
For each test case, output the minimum number of reverse operations that makePwell-formed.
Sample Input
3
18
(()())))(((((())((
2
()
8
(()))()(
Sample Output
4
題目意思：對于給出的一系列括号，設計一個AutoText，使得能夠自動完成括号比對，問最少需要轉變多少個括号，左括号和右括号可以互相轉變。
解題思路：之前經常做這種括号比對的題目，使用棧先将能夠比對的處理掉，之後棧内不能比對的兩個處理，使其能夠比對即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
stack<char>s;
int main()
{
int t,n,ans;
int x,y;
char c;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
getchar();
ans=0;
while(!s.empty())///清空棧
{
s.pop();
}
while(n--)
{
scanf("%c",&c);
if(c=='(')
{
s.push(c);
}
else if(c==')')
{
if(!s.empty()&&s.top()=='(')///已經比對出棧
{
s.pop();
}
else
{
s.push(c);
}
}
}
x=0;
y=0;
ans=0;
while(!s.empty())
{
if(s.top()=='(')
{
x++;
}
else if(s.top()==')')
{
y++;
}
if(x==1&&y==1)///出現')('的情況
{
x--;
y--;
ans=ans+2;///兩個同時翻轉
}
else if(x==2)///出現'(('的情況
{
x=x-2;
ans++;///翻轉一個
}
else if(y==2)///出現'))'的情況
{
y=y-2;
ans++;///翻轉一個
}
s.pop();
}
printf("%d\n",ans);
}
return 0;
} 7457Discrete Logarithm Problem
題目意思：求一個x使得 a^x%p = b 。
解題思路：開始一看這種表達式，第一反應是快速幂算法，但後來發現資料的規模并不是很大，是以可以直接暴力枚舉，同時發現而取模的結果一定在p次以内出現循環，是以直接從0~p枚舉x即可。
#include<cstdio>
#include<cstring>
#define ll long long int
#define maxs 102400
using namespace std;
/*ll fast_pow(ll a,ll x,ll p)
{
ll ans=1;
a=a%p;
while(x!=0)
{
if(x&1)
{
ans=(ans*a)%p;
}
x>>=1;
a=(a*a)%p;
}
return ans%p;
}*/
//快速幂
int main()
{
ll a,b,p,ans,i;
int flag;
scanf("%lld",&p);
while(scanf("%lld",&a)!=EOF)
{
if(a==0)
{
break;
}
scanf("%lld",&b);
ans=a;
flag=0;
for(i=2;i<p;i++)
{
ans=(ans*a)%p;
if(ans==b)
{
flag=1;
break;
}
}
if(flag)
{
printf("%d\n",i);
}
else
{
printf("0\n");
}
}
return 0;
} 7464Robots
Write a program to collect data from robots. We are given two sets of robotsX=fX1;:::;Xmg,Y=fY1;:::;Yng, and a baseB. Each robot has a data and we would like to compute the sum of datafrom all robots and deliver it to the base. In order to do so a robot can send its data to another robotor the base with the following constraints.
•A robot can only send its data to one destination (a robot or the base) at a time.
•A robot (or the base) can receive data from one robot at a time.
•The base can not send data to anyone.
•A robot inXcan complete sending its data in x seconds.A robot in Y can complete sending its data in y seconds.
The robots and the base can perform addition, so we can collect the final sum at the base. Thatis, we assume that after receiving a data, a robot or the base can perform an addition with zero time.Now let us illustrate this concept by an example. Let us consider a system with one robotX1inXand two robotsY1andY2inY. We also assume thatxis 1 andyis 10. At the beginningY1can sendits data toY2andX1can send its data to the base. After 1 second the base will know the data ofX1.However, only after 10 secondsY2will have the data ofY1, add its own data, and send the sum to thebase. After 20 seconds the base receives the sum of data fromY1andY2, adds the data fromX1, andhas the final sum. The entire summation will take 20 seconds.Now let us try a different schedule. At beginningY1sends data to the base, andY2sends data toX1, and both can complete after 10 seconds. Finally X1 starts sending the sum of data from Y2 anditself to the base after 10 seconds, and the entire summation can finish in 11 seconds.Now givenm,n(the numbers of robots in X and Y),x, andy, please determine the minimumnumber of seconds to finish the summation.Constraints•1x<y1000.•0m<1200.•0n<500.
Input
The input consists of multiple test cases. First line contains a single integertindicating the number oftest cases to follow. Each of the nexttlines contains four integers —x,y,m,n.
For each test case, output on a single line the minimum number of seconds to sum up all numbers fromall robots.
11 10 1 2
11
題目意思：有x,y兩種類型的機器人各n個和m個，還有一個基地B,x型的機器人将其貨物運到基地或其他機器人上需要x秒，y型的機器人将其貨物運到基地或其他機器人上需要y秒，同一時刻每個機器人隻能發送給一個對象，也隻能接受一個對象的貨物，基地在同一時刻也隻能接受一個機器人的貨物，問你如何搭配才能花費最短的時間将所有的貨物運送到基地。
解題思路：我剛開始按照那個樣例一直想模拟整個運送過程，但發現還是太麻煩，因為裡面有很多種情況的判斷，那麼我們可以從整體的角度出發，需要最少的時間肯定不能是一個個機器人排隊去送貨物到基地，必然是将一些耗時大的機器人身上的貨物送到耗時少的身上，通過哪些耗時少的來運送。這其實就是第一步，将耗時多的機器人身上的貨物盡可能的向耗時少的機器人身上送，這個時間段中可以選擇一個耗時多的機器人送貨到基地，之後耗時多的機器人不管有沒有剩餘，和耗時少的機器人隻要在條件限定内組合時間就像是左手倒右手，時間是一定的，也就是說我們隻能省出一個耗時長的機器人的時間。
作者：王陸