首页 > 其他分享 >Codeforces Round 972 (Div. 2)

Codeforces Round 972 (Div. 2)

时间：2024-09-16 08:53:22浏览次数：9  
标签：last 972 int Codeforces long while Div dp getchar

A. Simple Palindrome

给定整数 \(n\)，构造长度为 \(n\) 的只由a e i o u的字符串，使得它的回文子序列最少。

容易发现 aia 不如 aai 优，贪心的将每种字符放在一起，并将总个数尽量均分到每个字符上。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

void solve()
{
    int n = read();
    int k = n / 5, res = n % 5;
    for(int i = 1; i <= k; ++i) printf("a");
    if(res) {printf("a"); --res;}
    for(int i = 1; i <= k; ++i) printf("e");
    if(res) {printf("e"); --res;}
    for(int i = 1; i <= k; ++i) printf("i");
    if(res) {printf("i"); --res;}
    for(int i = 1; i <= k; ++i) printf("o");
    if(res) {printf("o"); --res;}
    for(int i = 1; i <= k; ++i) printf("u");
    printf("\n");

}

int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}

B1. The Strict Teacher (Easy Version)

有一排 \(n\) 间房间，\(m\) 个老师，一个学生在逃课，最初所有人的位置互不相同，每一步每个人都可以留在原地或者向相邻的房间走，问最多需要几步抓住学生。

如果没有老师在学生的左边或者右边，那么学生可以跑到最左边或者最右边直到被抓住。

如果学生两边都有老师，设最近的两个老师中间的房子为 \(len\) ，每次都可以使 \(len - 2\) ，直到 \(len\) 小于等于 \(0\)。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 2e5 + 5;
int a[N];

void solve()
{
    int n = read(), m = read(), q = read();
    for(int i = 1; i <= m; ++i) a[i] = read();
    sort(a + 1, a + m + 1);
    while(q--)
    {
        int pos = read();
        if(pos < a[1]) printf("%d\n", a[1] - 1);
        else if(pos > a[m]) printf("%d\n", n - a[m]);
        else
        {
            int id = upper_bound(a + 1, a + m + 1, pos) - a;
            int len = a[id] - a[id - 1] - 1;
            printf("%d\n", (len + 1) / 2);
        }
    }
}

int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}

B2. The Strict Teacher (Hard Version)

同 \(B1\)。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 2e5 + 5;
int a[N];

void solve()
{
    int n = read(), m = read(), q = read();
    for(int i = 1; i <= m; ++i) a[i] = read();
    sort(a + 1, a + m + 1);
    while(q--)
    {
        int pos = read();
        if(pos < a[1]) printf("%d\n", a[1] - 1);
        else if(pos > a[m]) printf("%d\n", n - a[m]);
        else
        {
            int id = upper_bound(a + 1, a + m + 1, pos) - a;
            int len = a[id] - a[id - 1] - 1;
            printf("%d\n", (len + 1) / 2);
        }
    }
}

int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}

C. Lazy Narek

给定 \(n\) 个长度为 \(m\) 的字符串，一个人 \(A\) 和 \(GPT\) 玩游戏，对于一个字符串 \(S\)，

\(A\) 的策略是循环选取n a r e k，每选出一组，\(score_A += 5\)，不足一组不算 \(A\) 选取的。

对于 \(A\) 没有选取的n a r e k，每一个字符使 \(score_{GPT} += 1\)。

目标是，在不改变 \(n\) 的字符串的相对顺序的情况下，选取一些字符串依次连接构成 \(S\)，使 \(score_A - score_{GPT}\) 最大。

容易发现秉持能匹配则匹配的原则一定最优。

发现只有5种字符有用，且字符串顺序不变，设 \(dp[i][j]\) 表示考虑前 \(i\) 个串，最后一组匹配了 \(j\) 个字符时，\(score_A - score_{GPT} + j\) 最大。

\(+ j\) 是最后 \(j\) 个字符既不算入 \(A\) 的分数，也不算入 \(GPT\) 的分数。

首先对第 \(i\) 个字符串 \(DP\) 求出 \(sum_i, len_i\)，表示前 \(i-1\) 个字符串最后一组匹配了 \(i\) 个字符时，匹配完 \(s_i\) 后最后一组匹配了 \(len_i\) 个字符，\(sum_i = score_A - score_{GPT} + len_i\)。

转移时枚举前 \(i-1\) 个字符串最后一组的匹配字符数。

\[dp[i][len[j]] = dp[i - 1][j] + sum[j] \]

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int inf = 0x3f3f3f3f;
const int N = 1e3 + 5;
int n, m;
int id[500], vis[500];
char s[N];
int sum[5], len[5];

