当前位置:网站首页>2021.1.27训练题解(CF1017D,CF1015E2,CF1012C)

2021.1.27训练题解(CF1017D,CF1015E2,CF1012C)

2021-01-27 19:40:54 Dijkstra6627

\(2021.1.27\)训练题解\((CF1017D,\space CF1015E2,\space CF1012C)\)

\(1.CodeForces\space \space CF1017D\)题解

本题目提供\(2\)种解法。

题解:解法一(我的&zzt的)

在想不出来解法的时候,仔细观察题目。

我们发现\(n\le12\),而题目又是围绕\(01\)串展开的,所以很容易想到状态压缩(注意,是状态压缩,不一定是状压\(dp\))。

对于题目已经给出的\(m\)个位于集合\(A\)的串,我们可以对其进行状态压缩预处理。

如何预处理呢?

对于第\(i\)个给定的\(01\)串,我们分别求出它们的十进制压缩状态,由于\(n\le12\),所以最大的状态不会超过\(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\n",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\n",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\n",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\n");
		else printf("%d\n",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\n",qwq[a[i].v][a[i].k]);
	return 0;
}

\(2.CodeForces\space \space CF1015E2\)题解

题解

本题思路受到\(lht\)启发。

我们发现,本题的数据范围很小,\(n\le1000\),容易想到三层循环的暴力枚举。

如何暴力?随便暴力都行吗?

我最开始的解法就不行。

如果你像我一样,前两层暴力枚举中心点坐标,最后一层枚举四个方向最远走多远的话,那么恭喜你,稳稳地超时。

因为这种算法是严格\(\Theta (n^3)\)的,时间不够。

那么怎么办呢?前两层坐标是必须枚举的,就看第三层了。

我们转念一想,如果,我们枚举四个方向延伸出去的长度,那么第三层循环\(k\)的大小肯定是\(k\le 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\n",s.size());
        while (!s.empty())
        {
            printf("%d %d %d\n",s.front().second.first,s.front().second.second,s.front().first);
            s.pop();
        }
    }
    return 0;
}

\(3.CodeForces\space \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;
}

版权声明
本文为[Dijkstra6627]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/juruo-wsy/p/14336605.html