T1 神秘大门

题目背景

ZZland最近成立了一个OI应急小组,简称ZZOI。ZZOI挑选了ZZland精英,他共同处 理ZZland中发生的重大事件……

题目描述

最近ZZOI的LWJ大牛经过调查发现,在ZZland的最南方——ZZ Antarctica出现了奇怪 的磁场反应。为了弄清楚这一现象, LWJ 大牛亲自出马,来到了ZZ Antarctica。 LWJ 大牛发现ZZ Antarctica出现了一道神秘的大门。人总有好奇心, LWJ 大牛想打开 这扇神秘大门,看门的后面究竟是什么东西,但用尽什么办法也不能打开这扇门。突然,门 上出现了一些奇怪的字符。凭着敏锐的直觉, LWJ 认为这些符号就是打开这扇门的关键, 于是 LWJ 抓紧时间开始研究这些符号。 经过一些时间的研究, LWJ 大牛发现这些符号其实是一串密码,只有破解了这个密码, 才能打开那扇神秘大门。这个密码十分简单,他给出了两个很长的字符串A和B,你只需要 判断B是否在A中出现过就可以了,当然如果B在A中出现,那么你还需要输出B的字符在A 中依次出现的位置。 这里解释一下B在A中出现的概念,设A=S1S2…SN,B= T1T2…TM,如果存在一组数K: K1<K2<…<KM,使得B=SK1SK2…SKM,那么就可以认为B在A出现过。比如说A=sdfesad, B=sfsad,那么B在A中出现过,因为B中的字符在A中依次出现的位置为1 3 5 6 7。 这个解密过程实在太简单了,于是 LWJ 大牛就将这个任务交给了ZZOI的你。由于 LWJ 大牛十分着急,他只给了你1s的时间。

输入输出格式

输入格式:

输入数据包含2行,分别包含一个字符串,第一行输入的是字符串A,第二行输入的是字 符串B。

输出格式:

第一行输出一个字符串“Yes”或“No”,如果B在A中出现,那么输出“Yes”,否则 输出“No”。 如果你的第一行输出“Yes”,那么在第接下来若干行你需要输出一组数K,使得 B=SK1SK2…SKM,每行一个数;否则第二行为空。如果存在多组数据满足条件,你需要输出 字典序最大的一组。

输入输出样例

输入样例#1:

sdfesad 
sfsad 

输出样例#1:

Yes 
1 
3 
5 
6 
7 

输入样例#2:

abcdef 
acdefg 

输出样例#2:

No

题解

难度黄,字符串+模拟;

考试上爆零了,实在不应该。

本来这次考试就是抱着冲100(T1+T2+T3)分的心态去的,所以想先打三道暴力。但是一上来看到T1,想到了最长公共子序列,推了一下,发现时间复杂度O(n^2),还想不到怎么输出路径。然后就没怎么想打了暴力,打的也不认真,没去想造数据测试,直接就爆零了。

下考场发现这么简单,还是太高估T1的的难度了。心态也不太好。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char a[1000010],b[1000010];
int ans[1000010];
inline int szmax(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	freopen("door.in","r",stdin);freopen("door.out","w",stdout);
	scanf("%s%s",a+1,b+1);
	int len=strlen(b+1),j=len;
	for(int i=strlen(a+1);i>=1;i--)
	if(a[i]==b[j]) ans[j--]=i;
	if(j==0)
	{
		printf("Yes\n");
		for(int i=1;i<=len;++i)
		printf("%d\n",ans[i]);
	}
	else printf("No\n");
	fclose(stdin);fclose(stdout);
	return 0;
}

T2 世界末日

题目背景

话说LWJ大牛终于打开了那扇神秘大门,但迎接他的不是什么神秘的东西,而是一大群 外星入侵者,ZZland岌岌可危…..(这里说一下为什么外星人不自己打开那扇神秘大门呢? 因为在开辟通道的时候他们不小心将门装反了,这才会有LWJ破密码这一出。)

题目描述

ZZland的国王向来喜爱和平,他不想与外星人正面冲突,于是他决定不和外星人战斗而 采用躲避的方式来逃过这一劫难。 ZZland的国王想找到一个地方(其实是新建一个避难所)来让ZZland的所有人藏身。这一 个伟大的任务就交给了ZZOI应急小组的成员来完成。 话说ZZland的版图是一个N×M的矩形,然后ZZland被分成N×M块正方形的土地。在某 些土地上是有ZZland的居民居住的,但某些土地是荒地没有任何人居住(ZZland的土地可 以用一个二元组(X,Y)来描述,表示这块土地处于第X行,第Y列)。 ZZland的国王希望找到一个地方建立一个紧急避难所,他要求所有人走过的路程最短。 如果土地1的坐标为(X1,Y1),土地2的坐标为(X2,Y2),那么从土地1到土地2的路程为 |X1-X2|+|Y1-Y2|。 时间十分紧迫,ZZOI的成员只有1s的时间来解决这个问题。

输入输出格式

输入格式:

输入数据第一行包含3个整数N,M,T,分别表示ZZland版图的大小和有人居住的土地的个 数; 第2行到第T+1行,每行包含3个整数X,Y,P(1≤X≤N, 1≤Y≤M),分别表示土地的坐标和居住 在这块土地的人数。输入数据保证同一块土地不会被多次描述。

输出格式:

输出数据只包含一行,1个实数S,分别表示所有人到达紧急避难所所走的距离之和(结果 保留两位小数)。

输入输出样例

输入样例#1:

1 1 1
1 1 1

输出样例#1:

0.00

输入样例#2:

5 6 3
1 2 1
3 4 2
1 3 4

输出样例#2:

7.00

说明

对于30%的数据,N,M≤1000,T≤200;
对于50%的数据,N,M≤1000000,T≤5000;
对于100%的数据,N,M≤10000000,T≤200000;
对于100%的数据,P≤1000000。

题解

难度绿,数学;

暴力过了4个点 36分,达到期望。

读完题后没什么思路,就开始打暴力。3层循环混了4个点。

打完T3后回看,想到一个贪心的思路,立马被我自己推翻了,但是抱着试一试的态度,还是打上去了,果然爆零。

下考场发现是一个加权中位数,不难理解。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define reg register int
using namespace std;
inline int ri()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	return x*f;
}
int n,m,t,k,x,y;
long long sum,temp;
double ans;
struct node{
	int x,y,p;
}pe[200010];
inline bool cmpx(node a,node b) {return a.x<b.x;}
inline bool cmpy(node a,node b) {return a.y<b.y;}
int main()
{
	freopen("doomsday.in","r",stdin);freopen("doomsday.out","w",stdout);
	n=ri();m=ri();t=ri();
	for(reg i=1;i<=t;++i)
	{
		pe[i].x=ri();pe[i].y=ri();pe[i].p=ri();
		sum+=pe[i].p;
	}
	sort(pe+1,pe+t+1,cmpx);
	while(temp<=(sum>>1))
	{
		temp+=pe[++k].p;x=pe[k].x;
	}
	sort(pe+1,pe+t+1,cmpy);
	k=0;temp=0;
	while(temp<=(sum>>1))
	{
		temp+=pe[++k].p;y=pe[k].y;
	}
	for(reg i=1;i<=t;++i)
	ans+=(double)(pe[i].p)*(abs(pe[i].x-x)+abs(pe[i].y-y));
	printf("%.2lf",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}

T3 先不写了

4 对 “SX小测 复盘”的想法;

wjh进行回复 取消回复

电子邮件地址不会被公开。