void init(char s[])
{
    for(int i = 0; i <= 4; ++i) sum[i] = 0, len[i] = i;
    for(int i = 1; i <= m; ++i)
    {
        if(vis[s[i]])
        {
            for(int j = 0; j <= 4; ++j)
            {
                if(id[s[i]] == len[j] + 1)
                {
                    len[j]++;
                    if(len[j] == 5) sum[j] += 5, len[j] = 0;
                }else sum[j]--;
            }
        }
    }
}

int dp[N][6];

void solve()
{
    n = read(), m = read();
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= 5; ++j)
            dp[i][j] = -inf;
    dp[0][0] = 0;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%s", s + 1);
        init(s);
        // for(int j = 0; j <= 4; ++j) printf("sum = %d len = %d\n", sum[j], len[j]);
        // printf("\n");
        for(int j = 0; j <= 4; ++j) dp[i][j] = dp[i - 1][j];
        for(int j = 0; j <= 4; ++j)
            dp[i][len[j]] = max(dp[i][len[j]], dp[i - 1][j] + sum[j]);
    }
    int ans = 0;
    for(int i = 0; i <= 4; ++i) ans = max(ans, dp[n][i] - i);
    printf("%d\n", ans);
}

int main()
{
    id['n'] = 1, id['a'] = 2, id['r'] = 3, id['e'] = 4, id['k'] = 5;
    vis['n'] = 1, vis['a'] = 1, vis['r'] = 1, vis['e'] = 1, vis['k'] = 1;
    int T = read();
    while(T--) solve();
    return 0;
}

D. Alter the GCD

注意到一个序列的前缀 \(\operatorname{gcd}\) 最多变化 \(\log\) 次。

记选择翻转区间的 \(\gcd\) 为 \(midA\) 和 \(midB\)，同理设前后缀 \(gcd\) 为 \(preA, sufA, preB, sufB\)。

考虑枚举选择翻转的段的左端点 \(l\)，对于不同的 \(r\)，\(midA, midB, sufA, sufB\) 都最多变化 \(\log\) 次。

那么对于不同的 \(r\) ，至多有 \(4\log\) 的位置会改变四种 \(\gcd\)，每次二分找到下一次改变 \(\gcd\) 的位置即可。

对于答案统计，由于每一段左端点固定，右端点是一段区间且四种 \(\gcd\) 都不变，方案数即右端点所在区间长度。

二分+求\(\gcd\)+右端点\(\log\)次变化 = \(O(n\log^3n)\)。

（这能过5e5？）

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 2e5 + 5;
int n, a[N], b[N];
int lg[N], stA[20][N], stB[20][N];

int gcd(int x, int y)
{
    if(!x || !y) return x | y;
    return gcd(y, x % y);
}

int getgcd(int l, int r, int d)
{
    if(l > r) return 0;
    int k = lg[r - l + 1];
    if(d == 0) return gcd(stA[k][l], stA[k][r - (1 << k) + 1]);
    if(d == 1) return gcd(stB[k][l], stB[k][r - (1 << k) + 1]);
    return 0;
}

void solve()
{
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i <= n; ++i) b[i] = read();
    for(int i = 1; i <= n; ++i) stA[0][i] = a[i], stB[0][i] = b[i];
    for(int i = 1; i <= 19; ++i)
        for(int j = 1; j + (1 << i) - 1 <= n; ++j)
        {
            stA[i][j] = gcd(stA[i - 1][j], stA[i - 1][j + (1 << (i - 1))]);
            stB[i][j] = gcd(stB[i - 1][j], stB[i - 1][j + (1 << (i - 1))]);
        }
    ll ans = 0, sum = 0;
    int preA = 0, preB = 0;
    for(int l = 1; l <= n; ++l)
    {
        int midA = a[l], sufA = getgcd(l + 1, n, 0), midB = b[l], sufB = getgcd(l + 1, n, 1);
        int last = l, L = l, R = n;
        while(L <= n)
        {
            while(L < R)
            {
                int mid = (L + R + 1) >> 1;
                if(midA == getgcd(l, mid, 0) && sufA == getgcd(mid + 1, n, 0) && midB == getgcd(l, mid, 1) && sufB == getgcd(mid + 1, n, 1)) L = mid;
                else R = mid - 1;
            }
            int tmp = gcd(preA, gcd(midB, sufA)) + gcd(preB, gcd(midA, sufB)), cnt = L - last + 1;
            // printf("l = %d, r = %d, preA = %d, midA = %d, sufA = %d, preB = %d, midB = %d, sufB = %d\n", l, L, preA, midA, sufA, preB, midB, sufB);
            // printf("tmp = %d, sum = %d\n", tmp, sum);
            if(tmp > ans) ans = tmp, sum = cnt;
            else if(tmp == ans) sum += cnt;
            ++L, R = n, last = L;
            midA = getgcd(l, L, 0), sufA = getgcd(L + 1, n, 0), midB = getgcd(l, L, 1), sufB = getgcd(L + 1, n, 1);
        }


        preA = gcd(preA, a[l]), preB = gcd(preB, b[l]);
    }
    printf("%lld %lld\n", ans, sum);
}

