6
6
2015
0

百度之星2015复赛滚粗记

大家……都能做出第三题来

T1: 给你n个和x、y轴平行的线段,问能够构成多少长方形n<=25,T<=100

这……就是四重循环让然后看一下就好

 

T2 : 给你一个吉他谱,然后让你找一个最方便的和弦转换方式使每个手指移动的距离和最小(题面竟然是错的!花了半天来理解样例才发现)

n<=5000 然后就是暴力dp写起来挺难受的

这两到2b题目就不放代码了

T3:给你一个图,每条边的权值是一个字符串,求字典序最小的路径N<=50,M<=500,len<=6

我写完第一道题(10min)的样子,然后看着道题目有人过了,于是就开坑了……然后被坑的好惨

一直在挂从未被超越

我的想法是对于每条边查成len+1个点和len条边这样每个边的边权都是1个字母然后我们枚举最大的字母寻找是否存在路径,如果存在路径那么输出,如果这里存在一个环,环上的点可以通过更大的字母联通到终点那么就是toughway。但是这样又有一个很难受的例子

4 4 0 3

0 1 aaa

1 2 aaa

0 2 aaaaa

2 3 b

然后这就是aaaaaab是答案,但是这样搞出来是aaaaab然后……算了,反正我这种蒟蒻
 

T4:

给你一个环,环上有n个n等分点,每个点有高度,选择两个点,高度之和加上两个点环上的最短距离最大,然后输出字典序最小的一对点。

环上问题改成链上复制一遍,每个点变成i的全职是高度加上等分距离*i。然后反正就是线段树查询区间最大值,然后注意字典序最小的时候要考虑环右边复制的字典序要比左边小。然后因为这个Wa了一发

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <ctime>
#include <vector>
#include <deque>
#include <queue>
#include <string>
using namespace std;
#define LL long long
#define X first
#define Y second
inline int read()
{
    int ret=0,f=1; char ch;
    for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
        if (ch=='-') f=-f;
    for (;'0'<=ch && ch<='9';ch=getchar())
        ret=ret*10+ch-'0';
    return ret*f;
}
const int N = 200010;
struct node{
	int l,r;
	inline int mid(){ return r+l>>1; }
	int mp;
}s[N<<2];
LL a[N],h[N],R;
int n;
inline int get(int x){
	return x>n?x-n:x;
}
inline void push_up(int x){
	int A=s[x<<1].mp,B=s[x<<1|1].mp;
	s[x].mp=a[A]>a[B] || (a[A]==a[B] && get(A)<get(B))?A:B;
}
inline void build(int i,int l,int r){
	s[i].l=l; s[i].r=r;
	if (l==r){
		s[i].mp=l;
		return;
	}
	int m=l+r>>1;
	build(i<<1,l,m);
	build(i<<1|1,m+1,r);
	push_up(i);
}
inline int query(int i,int l,int r){
	if (s[i].l==l && s[i].r==r) return s[i].mp;
	int m=s[i].mid();
	if (r<=m) return query(i<<1,l,r);
	else if (l>m) return query(i<<1|1,l,r);
	else{
		int A=query(i<<1,l,m),B=query(i<<1|1,m+1,r);
		return a[A]>a[B] || (a[A]==a[B] && get(A)<get(B))?A:B;
	}
}
inline void work(){
	LL cur=0;
	int al,ar;
	for (int i=1;i<=n;i++){
		int j=query(1,i+1,i+n/2);
		LL tmp=a[j]-i*R+h[i];
		int ll=i,rr=j;
		if (rr>n) rr-=n,swap(ll,rr);
		if (tmp>cur){
			cur=tmp;
			al=ll; ar=rr;
		}else if (tmp==cur && (ll<al || (ll==al && rr<ar))){
			al=ll; ar=rr;
		}
	}
	printf("%d %d\n",al,ar);
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	int T=read();
	for (int tt=1;tt<=T;tt++){
		printf("Case #%d:\n",tt);
		n=read(); R=read();
		for (int i=1;i<=n;i++){
			h[i]=read();
			a[i]=R*(LL)i+h[i];
		}
		for (int i=n+1;i<=2*n;i++){
			a[i]=i*R+h[i-n];
		}
		build(1,1,2*n);
		work();
	}
	return 0;
}

 

T5:

意思是给你一个字符串,找到最短的不是这个字符串子序列的字符串,然后问有多少个

一开始看错题了,以为是cf461E后来发现不对这里的子序列不是连续的(不是子串)选取规则也不一样

然后就非常水了

Dp[i]表示一个二元组表示我们现在匹配到了第i个位置,最少使用多少个字符,有多少种方案

