cf,atcoder杂(shui)题

899F Letters Removing(452,div2)

手速场div2…

题意:给一个字符串,每次给一个区间,要求你删掉这个区间内的某个字符(删掉后后面的字符往前移),输出最后的序列。

考虑把每个字符的位置都记下来(字符集很小。),每个位置加一个删除标记,每次操作的时候我们假定我们已经复原了$[l,r]$在原序列的位置,那么我们只用在这个字符的所有位置中找到区间中的所有位置,删除(即在这个位置打上删除标记)即可。怎么复原这个$[l,r]$呢?容易想到一个树状数组,删除了这个位置的话就在这个地方+1,那么对于给你的$[l,r]$,原序列的$L$一定是满足$L-getsum(L)$($getsum$是树状数组的求和),$R$一定是满足$R-getsum(R)$的,同时因为这个序列长度不为负数,那么整个序列里$pos-getsum(pos)$是递增的,于是可以通过二分解决这个复原问题。

复杂度,$O(nlogn)$,有常数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
inline int readInt()
{
char c;int tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
const int maxn=(int)2e5+5;
char s[maxn];
int n,m,sum[maxn];
inline int lowbit(int x){return x&(-x);}
void add(int pos,int val)
{
while(pos<=n) {
sum[pos]+=val;
pos+=lowbit(pos);
}
}
int getsum(int pos)
{
int ret=0;
while(pos>0) {
ret+=sum[pos];
pos-=lowbit(pos);
}
return ret;
}
set<int > pos[301];
int cal(int pos,bool tag=false)
{
int L=0,R=n+1;
while(L<R-1) {
int mid=(L+R)>>1;
if(mid-getsum(mid)>=pos) {R=mid;}
else {L=mid;}
}
return R;
}
bool del[maxn];
typedef set<int >::iterator seto;
int main()
{
n=readInt(),m=readInt();
scanf("%s",s+1);
for(int i=1;i<=n;i++) pos[s[i]].insert(i);
int l,r,ll,rr;seto L,R;
int sp;
char ss[21],c;
for(int z=0;z<m;z++) {
l=readInt(),r=readInt();
scanf("%s",ss);c=ss[0];
ll=cal(l),rr=cal(r+1)-1;
L=pos[c].lower_bound(ll);
R=pos[c].upper_bound(rr);
for(seto it=L;it!=R;) {
del[*it]=true;
add(*it,1);
sp=*it;
it++;
pos[c].erase(sp);
}
}
for(int i=1;i<=n;i++) {
if(del[i]) continue;
else printf("%c",s[i]);
}puts("");
return 0;
}

898F Restoring the Expression(451,div2)

手速场div2 * 2

题意:在字符串里添加一个加号和一个等号使之合法。

哈希即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
const int maxn=(int)1e6+5;
typedef long long ll;
const ll Hb[]={20120713,19260817};
ll Hs[2][maxn],powa[2][maxn];
string x,ss;
int n;
void Conclude(int p1,int p2)
{
for(int i=1;i<=p1;i++) cout<<ss[i];
cout<<"+";
for(int i=p1+1;i<=p2;i++) cout<<ss[i];
cout<<"=";
for(int i=p2+1;i<=n;i++) cout<<ss[i];
cout<<"\n";
}
ll range(int id,int l,int r){return (Hs[id][r]-Hs[id][l-1]*powa[id][r-l+1]%Hb[id]+Hb[id])%Hb[id];}
bool ok(int p1,int p2)
{
if(p1>=p2 || p1<1 || p2>=n) return false;
else if((p1>1 && ss[1]=='0') || (p1+1<p2 && ss[p1+1]=='0') || (p2+1<n && ss[p2+1]=='0')) return false;
else {
return (((range(0,1,p1)+range(0,p1+1,p2))%Hb[0]==range(0,p2+1,n))
&& ((range(1,1,p1)+range(1,p1+1,p2))%Hb[1]==range(1,p2+1,n)));
}
}
int main()
{
cin>>x;
n=x.length();
ss=" "+x;
powa[0][0]=powa[1][0]=1ll;
for(int i=1;i<=n;i++) powa[0][i]=powa[0][i-1]*10%Hb[0],powa[1][i]=powa[1][i-1]*10%Hb[1];
for(int i=1;i<=n;i++) {
Hs[0][i]=(Hs[0][i-1]*10+ss[i]-'0')%Hb[0];
Hs[1][i]=(Hs[1][i-1]*10+ss[i]-'0')%Hb[1];
}
for(int pos=1;pos<=n-(n/2);pos++) {
if(pos!=n-pos && n-pos!=n && ok(pos,n-pos)) {Conclude(pos,n-pos);exit(0);}
if(pos!=2*pos && 2*pos!=n && ok(pos,2*pos)) {Conclude(pos,2*pos);exit(0);}
if(pos!=pos+(n-pos)/2 && pos+(n-pos)/2!=n && ok(pos,pos+(n-pos)/2)) {Conclude(pos,pos+(n-pos)/2);exit(0);}
if(pos!=n-pos-1 && n-pos-1!=n && ok(pos,n-pos-1)) {Conclude(pos,n-pos-1);exit(0);}
if(pos!=2*pos+1 && 2*pos+1!=n && ok(pos,2*pos+1)) {Conclude(pos,2*pos+1);exit(0);}
}
return 0;
}

907E Party(454,div2)

题意:给一个连通有向图,每次选出一个点,这个点所连的所有点成为一个团,求最少选几个点使得整个图成为一个团,输出方案。

很裸的状压$dp[S|set(i)]=min(dp[S]+1)$其中$i$必须是,已经在当前是团的集合$S$中,或者它所连的边包含了整个集合 的点。

需要注意的是如果一个图已经是一个团,那么直接输出$0$,我这个傻逼选手比赛的时候没特判这个,$wa$了3次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
const int maxn=26;
int n,m;
typedef pair<int ,int > pii;
#define fir first
#define sec second
#define MP make_pair
int st[maxn],dp[1<<23];
pii pre[1<<23];
int main()
{
scanf("%d%d",&n,&m);
int u,v;
for(int z=0;z<m;z++) {
scanf("%d%d",&u,&v);
u--,v--;
st[u]|=(1<<v);
st[v]|=(1<<u);
}
for(int i=0;i<n;i++) st[i]|=(1<<i);
bool flag=true;
for(int i=0;i<n;i++) {
if(st[i]!=(1<<n)-1) {flag=false;break;}
}
if(flag) {printf("0\n");exit(0);}
memset(dp,0x3f3f3f3f,sizeof(dp));
dp[0]=0;
for(int S=0;S<(1<<n);S++) {
for(int i=0;i<n;i++) {
if((S&(st[i]))==st[i]) continue;
if(S==0 || (((S>>i)&1) || (st[i]&S)==S)) {
if(dp[S|st[i]]>dp[S]+1) {
dp[S|st[i]]=dp[S]+1;
pre[S|st[i]]=MP(i,S);
}
}
}
}
printf("%d\n",dp[(1<<n)-1]);
stack<int > ss;
int pos=(1<<n)-1;
while(pos>0) {
ss.push(pre[pos].fir);
pos=pre[pos].sec;
}
while(!ss.empty()) {
printf("%d ",ss.top()+1);ss.pop();
}
return 0;
}

agc20C Median Sum

题意:给定一个$n$个数的序列,显然有$2^{n}-1$个子序列的和,将这些和排序以后输出中间的(即第$2^{n-1}$个)。

题解:

​ 令$S_0=0$,其中$S0$为$A$的空子序列。注意$S{2^N-1}$等于$A$中所有元素的和。

​ 将$A$的所有子序列组成对,使得$A$中每个元素在每一对中只属于一个子序列(因此,所有的子序列都会和它互补的子序列组对)。很明显,可以组成$2^{N-1}$对。

​ 考虑任意的一对这样的子序列对$P_i,Q_i$,让$\sum P_i$和$\sum Q_i$分别成为$P_i$,$Q_i$中的元素之和。不失一般性,让$\sum P_i <\sum Q_i$。根据这些对子形成的方式,可知$\sum P_i+\sum Qi=S{2^{N-1}}$。因此,$\sum Pi\leq \frac{1}{2}S{2^{N-1}}$并且$\sum Qi\geq \frac{1}{2}S{s^{N-1}}$。

​ 我们发现所有的$Pi$因为$\frac{1}{2}S{2^{N-1}}$的界限而和$Q_i$区分开来。因此,我们可以大胆的假设$\sum P_i$属于$S$集的前一半,这一半列举起来就是$S_0,S1,\cdots, S{2^{N-1}-1}$;同时,$\sum Qi$属于$S$集合的后一半,这一半列举起来就是$S{2^{N-1}},\cdots ,S_{2^N-1}$。

​ 因此,想要找到$S{2^N-1}$的值,我们需要去找到$A$的最小的大于或等于$\frac{1}{2}S{2^{N}-1}$的子序列。

​ 这可以用$dp$来完成:$f(i,j)$表示是否存在一个和为$j$的$A$的前$i$个元素的子序列。既然$f(i,j)$的值是布尔值并且转移可以使用$or$位运算来完成,这个$dp$可以用$bitset$优化。

​ 这个解法总的复杂度是$O(\frac{N^2max(A_i)}{64})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int maxn=2000+5;
int a[maxn],n,sum=0;
bitset<4000010> f;
int main()
{
scanf("%d",&n);
f[0]=1;
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
f|=(f<<a[i]);
sum+=a[i];
}
int i=(sum+1)/2;
for(;!f[i];i++);
printf("%d\n",i);
return 0;
}