JZ DAY3总结
体面略显古怪，我竟理解题目都理解了二十分钟。
小Y 最近学习了线段树，但是由于她的智商比较低，运用的还不是很熟练。于是小R 给了她一点练习题训练，其中有一道是这样的。
这是小R 写的线段树的一段建树代码：
void build(int x,int l,int r)
{
if (l == r) return;
int mid = (l + r) >> 1;
build(x << 1,l,mid);
build(x << 1,mid + 1,r);
}
只要调用buildtree(1,0,n) 就可以得到一颗线段树了。显然，一颗线段树一共有O(n) 个节点，因为每一个节点都代表了一个不同的区间，所以线段树上一共出现了O(n) 个不同的区间。
现在小R 给了你一个区间[l; r]，他想要你告诉他一个最小的n 使得区间[l; r] 出现在了用buildtree(1,0,n) 建出来的线段树中。
L,R <= 1e9，lim <= 2e9，L/(R - L +1) <= 2e3。
EEEE
考场首先是先打了一个三十分的暴力，代码如下
#include <cstdio>
using namespace std;
int t,ll,rr,lim;
bool check(int l,int r)
{
if (l == ll && r == rr) return 1;
if (l == r) return 0;
int mid = (l + r) >> 1;
bool p = 0;
p = p | check(l,mid);
p = p | check(mid + 1,r);
return p;
}
int main()
{
scanf("%d",&t);
while (t --)
{
scanf("%d%d%d",&ll,&rr,&lim);
bool p = 0;
if (ll == 0)
{
printf("%d\n",rr);
continue;
}
for (int i = rr; i <= lim; i ++)
{
if (check(0,i))
{
printf("%d\n",i);
p = 1;
break;
}
}
if (!p) printf("%d\n",-1);
}
}
OK中规中矩，无任何优化的暴力。
那么考场我总感觉这题不是很难，反复思索后我有了如下思路。
对于一个给定的区间L，R，那我可以按照这个给定的区间去推它的父亲节点，这个思路其实也不难。对于一个给定的区间，那么它的父亲节点有且仅有四种可能。（有个十分显而易见的结论就是左区间一定小于等于右区间）
因此父亲节点的四种可能分别为
L，2 * R - L;
L，2 * R - L + 1;
2 * L - R - 1，R;
2 * L - R - 2，R;
所以就是一个深搜，考场由于没有判深度所以出错也就没交。
下面是AC代码
#include <cstdio>
#define ll long long
using namespace std;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int l,r,lim,T;
int read()
{
int x = 0,w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}
return x * w;
}
ll min(ll a,ll b) {return a < b ? a : b;}
ll build(ll l,ll r,int dep)
{
if (l == 0 && r <= lim) return r;
if (dep > 11) return inf;
ll res = inf;
if (r + (r - l) <= lim) res = min(build(l,r + (r - l),dep + 1),res);
if (l - 1 - (r - l) >= 0) res = min(build(l - 1 - (r - l),r,dep + 1),res);
if (r + (r - l) + 1 <= lim) res = min(build(l,r + (r - l) + 1,dep + 1),res);
if (l - 1 - (r - l) - 1 >= 0) res = min(build(l - 1 - (r - l) - 1,r,dep + 1),res);
return res;
}
int main()
{
T = read();
while (T --)
{
l = read(),r = read(),lim = read();
if (l == 0)
{
printf("%d\n",r);
continue;
}
ll x = build(1ll * l,1ll * r,1);
if (x != inf) printf("%lld\n",x); else printf("%d\n",-1);
}
}
小Y 最近开始学习算法姿势，但是因为小R 非常BB，给了她很多B6 题，所以她觉得自己已经没有什么前途了。于是小R 给了她一些稍微简单的题，让她觉得已经没有什么好害怕的了，其中一道是这样的：
给定一个长度为n 只包含左括号和右括号的序列，现在小R 想要知道经过每一个位置的合法子串有多少个。
空串是一个合法的串，如果A 和B 都是合法的串，那么(A) 和AB 都是合法的串。
考场最后三十分钟才思考这道题，且并未做出什么有效思考，因此直接零分。后面得知是差分+栈，暂时还没做出来，若我还记得，做出来会补上。
小Y：“小R 你是萝莉控吗。”小R：“…”
为了避免这个尴尬的话题，小R 决定给小Y 做一道题。
有一个长度为n 的正整数数组A，满足Ai >= Ai+1，现在构造一个数组B，令Bi = sigma a[j] （j = i to n )。
现在，有一个n * n 的网格图，左下角坐标是(1, 1)，右上角坐标是(n, n)。有一个小SB正在坐标为(n, 1) 的位置，每一时刻，如果他现在在(x, y)，他可以选择走到(x -1,y + 1) 或者(x, (y + 1) div 2)，如果选择后者，他要支付Bx的代价。
现在他想走到(1, 1)，你可以告诉他他支付的代价最少是多少吗？注意在任何时候他都不能离开这个网格图。
对于30% 的数据，n <= 10
对于50% 的数据，n <=1000
对于100% 的数据，n<= 10^5，1 <= T<= 10，1 <= Ai<= 10^4
考场一看感觉可做度挺高，便先思考了最后一题。首先拿下三十分的广搜暴力。代码如下
#include <cstdio>
#include <queue>
#include <cstring>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
struct Node{
int x,y;
ll sum;
};
int T,n,a[maxn];
ll b[maxn],v[5010][5010],ans;
queue <Node> q;
ll min(ll a,ll b) {return a < b ? a : b;}
int read()
{
int x = 0,w = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}
return x * w;
}
int main()
{
T = read();
while (T --)
{
while (!q.empty()) q.pop();
ans = 0x3f3f3f3f3f3f3f3f;
memset(v,0x3f,sizeof v);
memset(b,0,sizeof b);
memset(a,0,sizeof a);
n = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
b[n] = 1ll * a[n];
for (int i = n - 1; i >= 1; -- i) b[i] = b[i + 1] + 1ll * a[i];
v[n][1] = 0;
q.push(Node{n,1,0});
while (!q.empty())
{
Node u = q.front();
q.pop();
if (u.x - 1 >= 1 && u.y + 1 >= 1 && u.x - 1 <= n && u.y + 1 <= n && v[u.x - 1][u.y + 1] > u.sum)
{
v[u.x - 1][u.y + 1] = u.sum;
q.push(Node{u.x - 1,u.y + 1,u.sum});
}
if (v[u.x][(u.y + 1) / 2] > u.sum + b[u.x])
{
v[u.x][(u.y + 1)/ 2] = u.sum + b[u.x];
q.push(Node{u.x,(u.y + 1) / 2,u.sum + b[u.x]});
}
ans = min(ans,v[1][1]);
}
printf("%lld\n",ans);
}
return 0;
}
然后我竟然直接跳过了五十分的spfa，直接思考100分做法（当然没想出来），我考场想到了这一定符合某种规律，最后竟然直接套一个合并果子就过了（或哈夫曼树）。
#include <cstdio>
#include <algorithm>
using namespace std;
int T,n,a[100010],ans;
int main()
{
scanf("%d",&T);
while (T --)
{
scanf("%d",&n);
for (int i = 1; i <= n; i ++) scanf("%d",&a[i]);
ans = 0;
sort(a + 1,a + 1 + n);
int j = 1;
while (1)
{
if (j == n) break;
else
{
a[j] += a[j + 1];
ans += a[j];
for (int i = j + 1; i < n; i ++)
{
a[i] = a[i + 1];
}
n --;
}
for (int i = j; i < n; i ++)
{
if (a[i] > a[i + 1])
{
swap(a[i],a[i + 1]);
} else break;
}
}
printf("%d\n",ans);
}
return 0;
}
至于为什么可以直接套一个合并果子，暂时还不是非常理解，还需学习。
今天最终得分30 + 0 + 30；
PS.前两天的比赛明天补上