RocksonLee's Blog
标签云分类友链工具集关于
USACO training 学习计划
USACOTraining Records
avatar
RocksonLee
2022-03-15 13:33:25
  • 本文总阅读量次

前言

USACO training 其实是很久之前就想彻底刷一遍的题单，但是因为其他的原因，一直没有完整的刷过一遍，这两个星期也有空，尝试刷刷吧！

USACO Section 1

1.2.2

Problem

Luogu

Solution

这一道题的思路就是把 A 类似这类的字母转化成 1 这类的数字。

然后暴力加减即可。

Code

/*
ID: RocksonLee
TASK: ride
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

void usaco(string problem)
{
    string in=problem+".in",out=problem+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}

#define N 100
char a[N], b[N];
int ans1 = 1, ans2 = 1, len;

int main()
{
    usaco("ride");
    scanf("%s%s", a, b);
    len = strlen(a);
    for (int i = 0; i < len; i++) ans1 *= a[i] - 'A' + 1;
    len = strlen(b);
    for (int i = 0; i < len; i++) ans2 *= b[i] - 'A' + 1;
    if (ans1 % 47 == ans2 % 47)
        cout << "GO\n";
    else
        cout << "STAY\n";
    return 0;
}

1.2.5

Problem

Luogu

Solution

这道题我在做匹配的时候直接使用string，string的包装及使用都非常的重要，很有用啊。

匹配人，然后利用C++的整数运算会去掉小数部分的特性直接计算即可。

然后我们需要特判m=0的情况。

Code

/*
ID: RocksonLee
TASK: gift1
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

void usaco(string problem)
{
    string in = problem + ".in", out = problem + ".out";
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
}

map<string, int> mp;
int n, w, m;
string name[100], temp;
int main()
{
    usaco("gift1");
    cin >> n;
    for (int i = 0; i < n; i++) cin >> name[i];
    for (int i = 0; i < n; i++)
    {
        cin >> temp >> w >> m; // w=money,m=people
        if (m) mp[temp] -= w / m * m;
        for (int j = 0; j < m; j++)
        {
            cin >> temp;
            mp[temp] += w / m;
        }
    }
    for (int i = 0; i < n; i++) printf("%s %d\n", name[i].c_str(), mp[name[i]]);
    return 0;
}

1.2.6

Problem

Luogu

Solution

这道题其实挺简单的，直接加上当前月份的天数就可以到第二月的13日。

1900.1.13是周六！

然后用一句很复杂（其实也不会）的三目运算符就可以解决当前月份的天数计算。

(m == 2 ? (((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) ? 29 : 28) : ((m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12) ? 31 : 30))

先把最复杂的2月计算给分割开。

然后2月分闰不闰。

其他月份分大不大。

Code

/*
ID: RocksonLee
TASK: friday
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

void usaco(string problem)
{
    string in = problem + ".in", out = problem + ".out";
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
}

int x, w, ans[10];
int main()
{
    usaco("friday");
    scanf("%d", &x);
    w = 5;
    for (int y = 1900; y < 1900 + x; y++)
    {
        for (int m = 1; m <= 12; m++)
        {
            ans[w]++;
            w += (m == 2 ? (((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) ? 29 : 28) : ((m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12) ? 31 : 30));
            w %= 7;
        }
    }
    for (int i = 5; i <= 10; i++) printf("%d ", ans[i % 7]);
    printf("%d\n", ans[11 % 7]);
    return 0;
}

1.2.7

Problem

Luogu

Solution

对于这一道题，我们应该尝试破环成链。

然后对这个环跑一边，因为有白色是那种特殊的东西，所以我们特殊对待。

白色可接前可接后。

a 记录最接近的白色左边位置。

b 记录串右边位置。

c 记录当前颜色。

最后记得 min(ans,n) 当你破环成链，然后整条链都是一种字符（不要抠字眼）时，那么会大于n，嗯。

Code

/*
ID: RocksonLee
TASK: beads
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

void usaco(string problem)
{
    string in=problem+".in",out=problem+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}

#define N 1000
int n, a, b, ans, w;
char s[N], c;

int main()
{
    usaco("beads");
    scanf("%d %s", &n, s);
    memcpy(s + n, s, n);
    for (int i = 0; i < n<<1; i++)
    {
        if (s[i] == 'w')
            b++, w++;
        else if (s[i] == c)
            b++, w = 0;
        else
            ans = max(ans, a + b), a = b - w, b = w + 1, w = 0, c = s[i];
    }
    ans=max(ans,a+b);
    printf("%d\n", min(ans,n));
    return 0;
}

1.3.2

Problem

Luogu

Solution

记录连续区间最长的左值和右值，区间若断裂，则记录最长断裂区间。

Code

/*
ID: RocksonLee
TASK: milk2
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

struct qwq
{
    int l;
    int r;
} a[6000];
int n, ansl, ansr;
int maxn, minn;
int cmp(qwq a, qwq b)
{
    if (a.l == b.l)
        return a.r < b.r;
    else
        return a.l < b.l;
}

void usaco(string problem)
{
    string in = problem + ".in", out = problem + ".out";
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
}

int main()
{
    usaco("milk2");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d", &a[i].l, &a[i].r);
    sort(a, a + n, cmp);
    ansl = a[0].l, ansr = a[0].r;
    for (int i = 0; i < n; i++)
    {
        if (ansr < a[i].l) minn = max(minn, a[i].l - ansr), ansl = a[i].l, ansr = a[i].r;
        ansl = min(ansl, a[i].l), ansr = max(ansr, a[i].r);
        maxn = max(maxn, ansr - ansl);
    }
    printf("%d %d\n", maxn, minn);
    return 0;
}

1.3.3

Problem

Luogu

solution

纯暴力了，没啥好说，寄。

Code

/*
ID: RocksonLee
TASK: transform
LANG: C++
*/
#include<bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

