文档章节

11.10 考试整理

Loi_DL
 Loi_DL
发布于 2016/11/10 18:57
字数 1101
阅读 5
收藏 0

总结 :再次爆零╮(╯▽╰)╭,就当noip Rp++O(∩_∩)O~~

 正常开始读题,T1这不是模拟吗,又看了看样例,感觉还行,T2 woc昨晚上刚学了exgcd,这张的好像exgcd啊,觉得可以搞。T3 smg 样例都看不懂哎,最后骗骗分放弃了。第二次回头去看T1,再读一遍还是暴力模拟,嗯,我想的能做O(n*m),看了看数据范围woc10^18 smg 这O(n) 也过不了啊 得O(1)啊 ,我哪会什么算法是O(1)啊,看60分数据3000,n^2的数据范围貌似可以的,我想的算法是O(n*m),(并没有意识到到错误其实到这我的想法就出现了一种常见的错误“想当然 。。。”) 我想的就是直接折叠后覆盖掉原来的序号,以后再折叠肯定没有被覆盖掉的了。事实上是我想错了,也可以再折叠覆盖掉的序号,因为这样的效果与在折叠覆盖掉的效果一样。可是我已经全修改了,全wa了。T2搞搞搞自己!!!感觉很正确其实不如30分的枚举╮(╯▽╰)╭。T3还是一脸懵逼让了多组数据也不好偏分就把样例丢上去了。

经验:

1 .  一切一题目描述为主,不要“想当然”。切记,切记,切记。

2 . 如果你的想法的时间复杂度 跟 数据范围差别大不在一档上 ,这个时候应该警觉想法是不是哪里出了问题。

3 . 注意数据范围如果n太大不能接受,考虑考虑m。

4 . 当你打一个你无法证明正确性,一定要先打暴力,因为在考场上打的算法正确性很低。最后很可能还不如暴力。

5 . 如果有一个题10分钟样例看不懂or没点思路。考虑选择性的放弃。

T1 

