车站分级 题目传送门 解题思路 这题就是用拓扑排序分层 首先是建图 每进行一次输入，就将没有停靠的站与停靠的站都建立一条边 因为题目样例不怎么大，所以可以用邻接矩阵 for(int i=1;i<=m;i++)//输入 {  cin>>x; memset(c,0,sizeof(c));//清零 for(int j=1;j<=x;j++) {  cin>>a[j]; c[a[j]]=1;//标记 } for(int j=a[1];j<=a[x];j++)//建图 if(c[j]==0)//不是停靠站 for(int k=1;k<=x;k++) if(...

排序 题目传送门 解题思路 这题虽然是一道蓝题，但他的数据很小，所以，我们可以每输入一个关系就拓扑一次 我们可以把结果分为三种情况 1.根据前x个关系得到整体关系 这里我们可以用拓扑把度清零，记录每个字母都出现过 并且判断最长的链是多少就行了 即f[a[i].to]=max(f[a[i].to],f[p[h]]+1);//找最长链 s=max(s,f[a[i].to]); 如果最长链小于n，那么就没有得到整体关系 提问 那么就有人问了，为什么得不到呢，难道不是经过拓扑后都为0，并且n个字母都出现过就行了吗？ 回答 我们拿个样例来讲 4 6 C<D C<B B<A C<D...

技能树 Description 玩过Diablo的人对技能树一定是很熟悉的。一颗技能树的每个结点都是一项技能，要学会这项技能则需要耗费一定的技能点数。只有学会了某一项技能以后，才能继续学习它的后继技能。每项技能又有着不同的级别，级别越高效果越好，而技能的升级也是需要 耗费技能点数的。   有个玩家积攒了一定的技能点数，他想尽可能地利用这些技能点数来达到最好的效果。因此他给所有的级别都打上了分，他认为效果越好的分数也越高。现在他要你帮忙寻找一个分配技能点数的方案，使得分数总和最高。 Input 第一行是一个整数n（1<=n<=20）,表示所有不同技能的总数。接下来依次给出n个不同技能...

检讨书 尊敬的姜老师： 我很抱歉，这几天中午，在电脑室中违反了规矩，玩了游戏。中午，我看到学长和同学大多数在玩游戏，就也参与进来，一起玩游戏。一开始，我认为：大家都在玩游戏，没什么大不了的！但是，后来我发现我错了。那天下午，您说：“都自觉点，这几天中午在电脑室玩游戏，没有回宿舍的，去我办公室自首。”开始，我想去逃避，不告诉您这件事。可是，我回顾了这几天我的表现，发现自己再不反省，心就收不回来 了。所以，最后我还是去了您的办公室自首。 这几天中午玩的游戏 1.10号到13号中午，玩了战地模拟器 2.14号中午，玩了王国守卫战 3.15号中午，玩了Kana 我觉得这样做是不对的 1.虽然看到许多同...

数星星 Stars 题目传送门 【题目描述】 原题来自：Ural 1028 天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。如果一个星星的左下方（包含正左和正下）有 k 颗星星，就说这颗星星是 k级的。  例如，上图中星星 5 是 3 级的（1,2,4 在它左下），星星 2,4 是 1 级的。例图中有 1 个 0 级，2 个 1 级，1 个 2 级，1 个 3 级的星星。 给定星星的位置，输出各级星星的数目。 一句话题意：给定 n个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。 【输入】 第一行一个整数 N，表示星星的数目； 接下来 N行给...

校门外的树 Description 校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的…… 如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作： K=1，读入l,r表示在l~r之间种上的一种树 K=2，读入l,r表示询问l~r之间能见到多少种树 （l,r>0） Input 第一行n,m表示道路总长为n，共有m个操作 接下来m行为m个操作 Output 对于每个k=2输出一个答案 Sample Input 5 4 1 1 3 2 2 5 1 2 4 2 3 5 Sample Output 1 2 Hint 范围：20%的数据保证，...

Apple Tree Description There is an apple tree outside of kaka’s house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been carefully nurturing the big apple tree. The tree has N forks which are connected by branches. Kaka numbers the forks by 1 to N and th...

