赛时rank10,T1 100,T2 0,T3 5,T4 100
T2的部分分懒得打了，T3特判的5分，也是没有打暴力。
T1,T4签到题
T1 酸碱度中和
二分加贪心的水题，时间复杂度\(O(n\log V)\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
#define int long long
const int N = 1e5 + 10;
int n,k,a[N];
inline bool check(int mid){
int res = 0,last = 0;
for(int i = 1;i <= n; ++i){
while(i <= n){
int midd = (a[i]+a[last+1])/2;
if(max(abs(a[last+1]-midd),abs(a[i]-midd)) <= mid) i++;
else break;
}
i--;
int midd = (a[i]+a[last+1])/2;
if(max(abs(a[last+1]-midd),abs(a[i]-midd)) <= mid) res++,last = i;
}
if(last != n) return false;
return res <= k;
}
signed main(){
#ifndef ONLINE_JUDGE
infile("in.in");outfile("out.out");
#else
#endif
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
cin>>n>>k;
for(int i = 1;i <= n; ++i) cin >> a[i];
sort(a + 1,a + 1 + n);
int l = 0,r = a[n],ans = 0;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid)) ans = mid,r = mid-1;
else l = mid + 1;
}
cout<<ans;
}
T2 聪明的小明
状压难题。
暴力搜索加特殊性质可以拿到30pts的高分，但由于懒，就没打。
由于\(k\)和\(m\)很小，考虑状压。
将每一种U8酒最后出现的位置设为1，其余全部为0，则112332记作010011，将其状压，则所有的二进制数中，1的个数恰好为k且最后一位为1的状态都是合法的。
设\(f_{i,S}\)表示以第\(i\)位为结尾，后\(m\)位的状态数为\(S\)的方案数，设上一位能够转移到的状态为\(S^\prime\)，则\(f_{i,S}=\sum f_{i-1,S^\prime}\)
对于每一种状态\(S\)，其合法的状态有很多，计算方式如下：
- 设\(res\)为方案数，\(num\)为当前已经枚举到的1的个数，从后往前枚举，若遇到一个1，则\(res\times=(k-num)\)
dp转移分情况讨论
- 若状态的第1位为1，则\(f_{i+1,j<<1|1}+=f_{i,j}\)
- 若状态的第1位位0，则\(f_{i+1,j<<1}+=f_{i,j}，f_{i+1,(j\,xor\,x)<<1|1}+=f_{i,j}(x\in \{2^k\}(2^k\le j))\)
转移即可
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
const int N = 1e5 + 10,mod = 998244353;
ll f[N][1<<10];
int n,m,k;
vector<int> sta;
inline int get(int x){
// cerr<<x<<'\n';
int res = 1,num = 0;
for(int i = 1<<(m-1);i>0;i >>= 1) res *= k-num,num += (bool)(x&i),res %= mod;
return res;
}
signed main(){
// #ifndef ONLINE_JUDGE
// infile("in.in");outfile("out.out");
// #else
// #endif
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
cin>>n>>k>>m;
int ed = (1<<m);
for(int i = 0;i < ed; ++i)
if(__builtin_popcount(i) == k && (i&1)) sta.push_back(i);
for(auto i : sta) f[m][i] = get(i);
for(int i = m;i < n; ++i){
for(auto j : sta){
bool flag = j&(1<<m);
if(flag) f[i+1][(j<<1)|1] = (f[i+1][(j<<1)|1]+f[i][j])%mod;
else{
(f[i+1][j<<1] += f[i][j])%=mod;
for(int x = 1;x <= j; x <<= 1)
if(j&x) (f[i+1][((j^x)<<1)|1] += f[i][j])%=mod;
}
}
}
ll ans = 0;
for(auto j : sta) ans = (ans + f[n][j]) % mod;
cout<<ans;
}
T3 线段树
赛时想过区间dp，但不会打……
\(f_{l,r}\)下界显然为1，那么什么时候它的下界可以加1？
对于当前查询区间\([l,r]\)，在线段树上有一个区间\([L,R]\)，从\(k\)处划分该区间，若\([L,R]\)与\([l,r]\)有交且互不包含，且\([l,r]\)经过\(k+0.5\)，则必须要走\([L,R]\)的两颗子树，下界加一。
设\(dp_{i,j}\)表示在线段树上的一个区间\([i,j]\)其子树内产生的贡献的最小值。则有
\[dp_{i,j}=\min_{k=i}^{j-1}\{dp_{i,k}+dp_{k,j}+sum(i,j,k)\} \]\(sum(i,j,k)\)表示与区间\([i,j]\)有交且互不包含，经过\(k+0.5\)的查询区间个数。
考虑如何查询这个东西。
设\(w1_k\)表示经过\(k+0.5\)的位置的区间个数，\(w2_{l,r}\)表示包含区间\([l,r]\)的查询区间个数。
有\(num(l,r,k)=w1_k-w2_{l,r}\)
求\(w1\)是水，考虑如何求\(w2\)。
考虑使用二维前缀和，\(w2_{l,r} = w2_{l,r}+w2_{l-1,r}+w2_{l,r+1}-w2_{l-1,r+1}\)
然后就可以了
场上就是没有想到w2，然后就没打……
\(CaI_2\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
const int N = 510;
ll f[N][N],n,q,sum[N][N],w[N];
signed main(){
#ifndef ONLINE_JUDGE
infile("in.in");outfile("out.out");
#else
#endif
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
cin>>n>>q;
for(int i = 1,l,r;i <= q; ++i){
cin>>l>>r;sum[l][r]++;
w[l]++,w[r]--;
}
for(int i = 1;i <= n; ++i) w[i] += w[i-1];
for(int len = n - 1;len >= 1; --len){
for(int l = 1;l + len - 1 <= n; ++l){
int r = l + len - 1;
sum[l][r] = sum[l][r] + sum[l-1][r] + sum[l][r+1] - sum[l-1][r+1];
}
}
for(int len = 2;len <= n; ++len){
for(int l = 1;l + len - 1 <= n; ++l){
int r = l + len - 1;
f[l][r] = LLONG_MAX;
for(int k = l;k < r; ++k){
f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+w[k]-sum[l][r]);
}
}
}
cout<<f[1][n]+q<<'\n';
}
T4 公路
简单题，贪心即可。
设当前位置为\(now\),它能走到的最远位置为\(max\)，假设这段区间内有比当前位置的花费小的位置\(y\)，则在此处加油，直至恰好走到\(y\)。若没有，在当前位置加满油，找出区间内最小的位置\(y\)，走到这个位置即可。可以用单调队列维护，也可以用ST表、线段树维护。
单调队列:(come from wang54321)
点此查看代码
#include<bits/stdc++.h>
#define llt long long
const llt N=100010;
const llt mod=998244353;
using namespace std;
llt n,C,cnow,v[N],c[N],ans;
deque<llt> L,P;
int main()
{
#ifdef LOCAL
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
scanf("%lld%lld",&n,&C);
for(int i=2;i<=n+1;i++) scanf("%lld",&v[i]);
for(int i=1;i<=n;i++) scanf("%lld",&c[i]),c[n+1]=0;
for(int i=1;i<=n+1;i++)
{
cnow-=v[i];
while(!P.empty()&&L.front()<=v[i]) v[i]-=L.front(),L.pop_front(),P.pop_front();
L.front()-=v[i];
while(!P.empty()&&P.back()>=c[i]) cnow-=L.back(),ans-=L.back()*P.back(),L.pop_back(),P.pop_back();
ans+=(C-cnow)*c[i];
P.push_back(c[i]),L.push_back(C-cnow);
cnow=C;
}
printf("%lld\n",ans);
return 0;
}
ST表:
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
#define int long long
const int N = 1e5 + 10;
int n,c,v[N],a[N];
#define mk make_pair
pair<int,int> st[18][N];
inline void pre(){
for(int i = 1;i <= n; ++i) st[0][i] = mk(a[i],i);
int t = log2(n) + 1;
for(int j = 1;j <= t; ++j){
for(int i = 1;i + (1<<j) - 1 <= n; ++i){
st[j][i] = min(st[j-1][i],st[j-1][i+(1<<(j-1))]);
}
}
}
inline pair<int,int> query(int l,int r){
int k = log2(r-l+1);
return min(st[k][l],st[k][r-(1<<k)+1]);
}
signed main(){
#ifndef ONLINE_JUDGE
infile("in.in");outfile("out.out");
#else
#endif
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
cin>>n>>c;
for(int i = 2;i <= n + 1; ++i) cin>>v[i];
for(int i = 1;i <= n; ++i) cin>>a[i];
for(int i = 2;i <= n + 1; ++i) v[i] += v[i - 1];
pre();
ll ans = 0;
int nxxt = 1,now = 1,res = 0;
while(now<=n){
while(nxxt <= n+1 && v[nxxt] - v[now] <= c){
nxxt++;
if(a[nxxt-1] < a[now]) break;
}
nxxt--;
if(now == n){
ans += (v[n+1]-v[n]-res)*a[now];
res = 0;break;
}
pair<int,int> emm = query(min(now+1,n),min(nxxt,n));
int mnval = emm.first,mnpos = emm.second;
if(nxxt == n + 1){
if(mnval < a[now]){
ans += (v[mnpos]-v[now]-res)*a[now];
now = mnpos;
res = 0;
continue;
}
else{
ans += (v[n+1]-v[now]-res)*a[now];
now = n+1;
res = 0;
break;
}
}
else{
if(mnval < a[now]){
ans += (v[mnpos]-v[now]-res)*a[now];
now = mnpos;
res = 0;
continue;
}
else{
ans += (c-res)*a[now];
res = c-(v[mnpos]-v[now]);
now = mnpos;
continue;
}
}
}
cout<<ans;
}
线段树：(from abnormal123)
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+100,INF=1e9;
int n,c,v[N],a[N],sum[N],oil,mon;
struct node{
int id,va;
}t[N<<2];
void pushup(int rt){
if(t[rt<<1].va<=t[rt<<1|1].va){
t[rt].va=t[rt<<1].va;
t[rt].id=t[rt<<1].id;
}
else{
t[rt].va=t[rt<<1|1].va;
t[rt].id=t[rt<<1|1].id;
}
}
void build(int rt,int l,int r){
if(l==r){
t[rt].id=l;
t[rt].va=a[l];
return ;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
}
int get(int x){
int l=1,r=n;
if(sum[n]<=x)return n-1;
while(l<r){
int mid=(l+r)>>1;
if(sum[mid]<=x)l=mid+1;
else r=mid;
}
return l-1;
}
node query(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R)return t[rt];
int mid=(l+r)>>1;
node x={INF,INF},y={INF,INF} ;
if(mid>=L)x=query(rt<<1,l,mid,L,R);
if(mid+1<=R)y=query(rt<<1|1,mid+1,r,L,R);
if(x.va<=y.va)return x;
else return y;
}
signed main()
{
// freopen("q.in","r",stdin);
// freopen("q.out","w",stdout);
scanf("%lld%lld",&n,&c);
for(int i=0;i<n;i++){
scanf("%lld",&v[i]);
sum[i+1]=sum[i]+v[i];
}
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
}
build(1,0,n-1);
int i;
for(i=0;i<n;){
int to=get(sum[i]+c),now=i;
if(i+1==n){
if(oil<sum[n]-sum[i]){
mon+=(sum[n]-sum[i]-oil)*a[i];
}
break;
}
node minn=query(1,0,n-1,i+1,to);
if(minn.va<=a[now]){
while(a[++i]>a[now]&&i<n);
if(oil>=sum[i]-sum[now])oil-=(sum[i]-sum[now]);
else {
mon+=(sum[i]-sum[now]-oil)*a[now];
oil=0;
}
}
else if(sum[i]+c>=sum[n]){
if(oil<sum[n]-sum[now]){
mon+=(sum[n]-sum[now]-oil)*a[now];
}
break;
}
else{
i=minn.id;
mon+=(c-oil)*a[now];
oil=c-(sum[i]-sum[now]);
}
}
cout<<mon<<endl;
}
糖丸了，每次模拟赛都是赛时想到了正解然后要么不会打，要么自己给自己否了。
dp学的不行，主要是推不出柿子，还是要多练。