中山纪念中学培训游记
2018-08-05
day0
去机场的路上，莫名有点开心，像是要出去玩一样
飞机延误了一会，起飞时很平稳，耳朵毫无不适，当时的我在内心赞美机长。把午饭（除了橘子）基本全解决掉了，还有时间睡一会。飞上云层后景色真的很漂亮，sjz上方有一层乌云，从上方看就像灰蓝色的海面，上面漂浮着许多形态各异的白云（白得刺眼），像漂浮在海面上的冰山。结果飞机刚开始下降，左眼（和左脸那一片）就开始疼，可能是血管不适应气压变化。后来好了。
纪中挺漂亮的，绿化非常好。但是宿舍真的一般，食堂也不如ez好吃...一开始觉得汤（加了海带黄豆和姜什么的）的味道非常怪，后来觉得还可以。洗了下上衣，过程中就发现了死虫子x2，有点郁闷。挂蚊帐好不容易才挂好，也有点郁闷。
晚上在机房，jzoj死活注册不好。还有分组......唉。看了看以前的各种板子之类的，稍微留点印象。
忘了好多东西，现在有点虚。明明刚来，其实就有点想回去了【苦笑】。算了，艰苦奋斗，艰苦奋斗。
day1
模拟赛，看了看提高a组t1的样例就不太想写，于是转而写b组
t1:
找出来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事件会发生。老师希望获得最多的金钱，所以求助于你。
维护一个小根堆，每次遇见限制就弹出堆顶直到满足限制条件。这道题爆零爆的非常郁闷，特别注意一下最后一个条件只要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个点，求出用这些点可以构成的三角形数。
当时很懵，强行打了个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;
}
推荐阅读