吴国庆

acm

Codeforces(6) Xcpc(4) 未归档(2) 算法学习(6) 题解(38)

/ 注册

全部文章 / acm （共50篇）

Codeforces Round #596 (Div. 2)D. Power Products STL

传送门题意：求n个数中满足得对数 n<1e5,a[i]<1e5,2<=k<=100 STL！想到把每个数拆成素数的乘积得形式后得到a[i]=p1^k1 （**） p2 ^k2… 那么对应满足条件得aj=p1^(K1)（*） p2 ^k2… 其中(k1+K1)%k==0...

2020-05-04

0 514

Codeforces Round #597 (Div. 2)D. Shichikuji and Power Grid 神奇的最小生成森林

传送门题意：n个城市，每一个城市有对应的Ci，Ki，和所在位置xi，yi； Ci代表点亮这座城市的代价，使两座城市连接起来的代价为（Ki+Kj）*曼哈顿距离；问使所有城市都亮起来的最小代价思路：非常容易想到，最终的结果一定是有几个城市被点亮，之后每个城市都会有他的附属城市（直接相连或间接相...

2020-05-04

0 629

codeforces E Enigma (DP)

传送门](http://codeforces.com/group/xrTA2IaQje/contest/258354) 题意：给一个大数（长度小于1000）和一个n 但是这个大数的有些位用？表示不确定，现在要把所有？填上后使他是n的倍数，并且最小。思路：简单DP dp[i][j]表示使第i位模数的...

2020-05-04

0 551

Codeforces Round #598 (Div. 3)

传送门 F：Equalizing Two Strings（我见过最水的F）题意：给你两个字符串S，T 你可以反转两个串的任意区间，任意次数，前提是两个串的翻转次数相同，每次反转区间的长度相同。问你能不能是这两个串相等思路：首先两个串的不同字母的数量必须相等，然后因为可以反转任意次，那么其实只要...

2020-05-04

0 490

树上两点间距离倍增法求LCA

#include<bits/stdc++.h> #define pb push_back using namespace std; typedef long long L; vector<int>vec[100010]; int dp[100010][30]; int d[1...

2020-05-04

0 541

查询前缀串出现次数字典树

#include<bits/stdc++.h> #define pb push_back using namespace std; typedef long long L; char s[200001]; int trie[200001][58],tot=0; int ed[20000...

2020-05-04

0 537

java大数进制转换

x 进制的 z 转换成 y 进制 ```java import java.io.*; import java.math.BigInteger; import java.util.*; public class Main{ public static void main(String a...

2020-05-04

0 735

STL

tuble 元组（类似pair）

2020-05-04

0 505

Codeforces Round #609 (Div. 2) E. K Integers

K Integers 题意：给n个数的一个全排列，每次交换相邻两个数求使数字1-k相邻且递增的最小步骤，k（1，n）；思路：当1-k已经相邻时，ans即为1-k的逆序数。那么只需逐步算出使1-k这些数相邻所需的最小步骤容易看出使这k个数向中间靠拢时花费步数最小并容易推出如下公式 ...

2020-05-04

0 569

Educational Codeforces Round 78 (Rated for Div. 2)D - Segment Tree

D - Segment Tree 题意： n条线段当 li<lj<ri<rj 时 i，j之间有一条边相连。问这n条线段能否构成一棵树思路：树：无环，任意两点间都有一个公共祖先，最多n-1条边按左端点排序之后发现li<lj 已经满足了那么对于第i个线段只需找到前...

2020-05-04

0 537