int n;
char a[15][15], b[15][15], c[15][15], d[15][15];
bool work1()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            b[j][n - i + 1] = a[i][j];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (b[i][j] != c[i][j])
                return 0;
    return 1;
}
bool work2()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            b[n - i + 1][n - j + 1] = a[i][j];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (b[i][j] != c[i][j])
                return 0;
    return 1;
}
bool work3()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            b[n - j + 1][i] = a[i][j];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (b[i][j] != c[i][j])
                return 0;
    return 1;
}
bool work4()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            b[i][n - j + 1] = a[i][j];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (b[i][j] != c[i][j])
                return 0;
    return 1;
}
bool work5()
{
    work4();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = b[i][j];
    if (work1())
        return 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = b[i][j];
    if (work2())
        return 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = b[i][j];
    if (work3())
        return 1;
    return 0;
}
bool work6()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (b[i][j] != c[i][j])
                return 0;
    return 1;
}
void work()
{
    if (work1())
    {
        cout << "1\n";
        return;
    }
    if (work2())
    {
        cout << "2\n";
        return;
    }
    if (work3())
    {
        cout << "3\n";
        return;
    }
    if (work4())
    {
        cout << "4\n";
        return;
    }
    if (work5())
    {
        cout << "5\n";
        return;
    }
    if (work6())
    {
        cout << "6\n";
        return;
    }
    cout << "7\n";
}

void usaco(string problem)
{
    string in=problem+".in",out=problem+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}

int main()
{
    usaco("transform");
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> a[i][j];
            d[i][j] = a[i][j];
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> c[i][j];
    work();
    return 0;
}

1.3.4

Problem

Luogu

solution

这道题就是简单的搜索，或者说是循环也可。

输入一次字典和编号。

然后说出可能的名字，循环为 3^n 次。

Code