然后转移是一个区间[pre[i],i-1](这里的pre[i]表示i前面和相同的字母出现的最后位置),可以用线段树优化(有一道线段树题目)

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <ctime>
#include <vector>
#include <deque>
#include <queue>
#include <string>
using namespace std;
#define LL long long
#define X first
#define Y second
inline int read()
{
    int ret=0,f=1; char ch;
    for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
        if (ch=='-') f=-f;
    for (;'0'<=ch && ch<='9';ch=getchar())
        ret=ret*10+ch-'0';
    return ret*f;
}
const int N = 100010,mod=1000000007;
struct Ans{
	int len,way;
	Ans(int x=0,int y=0): len(x),way(y){}
}now;
inline Ans min(const Ans &a,const Ans &b){
	if (a.len<b.len) return a;
	else if (a.len>b.len) return b;
	else return Ans(a.len,(a.way+b.way)%mod);
}
struct node{
	int l,r;
	inline int mid(){ return r+l>>1; }
	Ans A;
}s[N<<2];
inline void push_up(int x){
	s[x].A=min(s[x<<1].A,s[x<<1|1].A);
}
inline void build(int i,int l,int r){
	s[i].l=l; s[i].r=r;
	if (l==r){
		return;
	}
	s[i].A=Ans(N,0);
	int m=l+r>>1;
	build(i<<1,l,m); build(i<<1|1,m+1,r);
}
inline Ans query(int i,int l,int r){
	if (l>r) return Ans(N,0);
	if (s[i].l==l && s[i].r==r) return s[i].A;
	int m=s[i].mid();
	if (r<=m) return query(i<<1,l,r);
	else if (l>m) return query(i<<1|1,l,r);
	else return min(query(i<<1,l,m),query(i<<1|1,m+1,r));
}
inline void modify(int i,int p){
	if (s[i].l==s[i].r){
		s[i].A=now;
		return;
	}
	if (p<=s[i].mid()) modify(i<<1,p);
	else modify(i<<1|1,p);
	push_up(i);
}
int last[26],a[N],pre[N];
char st[N];
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	int T=read();
	for (int tt=1;tt<=T;tt++){
		printf("Case #%d:\n",tt);
		scanf("%s",st+2);
		st[1]='.';
		int n=strlen(st+1);
		build(1,1,n);	
		now=Ans(0,1);
		modify(1,1);
		for (int i=0;i<26;i++) last[i]=1;
		for (int i=2;i<=n;i++){
			a[i]=st[i]-'a';
			pre[i]=last[a[i]];
			last[a[i]]=i;
		}
		for (int i=2;i<=n;i++){
			now=query(1,pre[i],i-1);
			now.len++;
			modify(1,i);
		}
		Ans ans=Ans(N,0);
		for (int i=0;i<26;i++){
			ans=min(ans,query(1,last[i],n));
		}
		printf("%d %d\n",ans.len+1,ans.way);
	}
	return 0;
}

 

T6看了以下完全不会

给你一个n个点m条边的有向图让你删去最多k条边,使得每个点的入读和初度的绝对值的最大值最小

n<=50 k<=m<=n*(n-1)

不会!

似乎有一点网络流的感觉但是这么少的人做出来应该不会是网络流吧。。。

 

 

 

Category: 未分类 | Tags: 游记
6
4
2015
0

Thusc游记

blog搬家之后的第一篇文章竟然是游记

好吧,我这么颓废的人,才不会拿题解坐地一篇文章呢

Day0:

早上坐着火车去了帝都(今年已经来了三次拉)住在高达上的西郊宾馆

帝都的天气可以烤活人,所以下午就我在宾馆里玩百度之星,我开始做的时候已经过去了近两个小时,然后玩了四道题目(其中两个一个是因为我有忘了bc的I64d另外一个神奇的精度问题爆了OJ)然后发现是坑爹的cf赛制然后我前面都是做出两三道题目的……然后前500我是531...

然后就颓在宾馆一直到睡觉

 

Day1:

上午首先坐车到清华大学(着貌似是我第四次来清华?)然后到了拍照集合的地方发现领导都没有来,我们要等1个多小时,然后还实验性的照了几张。

领导来了之后照完相然后去开幕式

开幕式还是那一套但是今年的吴文虎教授讲的给我印象非常深刻(话说thu阳光长跑的记录保持者竟然是现在已经80多岁的吴文虎教授啊啊啊)

然后是唐文斌大神……有一句话放在这里:永远要何必你优秀的人在一起,才可以进步

