字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位(P)，第 4 位(A)，第 6 位(T)；第二个 PAT 是第 3 位(P)，第 4 位(A)，第 6 位(T)。 现给定字符串，问一共可以形成多少个 PAT？ 输入格式： 输入只有一行，包含一个字符串，长度不超过10?0000，只包含 P、A、T 三种字母。 输出格式： 在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大，只输出对 1000000007 取余数的结果。 输入样例： APPAPT 输出样例：...
一、定义 k-SAT（Satisfiability）问题的形式如下：有 \(n\) 个 01 变量 \(x_1,x_2,\cdots,x_n\)，另有 \(m\) 个变量取值需要满足的限制。每个限制是一个 \(k\) 元组 \((x_{p_1},x_{p_2},\cdots,x_{p_k})\)，满足 \(x_{p_1}\oplus x_{p_2}\oplus\cdots\oplus x_{p_k}=a\)。其中 \(a\) 为 \(0\) 或 \(1\)，\(\oplus\) 是某种二元 bool 运算（如 或运算 \(\vee\)、与运算 \(\wedge\)）。要求构造一种满足所有限制的变量的赋值方案。当...
木棒切割问题 大意：给N根木棒，通过切割至少得到K段长度相同的木棒，长度相同的木棒最长能有多长 思路：已知结论，长度相同的木棒长度越长，切割得到的K越小，可以二分法，即求最后一个满足“k<=K”的L，可转换为第一个满足“k>K”的位置，再减一 #include<stdio.h> #include<algorithm> using namespace std;int main() {int n,K,k=0,length[10];scanf("%d%d",&n,&K);for(int i=0;i<n;i++){scanf("%d",&length[i]);}sort(length,...
问题 B: 找x 题目描述 输入一个数n，然后输入n个数值各不相同，再输入一个值x，输出这个值在这个数组中的下标（从0开始，若不在数组中则输出-1）。 输入 测试数据有多组，输入n(1<=n<=200)，接着输入n个数，然后输入x。 输出 对于每组输入,请输出结果。 样例输入 Copy 4 1 2 3 4 3 样例输出 Copy 2 #include<cstdio> int num[200]; int main(){int n,a,lo;while(scanf("%d",&n)!=EOF){lo=-1;for(int i=0;i<n;i++){scanf("%d",&num[...
大概题意 给定N个开区间，从中尽可能选择多的开区间，使得这些开区间两两没有交集 思路 如果有区间包含的情况，则选择小的区间，能容纳更多不包含的区间 去除区间包含的情况，将所有区间按照左端点从大到小排序，总是选择左端点最大的区间 #include<cstdio> #include<algorithm> using namespace std;const int maxn=11; struct Inteval{int x,y; }I[maxn];bool cmp(Inteval a,Inteval b)//将区间排序 {if(a.x!=b.x) return a.x>b....
文章目录 优先级队列介绍实现一个简单的优先级队列 优先级队列介绍 普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。 在优先队列中，元素被赋予优先级。在插入元素时，要按照优先级找到正确的位置并插入。 实现一个简单的优先级队列 数值的大小作为优先级，数值越大优先级越高。 插入：根据元素的大小插入。 取出：取出队头元素。 在这里插入代码片package queue;public class QueueTest3 {public static ...
前言： 21考研，正在啃《算法笔记》，不论能否进复试记录一下准备路上写下的垃圾代码。 解答： #include<iostream> #include<vector> #include<algorithm> #include<cmath> using namespace std;struct moon {double save;double price;double portion; }; bool cmp(moon brand1, moon brand2) {if (brand1.portion > brand2.portion)return true;elsereturn false; } int main() {int n, req;double income = 0;cin >> n >> req;v...
第一章基础 输入输出 C 输入 1、scanf() 注意 字符串不用取值符 一些说明： scanf() %c格式可以读入空格和换行，而其他的字符都已空白符（空格，换行）为结束判断标志，不读入 2、gets() 读入一整行 使用 gets() 时，系统会将最后“敲”的换行符从缓冲区中取出来，然后丢弃，所以缓冲区中不会遗留换行符。这就意味着，如果前面使用过 gets()，而后面又要从键盘给字符变量赋值的话就不需要吸收回车清空缓冲区了，因为缓冲区的回车...
进制转换 D进制的A+B python的进制转换已有函数，bin(),oct(),hex()分别是十进制转换为二进制，八进制和十六进制的函数，本题为了不让输出带有0b，用格式化的方式。 “{:b}”.format(summ) import time time_start=time.time()a,b,c = map(int,input().split()) summ = a + bif c == 2:print("{:b}".format(summ)) elif c == 8:print("{:o}".format(summ)) elif c == 16:print("{:x}".format(summ))time_end=time.time() print('ti...
栈 栈的实现有效的括号最长有效括号二叉树的递归遍历队列和栈两个队列实现一个栈两个栈实现一个队列 删除字符串中所有相邻重复项自定义栈 栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出的原则来存储数据，也就是说，先插入的数据将被压入栈底，最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。栈在汇编语言程序中，经常用于重要数据的现场保护。栈中没有数据时，称为空栈...
问题 B: 确定比赛名次 题目描述 有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。 输入 输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来...
算法笔记【7】 最短路问题 最短路问题简介 这篇文章应该会很长，因为我们要探讨图论中一个基本而重要的问题：最短路问题。如下图，我们想知道，某点到某点最短的路径有多长？最短路问题分为两类：单源最短路和多源最短路。前者只需要求一个固定的起点到各个顶点的最短路径，后者则要求得出任意两个顶点之间的最短路径。我们先来看多源最短路问题。 Floyd算法(弗洛伊德算法) 我们用Floyd算法解决多源最短路问题： public static int...
有的递推算法既可以从左向右推也可以从右向左推，这种特性赋予了我们一个技巧，双端处理法 当一个东西对递推数组的影响仅限于左半部分或右边部分，我们可以构造一个反向递推的数组，把不受影响的部分合起来计算 EX最大字段和 经典的最大子段和问题应该都很熟悉了，那么如果把这个问题魔改一下，选取两段不相交的子段，使得他们的和最大，该怎么做？ 先回忆一下最大字段和的DP做法，记f[i]为以i为右端点的最大字段和，那么则可以从左...
1. 基本模板 class Solution {public List<List<元素类型>> 方法名(参数列表){//返回answer容器集合List<List<元素类型>> ans = new ArrayList<>();if (返回空集合条件) return ans;//返回answer容器集合子集List<元素类型> path = new ArrayList<>();//标记数组，对使用过的元素进行标记boolean[] used = new boolean[数组长度];//首先全部标记为未使用falseArrays.fill(used);backtrack(ans,path,遍历目标,遍历开始位置,used);re...
问题 C: 合并果子（堆） 题目描述 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能...