2020 6月月赛题解

lpp123 2020-06-09 7:45:19 2020-06-24 15:59:26

2020 6月月赛题解

1001. 汉初三杰

送分题,输入三个数之后,直接输出这三个数的和即可,注意需要添加文件IO操作和多组样例,如下

freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
int a,b,c;
while(scanf("%d%d%d",&a,&b,&c)==3){
	printf("%d\n",a+b+c);
}

1002. 韩信点兵

判断数组是否是回文序列,可以采用双指针法。在允许最多删除一个数字的情况下,初始化两个指针 low 和 high 分别指向数组的第一个数字和最后一个数字。每次判断两个指针指向的数字是否相同,如果相同,则更新指针,令 low = low + 1 和 high = high - 1,然后判断更新后的指针范围内的子串是否是回文字符串。如果两个指针指向的数字不同,则两个数字中必须有一个被删除,此时我们就分成两种情况:即删除左指针对应的数字,留下子序列 s[low + 1], s[low + 1], ..., s[high],或者删除右指针对应的数字,留下子序列 s[low], s[low + 1], ..., s[high - 1]。当这两个子序列中至少有一个是回文子序列时,就说明原始字符串删除一个字符之后就以成为回文串。具体的代码逻辑如下:

bool check(int a,int b){
    for (int i=a,j=b;i<j;i++,j--){
        if(arr[i]!=arr[j])
            return false;
    }
    return true;
}
bool validPalindrome(int n) {
    if(check(1,n))
        return true;
    for(int i=1,j=n;i<j;i++,j--){
        if(arr[i]!=arr[j])
            return check(i,j-1)||check(i+1,j);
    }
    return true;
}

int main () {
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    int n;
    while(scanf("%d",&n)==1){
        for(int i=1;i<=n;i++)
            scanf("%d",&arr[i]);
        printf(validPalindrome(n)?"Yes\n":"No\n");
    }
	return 0;
}

1003. 萧何运粮

可以用深度优先搜索算法解决本题。可尝试把每袋军粮分配到车上,或者新用一辆车运送此袋军粮。于是,dfs关心的状态有已经运送的军粮,已经是用的车,每辆车上当前搭载的军粮重量之和。编写函数dfs(now,cnt)处理第now袋军粮的分配过程(前now-1袋军粮已经装载),并且目前已经用了cnt辆车。每辆车上的军粮重量使用全局数组cab[]来记录。每袋军粮都有两种选择,放到已经使用的前cnt辆车上,或者新用一辆车运载这袋军粮。当now=n+1时,搜索结束。
可以加入两个优化

  • 对军粮进行排序,先运送重量大的军粮
  • 搜索时发现cnt已经大于或等于已经搜索到的方案时,直接返回。
void dfs(int cat,int cur)
{
	if(cur>best) return;
	if(cat>n)
	{
		best=min(best,cur);
		return;
	}
	for(int i=1;i<=cur;i++)
	{
		if(w-car[i]>=c[cat])
		{
			car[i]+=c[cat];
			dfs(cat+1,cur);
			car[i]-=c[cat];
		}
	}
	car[cur+1]=c[cat];
	dfs(cat+1,cur+1);
	car[cur+1]=0;
}

int main()
{
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
	while(scanf("%d%d",&n,&w)==2){
        best=n;
        for(int i=1;i<=n;i++)
            scanf("%d",&c[i]);
        sort(c+1,c+n+1);
        reverse(c+1,c+n+1);
        dfs(1,0);
        printf("%d\n",best);
	}
	return 0;
 }

1004. 陈平反间

本道题实际上是求x的下属数量,加上自身。所以,在计算出每一个人的直接下属的下属数量之后,就可以求得该人的下属数量。因此可用拓扑排序算法求出一个拓扑序,然后按照拓扑序的倒序进行计算。因为不同人可能有同一个下属,不能直接用下属数量作为动态规划算法状态,可以使用状态压缩思路。利用STL提供的bitset,其中第i位为1表示i是x的下属,为0表示i不是x的下属,对每个人的直接下属能到达的下属集合求并集,即执行“按位或”运算。最后,每个人bitset中1的数量即该人的下属数量。