int main()
{
    lg[0] = -1;
    for(int i = 1; i <= 200000; ++i) lg[i] = lg[i >> 1] + 1;
    int T = read();
    while(T--) solve();
    return 0;
}

E1. Subtangle Game (Easy Version)

设 \(dp[i][j][k]\) 表示第 \(i\) 步选择 \(b[j][k]\) 时是否有必胜策略。

转移时，枚举 \(l > j, t > k\)。

若存在 \(dp[i + 1][l][t]\) 为真，则 \(dp[i][j][k]\) 为假。

若不存在，且 \(a[i] = b[j][k]\)（第 \(i\) 步可以选择 \(b[j][k]\)），则 \(dp[i][j][k]\) 为真。

发现可以二维前缀和优化，\(O(n^3)\) 过。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 305;
int l, n, m;
int a[N];
int b[N][N];
int dp[N][N][N];

void solve()
{
    l = read(), n = read(), m = read();
    for(int i = 1; i <= l; ++i) a[i] = read();
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            b[i][j] = read();
    for(int i = 0; i <= l + 1; ++i)
        for(int j = 0; j <= n + 1; ++j)
            for(int k = 0; k <= m + 1; ++k)
                dp[i][j][k] = 0;
    for(int i = l; i >= 1; --i)
    {
        for(int j = n; j >= 1; --j)
            for(int k = m; k >= 1; --k)
            {
                if(b[j][k] == a[i])
                {
                    if(!dp[i + 1][j + 1][k + 1]) dp[i][j][k] = 1;
                }
                dp[i][j][k] = dp[i][j][k] + dp[i][j + 1][k] + dp[i][j][k + 1] - dp[i][j + 1][k + 1];
            }
    }
    if(dp[1][1][1]) printf("T\n");
    else printf("N\n");
}

int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}

E2. Subtangle Game (Hard Version)

考虑 \(E1\) 的 \(dp\) 做完前缀和后的新定义：第 \(i\) 步选择子矩阵 $b[j][k] \sim b[n][m] $ 中的数，是否有必胜策略。

发现若 \(dp[i][j][k]\) 为真，\(dp[i+2][j][k]\) 也一定为真。

只需要对奇数和偶数分别考虑即可，设 \(dp0[j][k]\) 表示偶数步选择子矩阵 $b[j][k] \sim b[n][m] $ 中的数，最小的必胜步数（即最小的 \(i\))，\(dp1[j][k]\) 同理。

记 \(last[x]\) 表示值 \(x\) 在 \(a\) 序列中第一次出现的位置。

转移时，若 \(last[b[i][j]] \% 2 = 1\)，且 \(dp0[i+1][j+1] > last[b[i][j]]+1\)，则 \(dp1[i][j] = last[b[i][j]]\)。

意思是，第 \(last[b[i][j]]\) 步选了 \(b[i][j]\)，且另一个人不存在 在不超过 \(last[b[i][j]]+1\) 步选矩阵 \(b[i+1][j+1] \sim b[n][m]\) 中的数 的情况下的必胜策略，那么这一步是必胜的，最小步数是 \(last[b[i][j]]\)。

一点思考：同一个值在 \(a\) 序列中会出现多次，也会出现在奇数位和偶数位，为什么只考虑第一次出现？

在 \(b\) 矩阵中，同样的值，选择更靠近右下角的位置一定更优，因此对于 \(a\) 序列中的数，两个人是抢着选 \(b\)，因此只考虑每种值第一次出现的位置。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int inf = 0x3f3f3f3f;
const int N = 1505;
int l, n, m;
int a[N], b[N][N], last[N * N];
int dp0[N][N], dp1[N][N];

