Loli不是你们想的loli
20180302 Loli模拟赛
先解释一下，loli不是你们想象的那个……那是我们信息组总教练的外号，对，就是那个上次一口气出了五道奶牛题的神级教练(非黑)。
这次这个题也是有毒……两道板子+一道毒瘤题……
T1 ditch
这不就是最大流板子？说的还挺玄乎的……还是个奶牛题……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define ini inline int
#define inb inline bool
#define big 10000010
#define maxn 1010
using namespace std;
int m,n,cnt,tot,ans;
int head[maxn],cur[maxn],dis[maxn];
ini read()
{
char c;rint r=0,f=1;
c=getchar();
while (c<'0' || c>'9') {
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
r=r*10+(c^48);
c=getchar();
}
return r*f;
}
struct node
{
int next,to,dis,cnt;
}ljb[1001];
inv add_edge(int x,int y,int z)
{
ljb[++cnt].next=head[x];
ljb[cnt].to=y;
ljb[cnt].dis=z;
ljb[cnt].cnt=cnt;
head[x]=cnt;
}
inv add(int x,int y,int z)
{
add_edge(x,y,z);
add_edge(y,x,0);
}
queue <int> q;
inb bfs()
{
for (rint i=1;i<=n;i++) dis[i]=-1;
q.push(1);dis[1]=0;
while (!q.empty()){
int x=q.front();q.pop();
for (rint i=head[x];i!=-1;i=ljb[i].next){
int y=ljb[i].to;
if (dis[y]<0 && ljb[i].dis>0){
dis[y]=dis[x]+1;
q.push(y);
}
}
}
if (dis[n]>0) return 1;
return 0;
}
ini dfs(int x,int low)
{
if (x==n) return low;
for (rint& i=cur[x];i!=-1;i=ljb[i].next)
{
int y=ljb[i].to;
if (dis[y]==dis[x]+1 && ljb[i].dis>0)
{
int flow=dfs(y,min(low,ljb[i].dis));
if (flow)
{
ljb[i].dis-=flow;
ljb[ljb[i].cnt^1].dis+=flow;
return flow;
}
}
}
return 0;
}
int main()
{
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
m=read();n=read();
for (rint i=1;i<=n;i++) head[i]=-1;cnt=-1;
for (rint i=1;i<=m;i++){
int x,y,z;
x=read();y=read();z=read();
add(x,y,z);
}
while (bfs())
{
for (rint i=1;i<=n;i++) cur[i]=head[i];
do
{
tot=dfs(1,big);
ans+=tot;
}
while (tot);
}
printf("%d",ans);
}
T2 manager
好像是树剖板子？然而蒟蒻的我好像忘了树剖怎么打？
哎，看这个题好像只需要处理子树和到根节点两种情况就好了，这不就简单了吗……然而我的山寨树剖好像跑的贼慢？不管了能过就成……
当然要注意一个地方，就是卸载一个软件要先卸载子树，安装一个软件要把根节点到它的路径上的软件都安装上，别搞反了……标记的话搞一个覆盖标记，标记为1就是都要选，标记为0就是一个都不选，线段树维护区间和就行了。
还有就是往根节点上跳的时候不能是f[x]为0的时候退出修改或询问，因为当前重链的top不一定是0，得再往上跳到0才行……我们可以把根节点的父亲设成inf，x==inf的时候再退出
#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
#define inv inline void
#define ini inline int
#define inb inline bool
#define mid (l+r>>1)
#define ls (num<<1)
#define rs (num<<1|1)
#define big 1e9
#define maxn 100010
using namespace std;
int sum[maxn<<2],add[maxn<<2],res[maxn<<2];
int a[maxn],f[maxn],tot[maxn],dfn[maxn],idfn[maxn],son[maxn],top[maxn],head[maxn],dis[maxn];
int n,q,cnt;
char s[maxn];
struct node
{
int next,to;
}ljb[maxn];
ini read()
{
char c;rint r=0,f=1;
c=getchar();
while (c<'0' || c>'9') {
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
r=r*10+(c^48);
c=getchar();
}
return r*f;
}
inv add_edge(int x,int y)
{
ljb[++cnt].next=head[x];
ljb[cnt].to=y;
head[x]=cnt;
}
inv dfs1(int x,int fa)
{
f[x]=fa;tot[x]=1;
if (x) dis[x]=dis[fa]+1;else dis[x]=1;
rint maxx=0;
for (rint i=head[x];i;i=ljb[i].next)
{
int y=ljb[i].to;
if (y!=f[x])
{
dfs1(y,x);
if (tot[y]>maxx) maxx=tot[y],son[x]=y;
tot[x]+=tot[y];
}
}
}
inv dfs2(int x,int tp)
{
dfn[x]=++cnt;
top[x]=tp;
if (son[x]) dfs2(son[x],tp);
for (rint i=head[x];i;i=ljb[i].next)
{
int y=ljb[i].to;
if (y!=f[x] && y!=son[x])
dfs2(y,y);
}
}
inv pushdown(int ln,int rn,int num)
{
if (res[num])
{
add[ls]=0;add[rs]=0;
res[ls]=1;res[rs]=1;
sum[ls]=0;sum[rs]=0;
res[num]=0;
}
if (add[num])
{
add[ls]=1;add[rs]=1;
sum[ls]=ln;sum[rs]=rn;
add[num]=0;
}
}
inv change(int L,int R,int l,int r,int num,int f1,int f2)
{
if (L<=l && r<=R)
{
if (f1)
{
add[num]=1;
sum[num]=r-l+1;
}
if (f2)
{
res[num]=1;
add[num]=0;
sum[num]=0;
}
return;
}
pushdown(mid-l+1,r-mid,num);
if (L<=mid) change(L,R,l,mid,ls,f1,f2);
if (R>mid) change(L,R,mid+1,r,rs,f1,f2);
sum[num]=sum[ls]+sum[rs];
}
ini query(int L,int R,int l,int r,int num)
{
if (L<=l && r<=R) return sum[num];
pushdown(mid-l+1,r-mid,num);
rint ans=0;
if (L<=mid) ans+=query(L,R,l,mid,ls);
if (R>mid) ans+=query(L,R,mid+1,r,rs);
return ans;
}
ini treeq(int x)
{
rint ans=0;
do
{
ans+=query(dfn[top[x]],dfn[x],1,n,1);
x=f[top[x]];
}
while (x!=big);
return ans;
}
inv treec(int x)
{
do
{
change(dfn[top[x]],dfn[x],1,n,1,1,0);
x=f[top[x]];
}
while (x!=big);
}
int main()
{
freopen("manager.in","r",stdin);
freopen("manager.out","w",stdout);
n=read();
for (rint i=1;i<=n-1;i++){
a[i]=read();
add_edge(a[i],i);
}
dfs1(0,big);
cnt=0;
dfs2(0,0);
q=read();
for (rint i=1;i<=q;i++)
{
cin>>s;
rint x=read(),ans=0;
if (s[0]=='i')
{
ans=treeq(x);
treec(x);
printf("%d\n",dis[x]-ans);
}
if (s[0]=='u')
{
ans=query(dfn[x],dfn[x]+tot[x]-1,1,n,1);
change(dfn[x],dfn[x]+tot[x]-1,1,n,1,0,1);
printf("%d\n",ans);
}
}
}
T3 interval
这个玩意有毒吧……
考场上没搓出来，最后输出empty set得了十分，出了一堆脑残错误，不想复述。
更好的解法可以百度搜索“校门外的区间”这道题，正常人的做法比我的做法好理解多了……
这里说说蒟蒻的写法
一开始想分块，然后自我hack之后打的线段树。把一个点拆成三个，闭区间的左右括号都对应第二个点，但是要注意开区间的右括号对应第一个点，开区间的左括号对应第三个点，别搞反了。
还有就是读入的是一个字符串，而数字是好多位的，所以要写个函数读一下。
五种操作分别可以化为多次进行区间覆盖为1，区间覆盖为0，区间异或三种操作来进行，这里大家可以自己推一下，推不出来看底下的程序也能看出来。
对于线段树的每一个区间，有1，0，-1三种可能的值，1是全部为1，0是全部为0，-1是有0也有1，这样能优化后面查询的复杂度。
线段树的两种标记，覆盖和异或，我们可以看出覆盖优于异或。当一段区间有覆盖标记的时候，我们可以把覆盖标记取反，就不用打异或标记了，或者当一段区间为纯色(也就是值为0或1)的时候，我们可以把这个区间反色，然后给子区间打上覆盖标记，这样也不用打异或标记。如果这两种情况都不满足的话，我们再给区间打上一个异或标记，然后pushdown的时候下传，如果子区间满足以上两种情况，就按上面的方法结算，然后再pushup上去，我比较傻逼，只能想到这种笨办法。
查询的话就深搜这棵树，如果搜到纯色0的区间，直接return回来；如果搜到纯色1的区间，给左右区间打标记，然后如果是单点的话就单独打一种标记，输出的时候O(n)枚举每一个点，如果这个点被打过标记就分三种标记讨论一下要不要输出，代码里面关于输出的细节挺多的，手动推演一下比较好理解。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#define rint register int
#define inv inline void
#define inc inline char
#define ini inline int
#define mid (l+r>>1)
#define ls (num<<1)
#define rs (num<<1|1)
#define n 196608
using namespace std;
map<char,int> mp;
int sum[n<<2],cov[n<<2],flag[n<<2],a[n<<2];
char c,s[101],ch[101];
inv build() {for (rint i=1;i<=(n<<2);i++) sum[i]=0,cov[i]=-1,flag[i]=0,a[i]=-1;}
inv push_f(int num){
if (cov[num]>=0) {
cov[num]^=1,sum[num]=cov[num],flag[num]=0;
return;
}
if (sum[num]>=0) {
sum[num]^=1,cov[num]=sum[num],flag[num]=0;
return;
}
flag[num]^=1;
}
inv pushdown(int num)
{
if (cov[num]>=0){
cov[ls]=cov[rs]=cov[num];
sum[ls]=sum[rs]=cov[num];
flag[ls]=flag[rs]=0;
cov[num]=-1;
}
if (flag[num]){
push_f(ls);
push_f(rs);
flag[num]=0;
}
}
ini pushup(int num)
{
if (sum[ls]==-1 || sum[rs]==-1) return -1;
if (sum[ls]==sum[rs]) return sum[ls];
return -1;
}
inv change(int L,int R,int l,int r,int num,int tag)
{
if (L<=l && r<=R){
if (tag==0){
cov[num]=0;sum[num]=0;flag[num]=0;
}
if (tag==1){
cov[num]=1;sum[num]=1;flag[num]=0;
}
if (tag==2){
push_f(num); }
return;
}
pushdown(num);
if (L<=mid) change(L,R,l,mid,ls,tag);
if (R>mid) change(L,R,mid+1,r,rs,tag);
sum[num]=pushup(num);
}
inv query(int l,int r,int num)
{
if (sum[num]==1){
a[l]=0;a[r]=1;
if (l==r) a[l]=2;
return;
}
if (sum[num]==0) return;
pushdown(num);
query(l,mid,ls);
query(mid+1,r,rs);
}
inv write(int i,int now)
{
if (!now){
if (i%3==2) putchar('[');
else putchar('(');
printf("%d",(i-1)/3);
putchar(',');
}
else{
printf("%d",(i-1)/3);
if (i%3==2) putchar(']');
else putchar(')');
putchar(' ');
}
}
inv print()
{
rint now=0,fir=0,lst=0,flg=0;
for (rint i=1;i<=n;i++){
if (a[i]>=0){
flg=1;
if (a[i]==0 && a[i-1]>=0) continue;
if (a[i]==1 && a[i+1]>=0) continue;
if (a[i]==2){
if (a[i-1]<0 && a[i+1]<0){
putchar('[');printf("%d",(i-1)/3);
putchar(']');putchar(' ');continue;
}
if (a[i-1]>=0 && a[i+1]>=0) continue;
if (a[i+1]>=0 && now==1) continue;
}
write(i,now);now^=1;
}
a[i-1]=-1;
}
a[n]=-1;
if (!flg) puts("empty set");
}
ini read(int l,int r)
{
rint kk=0;
for (rint i=l;i<=r;i++) kk=kk*10+s[i]-'0';
return kk;
}
int main()
{
freopen("interval.in","r",stdin);
freopen("interval.out","w",stdout);
build();
rint l=0,r=0;
mp[')']=1;mp['(']=3;mp['[']=mp[']']=2;
while (cin>>c){
cin>>s;
for (rint i=1;i<=strlen(s)-1;i++)
if (s[i]==',') {l=read(1,i-1);r=i+1;break;}
r=read(r,strlen(s)-2);
l=l*3+mp[s[0]];
r=r*3+mp[s[strlen(s)-1]];
if (c=='U') change(l,r,1,n,1,1);
if (c=='I'){
change(1,l-1,1,n,1,0);
change(r+1,n,1,n,1,0);
}
if (c=='D') change(l,r,1,n,1,0);
if (c=='C'){
change(1,l-1,1,n,1,0);
change(r+1,n,1,n,1,0);
change(l,r,1,n,1,2);
}
if (c=='S') change(l,r,1,n,1,2);
}
query(1,n,1);
print();
}
赞 赏
蒟蒻的邮箱:xmzl200201@126.com
