目录
10.31 2020ICPC 小米 网络选拔赛第二场
运气太好了可以去北京玩啦!但是这运气不如换个au...
A.2020(贪心 二分)√
可以发现 (0)和左边最近的未匹配的(2)匹配 比 (0)和第一个未匹配的(2)匹配 优。
那么 (0)和左边最近的未匹配的(2)匹配 后，可以得到若干可能包含但不相交的区间。
区间(i)包含区间(j) 则(i,j)不能组成(2020)，否则一定可以。而区间不相交可以转化成树：每个区间(i)以最小的包含(i)的区间作为父节点。
这样建树后问题就是：每个点可以和除祖先外的所有点配对，求最大配对数。
设(mxd)为建树后某点的最大深度，(n)为点数，可以发现若(mxd*2leq n)则全部可以配对，答案为(frac n2)（每棵子树最多有(frac n2)个点，足够和其它子树全部匹配）；否则答案为(n-mxd)（一条链(mxd)个点+若干小支链(n-mxd)个点，显然只有(n-mxd)对能匹配）。
so求一个最大深度就ok。
也可以二分答案，贪心配对看是否可行。
//61ms 7288KB
#include <bits/stdc++.h>
#define gc() getchar()
typedef long long LL;
const int N=2e5+5;
int dep[N];
char s[N];
std::vector<int> e[N];
struct Node
{
int l,r;
bool operator <(const Node &x)const
{
return l==x.l?r<x.r:l<x.l;
}
}A[N];
inline int read()
{
int now=0,f=1; char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-48,c=gc());
return now*f;
}
inline void AE(int u,int v)
{
e[u].push_back(v), e[v].push_back(u);
}
void DFS(int x,int fa)
{
for(auto v:e[x])
if(v!=fa) dep[v]=dep[x]+1, DFS(v,x);
}
int main()
{
static int sk[N];
int n;
while(~scanf("%d",&n))
{
scanf("%s",s+1);
int t=0,cnt=0;
for(int i=1; i<=n; ++i)
if(s[i]=='2') sk[++t]=i;
else if(s[i]=='0'&&t) A[++cnt]=(Node){sk[t--],i};
if(!cnt) {puts("0"); continue;}
std::sort(A+1,A+1+cnt), A[sk[0]=0].r=2e9;
for(int i=1,t=0; i<=cnt; ++i)
{
while(A[i].l>A[sk[t]].r) --t;
AE(sk[t],i), sk[++t]=i;
}
DFS(0,0);
int mxd=0;
for(int i=1; i<=cnt; ++i) mxd=std::max(mxd,dep[i]);
printf("%d
",mxd<<1>cnt?cnt-mxd:cnt>>1);
for(int i=0; i<=cnt; ++i) std::vector<int>().swap(e[i]);
for(int i=0; i<=cnt; ++i) dep[i]=0;
}
return 0;
}
C.Data Structure Problem(线段树)√
对于(c_p)，如果存在一个最靠右的(i)使得(a_igeq c_{i-1}+b_i)，则(c_p=a_i+sum_{j=i+1}^pb_j=max{a_i,c_{i-1}+b_i}+sum_{j=i+1}^pb_j)。
因为是取(max)，(a_i<c_{i-1}+b_i)时不会被算，(c_p)就可以直接写成(max_{i=0}^p{a_{i}+sum_{j=i+1}^pb_j}=max_{i=0}^p{a_{i}+sum_{j=i+1}^nb_j}-sum_{j=p+1}^nb_j)。树状数组维护(b)的区间和，线段树维护括号里的值，每次询问区间查询最大值即可。
操作(1)即单点修改(a_i)；设操作(2)令(b_i)增加(v)，只需令线段树上(1sim i-1)加(v)即可。
另一种推的方法是
[egin{aligned}c_p&=max{max{c_{i-2}+b_{i-1},a_{i-1}}+b_i,a_i}\&=max{max{c_{i-2},a_{i-1}-b_{i-1}},a_i-b_i-b_{i-1}}+b_i+b_{i-1}\&=...=sum_{i=1}^pb_i+max{0,max_{i=1}^p{a_i-sum_{j=i}^pb_j}}end{aligned}
]
和上面一样做即可。
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define pb push_back
#define ll long long
const int N = 2e5+10;
const ll inf = 1e18;
int n, m;
ll a[N], b[N], c[N];
ll sumb[N];
void add(int x,ll y){
for(; x<N; x += x&-x) c[x] += y;
}
ll ask(int x){
ll ret = 0;
for(; x; x -= x&-x) ret = ret + c[x];
return ret;
}
struct node{
int l, r;
ll d, val;
}T[N*4];
void build(int p,int L,int R){
T[p].l = L; T[p].r = R;
T[p].d = 0;
if(L == R){
T[p].val = a[L] + (sumb[n]-sumb[L);
return ;
}
int mid = (L+R)/2;
build(p*2, L, mid);
build(p*2+1, mid+1, R);
T[p].val = max(T[p*2].val, T[p*2+1].val);
}
void spread(int p){
if(T[p].d){
T[p*2].val += T[p].d;
T[p*2].d += T[p].d;
T[p*2+1].val += T[p].d;
T[p*2+1].d += T[p].d;
T[p].d = 0;
}
}
void change(int p,int L,int R,ll x){
if(L <= T[p].l && R >= T[p].r){
T[p].val += x;
T[p].d += x;
return ;
}
spread(p);
int mid = (T[p].l+T[p].r)/2;
if(L<=mid)change(p*2, L, R, x);
if(R >mid)change(p*2+1, L, R, x);
T[p].val = max(T[p*2].val, T[p*2+1].val);
}
ll ask(int p,int L,int R){
if(L<=T[p].l && R>=T[p].r){
return T[p].val;
}
spread(p);
int mid = (T[p].l+T[p].r)/2;
ll ret = -inf;
if(L<=mid) ret = max(ret, ask(p*2, L, R));
if(R >mid) ret = max(ret, ask(p*2+1,L,R));
return ret;
}
int main(){
while(scanf("%d%d",&n,&m) == 2){
for(int i=1; i<=n; i++) scanf("%lld", a+i);
for(int i=0; i<=n; i++) c[i] = 0;
sumb[0] = 0;
for(int i=1; i<=n; i++) {
scanf("%lld", b+i);
add(i, b[i]);
sumb[i] = sumb[i-1]+b[i];
}
build(1,1,n);
ask(1,1,2);
while(m--){
int op; scanf("%d",&op);
//cout<<op<<endl;
if(op == 1){
int x; ll y; scanf("%d%lld",&x,&y);
change(1, x, x, y-a[x]);
a[x] = y;
} else if(op == 2){
int x; ll y; scanf("%d%lld",&x,&y);
if(x != 1) change(1, 1, x-1, y-b[x]);
add(x, y-b[x]);
b[x] = y;
} else {
int x; scanf("%d",&x);
ll d = ask(n)-ask(x);
ll ans = max(ask(x), ask(1,1,x)-d);
printf("%lld
",ans);
}
}
}
return 0;
}
F.Modulo Nine(数位DP)√
写了个数位DP的常规记忆化，非递推。。
区间合法即区间中有两个(3)或(6)，或有一个(0)或(9)。
如果按平时DFS的数位DP写法来写，记录前两个(3,6)、前一个(0,9) 出现的位置(p30,p31,p)，以及当前枚举到哪个区间了即可。转移就枚举选(3,6)还是(0,9)还是其它数。
可以发现(p30,p31,p)的状态数是(O(n^3))的，太大了，而数位DP的优化在于压缩状态记忆化，所以考虑压缩一下状态。
因为记录(p)是为了处理限制的，容易发现对限制区间排序后，设当前要判断的区间是([l,r])，若(p<l)可以给(p)一个统一的值(l-1)；否则令(p=下一个询问的l-1)。
这样状态数就少很多了。虽然不知道复杂度多少但跑得很快。
包含其它区间的大区间显然是没用的，可以删一下。
#include <bits/stdc++.h>
#define gc() getchar()
#define mod 1000000007
typedef long long LL;
const int N=1e3+7;
int n,m,bit[N],pw[N];
struct Node
{
int l,r;
bool operator <(const Node &x)const
{
return r==x.r?l>x.l:r<x.r;
}
}A[N],B[N];
struct Node2
{
int b,p0,p1,p2;
bool operator <(const Node2 &x)const
{
return b!=x.b?b<x.b:p0!=x.p0?p0<x.p0:p1!=x.p1?p1<x.p1:p2<x.p2;
}
};
std::map<Node2,int> f;
inline int read()
{
int now=0,f=1; char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-48,c=gc());
return now*f;
}
bool OK(int p30,int p31,int p,int now)
{
return (p>=A[now].l&&p<=A[now].r)||(p30>=A[now].l&&p31<=A[now].r);
}
int DFS(int bit,int p30,int p31,int p,int now)
{
while(now<=m && OK(p30,p31,p,now)) ++now;
p30=std::max(p30,A[now].l-1), p31=std::max(p31,A[now].l-1), p=std::max(p,A[now].l-1);
if(p31>=A[now].l) p31=std::max(p31,A[now+1].l-1);
Node2 tmp=(Node2){bit,p30,p31,p};
if(f.count(tmp)) return f[tmp];
if(now>m) return pw[n-bit+1];
if(bit>n) return 0;
if(A[now].r<bit) return 0;
if(A[now].l>bit) return 1ll*pw[A[now].l-bit]*DFS(A[now].l,p30,p31,p,now)%mod;//
LL res=0;
res+=2ll*DFS(bit+1,p30,p31,bit,now);//0 9
res+=2ll*DFS(bit+1,p31,bit,p,now);//3 6
res+=6ll*DFS(bit+1,p30,p31,p,now);
res%=mod, f[tmp]=res;
return res;
}
int main()
{
pw[0]=1;
for(int i=1; i<N; ++i) pw[i]=1ll*pw[i-1]*10%mod;
while(~scanf("%d%d",&n,&m))
{
for(int i=1,l; i<=m; ++i) l=read(),B[i]=(Node){l,read()};
std::sort(B+1,B+1+m);
int cnt=1; A[1]=B[1];
for(int i=2; i<=m; ++i)
if(A[cnt].l>=B[i].l && A[cnt].r<=B[i].r) ;
else A[++cnt]=B[i];
m=cnt, f.clear(), A[cnt+1].l=n;
int res=DFS(1,0,0,0,1);
printf("%d
",res);
}
return 0;
}/*
1000 5
12 34
25 123
99 345
311 556
878 999
*/
G.Shift and Reverse(Hash)√
求长度为(n)的本质不同的子串。拼成(2n)的串，哈希后枚举即可。注意要反过来求一遍。
三哈希会T。。
#include <bits/stdc++.h>
#define gc() getchar()
#define LIM 2
#define seed1 31
#define seed2 131
#define seed3 137
typedef long long LL;
typedef unsigned long long ull;
const int N=3e5+5;
int A[N];
std::set<ull> st[3];
struct Hash
{
ull seed,pw[N],hs[N];
ull GetHash(int l,int r)
{
return hs[r]-pw[r-l+1]*hs[l-1];
}
}h[3];
inline int read()
{
int now=0,f=1; char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-48,c=gc());
return now*f;
}
int main()
{
h[0].seed=31, h[1].seed=37, h[2].seed=131;
for(int i=0; i<LIM; ++i)
{
h[i].pw[0]=1; ull x=h[i].seed;
for(int j=1; j<=200000; ++j) h[i].pw[j]=h[i].pw[j-1]*x;
}
int n;
while(~scanf("%d",&n))
{
for(int i=1; i<=n; ++i) A[i]=read();
for(int i=1; i<=n; ++i) A[i+n]=A[i];
int m=n<<1;
for(int i=0; i<LIM; ++i)
for(int j=1; j<=m; ++j)
h[i].hs[j]=h[i].hs[j-1]*h[i].seed+A[j];
int res=0;
for(int i=1; i<=n; ++i)
{
bool f=0;
for(int j=0; j<LIM; ++j)
if(!st[j].count(h[j].GetHash(i,i+n-1))) {f=1; break;}
if(f)
{
++res;
for(int j=0; j<LIM; ++j)
st[j].insert(h[j].GetHash(i,i+n-1));
}
}
std::reverse(A+1,A+1+n), std::reverse(A+1+n,A+1+m);
for(int i=0; i<LIM; ++i)
for(int j=1; j<=m; ++j)
h[i].hs[j]=h[i].hs[j-1]*h[i].seed+A[j];
for(int i=1; i<=n; ++i)
{
bool f=0;
for(int j=0; j<LIM; ++j)
if(!st[j].count(h[j].GetHash(i,i+n-1))) {f=1; break;}
if(f)
{
++res;
for(int j=0; j<LIM; ++j)
st[j].insert(h[j].GetHash(i,i+n-1));
}
}
for(int i=0; i<LIM; ++i) st[i].clear();
printf("%d
",res);
}
return 0;
}
H.Knapsack(背包DP 分治 决策单调性)√
出了个原题 数据还特别水
#include <bits/stdc++.h>
#define gc() getchar()
typedef long long LL;
const int N=4e5+5;
LL f[2][N];
std::vector<LL> vec[105];
inline int read()
{
int now=0,f=1; char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-48,c=gc());
return now*f;
}
void Solve(int l,int r,int s,int t,int lim,int V,int x,int now)
{
if(l>r) return;
int m=l+r>>1,p=m;
for(int i=std::min(m-1,t); i>=s&&m-i-1<lim; --i)
if(x+m*V<N && f[now][x+m*V]<f[now^1][x+i*V]+vec[V][m-i-1])
p=i, f[now][x+m*V]=f[now^1][x+i*V]+vec[V][m-i-1];
Solve(l,m-1,s,p,lim,V,x,now), Solve(m+1,r,p,t,lim,V,x,now);
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
for(int i=1,x; i<=n; ++i) x=read(),vec[x].push_back(read());
int now=0,las=1;
for(int i=1,lim; i<=100; ++i)
if((lim=vec[i].size()))
{
std::sort(vec[i].begin(),vec[i].end(),std::greater<int>());
for(int j=1; j<lim; ++j) vec[i][j]+=vec[i][j-1];
now^=1;
for(int j=0; j<=m; ++j) f[now][j]=f[now^1][j];
for(int j=0; j<i; ++j) Solve(0,(m-j)/i,0,(m-j)/i,lim,i,j,now);
for(int j=1; j<=m; ++j) f[now][j]=std::max(f[now][j],f[now][j-1]);
}
printf("%lld
",f[now][m]);
for(int i=1; i<=100; ++i) std::vector<LL>().swap(vec[i]);
for(int i=0; i<=m; ++i) f[0][i]=0;
for(int i=0; i<=m; ++i) f[1][i]=0;
}
return 0;
}
I.Subsequence Pair(LCS)√
(Description)
给定两个串(S,T)，求(S,T)中的两个子序列(s,t)使得(s)的字典序小于等于(t)，且(|s|+|t|)最大。
(|S|,|T|leq2000)。
(Solution)
(sleq t)，则(s,t)存在一定长度（可以为(0)）公共子序列后有(s_i<t_j)，此时(s_i)和(t_j)后面的所有(n-i+1+m-j+1)个字符都可以加进去。
若(s_i=t_j)则(t_j)后面(m-j+1)个可以加进去。所以求最长公共子序列就可以了。
注意(s,t)可为空串（答案初值为(m)）。
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define pb push_back
#define ll long long
const int N = 2e3+10;
char s[N], t[N];
int n, m;
int f[N][N];
int main(){
while(scanf("%s%s",s+1,t+1) == 2){
n = strlen(s+1);
m = strlen(t+1);
f[0][0] = 0;
int ans = m;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
f[i][j] = max(f[i-1][j], f[i][j-1]);
if(s[i] == t[j]) f[i][j] = max(f[i][j], f[i-1][j-1]+1);
ans = max(ans, 2*f[i][j]+(m-j));
if(t[j] > s[i]) ans = max(ans, f[i-1][j-1]*2 + (n-i+1) + (m-j+1));
//cout<<f[i][j]<<' ';
}
//cout<<endl;
}
printf("%d
",ans);
}
return 0;
}