AtCoder Beginner Contest 223（D,E,F)
D（拓扑排序）
大意就是有\(n\)个点，\(m\)个关系，其中关系是指\(u\)和\(v\),在排序里面使得\(u\)的位置再\(v\)的位置的前面
要求找到一个排序满足上述条件的序列中字典序最小的那一个
这个使用拓扑排序，并加上优先队列即可
只要找到\(n\)个数，即为找到，否则没有这样的排序
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <deque>
#include <bitset>
#include <unordered_map>
#include <cstring>
using namespace std;
const int maxn=2e5+10;
const int mod=998244353;
const double eps=1e-12;
#define int long long
const int inf=1e9;
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
int n,m;
int d[maxn];
vector<int>g[maxn];
vector<int>ans;
bool topsort()
{
priority_queue<int,vector<int>,greater<int>>q;
for (int i=1;i<=n;i++)
{
if(d[i]==0)
{
q.push(i);
}
}
while (!q.empty())
{
int u=q.top();
q.pop();
ans.push_back(u);
for (auto v:g[u])
{
d[v]--;
if(d[v]==0)
{
q.push(v);
}
}
}
return ans.size()==n;
}
signed main ()
{
cin>>n>>m;
for (int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
d[v]++;
}
if(topsort())
{
for (auto x:ans)
{
cout<<x<<" ";
}
}
else cout<<-1;
cout<<"\n";
system ("pause");
return 0;
}
E（贪心）
这个题的大意就是给你一个方块长为\(x\),宽为\(y\),然后我们需要知道是否可以在这一个方块里面找到三个不重叠的矩形，并且这三个矩形的面积分别有三个最小值\(a,b,c\),而且矩形的边要和\(x\)或者\(y\)轴平行
这个我们贪心的来看，这些矩形的排布可以为这几种
大致是上面四种排布，这些格子里面哪一个是\(a\)，哪一个是\(b\),都可以一一列举
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <deque>
#include <bitset>
#include <unordered_map>
#include <cstring>
using namespace std;
const int maxn=2e5+10;
const int mod=998244353;
const double eps=1e-12;
#define int long long
const int inf=1e9;
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
int n,m;
int a[maxn],x,y;
int check1()
{
int sum=0;
for (int i=1;i<=3;i++)
{
sum+=(a[i]+x-1)/x;
}
return sum<=y;
}
int check2(int j)
{
int sum=y-(a[j]+x-1)/x;
if(sum<=0) return 0;
int now=0;
for (int i=1;i<=3;i++)
{
if(i==j) continue;
now+=(a[i]+sum-1)/sum;
}
return now<=x;
}
signed main ()
{
cin>>x>>y>>a[1]>>a[2]>>a[3];
int yes=0;
yes|=check1();
for (int i=1;i<=3;i++)
{
yes|=check2(i);
}
swap(x,y);
yes|=check1();
for (int i=1;i<=3;i++)
{
yes|=check2(i);
}
if(yes)
{
cout<<"Yes\n";
}
else
{
cout<<"No\n";
}
system ("pause");
return 0;
}
F（线段树，前缀和）
这个题题意很简单
就是给你一个字符串，然后下面有\(q\)个询问
输入\(op,l,r\),
如果\(op=1\)，就代表这我们需要交换第\(l\)个字符和第\(r\)个字符，
如果\(op=2\)，我们需要判断这一段里面字符的括号是否匹配
这个里面用到了线段树，但是我觉得很难的是怎么处理每一个点的状态和如何判断某一范围里面的括号是否匹配
对于一段匹配成功的字符串里面，\((\)和\()\)的数量是一样的，那么我们可以给\((\)赋值为\(1\),给\()\)赋值为\(-1\),那么对于一段匹配的字符的条件之一就是前缀和为\(0\)
但是这还不够，因为我们还可能出现\()(\)的情况
我们还可记录一个最小未匹配数\(mi\),可以这样更新
tr[root].mi=min(tr[lson].mi,tr[lson].sum+tr[rson].mi);
这一代码我们可以这样看
把l r 可分成两部分，lson是它左边的一部分，rson是它右边的一部分
tr[lson].sum是它左边这一段多出来的左括号，然后如果我们右边这一段也存在还未匹配的右括号，我们可以让这两个进行匹配
如出现)(,只要他的左边出现了()(,多出了一个左括号即可
以上是鄙人拙见
具体代码如下
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <deque>
#include <bitset>
#include <unordered_map>
#include <cstring>
using namespace std;
#define int long long
#define lson root<<1
#define rson root<<1|1
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e9+7;
const int maxn=1e6+100;
struct segtree
{
int l,r,sum,mi;
}tr[maxn<<2];
int n,q;
string s;
int a[maxn];
int x,y;
void build(int root,int l,int r)
{
tr[root]={l,r,0,0};
if (l==r) return ;
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
return ;
}
void pushup(int root)
{
tr[root].sum=(tr[lson].sum+tr[rson].sum);
tr[root].mi=min(tr[lson].mi,tr[rson].mi+tr[lson].sum);
return ;
}
void update(int root,int l,int r,int val)
{
if (l<=tr[root].l&&tr[root].r<=r)
{
tr[root].sum=val;
tr[root].mi=val;
return ;
}
int mid=(tr[root].l+tr[root].r)>>1;
if (l<=mid)
{
update(lson,l,r,val);
}
if (r>mid)
{
update(rson,l,r,val);
}
pushup(root);
return ;
}
void query(int root,int l,int r)
{
if (l<=tr[root].l&&tr[root].r<=r)
{
y=min(y,x+tr[root].mi);
x+=tr[root].sum;
return ;
}
int mid=(tr[root].l+tr[root].r)>>1;
int mi=inf,sum=0;
if (l<=mid)
{
query(lson,l,r);
}
if (r>mid)
{
query(rson,l,r);
}
return ;
}
signed main ()
{
cin>>n>>q;
cin>>s;
s=" "+s;
for (int i=1;i<=n;i++)
{
if(s[i]=='(')
{
a[i]=1;
}
else a[i]=-1;
}
build(1,1,n);
for (int i=1;i<=n;i++)
{
update(1,i,i,a[i]);
}
while (q--)
{
int op,l,r;
cin>>op>>l>>r;
if(op==1)
{
swap(a[l],a[r]);
update(1,l,l,a[l]);
update(1,r,r,a[r]);
}
else
{
x=0,y=inf;
query(1,l,r);;
if(x==0&&y==0)
{
cout<<"Yes\n";
}
else
{
cout<<"No\n";
}
}
}
system ("pause");
return 0;
}