USACO 4.3.2 The Primes

輝夜(tadvent) posted @ 2009年4月25日 07:29 in USACO with tags usaco , 3005 阅读
够BT的一道题,改了几遍才过 - -
一开始没想费太多内存觉得稍微预存几种结果应该就差不多了,结果完全低估了数据规模。
只好把所有可能用到的模式全预算出来再循环。结果弄了快300行ORZ...
还有一次犯傻没排序就跑去提交了
 
TASK: prime3
LANG: C++
 
Compiling...
Compile: OK
 
Executing...
   Test 1: TEST OK [0.065 secs, 2984 KB]
   Test 2: TEST OK [0.054 secs, 2988 KB]
   Test 3: TEST OK [0.065 secs, 2984 KB]
   Test 4: TEST OK [0.065 secs, 2988 KB]
   Test 5: TEST OK [0.076 secs, 2984 KB]
   Test 6: TEST OK [0.140 secs, 2984 KB]
   Test 7: TEST OK [0.119 secs, 2988 KB]
   Test 8: TEST OK [0.130 secs, 2988 KB]
   Test 9: TEST OK [0.205 secs, 2988 KB]
   Test 10: TEST OK [0.259 secs, 2988 KB]
 
All tests OK.
Your program ('prime3') produced all correct answers!  This is your
submission #5 for this problem.  Congratulations!
 
要速度,貌似只能模拟填表的过程,并且每步选限制尽可能多的行或列来填。
第1行和第1列限制最多,开头第1位已定,且各位都不能出现0,先把他们填了。
然后选辅对角线(左下到右上),因为开头结尾两位都已定。
再填主对角线,第1位和第3位已定。
下面是第二行、第二列、第四行、第四列,这四种情况都是 1、2、4 位已定
然后第三行和第三列都只剩下最后一位空缺了。最后检查一下第五行和第五列即可。
 
从上面过程看出要预先计算的是:
(1) 所有5位质数且各位数字和满足条件的数
(2) 第1位已知且满足(1),各位都不为0的组合
(3) 1、5位已知且满足(1)的组合
(4) 1、3位已知且满足(1)的组合
(5) 1、2、3、4位已知且满足(1)的组合
 
其他好像有提出先填第5行和第5列的,因为这两行除了满足质数与数字和外 各位只能是 1、3、7、9 四选一。不过我觉得这没有用,例如只要第一列填了质数,则第5行第一位自然就只会是 1、3、7、9 之一了,先填第5行对第1列来说也并没有其他额外限制作用。但仅是猜测,也没试验过。
 
预先开个100000的数组,第一遍求所有质数(顺便将不是质数的值存为下标方便遍历),然后筛选数字和满足条件的数,同样使下标形成链表方便遍历。同时选出各位数字满足条件的组合预先存起来,剩下只用循环便是。排序嘛,就每位挨个判断了,也没几个数。
njmcdirect 说:
2022年8月26日 10:27

NJMCdirect – the fast, secure and convenient way to access and pay your Traffic Ticket and Municipal Complaint online. njmcdirect To view or pay your Traffic 2021. NJMCDirect Pay Traffic Tickets Online – www.NJMCDirect.com · What is NJMCDirect? · NJMCDirect Pay – What will you need to pay njmcdirect ticket payment 2021.NJMCdirect – the fast, secure and convenient way to access and pay your Traffic Ticket and Municipal Complaint online.

Assam Board Question 说:
2022年9月07日 17:18

Assam Board Model Paper 2023 Class 6 Pdf Download with Answers for English Medium, Bangali Medium, Hindi Medium & Assamese Medium Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. Assam Board Question Paper Class 6 New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.

Alyssa 说:
2023年1月07日 20:28

The Primes is a USACO problem that asks for the number of prime numbers less than or equal to a given integer n. Given an integer n, the program should output the number of prime numbers less than or equal to n. This problem Lab grown diamonds can be solved using a simple brute force approach, which is to iterate through all the numbers from 2 to n and check if each number is prime. However, this approach is too slow for large values of n. A better approach is to use the Sieve of Eratosthenes, which is a fast algorithm for finding all prime numbers up to a given integer n.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter