Armin's Blog

learn,explore,create.


  • 首页

  • 关于

  • 标签

  • 分类

  • 归档

  • 搜索

Most Powerful(状压dp入门)

发表于 2018-10-13 | 分类于 题解 | 阅读次数:

描述

传送门:ZOJ-3471

 Recently, researchers on Mars have discovered N powerful atoms. All of them are different. These atoms have some properties. When two of these atoms collide, one of them disappears and a lot of power is produced. Researchers know the way every two atoms perform when collided and the power every two atoms can produce.

You are to write a program to make it most powerful, which means that the sum of power produced during all the collides is maximal.

阅读全文 »

Corn Fields(状压dp入门)

发表于 2018-10-13 | 分类于 题解 | 阅读次数:

描述

传送门:POJ-3254

 Farmer John has purchased a lush new rectangular pasture composed of $M$ by $N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12)$ square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can’t be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

阅读全文 »

swustACM2018国庆招新正式赛题解

发表于 2018-10-05 | 分类于 题解 | 阅读次数:

这次题其实不难,比较偏思维。
按照出题人的预期,题目难度分布是这样的:

难度 培训来了的都能A 签到题 中等题 防AK
题号 A D E I B J F C H

结果,看看榜…

阅读全文 »

Transport Ship(多重背包)

发表于 2018-09-17 | 分类于 题解 | 阅读次数:

描述

传送门:ACM-ICPC 2018 焦作赛区网络预赛 K

 There are $N$ different kinds of transport ships on the port. The $i^{th}$kind of ship can carry the weight of $V[i]$ and the number of the $i^{th}$ kind of ship is $2^{C[i]} - 1$. How many different schemes there are if you want to use these ships to transport cargo with a total weight of $S$?

It is required that each ship must be full-filled. Two schemes are considered to be the same if they use the same kinds of ships and the same number for each kind.

阅读全文 »

A Simple Math Problem(矩阵快速幂)

发表于 2018-08-23 | 分类于 题解 | 阅读次数:

描述

传送门:hdu-1757

 Lele now is thinking about a simple function $f(x)$.

And $a_i(0<=i<=9)$ can only be 0 or 1 .

Now, I will give $a_0 ~ a_9$ and two positive integers $k$ and $m$ ,and could you help Lele to caculate $f(k)%m$.

阅读全文 »

又见斐波拉契(矩阵快速幂)

发表于 2018-08-22 | 分类于 题解 | 阅读次数:

描述

传送门:2018年湘潭大学程序设计竞赛-G

 
这是一个加强版的斐波那契数列。

给定递推式
求F(n)的值,由于这个值可能太大,请对$10^9+7$取模。

阅读全文 »

Fibonacci(矩阵快速幂)

发表于 2018-08-21 | 分类于 题解 | 阅读次数:

描述

传送门:poj-3070

 In the Fibonacci integer sequence, $F_0 = 0, F_1 = 1$, and $F_n = F_n − 1 + F_n − 2 for n ≥ 2$. For example, the first ten terms of the Fibonacci sequence are:

An alternative formula for the Fibonacci sequence is

Given an integer $n$, your goal is to compute the last 4 digits of $F_n$.

阅读全文 »

To the Max(最大子矩阵)

发表于 2018-08-15 | 分类于 题解 | 阅读次数:

描述

传送门:hdu-1081

 Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.

阅读全文 »

Bridging signals(最长上升子序列)

发表于 2018-08-15 | 分类于 题解 | 阅读次数:

描述

传送门:hdu-1950

 ’Oh no, they’ve done it again’, cries the chief designer at the Waferland chip factory. Once more the routing designers have screwed up completely, making the signals on the chip connecting the ports of two functional blocks cross each other all over the place. At this late stage of the process, it is too
expensive to redo the routing. Instead, the engineers have to bridge the signals, using the third dimension, so that no two signals cross. However, bridging is a complicated operation, and thus it is desirable to bridge as few signals as possible. The call for a computer program that finds the maximum number of signals which may be connected on the silicon surface without rossing each other, is imminent. Bearing in mind that there may be housands of signal ports at the boundary of a functional block, the problem asks quite a lot of the programmer. Are you up to the task?

阅读全文 »

Distance Queries(带权LCA)

发表于 2018-08-11 | 分类于 题解 | 阅读次数:

描述

传送门:poj-1986

 Farmer John’s cows refused to run in his marathon since he chose a path much too long for their leisurely lifestyle. He therefore wants to find a path of a more reasonable length. The input to this problem consists of the same input as in “Navigation Nightmare” ,followed by a line containing a single integer K, followed by K “distance queries”. Each distance query is a line of input containing two integers, giving the numbers of two farms between which FJ is interested in computing distance (measured in the length of the roads along the path between the two farms). Please answer FJ’s distance queries as quickly as possible!

阅读全文 »
1234…8
Armin

Armin

梦里不知身是客,一晌贪欢

80 日志
5 分类
53 标签
GitHub Weibo E-Mail Facebook Twitter
友情链接
  • Phantaci
  • Angora
  • VoidR
  • fjk
  • Chengshao
  • Nico
© 2019 Armin
由 Hexo 强力驱动
|
主题 — NexT.Gemini v5.1.4
人 次