HDU 4135 – Co-prime [素因子+容斥]


Link 传送门 Problem Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N. Two integers are said to be co-prime or relatively prime if they have no common positive divisors other ...

HDU 4135 – Co-prime [素因子+容斥]

Link 传送门 Problem Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N. Two ...
阅读全文 0

hihoCoder #88 – Coordinates [简单数学]


Link 传送门 Problem Give you two integers P and Q. Let all divisors of P be X-coordinates. Let all divisors of Q be Y-coordinates. For example, when P=6 and Q=2, we can get the coordinates (1,1) (1,2) (2,1) (2,2) (3,1) (3,2) (6,1) (6,2). You shoul...

hihoCoder #88 – Coordinates [简单数学]

Link 传送门 Problem Give you two integers P and Q. Let all divisors of P be X-coordinates. Let all divisors of Q be Y-coordinates. For example, whe...
阅读全文 0

CodeForces 622C – Not Equal on a Segment [巧打表]


Link 传送门 Problem You are given array a with n integers and m queries. The i-th query is given with three integers li, ri, xi. For the i-th query find any position pi (li ≤ pi ≤ ri) so that api ≠ xi. The first line contains two integers n, m (1 ...

CodeForces 622C – Not Equal on a Segment [巧打表]

Link 传送门 Problem You are given array a with n integers and m queries. The i-th query is given with three integers li, ri, xi. For the i-th query...
阅读全文 0

HDU 1671 – Phone List [排序]


Link 传送门 Problem Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers: 1. Emergency 911 2. Alice 97 625 999 3. Bob 91 12 54 26 In t...

HDU 1671 – Phone List [排序]

Link 传送门 Problem Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say th...
阅读全文 0

HDU 4763 – Theme Section [KMP应用]


Link 传送门 Problem It’s time for music! A lot of popular musicians are invited to join us in the music festival. Each of them will play one of their representative songs. To make the programs more interesting and challenging, the hosts are ...

HDU 4763 – Theme Section [KMP应用]

Link 传送门 Problem It’s time for music! A lot of popular musicians are invited to join us in the music festival. Each of them will play one ...
阅读全文 0

UVa 11748 – Rigging Elections [求可达矩阵]


Link 传送门 Problem Elections in your country are performed in a one-on-one elimination style. Each week, two people are chosen from a pool of candidates and the country votes on which one they prefer. The loser is eliminated and the winner is ret...

UVa 11748 – Rigging Elections [求可达矩阵]

Link 传送门 Problem Elections in your country are performed in a one-on-one elimination style. Each week, two people are chosen from a pool of cand...
阅读全文 2

UVa 1423 – Guess [数列前缀和+拓扑排序]


Problem 传送门 Mean 给你一个数n和一个字符矩阵,矩阵中S(i, j)表示ai + a(i+1) +…aj的正负号,要你还原a序列,其中a序列中每个数的绝对值不大于10.数列最多10个数 Analysis 根据每个数列段的符号可以转化为两个前缀和的大小关系,这就就得到了拓扑关系,拓扑...

UVa 1423 – Guess [数列前缀和+拓扑排序]

Problem 传送门 Mean 给你一个数n和一个字符矩阵,矩阵中S(i, j)表示ai + a(i+1) +…aj的正负号,要你还原a序列,其中a序列中每个数的绝对值不大于10.数...
阅读全文 0

UVa 1424 – Salesmen [DP]


Link 传送门 Mean 给定一个N个点M条边的无向图,一个人走出了一个路径,但这个路径有可能是不对的,例如图上并没有某条边。给你这个路径,让你再找出一条等长的路径,使得两条路径的距离最近。 路径的距离定义如下:每个点相同为0,不同为1. Analysis 比较简单的dp,...

UVa 1424 – Salesmen [DP]

Link 传送门 Mean 给定一个N个点M条边的无向图,一个人走出了一个路径,但这个路径有可能是不对的,例如图上并没有某条边。给你这个路径,让你再找出一条等长...
阅读全文 0

UVa 12174 – Shuffle [滑动窗口]


Link 传送门 Problem You are listening to your music collection using the shuffle function to keep the music surprising. You assume that the shuffle algorithm of your music player makes a random permutation of the songs in the playlist and plays th...

UVa 12174 – Shuffle [滑动窗口]

Link 传送门 Problem You are listening to your music collection using the shuffle function to keep the music surprising. You assume that the shuffle...
阅读全文 0

CodeForces 621C – Wet Shark and Flowers [数学期望]


Link 传送门 Problem There are n sharks who grow flowers for Wet Shark. They are all sitting around the table, such that sharks i and i + 1 are neighbours for all i from 1 to n - 1. Sharks n and 1 are neighbours too. Each shark will grow some numbe...

CodeForces 621C – Wet Shark and Flowers [数学期望]

Link 传送门 Problem There are n sharks who grow flowers for Wet Shark. They are all sitting around the table, such that sharks i and i + 1 are neig...
阅读全文 0