UPD：
哥哥们怎么都给差评啊QAQ @siyuan 说他想说这句话：
本来以为自己是300分的...结果 $\to$ T1 不判 $l==r$ $ 70 $ 分 + T2 题目玄学取模 $ 30 $ 分 + T3 错用大根堆 $ 0 $ .
最后还掉了分...
告诉我们千万不要再 自认为AK 后去做一些别的事情还有被别人瞎膜最后被奶死。
大体总结：基本全是结论题，全是坑的较为简单的（相比泡泡糖）的模拟赛 $qwq$
线段树什么的最讨厌了
发现一个长度为 $len$ 区间 $[l,r]$ 的父亲只有四种情况：$[l,r+len],[l-len,r],[l,r+len-1],[l-len-1,r]$
大力dfs即可
注意到当 $l == r$ 的时候这样做可能被艹，直接特判输出 $l$ 或 $-1$.
代码：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int long long
int T;
LL L,R,lim,ans;
void dfs(LL l,LL r){
if(r > lim || r > ans) return;
if(!l) {ans=r;return;}
int len = r-l+1;
if(len+r <= lim && l >= 2*len) dfs(l,r+len);
if(l-len >= 0) dfs(l-len,r);
if(r+len-1 <= lim && l >= 2*len-1) dfs(l,r+len-1);
if(!(l-len-1) || l-len-1 >= 2*len+1) dfs(l-len-1,r);
}
inline void Solve(){
scanf("%lld%lld%lld",&L,&R,&lim);
ans = LLONG_MAX;
if(L == R) {printf("%lld\n",L <= lim ? L : -1);return;}
dfs(L,R);
if(ans == LLONG_MAX) puts("-1");
else printf("%lld\n",ans);
}
signed main(){
scanf("%lld",&T);
while(T--) Solve();
return 0;
}
已经没有什么好害怕的了
考虑到合法的括号序列 $[l,r]$ 会对这个区间的点的贡献增加 $1$
差分一下直接搞就可以了。
注意到该题的取模十分毒瘤！加起来是不需要取模的。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int long long // important!!!
const int MAXN = 1000000 + 5;
const int ha = 1000000000+7;
int T,N;
char str[MAXN];
int st[MAXN],tp;
int l[MAXN],r[MAXN];
int rr[MAXN],ll[MAXN],f[MAXN];
LL ans;
inline void Solve(){
ans = 0ll;
scanf("%s",str + 1);
N = strlen(str + 1);
tp=0;CLR(l,0);CLR(r,0);CLR(ll,0);CLR(rr,0);CLR(f,0);
FOR(i,1,N){
if(str[i] == '(') st[++tp] = i;
else if(tp){
r[st[tp]] = i+1;
l[i+1] = st[tp--];
}
}
ROF(i,N+1,1) rr[l[i]] += ++rr[i];
FOR(i,1,N+1) ll[r[i]] += --ll[i];
FOR(i,1,N) f[i] = f[i-1] + rr[i] + ll[i];
FOR(i,1,N) ans = (ans + i*f[i]%ha);
printf("%lld\n",ans);
}
signed main(){
scanf("%lld",&T);
while(T--) Solve();
return 0;
}
我才不是萝莉控呢
由于只能向左走，考虑动态规划。
设 $f[i][j]$ 表示走到点 $(i,j)$ 的最小花费，转移有 $f[i][j] = min(f[i-1][j+1],f[i][(j+1)/2 + \sum_{k=i+1}^n a[k])$
注意到该转移方程十分像 Huffman 树的动态规划做法的转移方程： 设 $g[i][j]$ 表示已经放置了 $i$ 个点，还需要放置 $j$ 个点的最小代价，转移有 $f[i][j] = min(f[i+1][j-1],f[i][j*2] + \sum_{k=i+1}^n val[k])$，只是过程倒过来了而已。
直接用优先队列维护一下求出序列 $a$ 的 Huffman 树的权值即可。注意 priority_queue<int> 默认是大根堆！！！不要像我这样被坑死了！！！
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int long long //important
const int MAXN = 100000 + 5;
const int CANSIZE = 1000 + 5;
int N,x;
int a[MAXN],b[MAXN];
int f[CANSIZE][CANSIZE];
std::priority_queue<int,std::vector<int>,std::greater<int> > q;
inline void Solve(){
scanf("%lld",&N);
while(!q.empty()) q.pop();
FOR(i,1,N) scanf("%lld",&x),q.push(x);
int ans=0;
FOR(i,1,N-1){
int cnt=0;cnt += q.top();q.pop();
cnt += q.top();q.pop();q.push(cnt);
ans += cnt;
}
printf("%lld\n",ans);
}
signed main(){
int T;scanf("%lld",&T);
while(T--) Solve();
return 0;
}
