前言
首先不要吐槽这个标题……我们也是为了彰显 53 这两个数字才选的这个名字， 并没有真的要你们模拟三年的意思。。 不知不觉我们 loi53 级也快要从 loi 毕业了， 省选之后可能就要有几个人离开， 回想在 loi 学习生活的点点滴滴总是感觉很温馨， 很快乐。 直到现在还以为自己是新生， 没想到已经快要到了离开的时候， 就让我们在 loi 留下一份印记， 把这份我们亲自准备的题目， 当作以后 loier 们的铺路石。
难度弱于 noip， 四道题时限三个小时。题目不难可以大胆去做。
好吧我们开始。
题目 爱疯 大神养兔子 禁地 基地占领
程序文件名 iphone.cpp rabbit.cpp forbidden. cpp craft.cpp
输入文件 iphone.in rabbit. in forbidden.in craft.in
输出文件 iphone.txt rabbit.out forbidden.out craft.out
时间限制 1s 1s 2s 2s
空间限制 64M 64M 256M 256M
1 爱疯
题目描述
土豪有一个神器：爱疯， 这款神器可以开 2048 位整型变量， 于是他在计算方面总是快人一步。 但有一天星云突然想和土豪比赛计算大数据。裁判由公正的凯文同学担任， 凯文同学知道爱疯这款神器的内幕： 2048 位整形变量并不是用二进制来计算， 而是说其计算的数的十进制长度可以达到 2048 位! 于是凯文就在这个范围内出题，星云的程序做不到那么厉害， 于是他找到了你。希望你能帮他解决这个问题。
输入数据
只有一行，第一个参数是一个字符， 加号代表要做加法运算， 减号代表要做减法运算，星号代表乘法运算， 后面有两个大正数， 三个参数间用空格隔开。减法保证前一个大于后一个。
输出数据
只有一行，为运算的结果。
输入样例
* 1 1
输出样例
1
题解：
高精度不讲……
2 大神养兔子
题目描述
loi 的 zkj 被班长 gz 派遣养兔子，为了实现规模化养殖，他很聪明地把很多个兔子窝建在一条笔直的道路旁，同时 zkj 比较懒，为了省事儿他要搭建规模都相等的兔子窝，所以每个兔子窝可以容纳的兔子数量都是相等的。 在这条笔直的道路旁，每个兔子窝（除了第一个和最后一个）都直接和相邻的两个兔子窝相连接，一只兔子一年要吃掉一吨胡萝卜，zkj 每年都会往兔子窝投放胡萝卜，每个兔子窝获得的胡萝卜数是不一样的。每个兔子窝获得的胡萝卜既可以窝内解决也可以运到其他兔子窝里，在运输过程中，每公里要上贡一顿胡萝卜作为过路费。已知每个兔子窝这一年获得的胡萝卜数，并假设运输方案是最佳的，计算 zkj 最多能养多少只兔子。
输入描述
输入文件第一行包含一个整数 N，1<=n<=100000，表示兔子窝总数。
接下来的 N 行每行包括两个整数 a 和 b，其中 1<=a<=1000000000，0<=b<=1000000000，分别表示兔子窝的位置（坐标）和该兔子窝获得的胡萝卜数，所有兔子窝按其位置从小到大排序给出，注意问题一定存在正整数解。
输出描述
输出文件仅一行，包含一个整数，表示每个兔子窝最多能养的兔子数。
样例输入
4
20 300
40 400
340 700
360 600
样例输出
415
题解：
首先，我们发现，其答案一定在一定范围内，所以可以二分。然后我们对答案进行二分，然后验证时，用贪心的思想，因为最后均分时，一定会有x多的资源从右边运到这个点，所以每次对答案贪心，然后判断最后那个点是否满足答案，如果满足，答案增大，否则，缩小答案。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int n;
ll pos[233333], fd[233333];
struct qer
{
ll pos, num;
}q[233333];
ll ls[233333];
int main()
{
freopen("rabbit.in", "r", stdin);
freopen("rabbit.out", "w", stdout);
cin>>n;
for(int i = 1;i <= n;i ++)
scanf("%I64d%I64d", &q[i].pos, &q[i].num);
ll l = 1, r = 1e9+1;
while(r - l > 1)
{
ll mid = (l+r)/2;
for(int i=1;i<=n;i++)
ls[i]=q[i].num;
for(int i = 1;i < n;i++)
{
if(ls[i]>mid)
ls[i+1]+=max((ll)0,ls[i]-mid-q[i+1].pos+q[i].pos);
if(ls[i]<mid)
ls[i+1]-=mid-ls[i]+q[i+1].pos-q[i].pos;
}
if(ls[n] >= mid)
l = mid;
else
r = mid;
}
cout<<l<<endl;
return 0;
}
3 禁地
题目描述
ix 和木易来到了 loi 门派的禁地之所。但是因为有复杂的阵法禁制他们无法进入， 于是在禁制外开始思考。
他们看到， 阵法是由 n 个从 1 到 n 标号的岛屿组成的， 岛屿之间由念力光线连接， 因为 ix 和木易拥有云中靴所以他们可以沿着念力光线通行， 即两个岛屿间只要有一条念力光线的存在， 那么他们就可以自由往返于两个岛屿间， 前提是他们的起始点要在其中的任意一个岛屿上。
他们两人在阵法里不断穿梭游动着……渐渐的忘记了他们来时的目的。
他们发现念力光线是有长度的， 于是 ix 想要计算一下连接阵法内各个岛屿使得各个岛屿都互相联通的最短光线长度， 但木易想要计算一下从他们现在所站的位置到阵法内任意一个岛屿的最短路径长度。 两人发生了争执， 因为声音过大激发了学长大神们留下的惩罚禁制之灵。
禁制之灵很不客气的让他们在 2s 之内计算出他们各自的问题， 但是 ix 和木易都是学过 oi 的所以很轻松的就切掉了， 禁制之灵便增大了难度， 它会多次询问并会在某两个岛屿之间添加一条念力光线。
因为 Ix 和木易实在是太弱了， 都不会做， 于是找到了学信息奥赛的你， 请你帮他们解决这个问题
输入格式
输入文件的第一行为两个正数 n, m 代表原阵法内的岛屿总数和念力光线总数。
以下 m 行， 每行三个正数 u, v, l. 代表每条念力光线连接的两个点以及其长度。
再一行只有一个正数 q， 代表操作数。
接下来每行先是一个正数 p, 若 p 为 1 则后面跟着两个正数 s, t。 请输出从 s 岛屿到 t 岛屿的最短路径长度；
若 p 为 2， 则输出连接阵法内各个岛屿使得各个岛屿都互相联通的最短光线长度；
若 p 为 3， 则后跟三个正数 a, b, d, 代表在 a, b 之间添加一条长度为 d 念力光线。
输出格式
与输入文件操作中 1, 2 操作数对应。
输入样例
5 8
1 2 4
2 3 6
3 4 2
4 5 6
1 3 2
1 3 8
2 5 3
4 1 5
5
1 1 5
2
3 1 5 1
1 1 5
2
输出样例
7
11
1
8
数据说明
0 <念力光线的长度<= 1000
保证所有岛屿都联通
数据共十个点， 对于：
N<= M<= Q<= 备注
点 1 10 100 10 询问中没有 2、3
点 2 10 100 1 询问中没有 1、3
点 3 10 100 10 询问中没有 3
点 4 100 1000 10
点 5 100 1000 100
点 6 100 1000 100
点 7 1000 10000 10
点 8 1000 10000 10
点 9 10000 100000 10
点 10 10000 100000 10
题解：
首先，我们看一下数据范围，极限数据的询问次数只有10次，而且时限为2s，所以我们就可以暴力跑。模板题，不仔细讲了。但要注意，kruskal和spfa不能用一个结构体。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n, m;
struct qer2
{
int from, to, cost;
}es2[233333];
struct qer
{
int from, to, cost;
}es[233333];
/*--------------------------------*/
int map[105][105], fa[233333], tot = 0, cnt = 1;
void floyd()
{
for(int k = 1;k <= n;k ++)
{
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= n;j ++)
{
map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
}
}
}
}
void builds(int f, int t, int d)
{
es2[cnt++] = (qer2){f, t, d};
}
bool cmp(qer2 a, qer2 b)
{
return a.cost < b.cost;
}
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
//--------------------------------------------
deque <int> q;
int first[233333], next[233333], d[233333];
bool used[233333];
void build(int f, int t, int d)
{
es[++tot] = (qer){f, t, d};
next[tot] = first[f];
first[f] = tot;
}
void init()
{
memset(first, -1, sizeof(first));
tot = 0;
}
void spfa(int s)
{
d[s] = 0;
used[s] = 1;
q.push_front(s);
while(!q.empty())
{
int u = q.front();
q.pop_front();
used[u] = 0;
for(int i = first[u];i != -1;i = next[i])
{
int v = es[i].to;
if(d[v] > d[u] + es[i].cost)
{
d[v] = d[u] + es[i].cost;
if(!used[v])
{
if(v < q.front())
q.push_front(v);
else
q.push_back(v);
used[v] = 1;
}
}
}
}
}
int main()
{
freopen("forbidden.in", "r", stdin);
freopen("forbidden.out", "w", stdout);
cin>>n>>m;
int q, p, s, t, c;
init();
for(int i = 1;i <= m;i ++)
{
int u, v, l;
scanf("%d%d%d", &u, &v, &l);
build(u, v, l);
build(v, u, l);
builds(u, v, l);
builds(v, u, l);
}
cin>>q;
for(int i = 1;i <= q;i ++)
{
memset(d, 0x3f, sizeof(d));
scanf("%d", &p);
if(p == 1)
{
scanf("%d%d", &s, &t);
spfa(s);
printf("%d\n", d[t]);
}
else if(p == 2)
{
int ans = 0;
for(int i = 1;i < cnt;i ++)
fa[i] = i;
sort(es2+1, es2+cnt, cmp);
for(int i = 1;i < cnt;i ++)
{
int x = es2[i].from, y = es2[i].to;
if(find(x) != find(y))
{
fa[find(x)] = find(y);
ans += es2[i].cost;
}
}
printf("%d\n", ans);
}
else if(p == 3)
{
scanf("%d%d%d", &s, &t, &c);
build(s, t, c);
build(t, s, c);
builds(s, t, c);
builds(t, s, c);
}
}
return 0;
}
4 基地占领
伟大的 cp 是一位懂得放松的好同学。他在放松的时候，经常玩一个名叫 loicraft 的即使战略类游戏。
这个游戏是有红蓝双方组成的，红方负责攻击，而蓝方负责挨揍。伟大的 cp 当然要当红方了。他经过侦查发现，蓝方的基地有 n 个，这 n 个基地恰好组成了一行的线性结构，从东到西依次标记为 1 到 n。比赛刚开始时，每一个基地都是完好的。比赛开始后，cp 学长为了尽早的打败对方，他使用了一种极其坑爹的武器：灵符。每一个灵符可以打坏区间[l,r]的全部基地。cp 共有 m 个灵符，因此他一定会攻击 m 次，每次攻击他都会攻击一个区间，但是，由于 cp 眼神不太好，因此他不能保证轰炸的这 m 个区间中不会出现重叠，也不能够保证这些区间不会出现包含一类的关系。换句话说，一个基地可能会被轰炸好多次。
现在，告诉你蓝方所有的基地数量 n、cp 的灵符数量 m 以及他每次攻击的区间[l,r]，请你输出他每次攻击后蓝方还没有被攻击的基地的数量。
输入格式
第一行两个整数 n（≤10^6），m（≤10^6）.
接下来共有 m 行，每行两个整数 l，r 表示他这次攻击的区间是[I,r]，输入数据保证 1≤ l ≤ r ≤ n.
输出格式
共 m 行，每行一个整数，表示此次攻击后蓝方还没有被攻击的基地的数量。
样例输入
10 3
3 7
1 2
2 5
样例输出
5
3
3
样例说明
第一次攻击[3,7]之后，还剩 1、2、8、9、10 号基地未被攻击。
第二次攻击[1,2]后，还剩 8、9、10 号基地未被攻击。
第三次攻击[2,5]后，还剩 8、9、10 号基地未被攻击。
其中，2，3，4，5 号基地被攻击了 2 次。
题解：
首先，我们发现它是区间修改，而且时限2s，空间也够，所以联想到线段树。但不知为什么，我就是wa一个点。。
但正解不是线段树，往下看：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
struct qer
{
int l, r;
int sum, add;
}tree[4000004];
void spread(int p)
{
if(tree[p].add)
{
tree[p*2].sum += (tree[p*2].r - tree[p*2].l + 1)*tree[p].add;
tree[p*2+1].sum += (tree[p*2+1].r - tree[p*2+1].l + 1)*tree[p].add;
tree[p*2].add += tree[p].add;
tree[p*2+1].add += tree[p].add;
tree[p].add = 0;
}
}
void build(int p, int l, int r)
{
tree[p].l = l;
tree[p].r = r;
if(l == r)
{
tree[p].sum = 1;
return ;
}
spread(p);
int mid = (l + r)/2;
build(p*2, l, mid);
build(p*2+1, mid+1, r);
tree[p].sum = tree[p*2].sum + tree[p*2+1].sum;
}
void change(int p, int l, int r, int x)
{
if(l <= tree[p].l && tree[p].r <= r)
{
tree[p].sum += (tree[p].r-tree[p].l+1)*x;
if(tree[p].sum <= 0)
tree[p].sum = 0;
tree[p].add += x;
return ;
}
spread(p);
int mid = (tree[p].l + tree[p].r)/2;
if(l <= mid) change(p*2, l, r, x);
if(r > mid) change(p*2+1, l, r, x);
tree[p].sum = tree[p*2].sum + tree[p*2+1].sum;
if(tree[p].sum < 0)
tree[p].sum = 0;
}
int main()
{
freopen("craft.in", "r", stdin);
freopen("craft.out", "w", stdout);
cin>>n>>m;
build(1, 1, n);
for(int i = 1;i <= m;i ++)
{
int l, r;
scanf("%d%d", &l, &r);
change(1, l, r, -1);
printf("%d\n", tree[1].sum);
}
return 0;
}
其实正解是并查集，因为这套题是NOIP-，所以不会考线段树。
关于并查集的做法，我会在另一篇文章中详细介绍，这里就先贴代码。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int fa[1000005];
queue <int> q;
int find(int x)
{
while(fa[x] != x)
{
q.push(x);
x = fa[x];
}
while(!q.empty())
{
int p = q.front();
q.pop();
fa[p] = x;
}
return x;
}
int main()
{
freopen("craft.in","r",stdin);
freopen("craft.out","w",stdout);
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1;i <= n+1;i ++)
fa[i] = i;
for(int i = 1;i <= m;i ++)
{
int l, r;
scanf("%d%d",&l, &r);
int ls = find(l);
while(ls <= r)
{
n--;
fa[ls] = ls+1;
ls = find(ls);
}
printf("%d\n", n);
}
return 0;
}