CF261D Maxim and Increasing Subsequence 题目传送门 题目大意 给你一个长度为n的B数组,A表示B数组复制ttt遍后首尾相连后的数组,求A的最长上升子序列 有k组询问 maxb表示B数组中最大的数 题目分析 观察样例与数据可以知道，当t>=sum时，答案就是sum，其中sum为序列中不同数字的个数，因为是严格单调的。 sum一定小于maxb。 dp，找最大值用树状数组 AC代码 #include<iostream> #include<cstring> #include<cstdio> using namespace...

友链（松湖莞中） ？？？？？？？？？？？？？？？？？？？？？ 以下是东莞市东莞中学松山湖学校的同学的链接 每年都会更新一次 有需要的可以查看 2020届 SSL_LYW SSL_WJ SSL_WCR SSL_MYD SSL_KYX 以上是2020届  2019届 SSL_DZJ SSL_LKJ SSL_CXY SSL_LJH SSL_LZH SSL_GYX SSL_MYC SSL_YTY SSL_KJ SSL_LYR SSL_XHY SSL_ZZL SSL_GJY（博客园） 以上是2019届  2018届 SSL_LTH SSL_LYF SSL_HKY SSL_FY SSL_TJH SSL_C...

状态压缩（状态压缩）    注：在涉及到位运算时，一定要注意位运算的优先级。该加的括号一定要加 定义状态（例如） 求每一种放法的背包价值，状态应该是这n件物品的放与不放的情况。 最容易想到的是开个n维数组，第i个维度的下标如果是1的话代表放第i件物品，0的话代表不放第i件物品； 但是这样很容易造成空间浪费，而且多维数组也不好开； 我们仔细观察就会发现，每件物品有放与不放两种选择；假设我们有5件物品的时候，用1和0代表放和不放 如果这5件物品都不放的话，那就是00000; 如果这5件物品都放的话， 那就是11111； 看到这，我们知道可以用二进制表示所有物品的放与不放的情况；如果这些二进制用十进...

车 Description 在n*n(n≤20)的方格棋盘上放置n个车(可以攻击所在行、列)，有些格子不能放,求使它们不能互相攻击的方案总数。 Input 第一行为棋盘的大小n 第二行为障碍的数量m 第三行到第m+3为m个障碍 Output 总数 Sample Input 4 2 1 1 2 2 Sample Output 14 解题思路 我们可以设f[i][j]为当前第i,j这个位置答案方案数,优化就是状压DP 状压DP就是降维，把其中一维用二进制表示，转换为十进制存到数组里 我们用a数组表示这一行障碍的状态，则它的转移就是 a[x]+=cf[y−1] 其中cf代表二的次方（注：我们这里是从...

SP39 PIGBANK - Piggy-Bank 题目传送门 解题思路 这题就是完全背包，只不过把max改为min就行了（再加个特判） AC代码 #include<iostream> #include<cstdio> using namespace std; long long n,m,k,T,v[100005],w[100005],f[100005]; int main() {  cin>>T; while(T--) {  scanf("%lld%lld",&n,&m); m=m-n;//m for(int i=1;i...

不在场的证明 题目传送门 解题思路 这题就和香甜的黄油（SPFA）差不多，改个输入和输出就AC了 AC代码 #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> using namespace std; int n,p,c,m,x,y,z,o,x1,tot,head,tail,hd[100005],b[10005],v[10005],f[10005],d[10005]; struct stu {  int to,next,w; }a[100005]; v...

车II Description 有一个nm的棋盘(n、m≤80,nm≤80)要在棋盘上放k(k≤20)个棋子，使得任意两个棋子不相邻。求合法的方案总数。 Input n,m,k Output 方案总数 Sample Input 3 3 2 Sample Output 24 解题思路 这题就是状压dp 先枚举出所有状态 （dfs） void dfs(int s,int ss,int sss)//dfs枚举状态 {  if(ss>n) {  a[++o]=s; b[o]=sss; return; } dfs(s,ss+1,sss); dfs(s+(1<<ss-1),ss+2,ss...