欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

中山纪念中学培训游记

程序员文章站 2022-10-04 22:58:58
2018-08-05 day0 去机场的路上,莫名有点开心,像是要出去玩一样 飞机延误了一会,起飞时很平稳,耳朵毫无不适,当时的我在内心赞美机长。把午饭(除了橘子)基本全解决掉了,还有时间睡一会。飞上云层后景色真的很漂亮,sjz上方有一层乌云,从上方看就像灰蓝色的海面,上面漂浮着许多形态各异的白云( ......

2018-08-05

day0


去机场的路上,莫名有点开心,像是要出去玩一样

 

飞机延误了一会,起飞时很平稳,耳朵毫无不适,当时的我在内心赞美机长。把午饭(除了橘子)基本全解决掉了,还有时间睡一会。飞上云层后景色真的很漂亮,sjz上方有一层乌云,从上方看就像灰蓝色的海面,上面漂浮着许多形态各异的白云(白得刺眼),像漂浮在海面上的冰山。结果飞机刚开始下降,左眼(和左脸那一片)就开始疼,可能是血管不适应气压变化。后来好了。

 

纪中挺漂亮的,绿化非常好。但是宿舍真的一般,食堂也不如ez好吃...一开始觉得汤(加了海带黄豆和姜什么的)的味道非常怪,后来觉得还可以。洗了下上衣,过程中就发现了死虫子x2,有点郁闷。挂蚊帐好不容易才挂好,也有点郁闷。

 

晚上在机房,jzoj死活注册不好。还有分组......唉。看了看以前的各种板子之类的,稍微留点印象。

 

忘了好多东西,现在有点虚。明明刚来,其实就有点想回去了【苦笑】。算了,艰苦奋斗,艰苦奋斗。

 

day1

模拟赛,看了看提高a组t1的样例就不太想写,于是转而写b组

 

t1:

Description

给定一个n个点m条边的有向图,有k个标记点,要求从规定的起点按任意顺序经过所有标记点到达规定的终点,问最短的距离是多少。
 

Input

第一行5个整数n、m、k、s、t,表示点个数、边条数、标记点个数、起点编号、终点编号。

接下来m行每行3个整数x、y、z,表示有一条从x到y的长为z的有向边。

接下来k行每行一个整数表示标记点编号。

Output

输出一个整数,表示最短距离,若没有方案可行输出-1。

 

 

找出来k个标记点和起点到所有点的最短路,然后dfs经过k个点的顺序就可以啦!

 

当时主要犯了两个错误,1.没有判无解情况,2.设的初值为0x3f3f3f3f,有点小。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct NODE
{
    int flg[11],cur;
    long long dis;
};
struct Edge
{
    int v,nxt,val;
}e[100010];
int head[50010],n,m,k,s,t,cnt,flg,pa;
long long dis[50010][11],vis[50010],num[50010];
int cut[50010];
long long ans;
void add(int u,int v,long long val)
{
    e[++cnt].nxt=head[u];
    e[cnt].v=v;
    e[cnt].val=val;
    head[u]=cnt;
}
void spfa(int st,int now)
{
    queue<int>q;
    for(int i=1;i<=n;i++)
        dis[i][now]=0xffffffff;
    for(int i=1;i<=n;i++)
        vis[i]=0;
    dis[st][now]=0;
    vis[st]=1;
    q.push(st);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(dis[v][now]>dis[u][now]+e[i].val)
            {
                dis[v][now]=dis[u][now]+e[i].val;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
void dfs(int lst_cur,int lst_num,long long ndis)
{
    if(lst_num==k)
    {
        if(dis[t][lst_cur]==0xffffffff)
            return;
        ndis+=dis[t][lst_cur];
        ans=min(ans,ndis);
        ndis-=dis[t][lst_cur];
        flg=1;
        return ;
    }
    for(int i=1;i<=k;i++)
    {
        if(vis[i])
            continue;
        if(dis[cut[i]][lst_cur]==0xffffffff)
            continue;
        vis[i]=1;
        ndis+=dis[cut[i]][lst_cur];
        dfs(i,lst_num+1,ndis);
        ndis-=dis[cut[i]][lst_cur];
        vis[i]=0;
    }
    return;
}
int main()
{
    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        long long z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    if(k==0)
    {
        spfa(s,0);
        if(dis[t][0]==0xffffffff)
            dis[t][0]=-1;
        printf("%lld",dis[t][0]);
    }
    else
    {
        cut[0]=s;
        for(int i=1;i<=k;i++)
        {
            scanf("%d",&cut[i]);
        }
        for(int i=0;i<=k;i++)
            spfa(cut[i],i);
        for(int i=1;i<=k;i++)
            vis[i]=0;
        ans=0xffffffff;
        dfs(0,0,0);
        if(!flg)
            cout<<"-1";
        else
            printf("%lld",ans);
    }
    return 0;
}

 

t2:

Description

万老师听说某大国很流行穿越,于是他就想写一个关于穿越的剧本。

闲话休提。话说老师穿越到了某一个剑与魔法的大陆。因为如此这般,所以老师从维娜艾那里得到了预言。老师一共被告知了若干件按顺序结算的事件。这些事件分为两类:战役事件(CASE)、穿越回去事件(END)。战役事件可以选择是否参加,参加了之后会获得一定的金钱。每个END事件发生需要至少参加一定数量的战役事件。特别的是,END事件如果满足要求就会强制发生。老师希望在大陆玩个够,所以他要求只有最后一个END事件会发生。老师希望获得最多的金钱,所以求助于你。   
 

Input

第一行一个数N,表示输入文件有多少行。

接下来每一行用空格隔开一个字符和一个整数。字符为“c”表示战役事件,接下来的整数表示这次涨RP顺带有多少钱;字符为“e”表示穿越回去事件,接下来的整数代表至少要涨多少RP。最后一个事件保证是END事件。   

Output

第一行一个整数,最多金钱数目。

若不可能则输出-1。

维护一个小根堆,每次遇见限制就弹出堆顶直到满足限制条件。这道题爆零爆的非常郁闷,特别注意一下最后一个条件只要rp大于要求就行,我理解错题意了,认为必须等于,于是用正确的方法却爆了零...

 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
priority_queue<int>q;
int main()
{
    int n,cnt=0;
    int flg=0;
    char c;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        cin>>c;
        if(c=='c')
        {
            int x;
            scanf("%d",&x);
            q.push(-x);
            cnt++;
        }
        if(c=='e')
        {
            int x;
            scanf("%d",&x);
            if(x==0)
                flg=1;
            x--;
            while(q.size()>x)
            {
                q.pop();
            }
        }
    }
    cin>>c;
    int p;
    scanf("%d",&p);
    int ans=0;
    if(q.size()<p)
        flg=1;
    else
    {
        while(!q.empty())
        {
            int t=q.top();
            q.pop();
            ans-=t;
        }
    }
    if(flg)
        ans=-1;
    cout<<ans;
    return 0;
}

 

t3:

平面上有n个点,求出用这些点可以构成的三角形数。

 

Input

第一行一个整数n。

接下来n行,每行两个整数,表示点的坐标。

Output

输出仅一个整数,表示所求答案。

 

当时很懵,强行打了个n^3暴力,用斜率判是否共线,给了50分(贼良心呀)。

 

正解是枚举一个点,求此点与其他点的斜率,斜率相同说明共线。记得不要重复计算。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long c[3010][5],ans;
double lk[3010];
struct NODE
{
    int x,y;
}node[3010];
bool cmp(NODE a,NODE b)
{
    if(a.y==b.y)
        return a.x<b.x;
    else
        return a.y<b.y;
}
int main()
{
    freopen("triangle.in","r",stdin);
    freopen("triangle.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=0;i<=3010;i++)
        c[i][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=3;j++)
            c[i][j]=c[i-1][j-1]+c[i-1][j];
    ans=c[n][3];
    for(int i=1;i<=n;i++)
        scanf("%d%d",&node[i].x,&node[i].y);
    sort(node+1,node+1+n,cmp);
    int nn=n-1;
    for(int i=1;i<nn;i++)
    {
        int con=0,tot=0;
        for(int j=i+1;j<=n;j++)
        {
            if(node[j].x==node[i].x)
            {
                tot++;
                continue;
            }
            lk[++con]=(double)(node[j].y-node[i].y)/(double)(node[j].x-node[i].x);
        }
        sort(lk+1,lk+1+con);
        ans-=c[tot][2];
        tot=1;
        for(int j=2;j<=con;j++)
        {
            if(lk[j]==lk[j-1])
                tot++;
            else
            {
                if(tot==1)
                    continue;
                ans-=c[tot][2];
                tot=1;
            }
        }
        if(tot!=1)
            ans-=c[tot][2];
    }
    cout<<ans;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

我这里还排了个序,其实应该不需要。

 

改完啦!

 

下午zzh的博客被(宋老师?)吐槽了(确实有点emmm),还吹了一波ez,说我们觉得这里条件不太好。其实我们上午被血虐。感觉这么说像是我们嫌弃人家纪中的条件,好像不太利于学校间同学的友谊。不过后来遇到了一个活泼可爱的纪中妹子,年龄比我们小,还非常dalao,感觉自己不仅菜,还老了。

 

转了转校园,爬了爬山,晚上还听纪中可爱的妹子讲了讲山上的蛇和盆大的蛾子(看上去是这么大)。食堂的饭比第一天好吃,开心。校园环境很好,有很多没怎么见过的植物,可惜我都不太认识......

 

day2


上午杂题选讲,难度说是联赛到省选,但我不觉得哪道题是联赛难度,有很多不太了解的名词,比如多维线段树,感觉自己要滚粗了。讲课的纪中学长平均每道题给了我们快1个小时思考,导致很多同学去机房了,我太菜了并想不出来,快下课时也去了机房。

 

中午同学跟老师反应了一下,得到的反馈结果是后天的杂题选讲给提高a,b组的同学加一场考试,省选组的听课,感觉十分迷茫,好像还不如听课。喝了很多次食堂的汤,感觉无论是海带汤,玉米猪骨汤,冬瓜猪骨汤还是萝卜汤,味道都完全一样,非常神。感觉可能直到培训结束可能都用不完卡上的钱,以后得多买点什么东西。

 

晚上在学校里转了转,因为要上晚自习所以只转了一会,但校园真的是很大了,我们也就转了一半。整个学校就像一个大公园,周围有一圈教学楼宿舍什么的,学校旁边好像还有个中山城。jzz的手机没关就放包里了,以至于我收到好几个迷之电话,对面一直没声音那种。直到电话那头传来一声“那有个庙!”,同时sxy同学在前面大喊:“那有个庙!”我才反应过来可能是jzz的手机。然而庙也是不存在的,那好像是中山纪念堂,而且还关着门不能进去,遗憾。


讲了很多题,把做了的分类整一下?

dp部分

1.bzoj2298

 

这道题有一个很神的思路。就是说把每个人成绩的范围看成一条线段,然后dp求不重叠的覆盖。记得相同的边要合并一下,记录为边的权值。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,f[100010],cnt;
struct Node
{
    int l,r;
}e[100010];
bool cmp(Node a,Node b)
{
    if(a.r==b.r)
        return a.l<b.l;
    else
        return a.r<b.r;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a+b>=n)
            continue; 
        e[++cnt].l=a+1;
        e[cnt].r=n-b;
    }
    sort(e+1,e+1+cnt,cmp);
    int j=1;
    for(int i=1;i<=n;i++)
    {
        f[i]=f[i-1];
        while(e[j].r<i)
            j++;
        int tot=0;
        while(e[j].r==i)
        {
            if(e[j].l==e[j-1].l)
                tot++;
            else
                tot=1;
            f[i]=max(f[i],f[e[j].l-1]+min(i-e[j].l+1,tot));
            j++;
        }
    }
    cout<<n-f[n];
    return 0;
}