+1

description： 小     G    G   G是     G   T    GT   GT国的国王，他的首都是一张     n    n   n个点的完全无向图，其中点     i    i   i和点     j    j   j之间的无向边长度为     D   i   s   [   i   ]   [   j   ]    Dis[i][j]   Dis[i][j]，恰好点     i    i   i和点     j    j   j之间的最短路长度也是     D   i   s   [   i   ]   [   j   ]    Dis[i][j]   Dis[i]...

description： JOI君有N个装在手机上的挂饰，编号为1…N。 JOI君可以将其中的一些装在手机上。 JOI君的挂饰有一些与众不同——其中的一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上，要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有1个。 此外，每个挂件有一个安装时会获得的喜悦值，用一个整数来表示。如果JOI君很讨厌某个挂饰，那么这个挂饰的喜悦值就是一个负数。 JOI君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰，而且一个都不挂也是可以的。 solution：      设   f   [   i   ]   [   j   ]   表   ...

description： N个政党要组成一个联合内阁，每个党都有自己的席位数. 现在希望你找出一种方案，你选中的党的席位数要大于总数的一半，并且联合内阁的席位数越多越好. 对于一个联合内阁，如果某个政党退出后，其它党的席位仍大于总数的一半，则这个政党被称为是多余的，这是不允许的. solution： 由于删除任意一个都要保证小于等于一半，所以只要保 证删除最小的那个后小于等于一半即可。 我们可以将所有党按照席位数从大到小排序，之后维护 一个     01    01   01背包。 fj表示通过前i大的党组成席位总数为j的内阁所占的席位       f   j    =   m   a   x...

description：  solution:      g   [   i   ]   表   示   二   进   制   下   有   i   个   1   时   的   方   案   数    g[i]表示二进制下有i个1时的方案数   g[i]表示二进制下有i个1时的方案数 则答案为      ∏    i    G   [   i   ]      \prod i^{G[i]}   ∏iG[i] 然后别忘了用快速幂，因为     g   [   i   ]    g[i]   g[i]会很大 code: #include<cstdio> using names...

description： 给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。      a   ≤   b   ≤   1    0   8     a\leq b\leq10^8   a≤b≤108 solution： 数位dp      设   f   [   i   ]   [   j   ]   [   k   ]   表   示   一   共   有   i   位   ，   最   高   位   是   j   ，   k   这   个   数   字   一   共   出   现   的   次   数    设f[i][j][k...

description： windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道， 在A和B之间，包括A和B，总共有多少个windy数？      1   ≤   A   ≤   B   ≤   2000000000    1\leq A\leq B\leq2000000000   1≤A≤B≤2000000000 solution: 数位dp。 设     f   [   i   ]   [   j   ]    f[i][j]   f[i][j]表示共i位，最高位为j时的方案总数  当     a   b   s   (   j...

description： 有     n    n   n个随机变量      x   1    ,    x   2    ,   .   .   .   ,    x   n     x_1,x_2,...,x_n   x1​,x2​,...,xn​。给定      l   1    ,   .   .   .   ,    l   n     l_1,...,l_n   l1​,...,ln​和      r   1    ,   .   .   .   ,    r   n     r_1,...,r_n   r1​,...,rn​，变量      x   i     x_i   xi...

description：  solution： 观察到答案并不会很大，于是我们可以枚举答案（这里不满足单调性，不能二分） 对于任意的i,j，原式可变形 为     (   P   i   −   P   j   )   ∗   x   −   M   ∗   y   =   C   j   −   C   i    (Pi −Pj)*x −M *y = Cj −Ci   (Pi−Pj)∗x−M∗y=Cj−Ci 于是这就是一个exgcd的模型 最后求出如果x不存在或者超过了野人的寿命m就是答案，否则就继续找。 code: #include<cstdio> using namespac...

description： 一开始有两个数A和B，进行K轮游戏，每一轮可能有两种情况：  若     A   ≤   B    A \le B   A≤B，本***作后      B   ′    =   B   −   A   ,    A   ′    =   A   +   A    B' = B - A, A' = A + A   B′=B−A,A′=A+A. 若     B   <   A    B < A   B<A， 本***作后      A   ′    =   A   −   B   ,    B   ′    =   B   +   B   .    A'...

description： Aron给他的朋友们买礼物后在礼物店排队，它的前面有n个人，但是它发现有些人实在等待他的朋友而并非在排队买单，并且我们可以认为站在一个人后面的朋友都穿着匹配颜色的衬衫，而两个相邻的群体、相邻的个人或相邻的个人和一个集体将永远不会穿着相同颜色的衬衫。 编写一个程序，给定排队的人所穿的衣服的颜色，输出Aron在第多少位？ solution： 显然stl解决 #include<cstdio> #include<algorithm> char a[35]; int main() { int n; scanf("%d",&n)...

description: 有M(M为偶数)头奶牛，每头奶牛有一个产奶量，将这些奶牛两两配对，每对奶牛的产奶的时间为两头奶牛产奶量的总和。现在这M/2对奶牛同时产奶，问所需的最短时间是多少 M保证为偶数 solution： 贪心。 将产奶量最少的和最多的匹配，最后取最大的时间即可 #include<cstdio> #include<algorithm> #include<iostream> using namespace std; struct ben { int x,y; }a[100005]; bool cmp(ben s,ben t) { return ...

description： 给定n个点，求出两点之间最短距离 solution： 观察数据范围，发现     n   ≤   100    n\leq100   n≤100，所以之间     O   (    n   2    )    O(n^2)   O(n2)暴力即可。 这里要注意不要丢失精度，于是就全开double，最后输出6位就行了 #include<cstdio> #include<iostream> #include<cmath> using namespace std; double sqr(double x) { return x*x; } ...

description： 给出一个长度为      n    n   n 的整数序列，     a   1   ,   a   2   ,   …   ,   a   n    a1,a2,…,an   a1,a2,…,an，序列中的数互不相同 给出质数      p    p   p 请问有多少序列中的有序数对     (   x   ,   y   )    (x,y)   (x,y)满足      (    x   2    +   y    )   2    ≡   (    x   2    −   y    )   2    +   1   (   m   o   d   p   ...