2017-07-14 20:06:49    527    0    0
#Why Is Video Game The Ninth Form of Art Today more and more people are fond of video games, but only few people know that game is widely accepted as the ninth kind of art. Actually, on May $9^{th}
2017-05-05 12:41:34    220    0    0

NYYZ欢乐小测试

Tutor

  • 所有题目均采用标准输入输出, 推荐使用scanfprintf提高IO速度.
  • 测试环境为Linux, i7-5500U, 选手或许可以不注意常数问题, 但请注意Linux下严格的头文件包括规则.
  • 提交时所有题目均只提交.cpp源文件, 将所有源文件放在文件夹名为自己姓名的文件夹内, 并将Cena客户端的路径地址设置为该文件夹, 每题对应源文件名称见题目名后方.
  • 所有题目时限为1s, 空间限制为500MB
  • 请不要喊"这套题太神了",可以大喊"这套题太水了,我要AK了!".

1.英语题(english.cpp)

小W回归高考党后,被英语老师叫到了办公室,他一头雾水,班主任还没来呢,英语老师要搞什么。难道要检查英语能力?小W心想,我可是每天都在打codeforce,英语这几个月的提高速度可比香港记者跑得快多了。于是小W不再江信江疑,大不了江公补过!于是胸有成竹的去了办公室···

W:What are you call me to do?
T:You guess.
W:You guess I guess or not.
T:You guess I guess you guess or not.
W:You guess I guess you guess I guess or not.
···

小W没想到老师给他玩起了文字游戏,他和老师说的每一句话都是对是否猜测前一句话的询问,且他俩轮流说话,语法符合英语语法. 他现在想知道某一句话往下第N句话是什么,但是他很懒,于是找了你们帮忙,如果谁能解决,他将付给他1000000000000%10的工资.

输入

两行, 第一行为上文段提到的"某一句话"(包含人称及内容, 人称与内容以单个冒号间隔) 第二行为一个正整数N(意义见题目描述).

输出

一行,"某一句话"后第N个句子.

2017-05-07 23:11:11    227    0    0

答案在风中飘荡

By 王启超

每个人的一生中都常常有一些字词烙印在心里,永远无法忘记。他会给人带来启迪,带来动力,也能让人终生铭记,无法释怀。我心中的词语便是留守,在我成长过程中极为特殊的词语。留守伴随着工业化和城镇化的进程,以及劳动力的转移而产生,是很多人心里最沉重的词语,很多人的命运因为它而改变。

当我第一次听到留守时,是羡慕。那时我在上小学,班里很多人是留守儿童,他们有很多零花钱,有高级玩具,而我只能眼巴巴的看着。第二次听到留守时,是苦笑,那时我在上初中,残酷的现实让我麻木,不留守就荒废学业的选择让我迷茫。第三次听到留守时是忧虑,现在我在上高中,很多人都将重复父母的道路,让下一代重复留守的轮回。

我的经历很特殊,既做过留守儿童,又当过进城务工子女,深知本地与外地的差距,也深昧团圆之夜思念父母的痛苦。一路上我遇到很多因留守而改变的人,他们大多过早的进入社会,重复父母的轮回。“留守”和“为了不留守”改变了很多人,让他们脱离了预定的人生轨道。我想知道什么时候才是尽头,答案在哪?

要么留守,要么进城。这是两难的选择,很多人选择后者,以为这是正确的答案,这样真的对么?进城虽然避免了四年的痛苦,但外面有很多诱惑,有时这比留守更可怕。疯子是我来到外地的第一个朋友,人如其名,他做事很偏执。我们经历相似,为了不留守,都跟父母来到外地。又因为在同一所学校上学,所以很快熟悉起来。初识之时他让我很诧异,他比我大两岁却和我同级,问他为什么,他只是笑笑。由于都住在工业区,附近没有什么朋友,再加上父母忙于工作,上网便成为我们唯一的选择,渐渐的我俩都陷入网络,不同的是我还能兼顾学习,但是他却刻意放纵,这样的后果可想而知,两年后我上初中,而他却辍学打工。有一次我问他怎么不上学,他说没意思,上学没用。我苦笑,他重复了父母的轮回,为了不留守,他成为现在的样子。

现实让人不得不留守,甚至像我,本以为自己能够逃脱留守的命运,可最终只是疲劳。那年我上初二,学期快要结束,要做出一个重大选择————回去还是留下。小学结束时也有一次选择,我很随意的选择留下,三年的时间足以改变一个人的习惯,我已经习惯了城市生活不想回去,但这次却不同,这个选择决定着中考,决定着未来三年所处的学校

