您现在的位置是:首页 > 正文

Codeforces Round 875 (Div. 2)(A~D)

2024-01-30 21:56:08阅读 0

文章目录


B题wa了一发,有点离谱取最大时取错了样例能过。C题读了半天,读懂立马有了思路,写了半天wa了标记没处理对。搞了半天。

A

题意:给你一个长度为n的排列a,现要求你构造一个长度为n的排列b使得 a [ i ] + b [ i ] ≤ a [ i + 1 ] + b [ i + 1 ] . . . ≤ a [ n ] + b [ n ] a[i]+b[i] \le a[i+1]+b[i+1] ... \le a[n]+b[n] a[i]+b[i]a[i+1]+b[i+1]...a[n]+b[n]

思路:
因为a和b都是一个长度为n的排列,那么我们一定可以构造出 a [ i ] + b [ i ] = a [ i + 1 ] + b [ i + 1 ] . . . = a [ n ] + b [ n ] a[i] + b[i] = a[i+1]+b[i+1] ... = a[n]+b[n] a[i]+b[i]=a[i+1]+b[i+1]...=a[n]+b[n]并且这个和一定为n+1
感兴趣可以自己下去证明一下,感觉这类题我们可以找那种特殊边界去构造就行。

代码:

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define int long long
#define endl "\n"
#define xx first
#define yy second

using namespace std;

typedef pair<int, int> PII;

const int N = 4e5 + 10, INF = 1e18;

int n, m, k, _, x;
int arr[N];
char s[N];

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> arr[i];
    int sum = n+1;

    for(int i = 1; i <= n; i ++) cout << sum-arr[i] << " ";
    cout << endl;
}

signed main()
{
    IOS;
    cin >> _;
    while(_--)
        solve();
    return 0;
}

B

题意:给你两个长度为n的数组a,b。然后给一个空数组c,现在有一种操作是每次选择两个数组a,b其中的一个,把第一个元素放到c数组末尾并把这个数删除掉。不限制操作次数,问最后操作完过后的数组c中最长子串是多长(子串的数都要相同)。

思路:
其实我们只需要统计出a,b数组中每段连续相同数字的最大长度,最后把a,b中对于每个数字统计出的答案求和取最大值即可。

代码:

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define int long long
#define endl "\n"
#define xx first
#define yy second

using namespace std;

typedef pair<int, int> PII;

const int N = 5e5 + 10, INF = 1e18;

int n, m, k, _, x;
int arr[N], brr[N];
char s[N];

void solve()
{
    cin >> n;

    for(int i = 1; i <= n; i ++) cin >> arr[i];

    for(int i = 1; i <= n; i ++) cin >> brr[i];

    map<int, int> mpa, mpb;

    int len = 1;
    for(int i = 2; i <= n; i ++)
    {
        if(arr[i] == arr[i-1]) len++;
        else
        {
            mpa[arr[i-1]] = max(len, mpa[arr[i-1]]);//最开始取最大时忘了i-1  T_T
            len = 1;
        }
    }
    mpa[arr[n]] = max(len, mpa[arr[n]]);

    len = 1;
    for(int i = 2; i <= n; i ++)
    {
        if(brr[i] == brr[i-1]) len++;
        else
        {
            mpb[brr[i-1]] = max(len, mpb[brr[i-1]]);
            len = 1;
        }
    }
    mpb[brr[n]] = max(mpb[brr[n]], len);

    int ans = 0;
    for(auto [k, v] : mpa) ans = max(ans, v+mpb[k]);


    for(auto [k, v] : mpb) ans = max(ans, v+mpa[k]);

    cout << ans << endl;
}

signed main()
{
    IOS;
    cin >> _;
    while(_--)
        solve();
    return 0;
}

C

题意:有n个点,给你n-1条边。你有三个操作,直到无法操作为止。
step0:你要找到1最开始出现的边的地方,并画出这个点(点1)。
step1:如果对于这条边来说,如果已经有画出的我点,那么把这条边给画出来。否则就跳过这条边。
step2:如果这条边已经画完了,那么转回1号操作。直到所有点被画出结束操作。
问你最终要浏览多少遍这些边把这颗树画完。(从上到下浏览一次算一遍)

