4
5
2016
0

USACO 刷水

1666: [Usaco2006 Oct]Another Cow Number Game 奶牛的数字游戏

如果N是奇数,就把它乘以3后再加1。如果N是偶数,那么这个数就会被除以2。

当N的值等于1时停止。问变换的次数。

1、数据太弱,直接模拟0s可过:其实还需特判1+大数据开LL

处理的数据可能远大于n,无法估计数据可能达到的大小时一定要开LL

2、记忆化搜索?这道题会慢很多

注意到1000W一下的数会被访问很多次,所以记录1000W以下的。

#include <iostream>
using namespace std;
int a[11111111];
int gao(long long x)
{
    if(x == 1) return 1;
    if(x < 10000000 && a[x]) return a[x];
    int tmp;
    if(x % 2 == 0)
        tmp = gao(x / 2) + 1;
    else
        tmp = gao(x * 3 + 1) + 1;
    if(x < 10000000) a[x] = tmp;
    return tmp;
}
int main()
{
    int n;
    cin >> n;
    cout << gao(n)  - 1<< endl;
    return 0;
}

3、著名的“角谷猜想”

这样一直算下去,最后数字会在一个循环圈里循环,这个循环圈是(4→2→1→4)。

即经过有限步后,一定可以得到1

扩展:

任举一个正整数n,如果n能被a整除,就将它变为n/a,如果除后不能再整除,则将它乘b加c(即bn+c)。不断重复这样的运算,经过有限步后,一定可以得到d吗?

此题的答案只能有3种 :1.不一定 2.一定不 3.一定都
以下都是一定都的情况
一 a=b=c=d=m
二 a=m b=1 c=-1 d=0
三 a=m b=c=d=1
四 a=2 b=2^m-1 c=-1 d=1
以上(m>1)
五 a=2 b=2^m-1 c=1 d=1
六 a=2 b=c=d=2^m-1
以上m为任意自然数
 

1579: [Usaco2009 Feb]Revamping Trails 道路升级

求无向带权图1-n最短路,其中可选择k条路径使其权值为0.


1690: [Usaco2007 Dec]奶牛的旅行

有向图中,点和边均有权值,要求找出一个环,使环内(Σ边权)/(点权)最大。不考虑自环。

01分数规划求最优比例环。

1708: [Usaco2007 Oct]Money奶牛的硬币

多重背包dp.


1782: [Usaco2010 Feb]slowdown 慢慢游


1711: [Usaco2007 Open]Dining吃饭

经典网络流


1725: [Usaco2006 Nov]Corn Fields牧场的安排

经典状压dp


1592: [Usaco2008 Feb]Making the Grade 路面修整

将一个序列A更改为不上升/不下降序列B的最小费用,费用定义为 |A_1 - B_1| + |A_2 - B_2| + ... + |A_N - B_N|

经典dp


1715: [Usaco2006 Dec]Wormholes 虫洞


登录 *


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

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com