Kejin Player Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 1901 Accepted Submission(s): 789 Problem Description Cuber QQ always envies those Kejin players, who pay a lot of RMB to get a higher level in the game. So he worked so hard that you...

题意翻译 有n 个人去执行n 个任务，每个人执行每个任务有不同的成功率，每个人只能执行一个任务，求所有任务都执行的总的成功率。 输入第一行，一个整数n （1≤n≤20 ），表示人数兼任务数。接下来n 行每行n 个数，第i 行第j个数表示第i 个人去执行第j 个任务的成功率（这是一个百分数，在0 到100 间）。 输出最大的总成功率（这应也是一个百分数） 输入输出样例 输入 #1复制 2 100 100 50 50 输出 #1复制 50.000000 输入 #2复制 2 0 50 50 0 输出 #2复制 25.00000 输入 #3复制 3 25 60 100 13 0 50 12 70 90...

题目链接：Antinomy与伊尔美格  比较明显的缩点，但是缩点之后怎么求最大值呢？ 我们缩点变成DAG之后，因为求最大值，而且不能往回走，所以跑最长路即可。  AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long using namespace std; const int N=5e5+10,M=1e6+10; int n,m,xx[N],u,k,a[N],b[N],res,d[N]; int dfn[N],low[N],sum[N],col[N],co,cnt; bool vi...

题目链接：C. And and Pair  可以找规律，当然也可以数位dp。 只不过这个数位dp是二维的数位dp。 我们对于每一个数字：如果当前某一位二进制为1，但是n这一位不为1，那么不合法，continue。 如果当前这一位 i，j都为1，也不合法，continue。 然后我们没有处理 i == j 和 j<= i 的关系的情况，i == j 并且合法，那么都为。我们利用对称性除以二就可以避免 j>i 然后加上 1就行了。  AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> #define int long ...

题目链接：Bob’s Problem 题意：就是给你一些白边和一些黑边，让你随便选，但是白边不超过k条。 很明显黑边能选就选，然后白边贪心从大往小，先从大到小让整个图连通，然后从大到小选没选过的即可。  AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> #define int long long using namespace std; const int N=5e4+10,M=5e5+10; int T,n,m,k,res,f[N],vis[M],flag; struct node{int u,v,w;}; vector&...

昨日做题时，见久不作过可持久化并查集矣，将忘光矣，乃有此博客。  可持久化并查集和普通并查集差不多，只是多了一个回退的操作。 一般支持的操作为：   a b 合并a,b所在集合  k 回到第k次操作之后的状态(查询算作操作)  a b 询问a,b是否属于同一集合，是则输出1否则输出0  怎么实现回退操作呢？我们就把普通的 f[] 数组变为可持久化的数组即可。但是我们不能路径压缩（会破坏原本树的结构），所以我们还要维护树的高度，来按秩合并。 例题：可持久化并查集例题  AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#d...

题目描述 凡凡开了一间宠物收养场。收养场提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。 每个领养者都希望领养到自己满意的宠物，凡凡根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养场的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养场总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。 被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为a，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。（任何两只宠物...

LCT就是动态树的一种，但是相比Top_Tree来说，处理子树能力不足（但是简单）。  LCT利用轻重路径的划分，也就是实边和虚边来实现边的删除和合并。 现在来说说LCT的几个重要操作：（默认会splay）  access(x) : 让x连到根上面，也就是让根到x的边全部变为实边。所以我们每次让当前节点splay到根，改变儿子，向上pushup传递信息即可。 makeroot(x) : 让x为根，也就是换根操作，我们先access(x)，之后x肯定为深度最大的点，然后splay到根即可。 find(x) : 找到原树的根，也是一样，我们先access(x) ，之后把根换到最底层，也就是把x，s...

题目描述 给定一棵有n个点的树 询问树上距离为k的点对是否存在。 输入格式 n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径 接下来m行每行询问一个K 输出格式 对于每个K每行输出一个答案，存在输出“AYE”,否则输出”NAY”(不包含引号) 输入输出样例 输入 #1复制 2 1 1 2 2 2 输出 #1复制 AYE 说明/提示 对于30%的数据n<=100 对于60%的数据n<=1000,m<=50 对于100%的数据n<=10000,m<=100,c<=10000,K<=10000000  因为数据比较大，故不能树形dp，所以我们...

2049: [Sdoi2008]Cave 洞穴勘测 Time Limit: 10 Sec Memory Limit: 259 MB Submit: 11970 Solved: 5988 [Submit][Status][Discuss] Description 辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十...

1180: [CROATIAN2009]OTOCI Time Limit: 50 Sec Memory Limit: 128 MB Submit: 1463 Solved: 941 [Submit][Status][Discuss] Description 给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作： 1、bridge A B：询问结点A与结点B是否连通。 如果是则输出“no”。否则输出“yes”，并且在结点A和结点B之间连一条无向边。 2、penguins A X：将结点A对应的权值wA修改为X。 3、excursion A B：如果结点A和结点B不连通...

题目链接：[国家集训队]Tree IIv  LCT维护树上链加法和乘法。 我们像线段树一样做一个加法标记，和一个乘法标记即可。转移和线段树一样的。 因为保证边是合法的，所以我们link和cut时就不必判断了。  AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> #define int long long using namespace std; const int N=3e5+10,mod=51061; int n,q,a[N]; struct Link_Cut_Tree{ int cnt,st[N]; struct nod...

题目背景 在一个叫做Travian的世界里，生活着各个大大小小的部落。其中最为强大的是罗马、高卢和日耳曼。他们之间为了争夺资源和土地，进行了无数次的战斗。期间诞生了众多家喻户晓的英雄人物，也留下了许多可歌可泣的动人故事。 其中，在大大小小的部落之间，会有一些道路相连，这些道路是Travian世界里的重要枢纽，简单起见，你可以把这些部落与部落之间相连的道路看作一颗树，可见每条道路对于Travian世界的重要程度。有了这些道路，建筑工人就可以通过这些道路进行友好外交啦。 然而，事情并不会像想象的那样美好，由于资源的匮乏，相邻的部落（由一条道路相连的部落）之间经常会发生大大小小的冲突事件，更有甚者，...

题目描述 聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。 他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。 聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，...