思路:

首先我们应该把这颗树建好,对于每个点和每条边出现的时间打上对应的次数。然后我们扫面这棵树,如果对于当前边出现的时间,是小于父亲节点出现的时间那么对于当前点我们就加1,最后我们对每个点取一个最大值就行了。
最开始以为是每一层有一条边出现的时间小于父亲节点的时间,答案+1,最后统计有多少层就行,最后看到一个样例才发现自己错了,贡献了一遍罚时。 T_T

代码:

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define int long long
#define endl "\n"
#define xx first
#define yy second

using namespace std;

typedef pair<int, int> PII;

const int N = 5e5 + 10, INF = 1e18;

int n, m, k, _, x;
int ux[N], vx[N];
vector<PII> e[N];
map<PII, int> mp;
map<int, bool> f;

int ans = 0;

void dfs(int u, int fa, int cnt)
{
    int tmp = mp[{u, fa}]; //这条边的时间
    ans = max(cnt, ans);

    for(auto &[x, y] : e[u])
    {
    	//y是这个点出现的时间。
        if(x == fa) continue;
        if(y < tmp) dfs(x, u, cnt+1);
        else dfs(x, u, cnt);
    }
}

void solve()
{
    cin >> n;
    ans = 0;
    for(int i = 0; i < n+10; i ++)
    {
        e[i].clear();
    }
    for(int i = 1; i < n; i ++)
    {
        int u, v;
        cin >> ux[i] >> vx[i];
        e[ux[i]].push_back({vx[i], i});
        e[vx[i]].push_back({ux[i], i});
        mp[{ux[i], vx[i]}] = i;
        mp[{vx[i], ux[i]}] = i;
    }

    dfs(1, -1, 1);
    cout << ans << endl;

    for(int i = 1; i < n; i ++)
    {
        mp[{ux[i], vx[i]}] = 0;
        mp[{vx[i], ux[i]}] = 0;
    }
}

signed main()
{
    IOS;
    cin >> _;
    while(_--)
        solve();
    return 0;
}

D

题意:给你两个长度为n的数组a,b。现问你 1 ≤ i < j ≤ n    ,   a i ∗ a j = b i + b j 1 \le i < j \le n \ \ , \ a_i*a_j = b_i + b_j 1i<jn  , aiaj=bi+bj满足这样条件的(i, j)有多少。

思路:这道题其实最开始就想出是 n 2 n^2 n2,那肯定是不现实的,那么我们最主要的是降低时间复杂度。赛时没注意看a,b的大小。(肯定看了也不一定写出来)。因为 b [ i ] ≤ n b[i] \le n b[i]n的,所以 b [ i ] + b [ j ] ≤ 2 n b[i] + b[j] \le2n b[i]+b[j]2n,那么对于同一个a[i],我们其实不用遍历a[j], a [ j ] ∈ [ b [ i ] a [ i ] , n + b [ i ] a [ i ] ] a[j] \in [\frac{b[i]}{a[i]}, \frac{n+b[i]}{a[i]}] a[j][a[i]b[i],a[i]n+b[i]],然后当a[i], a[j], b[i]都确定过后我们只需要求出(a[j], b[j])的数量就行了。因为我们上述提到了范围这个问题,那么如果我们排完序过后,a[i]从小到大,那么 a [ j ] ∈ [ 1 , 2 ∗ n ] a[j] \in [1, \sqrt{2*n}] a[j][1,2n ]那么我们这样处理就避免因为数据而出现时间复杂度不一样的问题。而我们最终的时间复杂度也就成了 2 ∗ n ∗ n \sqrt{2*n}*n 2n n了。
D题参考链接: link

代码:

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false);cin.tie(nullptr)
#define int long long 
#define endl "\n"
#define xx first
#define yy second

using namespace std;

typedef pair<int, int> PII;

const int N = 2e5 + 10;

