SDWC补题计划
2018的寒假去了SD的冬令营，因为一班二班难度悬殊，对我很不友好，几乎什么也没学会，但是我把两个班的课件都存了下来，现在慢慢把两个班的例题以及课后题都补一补（毕竟冬令营的钱不能白花）。
这些题目横跨各大知名题库以及一大批外国题库，以至于我注册了一批新账号......
基础班Day1：
这一天的课事实上我并没有去听，而是去二班考试并愉快的爆零了，幸好不大难，自己看也能学会。
Day1主要讲了队列，栈，堆，（加权）并查集。还提出了“因为数组也是数据结构，所以一切题目都是数据结构题”的精彩言论。
UVA514 Rails：https://www.luogu.org/problemnew/show/UVA514
题目概述：（火车，铁轨，车厢……）有一个无限大的栈，按照1-n的顺序依次入栈，询问是否能生成给定的出栈序。
栈的题目，模拟。以前练习初赛时见过这种题的手画版本...事实上也就是那个思路。如果现在想让一个数出栈，可是它还没入栈，就不停的入栈直到它入栈后再弹出；如果它已经在栈里，则必须是栈顶，否则就无法生成这个序列。这题在洛谷上难度虚高，主要是读入很奇妙；输出时如果n将要变化了，要换行，样例里却没换，导致很容易wa。
# include <cstdio>
# include <iostream>
# include <cstring> using namespace std; int n;
int a[],sta[],h=,q=,s=; int main()
{
scanf("%d",&n);
while (n)
{
memset(a,,sizeof(a));
scanf("%d",&a[]);
while (a[]!=)
{
for (int i=;i<=n;i++)
scanf("%d",&a[i]);
q=s=;
h=;
for (int i=;i<=n;++i)
{
while(s<=a[i])
sta[++h]=s++;
while(sta[h]==a[q])
q++,h--;
}
if(s!=n+||h!=||q!=n+)
printf("No\n");
else
printf("Yes\n");
scanf("%d",&a[]);
}
printf("\n");
scanf("%d",&n);
}
return ;
}
Rails
NOI2001 食物链:https://www.luogu.org/problemnew/show/P2024
题目概述：有三种动物，食物关系竟然形成了一个环（好不科学啊），给出一些描述：A被B吃，A吃B，A与B是同类，默认先说的话是正确的，并以此判断一共有几句假话。
这大概是加权并查集最著名的习题了，也可以不用加权做，注意一下加权并查集的路径压缩，还是挺容易写错的。(做完这个题，你的并查集就算入门了---loli)
int father(int x)
{
if (x!=f[x])
{
int aa=father(f[x]);
v[x]=(v[x]+v[f[x]])%;
f[x]=aa;
}
return f[x];
}
加权并查集_路径合并
有一个地方一定要想清楚，在同一个并查集里的元素并不一定是同种生物，只是可以确定相对的关系，如果这里明白了也就比较简单了。
带权并查集的集合合并也别写错啦...就是解一个方程。
# include <cstdio>
# include <iostream> using namespace std; int f[]={},v[]={}; int n,k,x,y,z,S=; int father(int x)
{
if (x!=f[x])
{
int aa=father(f[x]);
v[x]=(v[x]+v[f[x]])%;
f[x]=aa;
}
return f[x];
} bool Ya(int x,int y,int z)
{
int a=father(y);
int b=father(z);
if (a==b)
{
if(x==)
{
if(v[y]==v[z]) return true;
return false;
}
if (x==)
{
if(v[z]-v[y]!=-&&v[z]-v[y]!=) return false;
return true;
}
}
if (a!=b)
{
if(x==)
{
v[b]=(v[y]-v[z]+)%;
f[b]=a;
}
if (x==)
{
v[b]=(v[y]-v[z]+)%;
f[b]=a;
}
return true;
}
} int main()
{
scanf("%d%d",&n,&k);
for (int i=;i<=n;i++)
{
f[i]=i;
v[i]=;
}
for (int i=;i<=k;i++)
{
scanf("%d%d%d",&x,&y,&z);
if (z>n||y>n)
S++;
else
if (y==z&&x==) S++;
else
if (Ya(x,y,z)==false) S++;
}
printf("%d",S);
return ;
}
食物链
合并果子：https://www.luogu.org/problemnew/show/P1090
题意概述：合并两堆果子的代价是两堆重量之和，要求将n堆果子合并成一堆，求最小代价。
贪心的想一想发现每次选最小的两堆合并就是最优的。用堆是可以的，也可以用两个队列：首先排序作为第一个队列，每次新合并出来的放进第二个队列末尾，两个队列都是单调的，如果再用一个桶排序就可以达到$O(N)$，但是懒得写...
# include <cstdio>
# include <iostream> using namespace std; int a,H[]={},r=,n,po,M,t; void push(int x)
{
po=++r;
while(x<H[po/])
{
H[po]=H[po/];
po=po/;
}
H[po]=x;
} void Heapify(int x)
{
M=x;
if (r>=x*+&&H[M]>H[x*+]) M=x*+;
if (r>=x*&&H[M]>H[x*]) M=x*;
if (M!=x)
{
t=H[x];
H[x]=H[M];
H[M]=t;
Heapify(M);
}
} void pop()
{
if (r==)
{
H[]=;
r=;
return;
}
H[]=H[r--];
Heapify();
} int main()
{
int x,y,S=;
scanf("%d",&n);
for (int i=;i<=n;i++)
{
scanf("%d",&a);
push(a);
}
for (int i=;i<n;i++)
{
x=H[]; pop();
y=H[]; pop();
S+=x+y;
push(x+y);
}
cout<<S;
return ;
}
合并果子
蚯蚓：https://www.luogu.org/problemnew/show/P2827
题意概述：有n根蚯蚓，每次选出一根最长的切成给定比例的两段，同时其他的蚯蚓长度增加一个常数，求每次被切断的蚯蚓长度。
首先可以反着想，认为是被剪了的蚯蚓长度减少一个常数，就可以用堆维护了，听起来非常棒，而且很符合今天的上课内容，然而T掉了。那么正解是什么呢？和上一道题一样，又是队列...因为我们是用缩短长度的做法做的，所以每次取出的最长蚯蚓的长度是单调递减的，又因为比例相同，所以切成的两段也是递减的，所以就是三个递减的队列了。
# include <cstdio>
# include <iostream>
# include <algorithm>
# include <cstring>
# define R register int using namespace std; int h_1=,t_1=,h_2=,t_2=,h_3=,t_3=,n,m,q,t;
long long x_1,x_2,x,u,v;
long long q_1[],q_2[],q_3[],ans;
const int inf=-1e8; bool cmp(long long a,long long b)
{
return a>b;
} int main()
{
scanf("%d%d%d%lld%lld%d",&n,&m,&q,&u,&v,&t);
memset(q_1,,sizeof(q_1));
memset(q_2,,sizeof(q_2));
memset(q_3,,sizeof(q_3));
for (R i=;i<=n;++i)
scanf("%lld",&q_1[i]);
sort(q_1+,q_1++n,cmp);
for (R i=;i<=m;++i)
{
if(q_1[h_1]>=q_2[h_2]&&q_1[h_1]>=q_3[h_3])
x=q_1[h_1++];
else if(q_2[h_2]>=q_1[h_1]&&q_2[h_2]>=q_3[h_3])
x=q_2[h_2++];
else if(q_3[h_3]>=q_2[h_2]&&q_3[h_3]>=q_1[h_1])
x=q_3[h_3++];
x=x+(i-)*q;
if(i%t==) printf("%lld ",x);
x_1=u*x/v;
x_2=x-x_1;
q_2[++t_2]=x_1-i*q;
q_3[++t_3]=x_2-i*q;
}
printf("\n");
for (R i=;i<=n+m;++i)
{
if(q_1[h_1]>=q_2[h_2]&&q_1[h_1]>=q_3[h_3])
ans=q_1[h_1++];
else if(q_2[h_2]>=q_1[h_1]&&q_2[h_2]>=q_3[h_3])
ans=q_2[h_2++];
else if(q_3[h_3]>=q_2[h_2]&&q_3[h_3]>=q_1[h_1])
ans=q_3[h_3++];
if(i%t==) printf("%lld ",ans+m*q);
}
return ;
}
蚯蚓
Largest Rectangle in a Histogram：http://poj.org/problem?id=2559
Open Gold - Trapped in the Haybales：https://www.lydsy.com/JudgeOnline/problem.php?id=4099
这在bzoj上是个权限题，usaco上肯定有，然而我找不到。。。下次借个权限号做。
基础班Day2：我把课件弄丢啦！！有好心人给我一份吗！
基础班Day3:
深搜、广搜，虽然是基础算法但是也有不少难题呢。
基础班Day4:
贪心，dp。
基础班Day5:
数论，倍增。
基础班Day6:
线段树与树状数组。
提高班Day1：
线段树，主席树。
提高班Day2：
数论。
提高班Day3:
计算几何。
提高班Day4:
动规及优化。
提高班Day5:
Splay，Lct，链剖，网络流，图论题目选讲。
提高班Day6:（老师跑路了没上课）
补完这些还有每天的考试题，也都是很好的题，感觉任务艰巨。
---shzr
最新文章
- 图片效果集合(js、jquery或html5)
- java环境搭建系列：JDK环境变量详细配置
- iBatis框架简介
- highcharts 设置标题不显示
- Oracle高级查询,事物,过程及函数
- Ajax中send方法参数的使用
- XML编辑工具
- 使用 webpack + react + redux + es6 开发组件化前端项目
- iBatis第四章：动态SQL的用法
- [LeetCode] Cheapest Flights Within K Stops K次转机内的最便宜的航班
- （转）Centos下，Docker部署Yapi接口管理平台
- 《python for data analysis》第五章，pandas的基本使用
- 贝叶斯公式52张牌猜黑桃A策略
- shiro源码篇 - 疑问解答与系列总结，你值得拥有
- 转://使用insert插入大量数据的总结
- Android环境搭建（大学授课课件）
- 网络编程基础【day09】：socketserver使用（九）
- Vue小案例 之 商品管理------添加商品
- iOS开发 关于iBeacon的一些记录
- Degree Set CodeForces - 976D（双指针）