【题目记录】——2021牛客暑期多校训练营6

谁借莪１个温暖的怀抱￠ 2022-09-02 11:53 110阅读 0赞

### 文章目录 ###

*  C Delete Edges 思维
 *  F Hamburger Steak 思维+模拟
 *  H Hopping Rabbit 扫描线
 *  I Intervals on the Ring 思维

题目集地址 [2021牛客暑期多校训练营6][2021_6]  
这次题目集做的有点差，只做出了I题

# C Delete Edges 思维 #

题意：给定一个有 n 个点的完全无向图，每次在其中选出三个点，若这每两个点间的边都存在，则删去这三条边。可操作 m 次，直到该图中剩下的边的个数小于 n 为止。（ 操作次数不需要最小 ）  
思路：开赛时很多人都扑街的一道题，虽然表面上是图论，但考察的内容是如何避免出现重复的两两组合数，因为当删去某个三角形后，其中的任意两点将不能一起再出现在新的三角形内。  
由于本题需要保证两两间的组合不重复出现，因此可以在保证输出的三个点中 第三点 > 第二点 > 第一点 的前提下进行暴力枚举即可。  
结论题，结论：x+y+z=0(mod n)1<=x<y<z<=n所有解即可  
证明过程可以看看下面博客讲的  
[讲解][Link 1]  
我们当时连暴力都不知道怎么暴力。。

AC代码：

#include<bits/stdc++.h>
    
    using namespace std;
    const int inf=0x3f3f3f3f;
    struct node{ 
        int x,y,z;
    };
    vector<node>res;
    int main()
    { 
        freopen("in.txt","r",stdin);
    	freopen("out.txt","w",stdout);
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            for(int j=i+1;j<=n;++j)
            { 
                int k=((n-i-j-1+n)%n)%n+1;
                if(k<=j) continue;
                res.push_back({ i,j,k});
            }
        printf("%d\n",(int)res.size());
        for(auto x:res)
            printf("%d %d %d\n",x.x,x.y,x.z);
        return 0;
    }

# F Hamburger Steak 思维+模拟 #

题目地址【[F Hamburger Steak][]】  
题意：给n个汉堡和m个锅，给出每个汉堡蒸熟所需的时间，每个汉堡最多在两个锅里面蒸。问最少需要多少时间蒸熟所有汉堡，按照每个汉堡所需时间升序输出，每个汉堡的锅号，以及汉堡在锅里蒸的时间。  
思路：先找一个基准值，可以保证能把所有汉堡蒸熟，基准值是汉堡所需时间平均值和汉堡所需时间的最大值中的较大值。然后按顺序蒸汉堡，如果一个锅子无法在基准值时间内将某个汉堡蒸熟（因为这个锅子已经蒸熟了一个其它汉堡），就将这个汉堡分两个锅子蒸，先在下一个锅子蒸一段时间，到当前锅子剩余时间刚好把这个汉堡蒸熟。  
AC代码：

/* ** Author:skj ** Time:8-8 ** function:牛客第六场F */
    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn = 1e5+5;
    int ti[maxn];
    
    int main()
    { 
    	//freopen("in.txt","r",stdin);
    	//freopen("out.txt","w",stdout);
    	int n, m;
    	scanf("%d%d",&n,&m);
    	ll basevalue = 0;
    	int ma = 0;       //时间最大值
    	for(int i = 1;i <= n;i++)
        { 
            scanf("%d",&ti[i]);
            basevalue += ti[i];
            ma = max(ma,ti[i]);
        }
        int k = 0;
    
        if(basevalue % m)
        { 
            k=1;
        }
        basevalue /= m;
        basevalue += k;
        basevalue = ma > basevalue?ma:basevalue;
    
        ll t1 = 0;  //当前锅子用过的时间
        int num = 1;//锅子编号
        for(int i = 1;i <= n;i++)
        { 
            if(ti[i] <= basevalue-t1)
            { 
                printf("1 %d %lld %lld\n",num,t1,t1+ti[i]);
                t1 += ti[i];
                if(t1 == basevalue)
                { 
                    num++;
                    t1 = 0;
                }
            }
            else
            { 
                printf("2 %d 0 %lld %d %lld %lld\n",num+1,ti[i]-basevalue+t1,num,t1,basevalue);
                t1 = ti[i]-basevalue+t1;
                num++;
            }
        }
        return 0;
    }

# H Hopping Rabbit 扫描线 #

