A. Regular Bracket Sequences
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
A bracket sequence is a string containing only characters ”(” and ”)“. A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters “1” and ”+” between the original characters of the sequence. For example, bracket sequences ”()()” and ”(())” are regular (the resulting expressions are: “(1)+(1)” and “((1+1)+1)”), and ”)(”, ”(” and ”)” are not.
You are given an integer nn. Your goal is to construct and print exactly nn different regular bracket sequences of length 2n2n.
Input
The first line contains one integer tt (1≤t≤501≤t≤50) — the number of test cases.
Each test case consists of one line containing one integer nn (1≤n≤501≤n≤50).
Output
For each test case, print nn lines, each containing a regular bracket sequence of length exactly 2n2n. All bracket sequences you output for a testcase should be different (though they may repeat in different test cases). If there are multiple answers, print any of them. It can be shown that it’s always possible.
Example
input
Copy
3
3
1
3
output
Copy
()()()
((()))
(()())
()
((()))
(())()
()(())
解释与代码
简单构造,我的想法是,先存到数组里,
每次打印完,
把()()()中相邻的)(进行互换
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <stack>
#include <iostream>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <vector>
#include <limits.h>
#include <assert.h>
#include <functional>
#include <numeric>
#include <ctime>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define ppb pop_back
#define lbnd lower_bound
#define ubnd upper_bound
#define endl '\n'
#define mll map<ll,ll>
#define msl map<string,ll>
#define mls map<ll, string>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x) for(auto& a : x)
#define pll pair<ll,ll>
#define vl vector<ll>
#define vll vector<pair<ll, ll>>
#define vs vector<string>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (ll)x.size()
#define hell 1000000007
#define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl;
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x) cerr << #x << " is " << x << endl;
#define ini(a) memset(a,0,sizeof(a))
#define ini2(a,b) memset(a,b,sizeof(a))
//#define rep(i,a,b) for(int i=a;i<=b;i++)
#define case ll T;read(T);for(ll Q=1;Q<=T;Q++)
#define lowbit(x) x&(-x)
#define pr printf
#define sc scanf
//#define _ 0
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DBG(x) \
(void)(cout << "L" << __LINE__ \
<< ": " << #x << " = " << (x) << '\n')
#define TIE \
cin.tie(0);cout.tie(0);\
ios::sync_with_stdio(false);
//#define long long int
//using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
template <typename T>
void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + (ch ^ 48);
ch = getchar();
}
x *= f;
return;
}
inline void write(ll x) {
if(x<0) putchar('-'), x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
const ll LN = 5;
const int maxn = 205;
const int N = 31;
char ch[2] = {'(',')'};
char cb[10009];
void solve() {
int n;
cin>>n;
for (int i=0; i<n*2; i++) {
cb[i] = ch[i%2];
}
cb[n*2] = '\0';
for (int i=0; i<n; i++) {
if (i!=0) {
swap(cb[2*i], cb[2*i-1]);
}
cout<<cb<<endl;
}
}
int main()
{
// TIE;
// #ifndef ONLINE_JUDGE
// freopen ("input.txt","r",stdin);
// #else
// #endif
// solve();
case{solve();}
// case{cout<<"Case "<<Q<<":"<<endl;solve();}
// return ~~(0^_^0);
}
B. Combinatorics Homework
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given four integer values aa, bb, cc and mm.
Check if there exists a string that contains:
- aa letters ‘A’;
- bb letters ‘B’;
- cc letters ‘C’;
- no other letters;
- exactly mm pairs of adjacent equal letters (exactly mm such positions ii that the ii-th letter is equal to the (i+1)(i+1)-th one).
Input
The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of testcases.
Each of the next tt lines contains the description of the testcase — four integers aa, bb, cc and mm (1≤a,b,c≤1081≤a,b,c≤108; 0≤m≤1080≤m≤108).
Output
For each testcase print “YES” if there exists a string that satisfies all the requirements. Print “NO” if there are no such strings.
You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).
Example
input
Copy
3
2 2 1 0
1 1 1 1
1 2 3 2
output
Copy
YES
NO
YES
Note
In the first testcase strings “ABCAB” or “BCABA” satisfy the requirements. There exist other possible strings.
In the second testcase there’s no way to put adjacent equal letters if there’s no letter that appears at least twice.
In the third testcase string “CABBCC” satisfies the requirements. There exist other possible strings.
解释与代码
其实就是几种情况,if else全部写出就行
有两个边界值
例如
6 0 0 3
这样是不行的,不够也不行,超出也不行
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <stack>
#include <iostream>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <vector>
#include <limits.h>
#include <assert.h>
#include <functional>
#include <numeric>
#include <ctime>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define ppb pop_back
#define lbnd lower_bound
#define ubnd upper_bound
#define endl '\n'
#define mll map<ll,ll>
#define msl map<string,ll>
#define mls map<ll, string>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x) for(auto& a : x)
#define pll pair<ll,ll>
#define vl vector<ll>
#define vll vector<pair<ll, ll>>
#define vs vector<string>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (ll)x.size()
#define hell 1000000007
#define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl;
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x) cerr << #x << " is " << x << endl;
#define ini(a) memset(a,0,sizeof(a))
#define ini2(a,b) memset(a,b,sizeof(a))
//#define rep(i,a,b) for(int i=a;i<=b;i++)
#define case ll T;read(T);for(ll Q=1;Q<=T;Q++)
#define lowbit(x) x&(-x)
#define pr printf
#define sc scanf
//#define _ 0
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DBG(x) \
(void)(cout << "L" << __LINE__ \
<< ": " << #x << " = " << (x) << '\n')
#define TIE \
cin.tie(0);cout.tie(0);\
ios::sync_with_stdio(false);
//#define long long int
//using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
template <typename T>
void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + (ch ^ 48);
ch = getchar();
}
x *= f;
return;
}
inline void write(ll x) {
if(x<0) putchar('-'), x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
const ll LN = 5;
const int maxn = 205;
const int N = 31;
void solve() {
int a, b, c, m;
cin>>a>>b>>c>>m;
int ans = 0;
if (a!=0)
ans += a-1;
if (b!=0)
ans += b-1;
if (c!=0)
ans += c-1;
if (ans >= m) {
int d = max(a,max(b,c));
if (d == a) {
d -= (b+c);
} else if (d == b) {
d -= (a+c);
} else if (d == c) {
d -= (b+a);
}
if (d-1 <= m) {
cout<<"YES"<<endl;
} else {
cout<<"NO"<<endl;
}
} else {
cout<<"NO"<<endl;
}
}
int main()
{
// TIE;
// #ifndef ONLINE_JUDGE
// freopen ("input.txt","r",stdin);
// #else
// #endif
// solve();
case{solve();}
// case{cout<<"Case "<<Q<<":"<<endl;solve();}
// return ~~(0^_^0);
}
C. Slay the Dragon
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Recently, Petya learned about a new game “Slay the Dragon”. As the name suggests, the player will have to fight with dragons. To defeat a dragon, you have to kill it and defend your castle. To do this, the player has a squad of nn heroes, the strength of the ii-th hero is equal to aiai.
According to the rules of the game, exactly one hero should go kill the dragon, all the others will defend the castle. If the dragon’s defense is equal to xx, then you have to send a hero with a strength of at least xx to kill it. If the dragon’s attack power is yy, then the total strength of the heroes defending the castle should be at least yy.
The player can increase the strength of any hero by 11 for one gold coin. This operation can be done any number of times.
There are mm dragons in the game, the ii-th of them has defense equal to xixi and attack power equal to yiyi. Petya was wondering what is the minimum number of coins he needs to spend to defeat the ii-th dragon.
Note that the task is solved independently for each dragon (improvements are not saved).
Input
The first line contains a single integer nn (2≤n≤2⋅1052≤n≤2⋅105) — number of heroes.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤10121≤ai≤1012), where aiai is the strength of the ii-th hero.
The third line contains a single integer mm (1≤m≤2⋅1051≤m≤2⋅105) — the number of dragons.
The next mm lines contain two integers each, xixi and yiyi (1≤xi≤1012;1≤yi≤10181≤xi≤1012;1≤yi≤1018) — defense and attack power of the ii-th dragon.
Output
Print mm lines, ii-th of which contains a single integer — the minimum number of coins that should be spent to defeat the ii-th dragon.
Example
input
Copy
4
3 6 2 3
5
3 12
7 9
4 14
1 10
8 7
output
Copy
1
2
4
0
2
Note
To defeat the first dragon, you can increase the strength of the third hero by 11, then the strength of the heroes will be equal to [3,6,3,3][3,6,3,3]. To kill the dragon, you can choose the first hero.
To defeat the second dragon, you can increase the forces of the second and third heroes by 11, then the strength of the heroes will be equal to [3,7,3,3][3,7,3,3]. To kill the dragon, you can choose a second hero.
To defeat the third dragon, you can increase the strength of all the heroes by 11, then the strength of the heroes will be equal to [4,7,3,4][4,7,3,4]. To kill the dragon, you can choose a fourth hero.
To defeat the fourth dragon, you don’t need to improve the heroes and choose a third hero to kill the dragon.
To defeat the fifth dragon, you can increase the strength of the second hero by 22, then the strength of the heroes will be equal to [3,8,2,3][3,8,2,3]. To kill the dragon, you can choose a second hero.
解释与代码
贪心加二分
不二分会超时
贪心情况:找到第一个大于等于龙攻击力的人,然后判断金额,然后找这个人的前一个人(因为贪心),再次判断即可
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <iostream>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <vector>
#include <limits.h>
#include <assert.h>
#include <functional>
#include <numeric>
#include <ctime>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define ppb pop_back
#define lbnd lower_bound
#define ubnd upper_bound
#define endl '\n'
#define trav(a, x) for(auto& a : x)
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (ll)x.size()
#define hell 1000000007
#define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl;
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x) cerr << #x << " is " << x << endl;
#define ini(a) memset(a,0,sizeof(a))
#define case ll T;read(T);for(ll Q=1;Q<=T;Q++)
#define lowbit(x) x&(-x)
#define pr printf
#define sc scanf
#define _ 0
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DBG(x) \
(void)(cout << "L" << __LINE__ \
<< ": " << #x << " = " << (x) << '\n')
#define TIE \
cin.tie(0);cout.tie(0);\
ios::sync_with_stdio(false);
//#define long long int
//using namespace __gnu_pbds;
template <typename T>
void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + (ch ^ 48);
ch = getchar();
}
x *= f;
return;
}
inline void write(long long x) {
if(x<0) putchar('-'), x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
putchar('\n');
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 200009;
const ll N = 5;
ll arr[maxn];
void solve(){
ll n, m, x, y, sum = 0, ans = LLINF;
cin>>n;
for (int i=0; i<n; i++) cin>>arr[i], sum += arr[i];
sort(arr, arr+n);
cin>>m;
while (m--) {
ans = LLINF;
cin>>x>>y;
ll p = lbnd(arr, arr+n, x) - arr;
if (p < n) {
ll sw = sum - arr[p];
if (y - sw > 0) {
ans = min(ans, y - sw);
} else {
ans = min(ans, 0LL);
}
}
if (p != 0) {
ll sw = sum - arr[p-1];
ll ww = x - arr[p-1];
if (ww < 0) {
ww = 0;
}
if (y - sw > 0) {
ans = min(ans, y - sw + ww);
} else {
ans = min(ans, (ll)ww);
}
}
cout<<ans<<endl;
}
}
int main()
{
TIE;
#ifndef ONLINE_JUDGE
// freopen ("in.txt" , "r", stdin );
// freopen ("out.txt", "w", stdout);
#else
#endif
solve();
// case{solve();}
// case{cout<<"Case "<<Q<<":"<<endl;solve();}
return ~~(0^_^0);
}