`
java-mans
  • 浏览: 11710361 次
文章分类
社区版块
存档分类
最新评论

NYOJ四月份月赛总结

 
阅读更多

昨天下午的月赛【月赛地址】,做的很不理想。

总结一下跟自己的态度有很大的关系。首先,没有放平心态。刚开始G题拿到了first blood,无意中给自己增加了很大的压力。后来写CD,完全功利了,只想着一定要A掉,太心急了,以至于俩题都没A。比赛结束后,发现F是组合数学,B是矩阵模乘。泪呀大哭

比赛有俩水题A、G,B矩阵模乘,C是DP,D树状数组,F组合数学,H是AC自动机。

C题解题报告【这里仅记录下心得】

http://acm.nyist.net/JudgeOnline/problem.php?pid=536

题意:

看似是个矩阵连乘的题,其实是个DP。思路不太好想的一个题。

比赛的时候一直想着贪心可以解决,然后,WA了两次。信心就全无了。后来DD说是DP,当时还有半个多小时,由于心急,完全找不到子问题,最优子结构。

求1-n的最小乘法次数,必须先计算间隔小的最小乘法次数。即为最小乘法次数的最优子结构

#include<iostream>
#include<stdio.h>
using namespace std;
int N[101];
int sum[101][101];//i-j最少乘法次数
#define min(a,b) (((a)<(b)))?(a):(b);
int main()
{
	int n;
	int i,j,k;
	while(scanf("%d",&n)!=EOF)
	{
		for(j=0;j<=n;j++)
			sum[0][j]=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&N[i],&N[i+1]);
			for(j=0;j<=n;j++)
			sum[i][j]=0;
		}
		int e;
		for(i=1;i<n;i++)//间距【从间距为1开始遍历,直到间距为n-1】
		{
			for(j=1;j<=n-i;j++)//从第一个遍历
			{
				e=j+i;
				sum[j][e]=sum[j+1][e]+N[j]*N[j+1]*N[e+1];
				for(k=j;k<e;k++)//这里错了好久,例如,1-3的时候需要枚举1*[2.3]和[1.2]*3。必须从k=j开始计算
				sum[j][e]=min(sum[j][k]+sum[k+1][e]+N[j]*N[k+1]*N[e+1],sum[j][e]);
			}
		}
		printf("%d\n",sum[1][n]);
	}
	return 0;
}

D题

一看到题的时候,就开始模拟,果断TLE。后来仔细看看,发现树状数组的插线问点。写好后还是TLE。开始的时候注意到了query(0)会造成TLE,但是后来完全忽略了,一直TLE就是没有想到是这个问题。比赛结束的前几分钟,把query(0)消除后,就AC了。果断放弃了这个题的排名,唉。。。。

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=522

 
#include<stdio.h>
#include<cstring>
#include<string>
using namespace std;
int m;
int N[200005];
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int y)//改变的是一条线
{
	for(int i=x;i>0;i-=lowbit(i))
	{ N[i]+=y; }
}
int query(int x)//要访问的是一个点
{
    int s=0;
    while(x<=200001)
    {
        s+=N[x];
        x+=lowbit(x);
    }
    return s;
}
int main()
{
    int j,i,t,n,m;
	scanf("%d",&t); 
    for(i=0;i<t;i++)
    {
		memset(N,0,sizeof(N));
		int a,b;
		scanf("%d%d",&n,&m);
        for(j=0;j<n;j++)
        {
            scanf("%d%d",&a,&b);
            add(a+100000,-1);
            add(b+100001,1);
        }
		int x;
        for(j=0;j<m;j++)
        {
            scanf("%d",&x);
            printf("%d\n",query(x+100001));
        }
    }
    return 0;
}
                   

这个题有个O(n)的解法。在a-b之间添加数据,N[a-1]-=1,N[b]+=1;然后 后序遍历(N[i]+=N[i+1)一次,就是某点的N[i]值。【很好的想法!!!】

类似于士兵杀敌(五)

代码:

#include <iostream>
#include <stdio.h>
using namespace std;
int N[1000005]={0};
int main()
{
	int n,c,q;
	int i;int a,b,s;
	scanf("%d%d%d",&n,&c,&q);
	for(i=0;i<c;i++)
	{
		scanf("%d%d%d",&a,&b,&s);
		N[a-1]-=s;N[b]+=s;
	}
	for(i=n;i>=0;i--)//计算当前节点的杀敌数
	{
		N[i]+=N[i+1];
	}
	N[0]=0;
	for(i=1;i<=n;i++)//计算0-当前节点的杀敌总数
	{
		N[i]=(N[i]+N[i-1])%10003;
	}
	for(i=0;i<q;i++)
	{
		scanf("%d%d",&a,&b);
		printf("%d\n",(N[b]-N[a-1]+10003)%10003);
	}
	return 0;
}


分享到:
评论

相关推荐

    ACM在线评测系统 NYOJ 题库 离线看题网页版 nyoj

    NYOJ,全称为南阳理工学院在线评测系统(Nanyang Institute of Technology Online Judge),是为ACM(国际大学生程序设计竞赛)以及其他编程爱好者提供的一种在线编程练习平台。该系统支持用户提交代码并进行实时...

    nyoj部分ACM答案

    ### nyoj部分ACM答案解析 #### 背景与目的 本篇文章旨在解析一个针对NYOJ(网络在线裁判系统)中ACM题目解答的示例代码。该代码使用了C++语言,并且主要涉及到了回溯算法的实现。对于初学者来说,通过深入理解这段...

    NYOJ题目 离线版

    NYOJ(New York Online Judge)是一个在线编程竞赛平台,主要面向ACM(国际大学生程序设计竞赛)的参与者。这个离线版包含了NYOJ的所有题目,为编程爱好者和参赛者提供了一个方便的本地化练习环境。通过爬虫技术,...

    ACM题库题库啊

    NYOJ,全称New York Online Judge,是一个在线编程竞赛平台,提供了丰富的ACM竞赛训练题目。离线版的NYOJ可能是将该平台的部分内容打包成CHM文件,方便用户在没有网络的情况下查阅和练习。这个CHM文件可能包含题目的...

    nyoj16.rar_site:www.pudn.com

    总结来说,这个压缩包文件包含了一个关于最大单调递增子序列的问题,可能还有一个与之相关的矩形嵌入问题,这些问题都要求高效的算法实现,可以通过动态规划或贪心策略来解决。解压并阅读“nyoj16.cpp”文件,我们...

    nyoj 61 传纸条(一)

    双线程动态规划问题,很值得练习。传一个ac代码,测试一下csdn的功能。

    算法-矩形嵌套(NYOJ-16)(包含源程序).rar

    《算法-矩形嵌套(NYOJ-16)》是针对计算机科学中的一个典型问题进行探讨的资源包,其中包含了解决该问题的源程序。这个问题涉及到数据结构、图论以及算法设计等多个核心领域,是编程竞赛或算法学习中的常见题目。在...

    NYOJ.290.DictionaryTree.zip_trie树c_字典树_高级数据结构

    在NYOJ.290.DictionaryTree.cpp文件中,可能包含了以下内容: 1. `TrieNode`结构体定义,用于表示Trie树的节点。 2. 插入函数,如`insert(char *str)`,用于将字符串插入到Trie树中。 3. 查询函数,如`search(char *...

    nyoj_lvy实战开发系列《三》: 获取城市信息

    由于微信小程序没有方法可以获得当前用户所在城市的信息,所以需要调用方法来获取城市信息,用了两个方法去发送请求并返回城市信息  1. @Controller public class WechatLocationManager { private Logger logger ...

    nyoj_lvy实战开发系列《二》: 微信端开发:登录小程序

    这个小程序的主要目的是为了用户用微信的用户信息登录后将用户信息授权存入自己的数据库中,这样以后每次微信登录得到的code 所得到的 openid 可以在项目的数据库中查到该用户的相关信息。 在测试的过程中,需要用户...

    nyoj_lvy实战开发系列《一》:发送JSON信息,加密数据解密算法,UnionID机制说明

    前期小程序开发只进行到根据微信用户登录获取的code 去微信的API去获取到该用户的openId和session_key,到了第二阶段,老大让我重写OAuthManager的代码来实现微信小程序和微信公众号平台获取用户信息的优化,即将...

    南阳理工oj stl练习ac代码

    NYOJ(南阳理工在线判题系统)是南阳理工学院开发的OJ平台,它提供编程题目的提交和评测服务,帮助学生提升编程技能。在这个平台上,用户可以通过提交代码并获取反馈来检验自己对STL的理解和应用。 在STL的练习...

    南阳理工学院OJ第1版解题报告V1.0.pdf

    ### 南阳理工学院OJ第1版解题报告概览 #### 1. A+B Problem 虽然解题思路在报告中被省略,但我们可以推测这是一个基础的数学加法问题,涉及到数字输入与基本算术操作。此类题目旨在测试初学者对编程语言基本输入...

    经典动态规划 南阳104最大和

    给定一个由整数组成二维矩阵(r*c),现在需要找出它的一个子矩阵,使得这个子矩阵内的所有元素之和最大,并把这个子矩阵称为最大子矩阵。

Global site tag (gtag.js) - Google Analytics