《南开大学数分I月考III在初赛开始四十分钟时结束》
早晨试图速成泰勒展开失败了
考试前 zsy 把 yzf 接到学校了,应该是国赛后第一次见 yzf
考完试发现 yzf 已经买好 KFC 了/bx,但因此迷路了。。。正好三人都少打 1h
分头签到,我开到《转化》了,真不喜欢这题但只能硬着头皮写,WA 了之后还摇了 yzf 来看
然后跟榜做《套娃》和《二进制》。yzf 给我讲了半天《套娃》我也没太懂,丢给 zsy 了
《二进制》很快会了 \(\log^2\) 平衡树+哈希(实际上是单 \(\log\),因为删除只有 \(\frac{n}{\log n}\) 次)。现学了一下分块+SAM 感觉没前途,发现可以把平衡树局部拍平求哈希值来减小常数就去写了,还剩 2h。先写了个不拍平的,跑了大约 15s。。。加上拍平后一直 RE 到结束,自闭了
yzf 把《一棵树》过了/bx
loj6903「THUPC 2024 初赛」转化
赛时代码
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx;
#define For(i,x,y,...) for(int i=x,##__VA_ARGS__;i<=(y);++i)
#define rFor(i,x,y,...) for(int i=x,##__VA_ARGS__;i>=(y);--i)
#define Rep(i,x,y,...) for(int i=x,##__VA_ARGS__;i<(y);++i)
#define pb emplace_back
#define sz(a) int((a).size())
#define all(a) begin(a),end(a)
#define fi first
#define se second
typedef long long LL; typedef vector<int> Vi; typedef pair<int,int> Pii;
auto ckmax=[](auto &x,auto y) { return x<y ? x=y,true : false; };
auto ckmin=[](auto &x,auto y) { return y<x ? x=y,true : false; };
sfmt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r) { return uniform_int_distribution<>(l,r)(mt); }
template<typename T=int>T read() { T x; cin>>x; return x; }
const int N = 351495;
int n;
LL a[N],b[N],c[N];
void sub1() {
LL sum = 0;
vector<pair<LL,LL>> d;
For(i,1,n)
if( a[i] ) sum += min(a[i],b[i]);
else if( b[i] ) d.pb(b[i],c[i]);
sort(all(d),greater<pair<LL,LL>>());
for(auto [b,c] : d) {
if( !sum ) break; --sum;
sum += min(1+c,b);
}
For(i,1,n)
if( a[i] ) cout<<a[i]+sum-min(a[i],b[i])<<' ';
else {
if( sum ) {
if( b[i] ) cout<<sum+1+c[i]-min(1+c[i],b[i])<<' ';
else cout<<sum+c[i]<<' ';
} else cout<<"0 ";
}
cout<<'\n';
}
void sub2() {
LL sum = 0, ans = accumulate(a+1,a+n+1,0ll);
vector<pair<LL,LL>> d;
For(i,1,n)
if( a[i] ) sum += min(a[i],b[i]);
else d.pb(b[i],c[i]);
sort(all(d),greater<pair<LL,LL>>());
for(auto [b,c] : d) {
if( !sum ) break; --sum;
ans += c, sum += min(1+c,b);
}
cout<<ans<<'\n';
}
signed main() {
#ifdef FT
freopen("in","r",stdin); freopen("out","w",stdout);
#endif
ios::sync_with_stdio(0);cin.tie(0);
cin>>n; For(i,1,n) cin>>a[i]; For(i,1,n) cin>>b[i];
For(i,1,n)
if( a[i] ) a[i] += read();
else cin>>c[i];
sub1(), sub2();
return 0;
}
LG9970 [THUPC 2024 初赛] 套娃
LG9968 [THUPC 2024 初赛] 二进制
赛时死因是重算哈希值时传的区间混了(整个区间还是左端点区间)。最后一版代码没在洛谷上交,不记得还有没有其他错了
哈希模 \(993244853\) 被卡了,自然溢出能过