void solve()
{
    l = read(), n = read(), m = read();
    for(int i = 1; i <= l; ++i)
    {
        a[i] = read();
        if(!last[a[i]]) last[a[i]] = i;
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            b[i][j] = read();
    for(int i = 0; i <= n + 1; ++i)
        for(int j = 0; j <= m + 1; ++j)
            dp0[i][j] = dp1[i][j] = inf;
    for(int i = n; i >= 1; --i)
        for(int j = m; j >= 1; --j)
        {
            dp0[i][j] = min(dp0[i + 1][j], dp0[i][j + 1]);
            dp1[i][j] = min(dp1[i + 1][j], dp1[i][j + 1]);
            if(!last[b[i][j]]) continue;
            if(last[b[i][j]] % 2 == 0 && dp1[i + 1][j + 1] > last[b[i][j]] + 1) dp0[i][j] = min(dp0[i][j], last[b[i][j]]);
            if(last[b[i][j]] % 2 == 1 && dp0[i + 1][j + 1] > last[b[i][j]] + 1) dp1[i][j] = min(dp1[i][j], last[b[i][j]]);
        }
    if(dp1[1][1] == 1) printf("T\n");
    else printf("N\n");
    for(int i = 1; i <= l; ++i) last[a[i]] = 0;
}

int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}

标签：last,972,int,Codeforces,long,while,Div,dp,getchar
From： https://www.cnblogs.com/wenqizhi/p/18415136

相关文章

  • Codeforces Round 970 (Div. 3) 复盘
    CodeforcesRound970(Div.3)Sep/01/202422:35UTC+8length02:15好闲啊，还要写div3的复盘，就当听歌的同时练习翻译兼打字了。总而言之还是太菜了#Who=Penalty*ABCDEFGH1624BaSEc1d6250+00:04+00:19+00:24+00:34+01:17+01:32因为开学前......
  • Codeforces Round 968 (Div. 2)
    传送门A.判断首位字符是否相等即可#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+7;voidsolve(){intn;strings;cin>>n>>s;if(s[0]==s[n-1])cout<<"No"<<endl;elsecout<&l......
  • Codeforces 972 div2
    A-SimplePalindrome1、先对字母进行分配，每个字母分到n/5个2、对剩余字母进行分配，前n%5个字母每一个分配一个3、分别将其输出，相同字母放在一起，如果相同字母分开，就会出现如“ABA”这样的回文子串。AC代码：#include<bits/stdc++.h>usingnamespacestd;charss[7]={......
  • Codeforces Round 972 (Div. 2) 2005C. Lazy Narek 题解
    原题链接：https://codeforces.com/contest/2005/problem/C看了教程发现都是用dp做的，在这里分享一个差不多的SPFA的思路（赛场上忘了Dijkstra不能有负边所以炸了）时间复杂度与dp同样是O(nm)形式化题意和翻译：有n个长度为m的字符串，你可以选择或不选择来拼接它们，但是不能更改字符串的......
  • 【LGR-200-Div.4】洛谷入门赛 #27 A-H题解
    A#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;mt19937rnd(time(0));#defineintlonglongtypedeftuple<int,int,int>tp;#definexfirst#defineysecondtypedefpair<int,int>pii;typedefpair<double,double>......
  • CodeForces VP Record
    CodeForcesRound767(contest1628)AMeximumArray考虑二分。二分的时候计算区间$\text{mex}$，参考P4137RmqProblem/mex，主席树即可。时间复杂度$\Theta(n\log^2n)$，无需卡常。BPeculiarMoviePreferences首先，对于一个合法的回文串，容易证明首尾两个字符串一定......
  • CodeForces 1C - Ancient Berland Circus
    先通过三点确定一条直线，然后算出三条向量的夹角，与圆心角对比，如果呈倍数关系，说明可以接受。特别注意EPS1e-2和1e-7过不了全部数据，改成1e-4通过全部数据。点击查看代码#include<bits/stdc++.h>#definedoublelongdoubleusingnamespacestd;constdoublePI=acos(-1);......
  • 通过注释一行代码 开启关闭一个div的css样式 - 开发调试技巧
    通过注释一行代码开启关闭一个div的css样式-开发调试技巧需求：开发的时候，我需要对页面的某个样式反复开关，但是html不能通过注释来开关，所以可以在div的上面加一个js但是vue的template里面不能加script，需要加component重点代码不写v-bindvscode有红色波浪<componentv-bind:......
  • Pinely Round 2 (Div. 1 + Div. 2)
    A.Channel题意：最开始网上有\(a\)个人，共\(q\)次改变，每一次有一个人加入或离开。总共\(n\)个人，求这\(n\)个人是否都上过网，有没上过网的，都有可能。思路：贪心地每次选取尽可能多和少的人即可。提交记录B.SplitSort题意：给定一个排列，每次可以选取一个数\(x\)，将排列划......
  • pbootcms编辑器过滤div代码解决办法
    要在PBootCMS中解决编辑器将<div>标签转换为<p>标签的问题，你可以按照以下步骤操作：修改ueditor.all.js文件：找到core->extend->ueditor->ueditor.all.js文件。定位到大约第10830行，将allowDivTransToP:true改为allowDivTransToP:false。修改ueditor.config.js文件：找到c......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99