E – Placing Rectangles
题目描述：
给你一个x * y的矩形，问你能不能塞入三个不重叠的面积分别大于等于a、b、c的矩形
思路：
思维+爆搜
主要的思路是先放两个矩形，让这两个矩形占的面积尽可能小，剩下的尽可能是规整的矩形，而不是坑坑洼洼的，然后就直接判断剩下的能不能大于第三个矩形的面积
那么如何放那两个矩形，使得占的面积尽可能小还尽可能是规整的？
就以矩形的一条边(假设为x)当作大于等于s的面积的矩形的一条边，那么另一条边就是
,那此时大矩形的另一条边y就减去 ，然后就可以去算下一个，当然x和y是可以互换的，所以就可以用爆搜 还有要注意的就是放的顺序是可以互换的，所以要跑全排列去跑每一种情况，用全排列之前要从小到大排序！！！
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 300000 + 50
ll n, m, k;
ll x, y;
ll ss[5];
bool ans;
void dfs(ll x, ll y, ll id){
if(x <= 0 || y <= 0)return;
if(id == 3){
if(ss[3] <= x * y)ans = 1;
return;
}
ll num1 = (ss[id] + x - 1) / x;
ll num2 = (ss[id] + y - 1) / y;
dfs(x, y - num1, id + 1);
dfs(x - num2, y, id + 1);
}
void work(){
cin>>x>>y>>ss[1]>>ss[2]>>ss[3];
sort(ss + 1, ss + 4);
dfs(x, y, 1);
while (next_permutation(ss + 1, ss + 4)) {
dfs(x, y, 1);
}
if(ans)cout<<"Yes\n";
else cout<<"No\n";
}
int main(){
// io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
F – Parenthesis Checking
题目描述：
给你一个括号序列，两种操作
- 换第l个和第r个单括号
- 查询l到r是不是一个合法的括号序列
思路：
思维+线段树
开一个数组，' ( '为1，')'为-1，搞一次前缀和，数组记做tr
一个括号是合法的前提是左括号的数量等于右括号的数量，并且在每一个右括号出现时，前面必定有一个没有匹配成功的左括号
这个转换成上面的那个1与-1的判断就是：minx[l, r] >= tr[l – 1] && tr[r] = tr[l – 1]
就可以用线段树来维护区间最小值，区间修改区间查询
有一个很坑的点是，你会用到l-1，这里会发生越界，在更新的时候要判掉！！！
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
////不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 800000 + 50
int n, m, k;
int op, l, r;
string s;
int tr[MAX];
int la[MAX];
int minx[MAX];
inline void pushup(int p){
minx[p] = min(minx[ls], minx[rs]);
}
inline void lazy_cal(int p, int c){
la[p] += c;
minx[p] += c;
}
inline void pushdown(int p){
if(la[p]){
lazy_cal(ls, la[p]);
lazy_cal(rs, la[p]);
la[p] = 0;
}
}
inline void built(int p, int l, int r){
if(l == r){
la[p] = 0;
minx[p] = tr[l];
return;
}
int mid = (l + r) / 2;
built(ls, l, mid);
built(rs, mid + 1, r);
pushup(p);
}
inline void update(int p, int l, int r, int s, int t, int c){
if(s <= l && r <= t){
minx[p] += c;
la[p] += c;
return;
}
pushdown(p);
int mid = (l + r) / 2;
if(mid >= s)update(ls, l, mid, s, t, c);
if(mid < t)update(rs, mid + 1, r, s, t, c);
pushup(p);
}
inline int getminx(int p, int l, int r, int s, int t){
if(l > t || r < s)return 0;
if(s <= l && r <= t){
return minx[p];
}
pushdown(p);
int mid = (l + r) / 2;
int minxx = inf;
if(mid >= s)minxx = min(minxx, getminx(ls, l, mid, s, t));
if(mid < t)minxx = min(minxx, getminx(rs, mid + 1, r, s, t));
return minxx;
}
void work(){
cin>>n>>m;
cin>>s;
s = " " + s;
for(int i = 1; i <= n; ++i){
if(s[i] == '(')tr[i] = 1;
else tr[i] = -1;
}
for(int i = 1; i <=n; ++i)tr[i] += tr[i - 1];
built(1, 1, n);
for(int i = 1; i <= m; ++i){
cin>>op>>l>>r;
if(op == 1){
update(1, 1, n, l, n, s[l] == '(' ? -1 : 1);
update(1, 1, n, r, n, s[r] == '(' ? -1 : 1);
swap(s[l], s[r]);
update(1, 1, n, l, n, s[l] == '(' ? 1 : -1);
update(1, 1, n, r, n, s[r] == '(' ? 1 : -1);
}
else {
int a = getminx(1, 1, n, l, r);
int b = getminx(1, 1, n, r, r);
int c = getminx(1, 1, n, l - 1, l - 1);
if(a >= c && b == c)cout<<"Yes\n";
else cout<<"No\n";
}
}
}
int main(){
// io;
// int tt;cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
