发布时间: 2017年2月21日 20:05 最后更新: 2017年2月21日 20:06 时间限制: 1000ms 内存限制: 128M
描述
传说喵哈哈村有三种神奇的魔法石:第一种魔法石叫做人铁石,拥有A的能量;第二种魔法石叫做地冈石,拥有B的能量;而第三种,则是最神奇的天玄石,拥有无可比拟的C的能量!
但是有一天,沈宝宝太调皮了,把一颗天玄石玩丢了……
“这可玩大发了,这样我会被天行廖责备的。”沈宝宝悲伤的说到,“怎么办呢?”
这时候沈宝宝望了望窗外的飞过的白鸽,突然急中生智,想到了一个办法:干脆就用人铁石和地冈石把天玄石凑出来吧!
“只要我拿若干个人铁石,若干个地冈石,他们的能量之和,恰好加起来等于天玄石所拥有的能量。然后再把这些石头粘在一起,那么由若干个石头的组成的整体,我不就可以看做是一个天玄石了吗?“
沈宝宝愈发觉得自己机智。
所以现在有一个问题摆在你的面前了,给你A,B,C,请判断是否存在两个大于等于0的整数x,y满足Ax+By=C.
输入
第一行一个T,表示有T组测试数据。 接下来T行,每行三个整数a,b,c,分别表示三块石头的能量值。 满足(1<=T<=100,1 ≤ a, b ≤ 100, 1 ≤ c ≤ 10 000)
输出
对每一组测试答案均需要输出结果,如果可行的话,输出Yes,否则输出No
样例输入1 复制
2
1 2 3
4 6 15
样例输出1
Yes
No
题目链接:http://qscoj.cn/problem/10/
分析:明显就是一道水+暴力,直接上公式:
Ax+By=C--> x=(C-By)/A;
y=(C-Ax)/B;
下面给出AC代码:
1 #include <bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5 int a,b,c,n;
6 scanf("%d",&n);
7 while(n--)
8 {
9 scanf("%d%d%d",&a,&b,&c);
10 int flag=0;
11 for(int i=0;i<10000;i++)
12 {
13 if((c-a*i)%b==0&&(c-a*i)/b>=0)
14 {
15 flag=1;
16 break;
17 }
18 }
19 if(flag)
20 printf("Yes\n");
21 else printf("No\n");
22 }
23 return 0;
24 }
发布时间: 2017年2月21日 20:05 最后更新: 2017年2月21日 20:07 时间限制: 1000ms 内存限制: 128M
描述
喵哈哈村的括号序列和外界的括号序列实际上是一样的。
众所周知"()"这样的,就是一个标准的括号序列;"()()()()"这样也是括号序列;“((()))()”这样也是一个合法的括号序列。但是"((("这样,就不是一个合法的括号序列了。
现在沈宝宝非常好奇,给你一个字符串,请从中找出最长的合法括号序列出来。
不知道你能找到吗?
输入
第一行一个T,表示有T组数据。 接下来T行,每一行都是一个字符串。 保证字符串的长度小于100000。 而且字符串中保证只会出现"(",")"这两种字符之一。 1<=T<=10
输出
对于每一组测试数据,输出最长的合法括号序列的长度。
样例输入1 复制
2
)((())))(()())
)(
样例输出1
6
0
题目链接:http://qscoj.cn/problem/11/
分析:这是一道栈+dp的综合运用的题目。如果我们遇到(,那么我们就把这个位置放进栈里面。如果遇到)的话,就pop掉栈顶,且栈顶就是这个)匹配的(位置,如果我们用l[i]来表示与i匹配的左括号位置的话。
那么我们令dp[i]表示以i结尾的括号序列的最长长度的方程为:dp[i]=dp[l[i]-1]+(i-l[i]+1)。
最后在所有的dp里面取个max就好了。
下面给出AC代码:
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int maxn=1e5+7;
4 string s;
5 stack<int> k;
6 int dp[maxn];
7 void solve()
8 {
9 memset(dp,0,sizeof(dp));
10 while(k.size())
11 k.pop();
12 cin>>s;
13 for(int i=0;i<s.size();i++)
14 {
15 if(s[i]=='(')
16 k.push(i);
17 else
18 {
19 if(!k.empty())
20 {
21 dp[i]=i-k.top()+1;
22 if(k.top()>0)
23 dp[i]+=dp[k.top()-1];
24 k.pop();
25 }
26 }
27 }
28 int ans=0;
29 for(int i=0;i<s.size();i++)
30 if(dp[i]>ans)
31 ans=dp[i];
32 cout<<ans<<endl;
33 }
34 int main()
35 {
36 int t;
37 scanf("%d",&t);
38 while(t--)
39 {
40 solve();
41 }
42 return 0;
43 }