首页 > 其他分享 >Educational Codeforces Round 169 (Rated for Div. 2)

Educational Codeforces Round 169 (Rated for Div. 2)

时间:2024-08-28 13:27:53浏览次数:3  
标签:Educational Rated int Codeforces long ans define id pos1

A. Closest Point

两个数时只要不相邻就有解,超过两个数无解

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

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; 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;
}

int a[100];

int main()
{
    int T = read();
    while(T--)
    {
        int n = read();
        for(int i = 1; i <= n; ++i) a[i] = read();
        if(n >= 3) printf("NO\n");
        else if(a[1] + 1 == a[2]) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

B. Game with Doors

先特判两个区间不交的情况,关一扇门即可

两个区间有交时,枚举每一扇门,如果两个人有可能在门的两侧就把这扇门关上

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

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; 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;
}

int a[100];

int main()
{
    int T = read();
    while(T--)
    {
        int ans = 0;
        int l = read(), r = read(), L = read(), R = read();
        if(r < L || R < l)
        {
            printf("1\n");
            continue;
        }
        for(int i = 1; i <= 99; ++i)
        {
            if((l <= i && r >= i && L <= i + 1 && R >= i + 1) || (l <= i + 1 && r >= i + 1 && L <= i && R >= i)) ++ans;
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Splitting Items

转化题意为两个人轮流选最大值,后手 \(\text{BOb}\) 只能选到偶数位次的最大值,它可以调整某些数使它变大,但调整的总数不能超过 \(K\) ,尝试把每个偶数位置的数调整到比它大的那个数

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

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; 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];

int main()
{
    int T = read();
    while(T--)
    {
        int n = read(), K = read();
        for(int i = 1; i <= n; ++i) a[i] = read();
        sort(a + 1, a + n + 1);
        for(int i = n - 1; i >= 1 && K; i -= 2)
        {
            int tmp = a[i + 1] - a[i];
            if(tmp <= K) K -= tmp, a[i] += tmp;
            else a[i] += K, K = 0;
        }
        ll ans = 0, op = 1;
        for(int i = n; i >= 1; --i) ans += 1ll * op * a[i], op = -op;
        printf("%lld\n", ans);
    }
    return 0;
}

D. Colored Portals

首先用并查集判断无解,每一个数连接两个集合,如果询问的两个数不在同一个集合则无解

设询问的两个数为 \(i, j\) 其中 \(i < j\)

若两个数的集合有交,例如\((1, 2), (1, 3)\) ,答案为 \(j - i\)

若两个数的集合不交,需要第三方,例如 \((1, 2), (3, 4)\) 可以找第三方 \((1, 3), (1, 4), (2, 3), (2, 4)\) 只需要找一个第三方即可,且优先选择位于 \([i, j]\) 之间的第三方,若没有,则选择第一个小于 \(i\) 或第一个大于 \(j\) 的第三方

用 \(\text{vector}\) 分别存储每种第三方的数, \(\text{lower_bound}\)查找

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

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; 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;
vector<int> a[205];
string s[N];
int id[205];
int f[5];

int find(int x){ return (x == f[x]) ? f[x] : (f[x] = find(f[x])); }
void merge(int x, int y)
{
    x = find(x), y = find(y);
    if(x == y) return ;
    f[y] = x;
}

int get(int x, int y)
{
    if(x > y) swap(x, y);
    return x * 10 + y;
}

int main()
{
    int T = read();
    id['B'] = 1, id['G'] = 2, id['R'] = 3, id['Y'] = 4;
    while(T--)
    {
        int n = read(), q = read();
        for(int i = 1; i <= 4; ++i) f[i] = i;
        for(int i = 1; i <= 199; ++i) a[i].clear();
        for(int i = 1; i <= n; ++i)
        {
            cin >> s[i];
            int x = id[s[i][0]], y = id[s[i][1]];
            merge(x, y);
            a[x * 10 + y].emplace_back(i);
        }

        while(q--)
        {
            int i = read(), j = read();
            if(i > j) swap(i, j);
            int xi = id[s[i][0]], yi = id[s[i][1]];
            int xj = id[s[j][0]], yj = id[s[j][1]];
            if(xi == xj || xi == yj || yi == xj || yi == yj) printf("%d\n", abs(i - j));
            else
            {
                if(find(xi) != find(xj)) printf("-1\n");
                else 
                {
                    int id = 0, ans = 0x3f3f3f3f, pos1 = 0;
                    
                    id = get(xi, xj);
                    pos1 = lower_bound(a[id].begin(), a[id].end(), i) - a[id].begin();
                    if(pos1 < a[id].size()) ans = min(ans, abs(i - a[id][pos1]) + abs(j - a[id][pos1]));
                    if(pos1 >= 1) ans = min(ans, abs(i - a[id][pos1 - 1]) + abs(j - a[id][pos1 - 1]));
                
                    id = get(xi, yj);
                    pos1 = lower_bound(a[id].begin(), a[id].end(), i) - a[id].begin();
                    if(pos1 < a[id].size()) ans = min(ans, abs(i - a[id][pos1]) + abs(j - a[id][pos1]));
                    if(pos1 >= 1) ans = min(ans, abs(i - a[id][pos1 - 1]) + abs(j - a[id][pos1 - 1]));

                    id = get(yi, xj);
                    pos1 = lower_bound(a[id].begin(), a[id].end(), i) - a[id].begin();
                    if(pos1 < a[id].size()) ans = min(ans, abs(i - a[id][pos1]) + abs(j - a[id][pos1]));
                    if(pos1 >= 1) ans = min(ans, abs(i - a[id][pos1 - 1]) + abs(j - a[id][pos1 - 1]));

                    id = get(yi, yj);
                    pos1 = lower_bound(a[id].begin(), a[id].end(), i) - a[id].begin();
                    if(pos1 < a[id].size()) ans = min(ans, abs(i - a[id][pos1]) + abs(j - a[id][pos1]));
                    if(pos1 >= 1) ans = min(ans, abs(i - a[id][pos1 - 1]) + abs(j - a[id][pos1 - 1]));

                    printf("%d\n", ans);
                }
            }
        }

    }   
    return 0;
}

E. Not a Nim Problem

吃了没文化的亏,没理解题意

博弈论,发现每一堆石子是一个有向图游戏,只需求出每堆石子的 \(\text{SG}\) 函数再求异或和即可

考虑 \(SG(x)\) 怎么求?

\[SG(x) = mex_{gcd(x, y) = 1}\{ SG(x - y) \} \]

由于 \(gcd(x, y) = gcd(x, x - y)\)

\[SG(x) = mex_{gcd(x, y) = 1}\{ SG(y) \} \]

手动模拟发现 \(SG(1) = 1, SG(2) = 0, SG(3) = 2 \cdots\)

所有偶数的 \(SG\) 值都为0,所有奇数的 \(SG\) 值都是它的最小质因子的位次(3是第二个质因子)

恰好线性筛是每个数恰好被最小质因子筛一次

证明:质数 \(p\) 的 \(SG\) 由定义可知是它的位次,合数数学归纳法证

总结

  • 博弈论先猜后证
点击查看代码
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; 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 = 1e7 + 5;
int f[N];
int prime[N], cnt;
bool vis[N];

void init()
{
    prime[++cnt] = 2, vis[2] = vis[4] = 1;
    f[1] = 1;
    for(int i = 3; i <= 10000000; ++i)
    {
        if(!vis[i]) prime[++cnt] = i, f[i] = cnt;
        for(int j = 1; j <= cnt && prime[j] * i <= 10000000; ++j)
        {
            vis[prime[j] * i] = 1;
            f[prime[j] * i] = f[prime[j]];
            if(i % prime[j] == 0) break;
        }
    }
}

int main()
{
    int T = read();
    init();
    while(T--)
    {   
        int n = read(), ans = 0;
        for(int i = 1; i <= n; ++i)
        {
            int x = read();
            ans ^= f[x];
        }
        if(ans == 0) printf("Bob\n");
        else printf("Alice\n");
    }   
    return 0;
}

F. Make a Palindrome

发现对于某一步分裂能解决的问题,在它的回文位置做合并也能解决

因此直接舍弃分裂操作,只使用合并

设 \(dp[l][r]\) 表示区间 \([l, r]\) 合并成回文序列的最小操作数

转移时找到最小的 \(i\) 满足 \(i > l\) 且存在 \(j > i, j < r\) 使 \(a[l] + \cdots + a[i - 1] = a[j + 1] + \cdots + a[r]\)

\[dp[l][r] = \min_{s[r] + s[l - 1] = s[j] + s[i - 1]} dp[i][j] + (i - l - 1) + (r - j - 1) \]

将 \((s[j] + s[i - 1], dp[i][j] + i - j)\) 扔到map里即可

@Luckyblock 对前后缀和的思考感觉更优雅 博客链接

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

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; 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 = 2005;
int a[N], sum[N];
int dp[N][N];
map<int, int> mp;

void solve()
{
    mp.clear();
    int n = read(), ans = 0;
    for(int i = 1; i <= n; ++i) a[i] = read(), sum[i] = sum[i - 1] + a[i];
    for(int i = 0; i < n; ++i) mp[2 * sum[i]] = 1;
    for(int len = 1; len <= n; ++len)
        for(int l = 1, r = l + len - 1; r <= n; ++l, ++r)
        {
            if(a[l] == a[r]) dp[l][r] = dp[l + 1][r - 1];
            else
            {
                if(mp.find(sum[l - 1] + sum[r]) == mp.end()) mp[sum[l - 1] + sum[r]] = 0x3f3f3f3f;
                dp[l][r] = mp[sum[l - 1] + sum[r]] + r - l - 2;
            }
            dp[l][r] = min(dp[l][r], r - l);
            if(mp.find(sum[l - 1] + sum[r]) == mp.end()) mp[sum[l - 1] + sum[r]] = 0x3f3f3f3f;
            mp[sum[l - 1] + sum[r]] = min(mp[sum[l - 1] + sum[r]], dp[l][r] + l - r);
            ans += dp[l][r];
        }
    printf("%d\n", ans);
}

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

G. Substring Compression

刷题真能学到东西!对矩阵加速 \(DP\) 的理解还停留在斐波那契数列

先考虑 \(K\) 个数怎么做

显然的是奇数段一定只选一个数,即 1 ~ 9

设 \(dp[i][c]\) 表示压缩完前 \(i\) 个,上一个奇数段的值为 \(c\) 的最小压缩长度

\[dp[i + 1][c] = dp[i][c] + c \]

\[dp[i + 2][s_{i + 1}] = dp[i][c] + s_{i + 1} \]

到这直接放弃,没法优化

\(i \to i + 2\) 的转移很烦人,如何将所有转移都改为 \(i \to i + 1\) ?

神之一手:令 \(dp[i][0]\) 表示选 \(s_i\) 做新的奇数段,有转移

\[ dp[i + 1][c] = \begin{cases} dp[i][c] + c, & c \neq s_i \\ \min\{ dp[i][c], dp[i][0] \} + c, & c = s_i \\ \end{cases}\]

\[dp[i + 1][0] = \min_{1 \le c \le 9} dp[i][c] \]

发现可以矩阵加速,剩下的就是维护连续 \(K\) 的矩阵相乘,然后用向量左乘矩阵

那必然是线段树维护矩阵啊,每次询问的时候返回矩阵会T,带着向量递归就可以了,单次询问是 \(O(10^2 \log n)\) ,但是建树是 \(O(10^3\ n)\)

线段树大常数哭哭

题解用两个栈维护滑动窗口,只用队列的话删除元素的时候不好操作

用两个栈维护,并且每个元素记录两个值,一是自身矩阵,二是自身矩阵与栈中在它位置下面的所有矩阵的乘积

当第一个栈元素第一次达到 \(K\) 个时需要删除元素

此时暴力将栈中元素取出并放入另一个栈(相当于把整个栈翻转了)并重新计算矩阵乘积

此时第二个栈栈顶元素即 \(1\) ,可以直接删去,而 \(2\) 经过重新计算矩阵乘积恰好保存了 2 ~ K 的矩阵乘积

总操作为:

  1. 删去第二个栈栈顶元素,若第二个栈为空则先让一栈翻转到二栈

  2. 向一栈中加入新元素

  3. 取两栈栈顶元素相乘得转移矩阵,用向量左乘它

单次加入一个元素是 \(O(10^3)\) ,暴力翻转栈均摊每个元素是 \(O(10^3)\)

感觉分块也能做,块长设成 \(K\) ,然后块内维护矩阵前缀积和后缀积,询问的时候只需要两个矩阵相乘,预处理也是 \(O(10^3 n)\)

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

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

int read()
{
    int x = 0, f = 0; 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 = 0x3f3f3;
const int N = 2e5 + 5;
int n, K;
char S[N];

struct Matrix
{
    int c[10][10];
    Matrix()
    {
        for(int i = 0; i < 10; ++i)
            for(int j = 0; j < 10; ++j)
                c[i][j] = inf;
    }
    Matrix friend operator * (Matrix a, Matrix b)
    {
        Matrix c;
        for(int i = 0; i < 10; ++i)
            for(int k = 0; k < 10; ++k)
                for(int j = 0; j < 10; ++j)
                    c.c[i][j] = min(c.c[i][j], a.c[i][k] + b.c[k][j]);
        return c;
    }
}A[10];

void init(int x)
{
    A[x].c[0][x] = x;
    for(int i = 1; i <= 9; ++i)
    {
        A[x].c[i][0] = 0;
        A[x].c[i][i] = i;
    }
}

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

Matrix a[N << 2];

void build(int k, int l, int r)
{
    if(l == r)
    {
        a[k] = A[S[l - 1] - '0'];
        return ;
    }
    int mid = (l + r) >> 1;
    build(ls(k), l, mid), build(rs(k), mid + 1, r);
    a[k] = a[ls(k)] * a[rs(k)];
}

Matrix mul(Matrix a, Matrix b)
{
    Matrix c;
    for(int i = 0; i < 1; ++i)
        for(int k = 0; k < 10; ++k)
            for(int j = 0; j < 10; ++j)
                c.c[i][j] = min(c.c[i][j], a.c[i][k] + b.c[k][j]);
    return c;
}

Matrix query(int k, int l, int r, int L, int R, Matrix c)
{
    if(L <= l && r <= R) return mul(c, a[k]);
    int mid = (l + r) >> 1;
    if(R <= mid) return query(ls(k), l, mid, L, R, c);
    if(L > mid) return query(rs(k), mid + 1, r, L, R, c);
    c = query(ls(k), l, mid, L, R, c);
    return query(rs(k), mid + 1, r, L, R, c);
}

int main()
{
    n = read(), K = read();
    scanf("%s", S + 1);
    for(int i = 1; i <= 9; ++i) init(i);
    build(1, 2, n);
    for(int i = 1; i <= n - K + 1; ++i)
    {
        Matrix I;
        I.c[0][0] = 0;
        Matrix W = query(1, 2, n, i + 1, i + K - 1, I);
        int ans = inf;
        for(int j = 1; j <= 9; ++j) ans = min(ans, W.c[0][j]);
        printf("%d ", ans);
    }
    return 0;
}
题解的双栈法
#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const int D = 10;
const int INF = 1e9;
 
typedef array<array<int, D>, D> mat;
 
mat mul(const mat &a, const mat &b, bool fl){
	mat c;
	forn(i, D) forn(j, D) c[i][j] = INF;
	if (fl){
		forn(i, D) forn(j, D){
			c[j][i] = min(c[j][i], min(a[j][0] + b[0][i], a[j][i] + b[i][i]));
			c[j][0] = min(c[j][0], a[j][i] + b[i][0]);
		}
	}
	else{
		forn(i, D) forn(j, D){
			c[i][j] = min(c[i][j], min(a[i][0] + b[0][j], a[i][i] + b[i][j]));
			c[0][j] = min(c[0][j], a[0][i] + b[i][j]);
		}
	}
	return c;
}
 
struct minqueue{
	vector<pair<mat, mat>> st1, st2;
	
	void push(const mat &a){
		if (!st1.empty())
			st1.push_back({a, mul(st1.back().second, a, true)});
		else
			st1.push_back({a, a});
	}
	
	void pop(){
		if (st2.empty()){
			st2 = st1;
			reverse(st2.begin(), st2.end());
			st1.clear();
			assert(!st2.empty());
			st2[0].second = st2[0].first;
			forn(i, int(st2.size()) - 1)
				st2[i + 1].second = mul(st2[i + 1].first, st2[i].second, false);
		}
		st2.pop_back();
	}
	
	int get(){
		if (st1.empty()) return st2.back().second[0][0];
		if (st2.empty()) return st1.back().second[0][0];
		int ans = INF;
		forn(i, D) ans = min(ans, st2.back().second[0][i] + st1.back().second[i][0]);
		return ans;
	}
};
 
mat tran[D];
 
void init(int d){
	forn(i, D) forn(j, D) tran[d][i][j] = INF;
	for (int i = 1; i <= 9; ++i){
		tran[d][i][i] = i;
		tran[d][i][0] = i;
	}
	tran[d][0][d] = 0;
}
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	for (int i = 1; i <= 9; ++i) init(i);
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	minqueue q;
	forn(i, n){
		q.push(tran[s[i] - '0']);
		if (i - k >= 0) q.pop();
		if (i - k >= -1) cout << q.get() << ' ';
	}
	cout << '\n';
	return 0;
}

标签:Educational,Rated,int,Codeforces,long,ans,define,id,pos1
From: https://www.cnblogs.com/wenqizhi/p/18384465

相关文章

  • Codeforces Round 968 (Div. 2)
    题目链接:CodeforcesRound968(Div.2)-Codeforces总结:C题想到了,但是写成shi了,出得有点慢。A.TurtleandGoodStringtag:签到Solution:直接判断第一个字符是否与最后一个字符相等即可。voidsolve(){cin>>n;strings;cin>>s;if(s[0]==s[n-1]......
  • Codeforces Round 968 (Div. 2)
    题目链接:CodeforcesRound968(Div.2)-Codeforces总结:C题想到了,但是写成shi了,出得有点慢。A.TurtleandGoodStringtag:签到Solution:直接判断第一个字符是否与最后一个字符相等即可。voidsolve(){cin>>n;strings;cin>>s;if(s[0]==s[......
  • Codeforces Round 967 (Div. 2)
    题目链接:CodeforcesRound967(Div.2)-Codeforces总结:B题没测试就交wa一发,C题一直没想到怎么回溯,哎。A.MakeAllEqualtag:签到Solution:找到相同元素的最大值,将其它所有元素删去。voidsolve(){cin>>n;vector<int>a(n);map<int,int>mp;intans......
  • Codeforces Round 962 (Div. 3)
    A.Legs若只判断题,根据模4意义下分类即可。B.Scale模拟题,缩小同值矩阵即可。C.Sort对每个字母求前缀数量和,答案就是两端点的差。constintN=2e5+5;intT,n,q;chara[N],b[N];intc[N][26],d[N][26];signedmain(void){ for(read(T);T;T--){ read(......
  • Codeforces Round 968 (Div. 2)
    A.TurtleandGoodStrings题意:确定是否存在一种方案使得\(s=t_1+t_2+\cdots+t_m\),满足\(m>1\)且任意\(i<j\),\(t_i\)的第一个字母不等于\(t_j\)的最后一个字母。\(s_1\)和\(s_n\)一定不属于一个子串,因此\(s_1\nes_n\)是条件非法的必要条件。那么反......
  • Codeforces Round 968 (Div. 2)
    A.TurtleandGoodStrings思路:题意大致为把一个字符串分成若干段,要求每两段,前一段的首字符不能等于后的一段的尾字符,给你一个字符串,能不能构造出合法方案。观察到,分的段数越小,越有助于我们判断。所以,不妨分成两段,问题转化为判断首尾字符是否相等。代码:#include<bits/stdc++.......
  • Codeforces Round 968 (Div. 2)
    良心出题人给了中文题解!!!A.TurtleandGoodStrings长度为\(n\)的字符串至少分成两段,使\(\foralli<j\),第\(i\)段的首字符不等于第\(j\)段的尾字符第一个字符一定作为首字符,最后一个字符一定作为尾字符,只要判断这两个字符是否相等即可相等的话一定无解,不相等一定有......
  • 2024暑期牛客多校第10场 D Is it rated?
    题目大意有\(n\)场\(\textbf{按顺序}\)的比赛,第\(i\)场比赛有表现分\(p_i\)。参加第\(i\)场比赛后你的分数\(r\)将变为\(r\times(1-k)+k\timesp_i\)。你可以选择最多\(m\)场比赛不参加。给定初始分数\(r_0\)和参数\(k\)。问经过至少\(n-m\)场比赛后,分数最高是......
  • Codeforces Round #900 (Div. 3)
    三年之后第一次打比赛,用小号打了场\(Div.3\),居然没有AK,感觉实力退步到小学了。A.HowMuchDoesDaytonaCost?若只判断题,只要判断\(\{a_n\}\)中是否存在\(k\)即可。B.AleksaandStack构造方法不唯一,我直接输出奇数列,显然正确。C.VasilijeinCacak若只判断题......
  • Codeforces Round 967 (Div. 2) - C
    题意概述这是一个交互题。有一棵有\(n\)个节点的树,节点编号从\(1\)到\(n\),并要求你使用以下类型的查询来猜测它:"?ab"会告诉你哪个节点\(x\)在点\(a\)和\(b\)之间(\(|d(a,x)-d(b,x)|\)的值最小),其中\(d(x,y)\)是节点\(x\)和\(y\)之间的距离。如果存在不......