首页 > 其他分享 >cf_补题计划_Edu_163_DE

cf_补题计划_Edu_163_DE

时间:2024-08-30 18:25:53浏览次数:11  
标签:cout -- ll DE cf long 补题 回文 define

D. Tandem Repeats?



从复杂度来说,可以进行\(n^2\)的操作,呃因为是子串数量级也是\(n^2\),考虑是否子串之间可以相互转移,这个很类似求最长回文串(对于最长回文串我们枚举中点,向外延申即可,因为对于同一个中心可以转移),而对于串联重复串,前一部分等于后一部分,我们可以考虑固定长度,那么长度一样的字串就可以转移。

跟回文串的处理差不多

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define debug(x) cout << #x << " = " << x << endl
#define sz(a) ((int)a.size())
const int mod = 998244353, N = 505, G = 3;
void solve()
{
    ll ans = 0, n;
    string a;
    cin >> a;
    n = a.length();
    a = ' ' + a;
    for (ll k = n; k >=1; k--)
    {
        ll sum = 0;
        for (int i = 1; i + k <= n; i++)
        {
            if (a[i] == a[i + k] || a[i] == '?' || a[i + k] == '?')//如果相等就+1
                sum++;
            else
                sum = 0;
            if (sum >= k){
                cout << k * 2 << endl;
                return;
            }
        }
    }
    cout << 0 << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

E. Clique Partition


呃,大概意思是将n个数,每个数给个数,然后在把他们分成m块,每块里面满足\(|i-j|+|a_i-a_j|<=k\),然后让m尽可能的小。

然后我们发现i,j尽量的越接近会让|i-j|+|a_i-a_j|更小,更容易满足小于等于k的要求,所以每块的选取应该是连续的,然后大力guess

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define debug(x) cout << #x << " = " << x << endl
#define sz(a) ((int)a.size())
const int mod = 998244353, N = 2e5 + 10, G = 3;
ll d[N], c[N];
void solve()
{
    ll n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        d[i] = 0;
    for (int i = 1; i <= n; i++)
    {
        c[i] = (i - 1) / k + 1;
        d[c[i]]++;
    }
    ll sum = 0;
    for (int i = 1; i <= n; i++)
    {
        if (c[i] != c[i - 1])
            sum = 0;
        sum++;
        if (sum <= d[c[i]] / 2)
            cout << (c[i] - 1) * 2 * k + 1 + d[c[i]] / 2 - i << ' ';
        else
            cout << (c[i] - 1) * 2 * k + 1 + d[c[i]] / 2 + d[c[i]] - i << ' ';
    }
    cout << endl;
    cout << (n - 1) / k + 1 << endl;
    for (int i = 1; i <= n; i++)
        cout << c[i] << ' ';
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

标签:cout,--,ll,DE,cf,long,补题,回文,define
From: https://www.cnblogs.com/-3449/p/18389164

相关文章

  • 2024-08-30 error [email protected]: The engine "node" is incompatible with this m
    删掉依赖,使用yarn重新拉取,保错如下:[email protected]:Theengine"node"isincompatiblewiththismodule.Expectedversion">=18".Got"16.19.1" 错误[email protected]:引擎“节点”与此模块不兼容。预期版本“>=18”。得到“16.19.1”意思就是yarn拉取依赖过程中......
  • 使用ClassLoader.getSystemResource更新上线后空指针异常
     目录 问题描述:原问题代码:问题原因以及解决思路:解决方法:问题描述:项目中使用到一个功能,于是在资源路径下加了点依赖包:更新上线后,发现使用ClassLoader.getSystemResource("dependencies")找不到依赖包原问题代码:URLresourceURL=ClassLoader.getSystemResource(......
  • g++链接报错:undefined reference to typeinfo of xxx
    g++链接报错:undefinedreferencetotypeinfoofxxx问题背景在项目中遇到了这样一个问题:C++文件编译都OK,但链接的时候报错:undefinedreferencetotypeinfoforxxx。std::typeinfo是C++中的RTTI(RunTimeTypeIdentification)机制中记录类型信息用的,dynamic_cast和typeid......
  • nodejs实现将json转化为excel文件
    本文使用node.js实现将json数据转换导出为excel文件。一、安装json2xls库npmijson2xls二、封装转换方法新增jsonToExcel.js文件,该文件用于将json数据(对象数组)转换为excel文件,文件内容如下:constfs=require('fs')//引入文件系统模块constjson2xls=require('json2......
  • 【AI绘画】Midjourney前置指令/describe、/shorten详解
    文章目录......
  • CF603E 题解
    题意给定一个\(n\)个结点的无向图,初始没有边。接下来有\(m\)个询问,每次向图中加入一条连接\((u,v)\)权值为\(w\)的边。每次加边后,查询是否存在一个边集\(E\),满足当图中只有\(E\)中的边时,所有点的度数均为奇数。同时你还要最小化\(\max\limits_{(u,v,w)\inE}......
  • 使用devpi-server搭建pypi本地缓存服务器
    使用缓存机制可以显著减少对外部源的请求量,从而提高下载速度,并降低被源站封禁的风险。下面详细解释如何在本地服务器上设置和使用pip缓存机制。缓存机制的基本原理缓存机制的原理是在本地服务器上保存已经下载过的Python包,当其他服务器请求同样的包时,本地服务器可以直接提供,......
  • ModuleNotFoundError: No module named ‘utils.query‘ flask项目遇到这种报错怎么解
    ModuleNotFoundError:Nomodulenamed'utils.query'这个错误表明你的Python代码正在尝试导入一个名为utils.query的模块,但未能成功找到它。以下是解决该问题的几个步骤:1.检查模块路径如果utils.query是你自己的模块或在项目中的某个目录下,确保文件路径正确。util......
  • 用PowerDesigner创建Oracle模型转为mysql模型
    一.首先打开PowerDesigner1.File(位置:左上角)–>NewModel–>PhysicalDateModel(物理数据模型)(1)DBMS选择MySQL5.0(版本可能不对,但毕竟是mysql语句的)(2)之后点确定就行(3).可能会出现一个问题就是DBMS的下拉框什么也没有退出也不好用(其实挺简单的)1.点击DBMS最右边......
  • maven 插件之 maven-shade-plugin,解决同包同名 class 共存问题的神器50
    开心一刻有一天螃蟹出门,不小心撞倒了泥鳅泥鳅很生气地说:你是不是瞎啊!螃蟹说:不是啊,我是螃蟹概述maven-shade-plugin官网已经介绍的很详细了,我给大家简单翻译一下Thispluginprovidesthecapabilitytopackagetheartifactinanuber-jar,includingitsdependenciesa......