void f(int a,int b)
{
	tot++;
	ver[tot]=b;
	nxt[tot]=head[a];
	head[a]=tot;
}
int main()
{
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
	int n,m,a,b,v;
	while(scanf("%d%d",&n,&m)==2){
        memset(head,0,sizeof(head));
        memset(ver,0,sizeof(ver));
        memset(nxt,0,sizeof(nxt));
        memset(ans,0,sizeof(ans));
        memset(in,0,sizeof(in));
        for(int i=0;i<30005;i++) dp[i]=0;
        tot=1;A=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            in[b]++;
            f(a,b);
        }
        for(int i=1;i<=n;i++)
        {
            if(in[i]==0)
            q.push(i);
         }
        while(!q.empty())
        {
            ans[++A]=q.front();q.pop();
            for(int i=head[ans[A]];i;i=nxt[i])
            {
                if(--in[ver[i]]==0) q.push(ver[i]);
            }
        }
        for(int i=n;i>0;i--)
        {
            int u=ans[i],v;
            dp[u][u]=1;
            for(int i=head[u];i;i=nxt[i])
            {
                v=ver[i];
                dp[u]|=dp[v];
            }
        }
        for(int i=1;i<=n;i++)
        printf("%d\n",dp[i].count());
	}
	return 0;
}

叔孙定礼

题中给出了第 i 个人前面有多少比他功劳低,如果正着分析比较难找到规律。因此,采用倒着分析的方法(最后一个人的rank可以直接得出)。除此之外,从第n-1个人开始,对于第 i 个人来说,他的功劳排名为没有被占用的rank数组中的第A[i]+1大数。所以,采用树状数组维护0-1序列(表示是否被占用)的前缀和,每次再用二分得出第K大数的下标即可。

void add(int x,int d){
    for(;x<=n;x+=x&-x)
        c[x]+=d;
}

int ask(int x){
    int sum=0;
    for(;x>0;x-=x&-x)
        sum+=c[x];
    return sum;
}

int main(){
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    while(scanf("%d",&n)==1){
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
            add(i,1);
        a[1]=0;
        for(int i=2;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=n;i>0;i--){
            int lo=1,hi=n,mid;
            //printf("---------------------------\n");
            while(lo<=hi){
                mid=(lo+hi)/2;
                int t=ask(mid);
                //printf("%d %d\n",mid,t);
                if(t<a[i]+1)
                    lo=mid+1;
                else
                    hi=mid-1;
            }
            ans[i]=lo;
            add(lo,-1);
        }
        for(int i=1;i<=n;i++)
            printf("%d\n",ans[i]);

    }
    return 0;
}

张良定汉

参考最大连续子序列和,采用动态规划算法。用dp[i][0]表示以 nums[i] 结尾的连续子数组的最小值,用dp[i][1]表示以 nums[i] 结尾的连续子数组的最大值。当nums[i]>=0时,

dp[i][0] = min(nums[i], nums[i] * dp[i - 1][0]); 
dp[i][1] = max(nums[i], nums[i] * dp[i - 1][1]);

当nums[i]<0 时,

dp[i][0] = min(nums[i], nums[i] * dp[i - 1][1]);
dp[i][1] = max(nums[i], nums[i] * dp[i - 1][0]);

具体代码如下:

int maxProduct() {
        if (n == 0) {
            return 0;
        }

        // dp[i][0]:以 nums[i] 结尾的连续子数组的最小值
        // dp[i][1]:以 nums[i] 结尾的连续子数组的最大值
        dp[0][0] = nums[0];
        dp[0][1] = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] >= 0) {
                dp[i][0] = min(nums[i], nums[i] * dp[i - 1][0]);
                dp[i][1] = max(nums[i], nums[i] * dp[i - 1][1]);
            } else {
                dp[i][0] = min(nums[i], nums[i] * dp[i - 1][1]);
                dp[i][1] = max(nums[i], nums[i] * dp[i - 1][0]);
            }
        }
        // 只关心最大值,需要遍历
        int res = dp[0][1];
        for (int i = 1; i < n; i++) {
            res = max(res, dp[i][1]);
        }
        return res;
}

int main(){
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    while(scanf("%d",&n)==1){
        for(int i=0;i<n;i++){
            scanf("%d",&nums[i]);
        }
        printf("%d\n",maxProduct());
    }
    return 0;
}

Congratulations

共 3 条回复

FiLaReTKuN

前排(o゚v゚)ノ

maguangxian

前排!

azy

前排!!!!!!!!111(滑稽)

AMAZE UI
Hello world!