题目地址[H Hopping Rabbit][]  
题意：兔子在草原上跳跃，需要躲避陷阱。草原视为二维平面，有 n ( 1 ≤ n ≤ 1 0 5 ) n(1\\le n \\le 10^5) n(1≤n≤105)个陷阱，陷阱可以看成平面上的矩形。兔子可以平行于x轴或y轴跳跃，每次跳跃距离为 d ( 1 ≤ d ≤ 1 0 5 ) d(1 \\le d \\le 10^5) d(1≤d≤105)。  
兔子希望找到一个起始点( x 0 + 0.5 , y 0 + 0.5 x\_0+0.5,y\_0+0.5 x0\+0.5,y0\+0.5)，无论他怎么跳，都不会跳到陷阱内。如果存在这样的点，则输出“YES”和任意解，否则输出“NO”  
思路：看起来跟矩形覆盖有关，联想到扫描线，扫描线暂时不太会，先贴一篇题解吧。。  
[2021牛客暑期多校训练营6-H题][2021_6-H]  
AC代码：

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<vector>
    #define ll long long
    using namespace std;
    const int N=1e5+7;
    int n,d,ql,qr,x;
    struct node1{ 
    	int s,len;//s表示tr[i]是否被覆盖，len表示有效长度 
    }tr[N*4];
    struct node2{ 
    	int l,r,x;
    };
    vector <node2> vt[N];
    void pushup(int l,int r,int rt)
    { 
    	if(tr[rt].s) tr[rt].len=r-l+1;//tr[rt]被覆盖，长度为r-l+1 
    	else if(l==r) tr[rt].len=0;//若只有一个点且未被覆盖，长度标记为0 
    	else tr[rt].len=tr[rt*2].len+tr[rt*2+1].len;
    }
    void add(int x1,int x2,int y1,int y2)//添加新的覆盖
    { 
    	vt[x1].push_back((node2){ y1,y2,1});
    	vt[x2+1].push_back((node2){ y1,y2,-1});
    }
    void change(int l,int r,int rt)
    { 
    	if(ql<=l && r<=qr)
    	{ 
    		tr[rt].s+=x;//改变状态
    		pushup(l,r,rt);
    		return;
    	}
    	int mid=(l+r)/2;
    	if(ql<=mid) change(l,mid,2*rt);
    	if(mid<qr) change(mid+1,r,2*rt+1);
    	pushup(l,r,rt);
    }
    void search(int l,int r,int rt)
    { 
    	if(tr[rt].len==0)//当前点无覆盖，为一种答案 
    	{ 
    		printf("%d\n",l);
    		return;
    	}
    	int mid=(l+r)/2;
    	if(tr[2*rt].len<mid-l+1) search(l,mid,2*rt);
    	else search(mid+1,r,2*rt+1);
    }
    
    int main()
    { 
    	scanf("%d%d",&n,&d);
    	for(int i=1;i<=n;i++)
    	{ 
    		int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    		x2--; 
    		y2--;
    		if(x2-x1+1>=d)
    		x1=0,x2=d-1;
    		if(y2-y1+1>=d)
    		y1=0,y2=d-1;
    		
    		x1=(x1%d+d)%d;
    		x2=(x2%d+d)%d;
    		y1=(y1%d+d)%d;
    		y2=(y2%d+d)%d;
    		//将矩形分解、移动到同一个d*d的正方形内 
    		if(x1<=x2){ 
    			if(y1<=y2) add(x1,x2,y1,y2);
    			else add(x1,x2,0,y2),add(x1,x2,y1,d-1);
    		}
    		else{ 
    			if(y1<=y2) add(0,x2,y1,y2),add(x1,d-1,y1,y2);
    			else add(0,x2,0,y2),add(x1,d-1,y1,d-1),add(0,x2,y1,d-1),add(x1,d-1,0,y2);
    		}
    	}
    	for(int i=0;i<d;i++)
    	{  
    		for(int j=0;j<vt[i].size();j++)//更新 
    		{ 
    			ql=vt[i][j].l;
    			qr=vt[i][j].r;
    			x=vt[i][j].x;
    			change(0,d-1,1);
    		}
    		if(tr[1].len<d)//当扫描线上有效覆盖长度<d时存在一点符合题意 
    		{ 
    			puts("YES");
    			printf("%d ",i);//输出横坐标 
    			search(0,d-1,1);//找到这个点的纵坐标 
    			return 0;
    		}
    	}
    	puts("NO");
    	return 0;
    }

# I Intervals on the Ring 思维 #

题目地址[I Intervals on the Ring][]  
题意：给一个数n，代表序列中元素个数，序列为整数1~n-1，序列区间是成环状，l可以大于r。给出几个不相交的区间，要求找出几个区间满足区间的交集是给出区间的并集，输出区间个数和区间。  
思路:  
将给出的区间的并集全部标记在区间中，因为区间是整数区间，可以用数组来表示序列。  
AC代码：

