3 LSD20164388

尚未进行身份认证

我要认证

如果你过几天就忘了,那么你并没有真正的掌握。

等级
TA的排名 9k+

2014-2015 ACM-ICPC, Asia Xian Regional Contest Problem C. The Problem Needs 3D Arrays(网络流之最大密度子图)

题意:给你一个长度为n(<=100)的序列T,S为T的任意子序列,r(S)表示子序列S(不连续)中的逆序对数,l(S) 表示S的长度,求出 r(S) / l(S) 的最大值。思路:将r(S)看成边,l(S)看成点,问题转化为求 E / V 的最大值。经典的最大密度子图问题。利用类似0/1分数规划的思想,二分答案,设为mid,则有E /V=mid 即E=V*mid。即使E-V*mid趋近于0。问题再转化为求最大权闭合图。最大权闭合图参考:https://blog.csdn.ne.

2020-06-06 22:06:58

2014-2015 ACM-ICPC, Asia Xian Regional Contest Problem H. The Problem to Make You Happy(博弈,记忆化搜索)

题意:给你n(<=100)个点m(<=n*(n-1))条边的有向简单图,Alice和Bob(两个人都足够聪明)在这个图上玩游戏,两个人轮流沿着有向图走,一次只能走一条边,Bob先走,如果Alice和Bob走到同一个点,或者Bob无法走了,则Bob输,否则Bob赢(Alice永远追不上Bob或者Alice无路可走)。如果Bob能赢输出Yes,否则输出No。思路:考虑记忆化搜索。但是由于图并不是DAG,我们只能倒着从已知的状态往前推,从而找出所有的Bob的必败态。dp[i][j][k

2020-06-06 18:33:16

Educational Codeforces Round 88 (Rated for Div. 2) E. Modular Stability(组合数模板)

E. Modular Stabilitytime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputWe definexmodyxmodyas the remainder of division ofxxbyyy(%%operator in C++ or Java,modoperator in Pascal)....

2020-05-29 13:56:41

牛客练习赛63 F 牛牛的树行棋 (SG函数+树差分)

链接:https://ac.nowcoder.com/acm/contest/5531/F来源:牛客网牛牛的树行棋时间限制:C/C++ 2秒,其他语言4秒空间限制:C/C++ 524288K,其他语言1048576K64bit IO Format: %lld题目描述牛牛和牛妹是一对好朋友,这天他们俩决定在树上玩一个游戏。游戏的名字是“树行棋”,规则如下:给定一个含有n个节点分别从1到n编号且以节点1为根的树,一开始每个节点各有1个棋子。牛牛和牛妹轮流进行操作,且牛..

2020-05-09 17:02:22

Codeforces Round #638 (Div. 2) F. Phoenix and Memory(贪心+线段树)

F. Phoenix and Memorytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputPhoenix is trying to take a photo of hisnnfriends with labels1,2,…,n1,2,…,nwho are lined up in a row in a speci...

2020-05-08 18:41:09

C++ bitset用法小结

C++的 bitset 在 bitset 头文件中,它是一种类似数组的结构,它的每一个元素只能是0或1,每个元素仅用1bit空间。常用函数: bitset<8> foo ("10011011"); cout << foo.count() << endl;  //5  (count函数用来求bitset中1的位数,foo中共有5个1 cout &l...

2018-08-13 09:41:04

Wannafly挑战赛19-C-多彩的树(状压+容斥)

链接:https://www.nowcoder.com/acm/contest/131/C来源:牛客网多彩的树时间限制:C/C++ 5秒,其他语言10秒空间限制:C/C++ 262144K,其他语言524288K64bit IO Format: %lld题目描述有一棵树包含 N 个节点,节点编号从 1 到 N。节点总共有 K 种颜色,颜色编号从 1 到 K。第 i 个节点的颜...

2020-05-05 22:22:48

2020年4月26日训练日记

01bfs可以O(V+E)求解边权全为1的图上最短路。而当边权只有0或1时,使用其它最短路算法是有些浪费的,此时可以使用bfs的变种:0-1 bfs来快速求解,复杂度仍为O(V+E).01bfs维护一个双端队列,当边权为0时,使用push_front,当边权为1时,使用push_back.资料摘自:https://blog.csdn.net/m0_37809890/article/de...

2020-04-26 17:54:54

Codeforces Round #637 (Div. 2) - Thanks, Ivan Belonogov! D. Nastya and Scoreboard(贪心+dp)

D. Nastya and Scoreboardtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputDenis, who managed to buy flowers and sweets (you will le...

2020-04-24 16:29:51

Codeforces Round #635 (Div. 2) C - Linova and Kingdom(树形dp+思维)

Linova and Kingdomtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputWriting light novels is the most important thing in Linova's l...

2020-04-18 12:54:34

Educational Codeforces Round 85 (Rated for Div. 2)E. Divisor Paths(数论,思维)

E. Divisor Pathstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a positive integerDD. Let's build the following g...

2020-04-16 22:13:27

Codeforces Round #633 (Div. 2) E. Perfect Triples (打表找规律)

E. Perfect Triplestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputConsider the infinite sequencessof positive integers, create...

2020-04-15 14:58:28

Codeforces Round #631 (Div. 2) - Thanks, Denis aramis Shitov! D. Dreamoon Likes Sequences(打表找规律)

D. Dreamoon Likes Sequencestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputDreamoon likes sequences very much. So he created a pr...

2020-04-05 21:14:18

Codeforces Round #629 (Div. 3) E. Tree Queries(LCA+思维)

E. Tree Queriestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a rooted tree consisting ofnnvertices numbered fr...

2020-04-04 21:25:21

Codeforces Round #628 (Div. 2) E. Ehab's REAL Number Theory Problem(思维+BFS)

题目传送门E. Ehab's REAL Number Theory Problemtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an arrayaaof lengthn...

2020-03-16 18:29:12

Codeforces Round #627 (Div. 3) A~F 解题报告

题目传送门A:Yet Another Tetris Problem思路:如果奇数偶数都存在,则答案为NO,否则为YES#include<bits/stdc++.h>#define ll long long#define inf 0x3f3f3f3f#define rep(i,a,b) for(register int i=(a);i<=(b);i++)#de...

2020-03-13 11:51:26

Codeforces Round #626 (Div. 2, based on Moscow Open Olympiad in Informatics) D. Present(思维)

题目传送门D. Presenttime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputCatherine received an array of integers as a gift for March 8. ...

2020-03-11 11:03:37

CodeCraft-20 (Div. 2) E. Team Building(状压dp)

题目传送门E. Team Buildingtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAlice, the president of club FCB, wants to build a team f...

2020-03-09 17:06:04

CodeCraft-20 (Div. 2) D. Nash Matrix(队列)

题目传送门D. Nash Matrixtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputNash designed an interesting yet simple board game where a ...

2020-03-09 15:25:37

Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts+prizes!) F. Kuroni and the Punishment (随机数)

题目传送门F. Kuroni and the Punishmenttime limit per test2.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputKuroni is very angry at the other setters f...

2020-03-07 14:02:09

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。