因为是两个人，而且最后一定会把能拿的数全部拿完。所以我们只需要讨论能拿的数sum有多少个即可。  如果a,b两个数不互质，即他们的最大公因数g大于1，那么在范围内，所有满足的的数都会被拿走。 如果a,b两个数互质，即他们的最大公因数g等于1，那么在范围内，所有的数都会被拿走。  所以我们知道sum=n/gcd(a,b)，因为只有两人，且谁完成最后一次操作时，谁获胜。所以sum偶数时张老师必输，奇数时张老师必胜。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 ...

如果通过僵硬地涂色来计算单点权重，2e5*2e5必然TLE。 差分+前缀和可以完美地解决这个问腿。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=200005; ll num[N]; int main() { ll n, m ; cin >> n >> m; while (m--) { ll l , r ; cin >> l >> r; num[l]++; num[r + 1]--; } for (int i = 2; i...

显然我们需要给出所有弦不交的概率P。 先对分子（两两相连且不相交的情况总数）进行推导：其实这和经典题目凸多边形的三角形划分很相似（但我也没有做过）。易知 时有1种情况, 有2种情况。  时有五种情况，如图：  其实这里已经可以大概猜到是卡特兰数了，但是这里我们做一些更严谨的推导，网上的推导要么就是没有，要么就复杂而且不讲人话。下面给出一种简洁的证法来证明连不相交弦的情况总数为卡特兰数。 众所周知，卡特兰数本身和栈/递归联系非常紧密。所以无论是理解还是证明卡特兰数，引入递归的思想十分重要。   比如对于n=4的情况，我们轻轻地连一条线。此时圆被我们切割成了两个部分：线的左边和右边。左边和右边都是...

因为数据很小，我们都意识到了暴力搜索，DFS可以更简单地解决。 这题的主要难点在于编码难度，我在写这道题的时候认为每搜索一次重新开辟一个二维数组太蠢，又没想清楚如何动态管理车辆的位置信息，其实不需要管理车辆信息，每次重新搜索就可以了。 详细注释： #include <bits/stdc++.h> using namespace std; const int N = 15; const int inf = 0x3f3f3f3f; char mp[N][N]; int dx[] = {0, 0, -1, 1};//合起来分别对应上下左右 int dy[] = {1, -1, 0, 0}...

题意 n个点在数轴上排列，从其中一个点出发。每个点都有要求的最晚到达时间，问能否全部准时到达，如果能，给出完成时间。 分析   题目给出的n个景点是按照位置信息升序排列的。 把起始点，即t为0的点设为k，所有的点分成了两部分：k点左边的点和k点右边的点。 我们用一个数组dp[i][j][f]表示完成左边i个点右边j个点的最少所需时间，f==0时表示在左边结束，f==1时表示在右边结束。  看着数轴，考虑在左边结束的情况，即dp[i][j][0]：  上一个落脚点是左边（从右往左数，下同）第i-1个点，那么就是dp[i-1][j][0]再加上两点之间所需要消耗的时间即可。 上一个落脚点是右边第j...

最后集合中的数全部都是质因数。 假设 n 有 p 个质因数，那么这场游戏将进行 p-1 次操作（每次操作后集合中的数字个数+1），如果 p-1 为奇数那么后手便无法再进行操作，如果 p-1 为偶数则先手再无法进行操作。 特判n为1的情况。 #include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); if (n == 1) printf("Nancy\n"); else { int num = 0; for (int i = 2; i <= n; i++) whil...

斐波那契规律题。 只需要判断末尾是奇数还是偶数即可。 #include<bits/stdc++.h> using namespace std; char s[2025]; int main(){ gets(s); int n=strlen(s); int a=s[n-1]-'0'; if(a&1)cout<<-1<<endl; else cout<<1<<endl; return 0; } 代入得结果 我比赛的时候就是自己手动试了几个

用dp来推断子序列个数 if (s[i] >= 'A' && s[i] <= 'Z') s[i] += 32;统一小写，大小写不敏感。 dp[j] = dp[j] + (s[i] == a[j]) * dp[j - 1];如果匹配，对当前位置加上前一位。 #include <bits/stdc++.h> using namespace std; int n, Mod = 20010905, dp[10]; char a[] = "0iloveyou", s[684600]; int main...

本章我们要制作一个俄罗斯方块游戏。 Tetris  译注：称呼：方块是由四个小方格组成的  俄罗斯方块游戏是世界上最流行的游戏之一。是由一名叫Alexey Pajitnov的俄罗斯程序员在1985年制作的，从那时起，这个游戏就风靡了各个游戏平台。 俄罗斯方块归类为下落块迷宫游戏。游戏有7个基本形状：S、Z、T、L、反向L、直线、方块，每个形状都由4个方块组成，方块最终都会落到屏幕底部。所以玩家通过控制形状的左右位置和旋转，让每个形状都以合适的位置落下，如果有一行全部被方块填充，这行就会消失，并且得分。游戏结束的条件是有形状接触到了屏幕顶部。 方块展示：   PyQt5是专门为创建图形界面产生的...

PyQt5有丰富的组件，但是肯定满足不了所有开发者的所有需求，PyQt5只提供了基本的组件，像按钮，文本，滑块等。如果你还需要其他的模块，应该尝试自己去自定义一些。 自定义组件使用绘画工具创建，有两个基本方式：根据已有的创建或改进；通过自己绘图创建。 Burning widget 这个组件我们会在Nero，K3B，或者其他CD/DVD烧录软件中见到。 #!/usr/bin/python3 # -*- coding: utf-8 -*- """ ZetCode PyQt5 tutorial In this example, we create a custom wi...

PyQt5绘图系统能渲染矢量图像、位图图像和轮廓字体文本。一般会使用在修改或者提高现有组件的功能，或者创建自己的组件。使用PyQt5的绘图API进行操作。 绘图由paintEvent()方法完成，绘图的代码要放在QPainter对象的begin()和end()方法之间。是低级接口。 文本涂鸦 我们从画一些Unicode文本开始。 #!/usr/bin/python3 # -*- coding: utf-8 -*- """ ZetCode PyQt5 tutorial In this example, we draw text in Russian Cylliric...

在GUI里，拖放是指用户点击一个虚拟的对象，拖动，然后放置到另外一个对象上面的动作。一般情况下，需要调用很多动作和方法，创建很多变量。 拖放能让用户很直观的操作很复杂的逻辑。 一般情况下，我们可以拖放两种东西：数据和图形界面。把一个图像从一个应用拖放到另外一个应用上的实质是操作二进制数据。把一个表格从Firefox上拖放到另外一个位置 的实质是操作一个图形组。 简单的拖放 本例使用了QLineEdit和QPushButton。把一个文本从编辑框里拖到按钮上，更新按钮上的标签（文字）。 #!/usr/bin/python3 # -*- coding: utf-8 -*- ""...

本章我们继续介绍PyQt5控件。这次的有QPixmap，QLineEdit，QSplitter，和QComboBox。 图片 QPixmap是处理图片的组件。本例中，我们使用QPixmap在窗口里显示一张图片。 #!/usr/bin/python3 # -*- coding: utf-8 -*- """ ZetCode PyQt5 tutorial In this example, we dispay an image on the window. Author: Jan Bodnar Website: zetcode.com Last edited: Augus...

控件就像是应用这座房子的一块块砖。PyQt5有很多的控件，比如按钮，单选框，滑动条，复选框等等。在本章，我们将介绍一些很有用的控件：QCheckBox，ToggleButton，QSlider，QProgressBar和QCalendarWidget。 QCheckBox QCheckBox组件有俩状态：开和关。通常跟标签一起使用，用在激活和关闭一些选项的场景。 #!/usr/bin/python3 # -*- coding: utf-8 -*- """ ZetCode PyQt5 tutorial In this example, a QCheckBox wid...