【问题描述】
一张长度为𝑁的纸带,我们可以从左至右编号为0 − 𝑁(纸带最左端 标号为
0) 。 现在有𝑀次操作, 每次将纸带沿着某个位置进行折叠, 问所有操作之后纸带
的长度是多少。
【输入格式】
第一行两个数字𝑁, 𝑀如题意所述。
接下来一行𝑀个整数代表每次折叠的位置。
【输出格式】
一行一个整数代表答案。
【样例输入】
5 2
3 5
【样例输出】
2
【样例解释】
树上有只鸟。
【数据规模与约定】
对于60%的数据,𝑁, 𝑀 ≤ 3000。 
对于100%的数据,𝑁 ≤ 10^18, 𝑀 ≤ 3000。 

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
LL n,m;
LL xh[5000];
int main()
{
	freopen("he.in","r",stdin);
	freopen("he.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)
	scanf("%lld",&xh[i]);
	LL l=0,r=n;
	for(int i=1;i<=m;i++)
	{
		LL mid=(l+r)/2;
		if(xh[i]<=mid)
		{
			for(int j=i+1;j<=m;j++)
			{
				if(xh[j]<xh[i])
				xh[j]=xh[i]+(xh[i]-xh[j]);	
			}
			l=xh[i];
		}
		else 
		{
			for(int j=i+1;j<=m;j++)
			{
				if(xh[j]>xh[i])
				xh[j]=xh[i]-(xh[j]-xh[i]);	
			}
			r=xh[i];
		}
	}
	printf("%lld",r-l);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T2

【问题描述】
给你𝐿, 𝑅, 𝑆, 𝑀,求满足𝐿 ≤ (𝑆 × 𝑥)  𝑚𝑜𝑑  𝑀 ≤ 𝑅最小的正整数𝑥。
【输入格式】
第一行一个数𝑇代表数据组数。
接下来𝑇行每行四个数代表该组数据的𝐿, 𝑅, 𝑆, 𝑀。
【输出格式】
对于每组数据,输出一行代表答案。如果不存在解,输出“−1” 。
【样例输入】
1
5 4 2 3
【样例输出】
2
【样例解释】
叫南小鸟。
【数据规模与约定】
对于30%的数据,保证有解且答案不超过10^6。
对于另外20%的数据,𝐿 = 𝑅。
对于100%的数据,1 ≤ 𝑇 ≤ 100,0 ≤ 𝑀, 𝑆, 𝐿, 𝑅 ≤ 10^9。

题解 :前百分之30枚举即可,之后L==R的用exgcd就行。剩下的不会了 QAQ。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
LL m,s,l,r,t;
LL x,y;
LL T;
void exgcd(LL a,LL b)
{
	if(b==0)
	{
		x=1,y=0;
		return ;
	}
	exgcd(b,a%b);
	LL x2=x,y2=y;
	x=y2;
	y=x2-a/b*y2; 
}
int main()
{
	freopen("she.in","r",stdin);
	freopen("she.out","w",stdout);
	scanf("%lld",&T);
	int aaa;
	while (T!=0)
	{
		T--;
		x=0,y=0;
		scanf("%lld%lld%lld%lld",&m,&s,&l,&r);
		if(l==r)
		{
			t=l;
			if(t%__gcd(m,s)!=0|| m<=l)
				printf("-1\n");
			else 
			{
				LL haha=t/__gcd(m,s);
				exgcd(s,m);
				x*=haha;
				haha=m/__gcd(m,s);
				while(x<0) x+=haha;
				x%=haha;
				printf("%lld\n",x);
			}
		}
		else 
		{
			for(LL i=1;i<=1000000;i++)
			{
				if(l<=s*i%m&&s*i%m<=r)
				{
					printf("%lld\n",i);
					break;
				}
			}
		}
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

 

© 著作权归作者所有

Loi_DL
粉丝 0
博文 60
码字总数 48692
作品 0
莱芜
私信 提问
Anyers/WeChat-WeApp-Resources

title: 微信小程序资源整理 - 更新汇总 tags: 小程序,微信,更新,资源整理 grammar_cjkRuby: true 微信小程序相关的文档、教程、开源项目等资源的整理,以便于开发学习使用。 —— —— 收录仅...

Anyers
2016/11/07
0
0
Kubuntu/Xubuntu/Edubuntu 11.10 发布

随着 Ubuntu 11.10 的发布,Ubuntu 的一些衍生版本也相应的发布了 11.10 版本。 Kubuntu 11.10 (使用 KDE 桌面的 Ubuntu): kubuntu-11.10-desktop-i386.iso (699MB, torrent) kubuntu-11...

红薯
2011/10/14
1K
2
Ubuntu 11.10 开发日程表已经公布

Ubuntu 11.10 (代号为 Oneiric Ocelot) 的开发日程表已经公布在 Ubuntu wiki 上了,它将会在2011年10月正式发布。与下个月即将发布的 Ubuntu 11.04 的开发日程类似,Ubuntu 11.10 也不会发布...

红薯
2011/03/17
1K
3
Ubuntu 11.10 Alpha 2 将于 7 月 7 日发布

根据 Ubuntu 原先计划的发行进度表original release schedule, Ubuntu 11.10 Alpha 2 原定于 6 月 30 日发布,但最近流行跳票,该事件推迟了一个星期(比起 CentOS 好1000倍)改到了 7 月 7 ...

红薯
2011/07/05
962
5
Ubuntu 11.10 正式版专题

Ubuntu 11.10 正式版就要发布啦,我笑了。来,大家一起笑,哈哈。 一、Ubuntu 11.10的发布日程 Now Ubuntu 11.10 is comming,官方已开售光盘,镜像下载可能要等到13号。 发布日程:http://bb...

AndroidMe
2011/10/11
9.4K
10

没有更多内容

加载失败,请刷新页面

加载更多

中国地理位置四至点及计算方法

中国地理位置四至点(China's geographical position is four o'clock),是指中国领土最东、西、南、北的四个地理位置。处于太平洋西岸,亚洲东部。 中文名 中国地理位置四至点 外文名 Chin...

boonya
13分钟前
0
0
8.eclipse 安装 lombook插件

1.效果 2.安装过程 参考: https://blog.csdn.net/zflovecf/article/details/80178679 2.1 下载插件 https://projectlombok.org/download.html 并放入eclipse所在目录 (位置参考下图) 2.2 ......

20190513
15分钟前
0
0
java io的编码和解码

public class copyFIle { public static void main(String[] args) throws UnsupportedEncodingException { String str="中国人民";//编码byte data[]=str.getBytes("gbk");//解码Sys......

南桥北木
29分钟前
0
0
SpringBoot中使用Filter

1.在传统web项目中添加filter <filter> <filter-name>TestFilter</filter-name> <!--定义filter名称 和filter类 --> <filter-class>com.jiafeng.filter.TestFilter</filter-class>......

贾峰uk
29分钟前
1
0
?为什么要学这个技术(有什么优秀的地方,可以解决哪些问题?

今天来总结一下Struts2的知识点,学习编程我的思路一般是这样的:     ① why ?为什么要学这个技术(有什么优秀的地方,可以解决哪些问题?)。     ②what ? 这个技术是什么玩意?有...

SEOwhywhy
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部