然后去试机,试机的机器非常有意思,好像是有什么安全系统,每运行一个程序,就要有3s的时间认证以下,然后才跑对拍非常蛋疼(反正thusc的题目那么难,怎么可能用到对拍?!)然后用了30分钟切完了三道题目然后就准备去吃饭这次还是外卖,然后吃完了休息一下准备考试

 

14:00开始考试

首先浏览一遍题目:

T1: 给你一个 $$ n*m $$ 的矩阵 第i行j列位置的数是 $$ A_i xor B_j  $$ 然后p此询问每次询问一个子矩阵的第k大 $$ n<=1000,m<=300000,p<=500 $$

T2 : 给你一个数列有两种操作,第一种是让一个数字平方在对一个给定的数去摸(20个测试点这个数字都不一样但都提前告诉),第二种是求区间和

T3 : 给你一个字符串,他的加密方式是在后面加入一个字符‘\0’然后滚动排序取每列的最后一个加密,给你加密玩的结果让你解密

。。。。。

貌似T2可以向那种区间开跟或者去摸的方式用并查集什么的随便搞搞都会搞到1和0 然后写了一发,为什么这么慢,然后我发现还有循环结,那怎么办,线段数维护每个循环结就好,模数都非常良心,然后循环结最大是60,用并查集维护是不是每个数都在循环结里面然后这样查询的发杂度是 $$ O(m * log(n) )$$ 然后修改如果在循环解里就暴力推动循环解,否则暴力修改这样的发杂度是 $$ O(f(mod) * m * log(n) )$$ 其中 $$ f(mod) $$ 是关于mod的一个函数,大致可以理解为循环结,然后就搞定了……

 

然后这道题目……貌似可以A掉,考虑到上次的难度我觉得当时太厉害了,感觉这样就可以1本稳稳的了

然后就等着那10s对一下的拍发呆

 

然后发现lzr(qmqmqm) 在我身后开始玩水瓶了,难道……?

 

我们还是看看剩下两道题吧

T1: 仔细分析数据范围,这不是可持久化的Trie吗?然后写了一发……回来才发现比标称多了个log然而当时本季测试并没有人和问题

T3: 当时的心情可谓是百感交集(因为马上就要交卷了),然后根本没有心情去管第三道题目(好像管了也写不出来)最暴力,不可能更暴力的十分

然后交卷走人 发现第三题的一个循环的性质可以暴力搞,然后用sort 加速以下可以做到 $$ O(n * log(n)) $$ 然后就滚粗了,发现lzr确实三个小时AK(当时我正好调完T2) 然后开始玩水瓶

 

然后我就感觉滚粗了,今年题目这么简单,我估计不AK进不了面试了,然而我……就当旅游了

后来发现其他一些人有些和我一样有些还差一些,并不是那么的神。。

然后滚回去发现所有省队都在pku和thu的时候,去年已经Au的faebdc在家里欢快的AK了百度之星

然而我也没有心情看第二天的题目,颓了一会儿就滚去睡觉了

 

最后一天上午面试,我5:30就起来了电话8:30才来,去了才发现好像所有人都来了,然后一位老师一句话: 今年面试是差额的!

gg gg gg

 

他是分了几组按姓名拼音字典序排序,所以到我就快中午了

第一个面试官: 六个运动员站成一条直线有多少中方法??

@#¥%……&*不是吧!小学生面试? 一条直线,横着也算竖着也算吧? 于是我就做死的来了一个 $$ 2 * 6! $$

面试官: 哦,你这样想的阿,那之后的问题都不考虑了,就当运动员是一个球体好了

!@#¥!&……*@#

面试管: 一个圆呢……

(我虽然没上过几节数学课也不用这样吧。。。)

面试官: 三男三女隔着站呢?

(感觉智商被鄙视了)

第二个面试官愉快的和我聊了聊写程序

第三个面试官: Q:地球上什么点向南1km向东1km向北1km回到原点

A:北极点!

Q:还有什么点?

(这是什么题目……)

20s之后Q:想不出来?那就下一个问题吧

第四个面试官:Q:你已经进入了清华大学计算机科学技术系,你最感兴趣的专业是什么?(这。。就是做个梦吧)

然后就谈了谈 人生就出来了

出来之后我发现第二个面试官的脑筋急转弯答案是南极点有很多纬线的长度是1的正整分数,然后在那些纬线北部1km的地方都是所求的

然后就结束了

下午是院系介绍和签约,打死都不敢相信签到了一本线,后来才知道今年thu招办被pku的气到了(北大在ZJ和Hn胜选的时候就用1本吧他们省队都签走了)

然后有多睡了一天第二天回来,路上发现我竟然百度之星因为他奇怪的计算方式进了复赛……

总的来说是不错吧

 

Category: 未分类 | Tags: Thusc游记 游记

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com