(2021.1.27)训练题解((CF1017D,space CF1015E2,space CF1012C))
(1.CodeForcesspace space CF1017D)题解
本题目提供(2)种解法。
题解：解法一（我的&zzt的）
在想不出来解法的时候，仔细观察题目。
我们发现(nle12)，而题目又是围绕(01)串展开的，所以很容易想到状态压缩（注意，是状态压缩，不一定是状压(dp)）。
对于题目已经给出的(m)个位于集合(A)的串，我们可以对其进行状态压缩预处理。
如何预处理呢？
对于第(i)个给定的(01)串，我们分别求出它们的十进制压缩状态，由于(nle12)，所以最大的状态不会超过(4096)，数组完全存的下。
之后，对于所有状态对应的(w_i)权值的和，我们要求出前缀和，因为题目问的是最终"关联值"(le k)的所有答案，所以要求和。
之后就很简单了，对于每个询问，用同样的方法求出压缩值，二分查找满足条件的答案，直接输出即可。
代码一
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int w[20];
struct node
{
int val,sta,cnt;
node(int vv,int ss){val=vv;sta=ss;cnt=0;}
node(){cnt=0;}
bool operator<(const node&x)const{return val<x.val;}
};vector<node> v[5000];
int cnt[5000],t[500010];
char s[20];
int main()
{
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<=m;i++)
{
scanf("%s",s+1);
int len=strlen(s+1),ss=0;
for(int j=len;j;j--)
{
ss<<=1;
ss|=(s[j]=='1');
}
cnt[ss]++;
t[i]=ss;
// printf("ss:%d
",ss);
}
sort(t+1,t+m+1);
m=unique(t+1,t+m+1)-t-1;
for(int i=0;i<(1<<n);i++)
{
for(int j=1;j<=m;j++)
{
int vv=0;
for(int k=1;k<=n;k++)
if((i&(1<<k-1))==(t[j]&(1<<k-1)))
vv+=w[k];
v[i].push_back(node(vv,t[j]));
}
}
for(int i=0;i<(1<<n);i++) sort(v[i].begin(),v[i].end());
for(int i=0;i<(1<<n);i++)
{
// printf("i==%d
",i);
for(int j=0;j<v[i].size();j++)
{
if(j) v[i][j].cnt+=v[i][j-1].cnt;
v[i][j].cnt+=cnt[v[i][j].sta];
}
}
for(int i=1;i<=q;i++)
{
int k;
scanf("%s%d",s+1,&k);
int len=strlen(s+1);
int ss=0;
for(int i=len;i;i--)
{
ss<<=1;
ss|=(s[i]=='1');
}
// printf("ss:%d
",ss);
int l=0,r=v[ss].size()-1;
int p=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(v[ss][mid].val<=k)
{
p=mid;
l=mid+1;
}
else r=mid-1;
}
if(p==-1)printf("0
");
else printf("%d
",v[ss][p].cnt);
}
return 0;
}
解法二（ll的）
这个解法利用了(Trie)树的思想和部分代码。
我们可以对于每种状态建立一颗(Trie)树，在一棵树中，不同的层对应不同的数位，建树的”原材料“就是集合(A)中的元素。
之后，我们每查询一个串，就让这个串在树中的需要加的权值计算一遍，即可。
代码二：
#include<bits/stdc++.h>
using namespace std;
const int N=15,M=5e5+10,S=(1<<12)+10;
struct node {char str[N]; int v,k,id;} a[M];
char s[M][N];
int w[N],t[4*S][2],num[4*S],qwq[S][N*110],cnt,n;
bool cmp(node a,node b) {return a.v<b.v;}
bool cmp2(node a,node b) {return a.id<b.id;}
void add(char *b)
{
int pos=0;
for(int i=1;i<=n;i++)
{
bool ti=b[i]-'0';
if(!t[pos][ti]) t[pos][ti]=++cnt;
pos=t[pos][ti];
if(i==n) num[pos]++;
}
}
void cul(node b,int x,int pos,int sum)//x:树中下标,pos:串中下标,sum:Wu值总和
{
bool tmp=b.str[pos]-'0';
if(pos==n)
{
qwq[b.v][sum]+=num[x];
return;
}
if(t[x][tmp]) cul(b,t[x][tmp],pos+1,sum+w[pos]);
if(t[x][tmp^1]) cul(b,t[x][tmp^1],pos+1,sum);
}
int main()
{
int m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i=0;i<n;i++) scanf("%d",&w[i]);
for(int i=1;i<=m;i++) {scanf("%s",s[i]+1); add(s[i]);}
for(int i=1;i<=q;i++)
{
scanf("%s%d",a[i].str,&a[i].k); a[i].id=i;
for(int j=0;j<n;j++) a[i].v+=(a[i].str[j]-'0')*(1<<j);
}
sort(a+1,a+q+1,cmp); a[0].v=-1;
for(int i=1;i<=q;i++)
{
if(a[i].v==a[i-1].v) continue;
cul(a[i],0,0,0);
}
for(int i=1;i<=q;i++)
{
if(a[i].v!=a[i-1].v)
for(int j=1;j<=100;j++) qwq[a[i].v][j]+=qwq[a[i].v][j-1];
}
sort(a+1,a+q+1,cmp2);
for(int i=1;i<=q;i++) printf("%d
",qwq[a[i].v][a[i].k]);
return 0;
}
(2.CodeForcesspace space CF1015E2)题解
题解
本题思路受到(lht)启发。
我们发现，本题的数据范围很小，(nle1000)，容易想到三层循环的暴力枚举。
如何暴力？随便暴力都行吗？
我最开始的解法就不行。
如果你像我一样，前两层暴力枚举中心点坐标，最后一层枚举四个方向最远走多远的话，那么恭喜你，稳稳地超时。
因为这种算法是严格(Theta (n^3))的，时间不够。
那么怎么办呢？前两层坐标是必须枚举的，就看第三层了。
我们转念一想，如果，我们枚举四个方向延伸出去的长度，那么第三层循环(k)的大小肯定是(kle n/2)，一下子优化掉了很多，又因为有些情况到不了(n/2)，所以在这种方法优化之后是可以通过的。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char mp[N][N];
int ans;
bool vis[N][N];
int n,m;
queue<pair<int,pair<int,int> > > s;
int read()
{
int x=0,f=1;
char c=getchar();
while (c<'0'||c>'9')
{
if(c=='-') f=-1;
}
while (c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
bool check(int x,int y)
{
if(x<1 || x>n || y<1 || y>m || mp[x][y]!='*') return false;
return true;
}
int main()
{
int tot=0;
n=read(),m=read();
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>mp[i][j];
ans=0;
bool ch=false;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]=='*') ch=true;
if(!ch)
{
puts("0");
return 0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j]=='*')
{
for(int k=1;k<=n;k++)
{
if(k==2) vis[i][j]=1;
if(check(i-k,j) && check(i+k,j) && check(i,j-k) && check(i,j+k))
{
vis[i-k][j]=true;
vis[i+k][j]=true;
vis[i][j-k]=true;
vis[i][j+k]=true;
}
else if(k!=1)
{
//tot++;
s.push(make_pair(k-1,make_pair(i,j)));
break;
}
else break;
}
}
}
}
bool flag=false;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!vis[i][j] && mp[i][j]=='*') flag=true;
if(!s.size() || flag) puts("-1");
else
{
printf("%d
",s.size());
while (!s.empty())
{
printf("%d %d %d
",s.front().second.first,s.front().second.second,s.front().first);
s.pop();
}
}
return 0;
}
(3.CodeForcesspace space CF1012C)题解
题解
状态是对的，转移方程是对的，没时间了...........
我们设(dp_{i,j,0/1})表示当前枚举到第(i)个，前(i-1)个位置已经盖了(j)座房子，且当前位置盖/不盖。
如果我们在(i)位置盖，那么显而易见的是(i-1)位置不能盖，且(a_{i-1})需要被挖到(<a_i)，如果(i-2)位置要盖，那么(a_{i-1})的高度上线就是(min(a_{i-2}-1,a_i-1))。否则上限为(a_i-1)。
如果(i)位置不盖，那么如果(i-1)也不盖，就直接转移即可，否则的话(a_i)的高度上限是(a_{i-1}-1)。
代码
#include<bits/stdc++.h>
using namespace std;
int h[5050];
int dp[5050][5050][2];
int read()
{
int x=0,f=1;
char c=getchar();
while (c<'0'||c>'9')
{
if(c=='-') f=-1;
}
while (c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
int main()
{
memset(dp,0x3f,sizeof(dp));
dp[0][0][0]=0;
dp[1][1][1]=0;
dp[1][0][0]=0;
int n=read();
for(int i=1;i<=n;++i) h[i]=read();
h[0]=0x3fffffff;
for(int i=2;i<=n;++i)
{
dp[i][0][0]=dp[i-1][0][0];
for(int j=1;j<=(i+1)/2;++j)
{
dp[i][j][1]=min(dp[i-2][j-1][0]+max(0,h[i-1]-h[i]+1),dp[i-2][j-1][1]+max(0,h[i-1]-min(h[i],h[i-2])+1));
dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][1]+max(0,h[i]-h[i-1]+1));
}
}
for(int i=1;i<=(n+1)/2;++i) printf("%d ",min(dp[n][i][0],dp[n][i][1]));
return 0;
}