【福利】USACO 2022-2023赛季试题解析系列（3月公开赛）

#include <bits/stdc++.h>using namespace std;char s[200010];int main() {    int n;    cin >> n;    if (n == 1) {        cout << 0;        return 0;    }    // l和r之间都为F    int l = -1, r = -1, d = 0, u = 0, isc = 1;    cin >> s;    for (int i = 0; i < n; i++) {        if (s[i] == 'F') {            if (i == 0)                l = -1;            else if (s[i - 1] != 'F')                l = i - 1;
            if (i == n - 1) {  // 末尾是F                isc = 0;                if (l == -1)                    u += n - 1;                else                    u += i - l;            } else if (s[i + 1] != 'F') {                r = i + 1;                if (l == -1) {                    isc = 0;                    u += r;                } else if (s[r] == s[l]) {                    u += r - l;                    d += (r - l) % 2;                } else {                    u += r - l - 1;                    d += (r - l - 1) % 2;                }            }        }        if (i > 0) {            if (s[i] != 'F' && s[i] == s[i - 1]) { // 相邻两个字符一样，最大最小值各加1                u++;                d++;            }        }    }
    if (isc) { // F都在中间        cout << (u - d) / 2 + 1 << endl;        for (int i = d; i <= u; i += 2) cout << i << '\n';    } else {        cout << (u - d) + 1 << endl;        for (int i = d; i <= u; i += 1) cout << i << '\n';    }}

#include <bits/stdc++.h>using namespace std;vector<string> iverb, tverb, noun, con;
int main() {    int T;    cin >> T;    while (T--) {        int n, c, p;        cin >> n >> c >> p;        string s1, s2;        string ans = "";        iverb.clear(); // intransitive-verb        tverb.clear(); // transitive-verb        noun.clear(); // noun        con.clear(); // conjunction        for (int i = 0; i < n; i++) {            cin >> s1 >> s2;            if (s2[0] == 'i')                iverb.push_back(s1);            else if (s2[0] == 't')                tverb.push_back(s1);            else if (s2[0] == 'n')                noun.push_back(s1);            else                con.push_back(s1);        }    int ivcnt = iverb.size();    int tvcnt = tverb.size();    int nocnt = noun.size();    int cocnt = con.size();
        int ivcnt2 = 0, tvcnt2 = 0, nocnt2 = 0, cocnt2 = 0;        int wordcnt = 0;
        for (int i = 0; i <= ivcnt; i++) // 枚举用i个intransitive verb            for (int j = 0; j <= tvcnt; j++) { // 用j个transitive-verb                if (i + j > p + min(cocnt, p)) continue; // 每个verb都要算一句话，一个conjunction可以连接两句话                                                               // conjunction数量要小于等于periods                if (i + j * 2 > noun.size()) continue; // int-veb要用一个noun, t-verb至少两个noun，不够就continue                int cnt = i * 2 + j * 3 + min((i + j) / 2, cocnt);                if (j > 0) {          cnt += min(nocnt - i - j * 2, c); // 加上comma的贡献        }                if (cnt > wordcnt) {                    ivcnt2 = i;                    tvcnt2 = j;                    if (j > 0)                        nocnt2 = i + j * 2 + min(nocnt - i - j * 2, c);                    else                        nocnt2 = i;                    cocnt2 = min((i + j) / 2, cocnt);                    wordcnt = cnt;                }            }        cout << wordcnt << endl;
    ivcnt = ivcnt2;    tvcnt = tvcnt2;    nocnt = nocnt2;    cocnt = cocnt2;
        int coid = 0, finished = 0;        for (int i = 0; i < ivcnt; i++) {            ans += noun[i];            ans += ' ';            ans += iverb[i];      // 拼接 conjunction            if (coid < cocnt && finished == 0) {                ans += ' ' + con[coid] + ' ';                coid++;                finished = 1; // 一句话中最多用一个conjunction            } else {                ans += ". ";                finished = 0;            }        }
        int noid = ivcnt;        for (int i = 0; i < tvcnt; i++) {            ans += noun[noid];            noid++;            ans += ' ';            ans += tverb[i];            ans += ' ';            ans += noun[noid];            noid++;      // 拼接 comma + noun            if (i == tvcnt - 1) {                while (noid < nocnt) {                    ans += ", " + noun[noid];                    noid++;                }            }
      // 拼接 conjunction            if (coid < cocnt && finished == 0) {                ans += ' ' + con[coid] + ' ';                coid++;                finished = 1;            } else {                ans += ". ";                finished = 0;            }        }        if (ans.length() > 0)            cout << ans.substr(0, ans.length() - 1) << endl; // 减1是去掉行末空格        else            cout << ans << endl;    }}

#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 1;int n, k, t;int a[N], f[N], p2[N];int main() {  cin >> n >> k >> t;  for (int i = 1; i <= k; i++) {    cin >> a[i];  }  a[k + 1] = a[1] + n;  for (int i = 1; i <= k; i++) {    // f[i]存储数组a的第i个和第(i+1)个元素之间的距离。    f[a[i]] = a[i + 1] - a[i];  }    // 往答案数组里填数据  int lst = 0;  // 循环遍历n个值，并为每个值计算p2中相应值的索引。  for (int i = 0; i < n; i++) {    if (f[i]) lst = i;        // 计算t1的值，它是当前索引i被处理后的剩余时间。处理当前索引所花费的时间是(i-lst)。    int t1 = t - (i - lst);        // 计算在剩余时间t1内可以完成的距离f[lst]的完整循环数。    int round = ceil(1.0 * t1 / f[lst]);        // 使用公式(i+k*f[lst])%n计算出p2中对应值的索引，并设置为i。    p2[(i + round * f[lst]) % n] = i;  }    cout << p2[0];  for (int i = 1; i < n; i++) {    cout << " " << p2[i];  }}

#include <bits/stdc++.h>using namespace std;char s[20];int num[100010];int dis[600][600];int h[600];int main() {    int n, c;    cin >> c >> n;    for (int i = 0; i < 512; i++) {        int j = i;        while (j) {            if (j % 2 == 1) h[i]++;            j /= 2;        }    }    for (int i = 1; i <= n; i++) {        scanf("%s", s);        int t = 0;        for (int j = 0; j < c; j++)            if (s[j] == 'G')                t = t * 2;            else                t = t * 2 + 1;        num[i] = t;    }    for (int i = 0; i < 512; i++)        for (int j = 0; j < 512; j++) dis[i][j] = -1e9;
    for (int i = 1; i <= n; i++) {        int a = num[i] / 512, b = num[i] % 512;        for (int j = 0; j < 512; j++) dis[a][j] = max(dis[a][j], h[b ^ j]);    }
    for (int i = 1; i <= n; i++) {        int ans = 0, a = num[i] / 512, b = num[i] % 512;        for (int j = 0; j < 512; j++) ans = max(ans, h[a ^ j] + dis[j][b]);        printf("%d\n", ans);    }}