Archives: Uva 11064 problem

Advertisement

UVa 11064 - Number Theory

题目:求给顶一个数n,的所有的1 ≤ m ≤ n的m,使得gcd(m,n)≠ 1 且 gcd(m,n)≠ m. 分析:数论,素数筛法,欧拉函数. 设pi为n的第i个素数因,k1为第i个素数因子的个数,则有: 1 ≤ m ≤ n,gcd(m,n)= 1 的m的个数为欧拉函数: 欧拉函数:φ(n)= n *(1 - 1/p1)*(1 - 1/p2)*(1 - 1/p3)*-*(1 - 1/pt): 1 ≤ m ≤ n,gcd(m,n)= m 的m的个数为n的所有因数的个数: 因数个数:f(n)= (

uva 11700 Pipes(DP)

Problem G : Pipes From:UVA, 11700 Problem B: Pipes After writing a solver for the "moveable maze" game last week, you have grown tired of it. After all, you already know the optimal solution. To entertain yourself, you find another puzzle game c

近期精品网站回顾(060422--060519)

近期精品网站回顾(060422--060519) Computer Science: 1Computer and Information Science Papers CiteSeer Publications ResearchInde http://citeseer.ist.psu.edu/ 一个公开的免费查找并下载信息类专业论文的的网站. 2SIGCSE Home http://www.sigcse.org/index.shtml ACM中负责计算机教学的分部 3ACM SIGGRAPH h

UVa 100 - The 3n + 1 problem(函数循环长度)

题目来源:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36 The 3n + 1 problem Background Problems in Computer Science are often classified as belonging to a certain class of problems

[2016-02-19][UVA][524][Prime Ring Problem]

[2016-02-19][UVA][524][Prime Ring Problem] UVA - 524 Prime Ring Problem Time Limit: 3000MS Memory Limit: Unknown 64bit IO Format: %lld & %llu Submit Status Description A ring is composed of n (even number) circles as shown in diagram. Put natural num

uva 10026 Shoemaker's Problem

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=967 对价钱与天数比例排序,贪心即可. 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 2000 5 using namespace std; 6

UVa Problem 10026 Shoemaker’s Problem (鞋匠的烦恼)

// Shoemaker's Problem (鞋匠的烦恼) // PC/UVa IDs: 110405/10026, Popularity: C, Success rate: average Level: 2 // Verdict: Accepted // Submission Date: 2011-05-23 // UVa Run Time: 0.008s // // 版权所有(C)2011,邱秋.metaphysis # yeah dot net // // 算法:假设有 n 个订单 T1

uva 10837 - A Research Problem(欧拉函数+暴力)

题目链接:uva 10837 - A Research Problem 题目大意:给定一个phin,要求一个最小的n,欧拉函数n等于phin 解题思路:欧拉函数性质有,p为素数的话有phip=p−1;如果p和q互质的话有phip∗q=phip∗phiq 然后根据这样的性质,n=pk11(p1−1)∗pk22(p2−1)∗⋯∗pkii(pi−1),将所有的pi处理出来,暴力搜索维护最小值,虽然看上去复杂度非常高,但是因为对于垒乘来说,增长非常快,所以搜索范围大大被缩小了. #include <cs

UVa Problem 123 - Searching Quickly

// UVa Problem 123 - Searching Quickly // Verdict: Accepted // Submission Date: 2012-01-04 // UVa Run Time: 0.016s // // 版权所有(C)2012,邱秋.metaphysis # yeah dot net // // [解题方法] // 简单的字符串处理和排序题. // // 提交时错误了一次,因为没有注意到需要忽略的关键词可能会重复给出的情况,修正后就 AC 了. #inclu

UVa Problem 104 - Arbitrage

// UVa Problem 104 - Arbitrage // Verdict: Accepted // Submission Date: 2011-12-22 // UVa Run Time: 0.068s // // 版权所有(C)2011,邱秋.metaphysis # yeah dot net // // [解题方法] // 本质是求一个最小环,要求边权的积大于或等于 1.02,可以使用动态规划和 Floyd-Warshall 算法(实际上 // Floyd-Warshall 本身就

UVa Problem 119 - Greedy Gift Givers

// UVa Problem 119 - Greedy Gift Givers // Verdict: Accepted // Submission Date: 2011-11-26 // UVa Run Time: 0.012s // // 版权所有(C)2011,邱秋.metaphysis # yeah dot net // // [解题方法] // 简单的模拟题. #include <iostream> #include <map> using namespace std;

UVa Problem 10165 - Stone Game

// UVa Problem 10165 - Stone Game // Verdict: Accepted // Submission Date: 2011-11-17 // UVa Run Time: 0.020s // // 版权所有(C)2011,邱秋.metaphysis # yeah dot net // // [解题方法] // 啊哈,很有趣的一个题目.在网络上搜索一下 Nim 和 Xor,就可以了解到相关信息.若是自己想,一年也 // 想不出来吧. #include <iostr

UVa Problem 922 - Rectangle by the Ocean

// UVa Problem 922 - Rectangle by the Ocean // Verdict: Accepted // Submission Date: 2011-11-08 // UVa Run Time: 0.028s // // 版权所有(C)2011,邱秋.metaphysis # yeah dot net // // [解题方法] // 本题为计算几何题,使用有向面积计算多边形的面积.使用穷举法枚举可能的矩形左下角和右上角坐标,判断 // 矩形是否至少有三个角落在多边形

Uva 101 the block problem 木块问题(算法竞赛经典入门)STL vector

Uva 101 the block problem 木块问题 题目大意: 输入n,得到编号为0~n-1的木块,分别摆放在顺序排列编号为0~n-1的位置.现对这些木块进行操作,操作分为四种. 1.move a onto b:把木块a.b上的木块放回各自的原位,再把a放到b上: 2.move a over b:把a上的木块放回各自的原位,再把a发到含b的堆上: 3.pile a onto b:把b上的木块放回各自的原位,再把a连同a上的木块移到b上: 4.pile a over b:把a连同a上木块

UVa 893 Y3K Problem (用GregorianCalendar类秒杀)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=834 不解释. 完整代码: import java.util.*; import java.io.*; public class Main { static Scanner cin = new Scanner(new BufferedInputStream(Sy

Uva 17239 The 3n + 1 problem

 The 3n + 1 problem  Background Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is

uva 10401 Injured Queen Problem(dp)

题目链接:10401 - Injured Queen Problem 题目大意:给出一个字符串,要求在n * n(n为字符串的长度)的棋盘上摆放n个受伤的皇后,受伤的皇后只能攻击到同一列和它周围8个格子,如果字符串中第i个字符为'?'表示第i + 1个皇后可以摆放在任意行,如果为1 ~ F表示第i+1个皇后必须摆放在第str[i]行, 问,有多少种不同的摆法? 解题思路:一开始用递归 + 记忆化, 结果超时了, 后来发现其实可以写成递推,dp[i][j]代表第i个皇后摆放在第j行的摆法种类, d