2017-04-07 10:31:20    195    0    0
首先将图缩成dag 如果存在多于一个出度等于0的强连通分量,说明无解 如果只有1个出度等于0的强连通分量,则这个强连通分量的大小就是答案 练习手工栈... ``` #include #define mset(a,b) memset(a,(b),sizeof(a)) #define scan(a) scanf("%d",&a) #define debug puts("Hello,world.") using namespace std; typedef long long ll; typedef unsig
2017-04-06 21:42:26    265    0    0
因为SDOI常年cena评测还不开栈, 导致树链剖分\tarjan等根本没人干写, 神通广大的OIer们就开始写手工栈, 强行代替系统栈 * 树链剖分 * 第一次dfs * 开个数组模拟访问栈, 存节点编号 * 每次取顶上的尝试扩展下一个节点 * 扩展到就将它进栈, 重新取栈顶元素 * 扩展不到就说明这个节点的子树访问完了
2017-04-06 15:41:53    89    0    0
枚举第一列有没有雷, 剩下的列的情况就确定了. ``` #include #define mset(a,b) memset(a,(b),sizeof(a)) #define scan(a) scanf("%d",&a) #define debug puts("Hello,world.") using namespace std; typedef long long ll; typedef unsigned long long ull; inline int init(){ int x = 0,f =
2017-03-04 14:25:00    169    0    0
  • 题意:求第k(<109)个不含平方因子的数
  • sol:
    • 不难发现此题满足二分性质,答案区间为[k,4k)
    • 现在的问题转化为如何快速计算区间[1,n]内不含平方因子的数有几个
    • 可以用容斥原理:
      Q=n(4,9...)+(36,100,...)...
    • 可以看出系数就是
2017-04-06 09:42:34    142    0    0

已AC 4

#31. 【UR #2】猪猪侠再战括号序列

很巧妙的一道题
不妨把括号序列调整成显然合法的情况:(((())))
从左遍历到中点,每次找到一个不是'('的,就在它的右侧找第一个是'('的,然后中间夹着的肯定是一堆')',直接交换两端即可,而且右侧'('的位置一定越来越靠右,所以每次在上一次的基础上找即可
O(n)

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<vector>
  4. using namespace std;
  5. const int maxn = 200005;
  6. char a[maxn];
  7. vector<pair<int,int> > ans;
  8. int main(){
  9. scanf("%s",a);
  10. int l = 0,r = 0,n = strlen(a)/2;
  11. for(;l<n;++l){
  12. if(a[l]=='(')continue;
  13. if(!r)r = l+1;
  14. for(;a[r]!='(';++r);
  15. swap(a[l],a[r]);
  16. ans.push_back(make_pair(l,r));
  17. }
  18. printf("%d\n",ans.size());
  19. for(int i = 0,lim = ans.size();i<lim;++i)
  20. printf("%d %d\n",ans[i].first+1,ans[i].second+1);
  21. return 0;
  22. }

#48. 【UR #3】核聚变反应强度

很好玩的一道题
预处理a1的所有质因子

2017-04-05 08:47:20    92    0    0
构造AC自动机, 计数的转移是矩阵乘法形式, 快速幂加速. * 坑点: 1. poj特慢, 以致于你某个式子模两次会tle, 模一次就ac 2. 构造fail边时不要忘了转移匹配节点的关系! ``` #include #include #include #include #include #include #include #include #include
2017-04-04 20:57:36    232    0    0

询问x串在y串中出现几次,相当于询问y中多少个前缀的后缀是x
AC自动机中trie树的正常边维护了一个前缀信息,fail边维护了一个后缀信息,也就是说从根节点到表示y串路径上有多少节点的fail边直接或间接指向x节点
我们将fail边反向,由这些边构成的有向图所有点的入度为1,是一颗树,对应询问(x,y)就变成了x对应节点的子树上有多少y的前缀节点
每次暴力去遍历x的子树显然可以卡到O(nm)
题目不要求在线,我们想离线做法,我们发现每个串y的前缀节点构成一条根节点到y串节点的路径,也就是说我们去dfs原trie,访问y时的调用栈内所有的点都是y串的前缀,我们为这些点设置一个权值1, 询问就变成了x串子树上节点权值和,而到了y节点,所有对应它的询问就都可以处理了,而维护子树权值和的工具就是树状数组维护dfs
做法显而易见,dfs trie,每访问一个节点它的权值+1,然后处理所有当前节点的询问,退出时权值1
时间复杂度O(n+mlogn)

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<set>
  7. #include<map>
  8. #include<vector>
  9. #include<stack>
  10. #include<queue>
  11. #define scan(a) scanf("%d",&a)
  12. #define mset(a,b) memset(a,(b),sizeof(a))
  13. using namespace std;
  14. typedef long long ll;
  15. typedef unsigned long long ull;
  16. const int inf = 0x3f3f3f3f;
  17. const int maxn = 100005;
  18. int m;
  19. namespace bit{
  20. int s[maxn];
  21. inline int lowbit(int x){
  22. return x&-x;
  23. }
  24. void a