int n, m, k, _;
int arr[N];
PII crr[N];

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> arr[i];

    for(int i = 1; i <= n; i ++)
    {
        int b;
        cin >> b;
        crr[i] = {arr[i], b};
    }
    sort(crr+1, crr+1+n);
    int ans = 0;
    for(int sum = 1; sum*sum <= 2*n; sum++)
    {
        vector<int> cnt(n+1, 0);
        for(int i = 1; i <= n; i ++)
        {
            int a = crr[i].xx , b = crr[i].yy;
            int t = a*sum-b;
            if(t >= 1 && t <= n) ans += cnt[t];
            if(sum == a) cnt[b]++;
        } 
    }
    cout << ans << endl;
}

signed main()
{
    IOS;
    cin >> _;
    while(_--) solve();
    return 0;
} 

网站文章

  • MySQL主从复制 最新发布

    MySQL主从复制 最新发布

    主从复制(也称AB复制)允许将来自一个MySQL数据库服务器(主服务器)的数据复制到一个或多个MySQL数据库服务器(从服务器)。根据配置,自己可以复制数据库中的所有数据库,所选数据库甚至选定的表。

    2024-01-30 21:55:37
  • Unit Test

    Unit Test

    关于单元测试的一篇博文

    2024-01-30 21:55:29
  • Controller响应界面跳转的几种方式 热门推荐

    前面已经了解了Controller的几种配置方式 今天主要写一下响应界面跳转的几种方式 1.在注解的方式中 1.1通过HttpServletResponse的API直接输出(不需要配置渲染器) controller类的主要代码 @Controller public class RequestController{ @RequestMapping(&quot;/resp&quot;) p

    2024-01-30 21:55:20
  • web:[SUCTF 2019]EasySQL

    web:[SUCTF 2019]EasySQL

    将”||”视为字符串的连接操作符而非或运算符,这和Oracle数据库是一样的,也和字符串的拼接函数Concat相类似.SELECT * 和 SELECT 所有列,两者差别几乎可忽略。所以查询所有字段(...

    2024-01-30 21:54:52
  • kubernetes二进宫系列——k8s整体架构与核心组件详解-2

    kubernetes二进宫系列——k8s整体架构与核心组件详解-2

    目录六、kubernetes核心组件之apiserver详解七、kubernetes核心组件之scheduler详解八、kubernetes核心组件之controller manager详解九、kub...

    2024-01-30 21:54:45
  • 警告:Use // eslint-disable-next-line to ignore the next line.Use /* eslint-disable */ to ignore all w

    警告:Use // eslint-disable-next-line to ignore the next line.Use /* eslint-disable */ to ignore all w

    是没有发现使用eslint的配置,所以设置:lintOnSave:false。

    2024-01-30 21:54:33
  • Ubuntu安装Netron并创建快捷键启动图标 最新发布

    Ubuntu安装Netron并创建快捷键启动图标

    2024-01-30 21:54:02
  • 吉大计算机如何本科进实验室,南科大:川大吉大请让路,我们本科生就可以进实验室!新学院更牛...

    吉大计算机如何本科进实验室,南科大:川大吉大请让路,我们本科生就可以进实验室!新学院更牛...

    近几年,南方科技大学的名气越来越大,不管是通过各个排行榜还是从各个省份录取分数来看,都赶上不少985高校了。新任校长为原清华大学副校长据南方科技大学消息,中国科学院院士、原清华大学副校长薛其坤已经出任...

    2024-01-30 21:53:55
  • C++纯虚函数实现接口

    C++纯虚函数纯虚函数语法 virtual type functionname()=0;virtual声明的方法后加上=0是纯虚函数 Java Interface接口Java 中使用Interface开放接口,让另一个类implements interface来达到逻辑和接口分离的作用 Java Interface接口C++实现接口利用两个特性 1. 纯虚函数必须被派生类实现

    2024-01-30 21:53:49
  • 深度神经网络中的多任务学习研究综述

    深度神经网络中的多任务学习研究综述

    在机器学习或者深度学习中,都有一个任务目标,例如猫狗分类准确率、回归预测损失最小化等,为了达到的目标,通常都会训练一个单一的(大)模型或者一系列模型(集成学习),然后根据的目标不断的对模型进行调优,直...

    2024-01-30 21:53:20