长沙雅礼中学集训-------------------day1（内含day0）

day0：

首先，请允许我吐槽一下：

1.那些一个人住一个标准房的人您们真的是#@**￥&%……#*（）%……*（）@Q$&。

2.感谢那些一个人住一个标准间的人，要不然我们也找不到这个住宿完美，离学校贼进的宾馆。

3.经过一天的物价观察，我终于发现了如何将长沙的东西和焦作的相比从而得出贵不贵，你把价格除个二就差不多是焦作的价格了，如果价格一样的话请把东西的质量除以二。

day1：

6:30起床顺便把懒虫高正从被窝里踹出来。然后那个懒虫就趁我洗漱的时候又睡了个回笼觉

没有摸清地点的我们傻不拉几的买了个二十多的三明治做早餐

八点准时到了上课的机房，开始了一上午的考试。

-----------------------------------------------------------------------------------------------------华丽的分割线--------------------------------------------------------------------------------------------------------

T1：

一句话题目：给你一个有向无自环无重边的图，其中不能出现：点v到u有边，点u到t有边，但是点v到t无边。求加多少条边能够使这个图不存在上述情况。

数据范围：点数<=6*10^4，边数<=10^5；

总之这个题还是挺有良心的，暴力dfs能拿40分，再加上一组数据m=n-1，能拿到60分；

我写的暴力dfs，期望得分：40，实际得分：20.QAQ好菜，检查的时候发现使dfs中有个地方写挂了。

正解是用bitset优化的dfs。

T2：

一句话题目：给你n种区间，第i种区间有si个，再给你m种区间第i种区间有ki个，问你能否用那n种区间覆盖另外m种区间

数据范围n,m<=4*10^5；si，ki<=10^9,区间大小范围为10^9；

emmmmm考试的时候没有带笔和纸，纯靠脑补把题想复杂了。

总之我的总体思路没有错，只不过我想到了排序以后用树状数组搞定，但是下来以后拿笔拿纸推了一下发现不行，考试的时候就拿了前三十分暴力。

机房大佬：前70一看就是裸地网络流啊

正解：用map维护一下这些区间，根据左端点从小到大排序，遇到n中的就插入，遇到m中的查询右端点再往右够不够覆盖，不够即为不行。

AC代码：

#include<map>

#include<queue>

#include<ctime>

#include<cmath>

#include<cstdio>

#include<vector>

#include<string>

#include<limits>

#include<cstring>

#include<cstdlib>

#include<iomanip>

#include<utility>

#include<iostream>

#include<algorithm>

#include<functional>

#define LL long long

#define it map<int,LL>::iterator

using namespace std;

struct hh{

    int l,r,k,w;

};

hh e[];

int T,n,m,sum;

map<int,LL>q;

inline int read(){

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-') f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        x=(x<<)+(x<<)+(ch-'');

        ch=getchar();

    }

    return x*f;

}

bool mycmp(hh x,hh y){

    return (x.l<y.l || (x.l==y.l && x.w>y.w));

}

void add(int u,int s){

    if(!q.count(u)) q[u]=s;

    else q[u]+=s;

}

void work3(){

    sum=n+m;

    for(int i=;i<=sum;i++){

        e[i].l=read(); e[i].r=read();

        e[i].k=read();

        if(i<=n) e[i].w=;

        else e[i].w=;

    }

    sort(e+,e+sum+,mycmp);

    for(int i=;i<=sum;i++){

        if(e[i].w==)

            add(e[i].r,e[i].k);

        else{

            while(e[i].k){

                it p=q.lower_bound(e[i].r);

                if(p==q.end()){

                    printf("No\n");

                    return;

                }

                else{

                    if(e[i].k<p->second) p->second-=e[i].k,e[i].k=;

                    else{

                        e[i].k-=p->second;

                        q.erase(p);

                    }

                }

            }

        }

    }

    printf("Yes\n");

}

int main(){

    freopen("machine.in","r",stdin);

    freopen("machine.out","w",stdout);

    T=read();

    for(int o=;o<=T;o++){

        q.clear();

        n=read(); m=read();

        work3();

    }

    fclose(stdin);fclose(stdout);

    return ;

}

T3：

奇奇怪怪的组合数学。

求C(n,m)(1<=m<=L，1<=n<=m)中有多少个组合能被p^k整除，并对1000000007取模。

emmmmmmm

反正就是一堆奇奇怪怪的公式最后推出一个奇奇怪怪的结论。

当然这个题的前30分还是很好拿的

前两组数据直接暴力枚举n，m就可以。

第三组：由于p^k太大，而数据要求的n,m太小，所以直接输出0即可拿这10分（我有机麻和麦皮不知当桨不当桨）。

第一天，完美50分滚粗。

总结：辣鸡ysc

巴特西

长沙雅礼中学集训-------------------day1（内含day0）

最新文章

热门文章