#include<iostream>
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int a[1005];
    int k[1005];
    
    int main()
    { 
        int t,n,m;
        scanf("%d",&t);
        while(t--)
        { 
            scanf("%d%d",&n,&m);
            int l,r;
            memset(a,0,sizeof(a));
            for(int i=1;i<=m;i++)
            { 
                scanf("%d%d",&l,&r);
                if(l<=r)
                    for(int j=l;j<=r;j++)
                    { 
                        a[j]=1;
                    }
                else
                { 
                    for(int j=1;j<=r;j++)
                    { 
                        a[j]=1;
                    }
                    for(int j=l;j<=n;j++)
                    { 
                        a[j]=1;
                    }
                }
            }
            int num=0;
            int i;
            int kx=0;
            for(i=1;i<=n;)
            { 
                if(a[i]==0)
                { 
                    i++;
                    continue;
                }
                bool bol=true;
                while(1)
                { 
                    if(bol)
                    { 
                        bol=false;
                        k[kx]=i;
                        kx++;
                    }
                    i++;
                    if(a[i]==0)
                    { 
                        k[kx]=i-1;
                        kx++;
                        num++;
                        break;
                    }
                }
            }
            bool biao=true;
            if(a[1]==1&&a[n]==1&&num>1)
            { 
                num--;
                biao=false;
            }
            if(num>2)
            { 
                if(biao)
                { 
                    printf("%d\n",kx/2);
                    for(int kk=0;kk<kx-1;kk+=2)
                    { 
                        printf("%d %d\n",k[kk],k[(kx-1+kk)%kx]);
                    }
                }
                else
                { 
                    kx-=2;
                    printf("%d\n",kx/2);
                    printf("%d %d\n",k[kx],k[kx-1]);
                    for(int kk=2;kk<kx-1;kk+=2)
                    { 
                        printf("%d %d\n",k[kk],k[(kx-1+kk)%kx]);
                    }
                }
            }
            else if(num==2)
            { 
                if(biao)
                { 
                    printf("2\n%d %d\n%d %d\n",k[2],k[1],k[0],k[3]);
                }
                else
                { 
                    printf("2\n%d %d\n%d %d\n",k[2],k[1],k[4],k[3]);
                }
            }
            else if(num==1)
            { 
                if(biao)
                { 
                    printf("1\n%d %d\n",k[0],k[1]);
                }
                else
                { 
                    printf("1\n%d %d\n",k[2],k[1]);
                }
            }
            else
            { 
                printf("-1\n");
            }
        }
        return 0;
    }

补充：上面是我们现场做题的时候的思路，后来发现这只是一个定律。。。。基础太差了，哭辽。  
集合的德摩根律告诉我们  ⋃ A i ‾ = ⋂ A i ‾ \\overline\{\\bigcup A\_i\}=\\bigcap \\overline\{A\_i\} ⋃Ai=⋂Ai(区间的并的补等于区间的补的交)，先找到所有给出区间的并的补区间，然后输出**每一段**区间的补区间即可。  
从网上找来的简单解法。

#include <bits/stdc++.h>
    #define PII pair<int, int>
    #define ll first
    #define rr second
    #define endl '\n'
    using namespace std;
    const int N = 1010;
    PII a[N];
    void solve()
    { 
        int n, m;
        cin >> n >> m;
        for(int i = 0;i < m;i ++)
            cin >> a[i].ll >> a[i].rr;
        sort(a, a+m);
        cout << m << endl;	//有多少个给出的区间就有多少个区间的并的补区间，每一段补区间都有一个要输出的补区间。
        for(int i = 0;i < m;i ++)
        { 
            if(i) cout << endl;
            cout << a[i].ll << ' ' << a[(i-1+m) %m].rr;
        }
    }
    int main()
    { 
        int T;
        cin >> T;
        while(T --)
        { 
            solve();
            if(T) printf("\n");
        }
        return 0;
    }

[2021_6]: https://ac.nowcoder.com/acm/contest/11257
[Link 1]: https://blog.csdn.net/qq_60252920/article/details/119350752
[F Hamburger Steak]: https://ac.nowcoder.com/acm/contest/11257/F
[H Hopping Rabbit]: https://ac.nowcoder.com/acm/contest/11257/H
[2021_6-H]: https://blog.csdn.net/Nep_Genesis/article/details/119348085
[I Intervals on the Ring]: https://ac.nowcoder.com/acm/contest/11257/I