/*
ID: RocksonLee
TASK: namenum
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

string dict[5000];
int cnt = 0;
bool ans = false;
string kb[10] = {"", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PRS", "TUV", "WXY"};

inline void dfs(string namenum, string result)
{
    if (namenum.empty())
    {
        if (*lower_bound(dict, dict + 4617, result) == result)
        {
            cout << result << endl;
            if (!ans) ans = true;
        }
    }
    else
        for (int i = 0; i < 3; i++) dfs(namenum.substr(1), result + kb[namenum[0] - '0'][i]);
    return;
}

void usaco(string problem)
{
    string in = problem + ".in", out = problem + ".out";
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
}

int main()
{
    usaco("namenum");
    string namenum;
    cin >> namenum;
    freopen("dict.txt", "r", stdin);
    for (int i = 0; i < 4617; i++) cin >> dict[i];
    dfs(namenum, "");
    if (!ans) cout << "NONE" << endl;
    return 0;
}

1.3.5

Problem

Luogu

solution

对于这道题，我们直接在结构体编写函数，以及编写一个初始化函数。

那么针对每一数，我们都可以搞一个答案出来。

Code

/*
ID: RocksonLee
TASK: palsquare
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

void usaco(string problem)
{
    string in = problem + ".in", out = problem + ".out";
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
}

int b;
inline char c(int x)
{
    if (x >= 0 && x <= 9) return x + '0';
    return x - 10 + 'A';
}
struct node
{
    int l, a[20];
    node(int x)
    {
        for (l = 0; x; l++) a[l] = x % b, x /= b;
    }
    void out()
    {
        for (int i = l - 1; i >= 0; i--) printf("%c", c(a[i]));
    }
    bool tf()
    {
        for (int i = 0; i < l; i++)
            if (a[i] != a[l - i - 1]) return false;
        return true;
    }
};
int main()
{
    usaco("palsquare");
    scanf("%d", &b);
    for (int i = 1; i <= 300; i++)
    {
        node n(i * i);
        if (n.tf())
        {
            node m(i);
            m.out();
            putchar(' ');
            n.out();
            putchar('\n');
        }
    }
    return 0;
}

1.3.6

Problem

Luogu

Solution

与上一题的解决方法不尽相同。

Code

/*
ID: RocksonLee
TASK: dualpal
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

struct Num
{
    int val[100], pp, n;
    Num(int x, int p)
    {
        for (n = 0; x; n++) val[n] = x % p, x /= p;
    }
    bool check()
    {
        for (int i = 0; i < n; i++)
            if (val[i] != val[n - i - 1]) return false;
        return true;
    }
};

void usaco(string problem)
{
    string in=problem+".in",out=problem+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}

int main()
{
    usaco("dualpal");
    int ans = 0;
    int n, s;
    scanf("%d%d", &n, &s);
    for (int i = s + 1; ans < n; i++)
    {
        int ok = 0;
        for (int j = 2; j < 11; j++)
        {
            Num temp(i, j);
            if (temp.check()) ok++;
        }
        if (ok>=2) printf("%d\n", i), ans++;
    }
    return 0;
}

1.4.2

Problem

Luogu

Solution

我们思考一下，贪心，就是需要把最便宜的先买了再说。

再买贵点的。

所以排序一下，再去买。

Code

/*
ID: RocksonLee
TASK: milk
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

#define N 200200
pair<int, int> q[N];
int x, n, ans;

void usaco(string problem)
{
    string in = problem + ".in", out = problem + ".out";
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
}

int main()
{
    usaco("milk");
    scanf("%d%d", &x, &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &q[i].first, &q[i].second);
    sort(q, q + n);
    for (int i = 0; i < n && x > 0; i++)
    {
        ans += (x < q[i].second ? x : q[i].second) * q[i].first;
        x -= q[i].second;
    }
    printf("%d\n", ans);
    return 0;
}

1.4.3

Problem

Luogu

Solution

对于这道题，我们还是尝试贪心做法，先有一块木板从头铺到尾，然后再断开 最长 的地方，重复断开 m-1 处，就可以只使用 m 块木板了。

特判你的牛的数量如果比木板多，那就是不是直接放就好呢。

Code

/*
ID: RocksonLee
TASK: barn1
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

#define N 500
int m, s, c, a[N], w[N];
int cmp(int a, int b)
{
    return a > b;
}

void usaco(string problem)
{
    string in=problem+".in",out=problem+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}

int main()
{
    usaco("barn1");
    scanf("%d%d%d",&m,&s,&c);
    if (m > c) { printf("%d\n", c); return 0; }
    for (int i = 0; i < c; i++) scanf("%d", &a[i]);
    sort(a, a + c);
    int ans = a[c - 1] - a[0] + 1;
    for (int i = 1; i < c; i++) w[i] = a[i] - a[i - 1];
    sort(w + 1, w + c, cmp);
    for (int i = 1; i <= m - 1; i++) ans -= w[i] - 1;
    printf("%d\n", ans);
    return 0;
}

1.4.5

Problem

Luogu

Solution

暴力拆解每一位，我们从100-999直接循环就好了，用一个函数解决重复问题（值得学习）。

Code

/*
ID: RocksonLee
TASK: crypt1
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

int a[20], n, ans;
il int check(int x)
{
    for (int i = 0; i < n; i++)
    {
        if (a[i] == x) return true;
    }
    return false;
}

il bool find(int xx, int p)
{
    for (int k = 0, x = xx; x; k++, x /= 10)
        if (k == p || !check(x % 10)) return false;
    return true;
}

void usaco(string problem)
{
    string in=problem+".in",out=problem+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}

int main()
{
    usaco("crypt1");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 100; i <= 999; i++)
    {
        for (int j = 10; j <= 99; j++)
        {
            int now1 = i * (j % 10), now2 = i * (j / 10), now3 = i * j;
            if (find(i, 3) && find(j, 2) && find(now1, 3) && find(now2, 3) && find(now3, 4)) ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}

1.4.6

Problem

Luogu

Solution

枚举锁头的每一位即可。

Code

/*
ID: RocksonLee
TASK: combo
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

int n, a[10], b[10];
bool flag[120][120][120];
ll ans;

void usaco(string problem)
{
    string in = problem + ".in", out = problem + ".out";
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
}

int main()
{
    usaco("combo");
    scanf("%d", &n);
    scanf("%d%d%d", &a[1], &a[2], &a[3]);
    scanf("%d%d%d", &b[1], &b[2], &b[3]);
    for (int i = -2; i <= 2; i++)
        for (int j = -2; j <= 2; j++)
            for (int k = -2; k <= 2; k++)
            {
                if (!flag[(a[1] + i + n) % n][(a[2] + j + n) % n][(a[3] + k + n) % n]) ans++;
                flag[(a[1] + i + n) % n][(a[2] + j + n) % n][(a[3] + k + n) % n] = true;
            }
    for (int i = -2; i <= 2; i++)
        for (int j = -2; j <= 2; j++)
            for (int k = -2; k <= 2; k++)
            {
                if (!flag[(b[1] + i + n) % n][(b[2] + j + n) % n][(b[3] + k + n) % n]) ans++;
                flag[(b[1] + i + n) % n][(b[2] + j + n) % n][(b[3] + k + n) % n] = true;
            }
    printf("%lld\n", ans);
    return 0;
}

1.4.7

Problem

Luogu

Solution

这道题的解法也是相当简单，比前面的题要求码力高一点。

首先你从一个传送门出来，进入第二个传送门，你是直接进入第一个传送门出来的右边第一个。

其次你走遍所有传送门最多就是所有传送门的个数。

然后你预处理一个门右面的那个门的位置。

暴力 DFS！

Code

/*
ID: RocksonLee
TASK: wormhole
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

#define N 20
int n;
struct qwq
{
    int x;
    int y;
} mp[N];
bool cmp(qwq a, qwq b)
{
    if (a.y == b.y)
        return a.x < b.x;
    else
        return a.y < b.y;
}
int r[N], to[N];
int ans;

bool is_cycle()
{
    for (int i = 1; i <= n; i++)
    {
        int pos = i;
        for (int cnt = 1; cnt <= n && pos; cnt++)
            pos = r[to[pos]];
        if (pos) return true;
    }
    return false;
}

void dfs(int step, int pre)
{
    if (step >= n)
    {
        if (is_cycle()) ans++;
    }
    else
        for (int i = pre + 1; i <= n; i++)
            if (!to[i])
                for (int j = i + 1; j <= n; j++)
                    if (!to[j])
                    {
                        to[i] = j, to[j] = i;
                        dfs(step + 2, i);
                        to[i] = to[j] = 0;
                    }
}

void usaco(string problem)
{
    string in = problem + ".in", out = problem + ".out";
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
}

int main()
{
    usaco("wormhole");
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &mp[i].x, &mp[i].y);
    sort(mp + 1, mp + n + 1, cmp);
    for (int i = 1; i <= n; i++)
        if (mp[i].y == mp[i + 1].y) r[i] = i + 1;
    dfs(0, 0);
    printf("%d\n", ans);
    return 0;
}

1.4.8

Problem

Luogu

Solution

尝试枚举最小到最大这个区间，这个区间的数来当这个所被允许的区间的左端点。

那么你在每一次枚举中计算每个山峰给你带来的贡献。

统计最小贡献就可以了。

Code

/*
ID: RocksonLee
TASK: skidesign
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

int n, now, ans = INF;

#define N 1000

int a[N];

void usaco(string problem)
{
    string in=problem+".in",out=problem+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}

int main()
{
    usaco("skidesign");
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    for (int i = a[i]; i <= a[n]; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (a[j] + 17 < i) now += (i-a[j] - 17) * (i-a[j] - 17);
            if (a[j] > i) now += (a[j]-i) * (a[j]-i);
        }
        ans = min(ans, now);
        now = 0;
    }
    printf("%d\n", ans);
    return 0;
}

1.5.2

Problem

Luogu

Solution

对于这道题，我们应该想清楚他要让我们干什么。

找到一个长度为n的等差数列，这个等差数列的数满足 { x | p^2 + q^2\ \ \ p,q \in N \cap [0,m] }。

而且输出需要按照 b 为第一关键字，a 为第二关键字进行排序。

所以我们再找这个的时候要记得按照 b 在外循环，a 在内循环。

然后暴力检查合不合法，那恭喜你，超时 啦！

因为 USACO 的内存限制为 16MB，但不要被这么小的内存限制住手脚，因为这个内存还可以开大约 4000000 的int数组，我们将 p^2 + q^2 预处理，用空间换时间，是不是很爽。

m \leq 250 所以只需要开 250000 左右的数组即可。

ok想好就开始搞！

Code

/*
ID: RocksonLee
TASK: ariprog
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

int n, top, flag, s[100000], check[250 * 250 * 2 + 100], tot;

void usaco(string problem)
{
    string in=problem+".in",out=problem+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}

int main()
{
    usaco("ariprog");
    scanf("%d %d", &n, &top);
    for (int i = 0; i <= top; i++)
        for (int j = 0; j <= top; j++)
            s[++tot] = i * i + j * j;
    for (int i = 0; i <= top; i++)
        for (int j = 0; j <= top; j++)
            check[i * i + j * j] = true;
    sort(s + 1, s + tot + 1);
    int m = unique(s + 1, s + tot + 1) - s;

    for (int i = 1; i * (n - 1) <= top * top + top * top; i++)
    {
        for (int j = 1; j <= m && s[j] + i * (n - 1) <= top * top + top * top; j++)
        {
            int now = i + s[j], ans = 1;
            while (check[now] && ans < n) now += i, ans++;
            if (ans == n) printf("%d %d\n", s[j], i), flag = true;
        }
    }
    if (flag == false) printf("NONE\n");
    return 0;
}

1.5.3

Problem

Luogu

Solution

对于这道题，我使用宽度（广度）优先搜索 BFS 进行解答。

对于每一个桶的的状态，使用 空间换时间 的方式进行判重。

装满溢出，还是完全倒干净，这样解决。

change = min ( limit - now , another_bottle_now)

然后最后储存答案。

当 a 桶是空的时候，c 桶中牛奶所剩量的所有可能性。

Code

/*
ID: RocksonLee
TASK: milk3
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

struct qwq
{
    int a, b, c;
    int step;
};

queue<qwq> q;

int n, checkx[30 * 30 * 30 + 100], limita, limitb, limitc, ans[30];

int check(qwq x)
{
    if (checkx[x.a * n * n + x.b * n + x.c]) return true;
    if (x.a == 0) ans[x.c] = true;
    checkx[x.a * n * n + x.b * n + x.c] = true;
    return false;
}

void bfs()
{
    while (!q.empty())
    {
        qwq temp, now = q.front();
        int change;
        if (now.a)
        {
            temp = now;
            change = min(limitb - temp.b, temp.a);
            temp.b += change, temp.a -= change;
            if (!check(temp)) q.push(temp);
            temp = now;
            change = min(limitc - temp.c, temp.a);
            temp.c += change, temp.a -= change;
            if (!check(temp)) q.push(temp);
        }
        if (now.c)
        {
            temp = now;
            change = min(limita - temp.a, temp.c);
            temp.a += change, temp.c -= change;
            if (!check(temp)) q.push(temp);
            temp = now;
            change = min(limitb - temp.b, temp.c);
            temp.b += change, temp.c -= change;
            if (!check(temp)) q.push(temp);
        }
        if (now.b)
        {
            temp = now;
            change = min(limita - temp.a, temp.b);
            temp.a += change, temp.b -= change;
            if (!check(temp)) q.push(temp);
            temp = now;
            change = min(limitc - temp.c, temp.b);
            temp.c += change, temp.b -= change;
            if (!check(temp)) q.push(temp);
        }
        q.pop();
    }
}

void usaco(string problem)
{
    string in = problem + ".in", out = problem + ".out";
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
}

int main()
{
    usaco("milk3");
    scanf("%d%d%d", &limita, &limitb, &limitc);
    n = max(limita, max(limitb, limitc)) + 1;
    q.push((qwq){0, 0, limitc, 0});
    bfs();
    bool flag = false;
    for (int i = 0; i < 30; i++)
    {
        if (ans[i])
        {
            if (flag) printf(" ");
            printf("%d", i);
            flag = true;
        }
    }
    printf("\n");
    return 0;
}

1.6.2

Problem

Luogu

Solution

对于这道题，我们的递推方程是这样的。

f[i][j]=max{f[i-1][j],f[i-1][j-1]}+a[i][j]

于是就写完了。

Code

/*
ID: RocksonLee
TASK: numtri
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

#define N 1010

int a[N][N], temp, maxn = -INF, n;

void usaco(string problem)
{
    string in = problem + ".in", out = problem + ".out";
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
}

int main()
{
    usaco("numtri");
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            scanf("%d", &temp);
            a[i][j] = temp + max(a[i - 1][j], a[i - 1][j - 1]);
            if (i == n)
                maxn = max(maxn, a[i][j]);
        }
    }
    printf("%d\n", maxn);
    return 0;
}

1.6.3

Problem

Luogu

Solution

这道题有两种方法

第一个枚举各位上的数，然后判断是否为素数。

第二种则是素数筛，判断素数。

我采用第二种。

但是 USACO 他卡我！！空间！！！

那么没办法了，打表吧。

Code

/*
ID: RocksonLee
TASK: pprime
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

int a[1000]={5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899};

void usaco(string problem)
{
    string in = problem + ".in", out = problem + ".out";
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
}

int main()
{
    usaco("pprime");
    int s, e;
    cin >> s >> e;
    for (int j = 0;; j++)
    {
        if (j >= 1000) break;
        if (a[j] >= s && a[j] <= e) cout << a[j] << endl;
        if (a[j] > e) break;
        if (a[j] < s) continue;
    }
    return 0;
}

Code2

/*
ID: RocksonLee
TASK: pprime
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

#define N 10000000

int prime[N/10], ptot = 0;
bool vis[N];

void get_prime(int n)
{
    vis[0] = vis[1] = true;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i]) prime[++ptot] = i;
        for (int j = 1; j <= ptot && i * prime[j] <= n; j++)
        {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

bool check(int x)
{
    int temp[10], tot = 0;
    while (x)
    {
        temp[++tot] = x % 10;
        x /= 10;
    }
    for (int i = 1; i <= tot; i++)
        if (temp[i] != temp[tot - i + 1]) return false;
    return true;
}

void usaco(string problem)
{
    string in = problem + ".in", out = problem + ".out";
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
}

int main()
{
    usaco("pprime");
    int l, r;
    scanf("%d %d", &l, &r);
    if (r > 10000000) r = 9999999;
    get_prime(r);
    for (int i = 1; i <= ptot; i++)
    {
        if (prime[i] < l) continue;
        if (check(prime[i])) printf("%d\n", prime[i]);
    }
    return 0;
}

1.6.4

Problem

Luogu

Solution

我们只需要用欧拉筛筛出质数，然后对质数进行一个拆分，再检查是否合法即可。

但是，USACO 我爱你，又爆内存了，那么看到这个输入这么简单。

n \leq 8

我直接就打表吧!

Code1

/*
ID: RocksonLee
TASK: sprime
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

void usaco(string problem)
{
    string in = problem + ".in", out = problem + ".out";
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
}

int main()
{
    usaco("sprime");
    int n;
    scanf("%d", &n);
    if (n == 8) printf("23399339\n29399999\n37337999\n59393339\n73939133\n");
    if (n == 7) printf("2339933\n2399333\n2939999\n3733799\n5939333\n7393913\n7393931\n7393933\n");
    if (n == 6) printf("233993\n239933\n293999\n373379\n373393\n593933\n593993\n719333\n739391\n739393\n739397\n739399\n");
    if (n == 5) printf("23333\n23339\n23399\n23993\n29399\n31193\n31379\n37337\n37339\n37397\n59393\n59399\n71933\n73331\n73939\n");
    if (n == 4) printf("2333\n2339\n2393\n2399\n2939\n3119\n3137\n3733\n3739\n3793\n3797\n5939\n7193\n7331\n7333\n7393\n");
    if (n == 3) printf("233\n239\n293\n311\n313\n317\n373\n379\n593\n599\n719\n733\n739\n797\n");
    if (n == 2) printf("23\n29\n31\n37\n53\n59\n71\n73\n79\n");
    if (n == 1) printf("2\n3\n5\n7\n");
    return 0;
}

Code2

/*
ID: RocksonLee
TASK: sprime
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

#define N 100000000

int prime[N / 10], ptot = 0;
bool vis[N];

void get_prime(int n)
{
    vis[0] = vis[1] = true;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i]) prime[++ptot] = i;
        for (int j = 1; j <= ptot && i * prime[j] <= n; j++)
        {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

void usaco(string problem)
{
    string in = problem + ".in", out = problem + ".out";
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
}

int main()
{
    usaco("sprime");
    int n;
    scanf("%d", &n);
    n = (int)pow(10, n);
    get_prime(n);
    for (int i = 1; i <= ptot; i++)
    {
        if (prime[i] < n / 10) continue;
        if (prime[i] > n) break;
        int x = prime[i];
        while (x)
        {
            if (vis[x]) break;
            x /= 10;
        }
        if (!x) printf("%d\n", prime[i]);
    }
    return 0;
}

USACO Section 2

2.1.3

Problem

Luogu

Solution

首先进行墙的二进制拆分

然后对图进行一个染色，输出颜色数量

接着检查每个颜色记录大小并输出

选择最佳的墙来推倒。有多解时选最靠西的，仍然有多解时选最靠南的。同一格子北边的墙比东边的墙更优先。 用该墙的南邻单位的北墙或西邻单位的东墙来表示这面墙，方法是输出邻近单位的行数、列数和墙的方位（ N（北）或者 E（东））。

因此，我们从左下向右上搜索，然后记录最大值

最后输出一下

Code

/*
ID: RocksonLee
TASK: castle
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

#define N 60

int n, m, ansx, ansy, ansn, answay, temp;

bool wall[N][N][5];

int color[N][N], ctot, size[N * N];

queue<pair<int, int>> q;

void bfs(int x, int y)
{
    if (color[x][y]) return;
    ctot++;
    q.push(make_pair(x, y));
    while (!q.empty())
    {
        int i = q.front().first, j = q.front().second;
        q.pop();
        if (color[i][j]) continue;
        color[i][j] = ctot;
        if (!color[i + 1][j] && !wall[i][j][3]) q.push(make_pair(i + 1, j));
        if (!color[i][j + 1] && !wall[i][j][2]) q.push(make_pair(i, j + 1));
        if (!color[i - 1][j] && !wall[i][j][1]) q.push(make_pair(i - 1, j));
        if (!color[i][j - 1] && !wall[i][j][0]) q.push(make_pair(i, j - 1));
    }
}

void usaco(string problem)
{
    string in=problem+".in",out=problem+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}

int main()
{
    usaco("castle");
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &temp);
            for (int k = 0; k < 4; k++) wall[i][j][k] = temp & (1 << k);
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            bfs(i, j);
    printf("%d\n", ctot);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            size[color[i][j]]++;
    for (int i = 1; i <= ctot; i++)
        ansn = max(ansn, size[i]);
    printf("%d\n", ansn);
    ansn = 0;
    for (int j = 1; j <= m; j++)
        for (int i = n; i >= 1; i--)
        {
            if (color[i][j] != color[i - 1][j] && ansn < size[color[i][j]] + size[color[i - 1][j]])
            {
                ansn = size[color[i][j]] + size[color[i - 1][j]];
                answay = 1;
                ansx = i;
                ansy = j;
            }
            if (color[i][j] != color[i][j + 1] && ansn < size[color[i][j]] + size[color[i][j + 1]])
            {
                ansn = size[color[i][j]] + size[color[i][j + 1]];
                answay = 2;
                ansx = i;
                ansy = j;
            }
        }
    printf("%d\n", ansn);
    printf("%d %d %c\n", ansx, ansy, (answay == 1 ? 'N' : 'E'));
    return 0;
}

2.1.4

Problem

Luogu

arrow_backCF 1650A Deletions of Two Adjacent Letters
USACO training 学习计划
USACO training 学习计划arrow_forward
comment评论
Search
search