[ARC114D] Moving Pieces on Line 解题报告

这篇具有很好参考价值的文章主要介绍了[ARC114D] Moving Pieces on Line 解题报告。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

AT题面

简要题意

有一个红色的数轴,相邻两个整点之间连有一条边,所有边初始为红色。数轴上有 \(n\) 个棋子,将一个棋子从 \(a\) 位置移到 \(b\) 位置,可以将 \((a,b)\) 之间红边变为蓝边,蓝边变为红边。给定 \(k-1\) 条线段,问能否进行若干次操作,使得当 \(i\) 是奇数,第 \(i\) 条线段是蓝色,当 \(i\) 是偶数,第 \(i\) 条线段是红色。

分析

将线段和棋子都排好序。
容易发现一个棋子最多朝一个方向走一定路程,不然反复走的那一段肯定多余。令 \(x_i\) 表示点 \(i\) 左右两条线段是否相同,那么一个棋子移动就相当于一个区间异或操作,将其差分,就变成了起始点异或 \(1\),终止点异或 \(1\)。因为线段的端点均是 \(x_i=1\),所以只有被异或奇数次的才有可能是终止点,假设这样的点有 \(m\) 个。
根据上面的分析,可以知道 \(m\) 一定小于等于 \(n\)
对于 \(m\le n\) 的情况,将棋子的位置看作白点,将异或奇数次的点看作黑点。首先黑白点能互相匹配,代价为 \(|a_i-b_j|\);相邻的白白点也可以互相匹配,代价为 \(a_i-a_{i-1}\)。令 \(f_{i,j}\) 表示 \(i\) 个白点和 \(j\) 个黑点匹配的代价,直接dp,答案为 \(f_{n,m}\)文章来源地址https://www.toymoban.com/news/detail-450849.html

Code

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=5e3+10;
int n,m,a[N],b[N<<1],c[N<<1],cnt;
ll f[N][N];
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    read(n),read(m);
    for(int i=1;i<=n;i++){
        read(a[i]);
        b[i]=a[i];
    }
    for(int i=1;i<=m;i++){
        read(b[i+n]);
    }
    m+=n;
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    for(int i=1,j;i<=m;i=j){
        for(j=i;j<=m;j++){
            if(b[j]!=b[i]){
                break;
            }
        }
        if((j-i)%2){
            c[++cnt]=b[i];
        }
    }
    if(n<cnt){
        puts("-1");
        return 0;
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=cnt;j++){
            if(j)f[i][j]=f[i-1][j-1]+abs(a[i]-c[j]);
            if(i>=2){
                f[i][j]=min(f[i][j],f[i-2][j]+a[i]-a[i-1]);
            }
        }
    }
    write_endl(f[n][cnt]);
    return 0;
}

到了这里,关于[ARC114D] Moving Pieces on Line 解题报告的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • kinit报错 /etc/host.conf: line 3: bad command `nospoof on‘

    kinit报错 /etc/host.conf: line 3: bad command `nospoof on’ linux7.5不再支持nospoof命令了, 修改/etc/host.conf注释掉nospoof on即可。

    2024年02月13日
    浏览(41)
  • LeetCode --- 1732. Find the Highest Altitude 解题报告

    There is a biker going on a road trip. The road trip consists of  n + 1  points at different altitudes. The biker starts his trip on point  0  with altitude equal  0 . You are given an integer array  gain  of length  n  where  gain[i]  is the  net gain in altitude  between points  i ​​​​​​ and  i + 1  for all ( 0 = i n) . Return 

    2024年02月02日
    浏览(37)
  • LeetCode --- 1903. Largest Odd Number in String 解题报告

    You are given a string  num , representing a large integer. Return  the  largest-valued odd  integer (as a string) that is a  non-empty substring  of  num , or an empty string  \\\"\\\"  if no odd integer exists . A  substring  is a contiguous sequence of characters within a string. Example 1: Example 2: Example 3:

    2024年02月10日
    浏览(35)
  • 解决Android Studio Unexpected tokens (use ; to separate expressions on the same line)

    @[TOC](Unexpected tokens (use ; to separate expressions on the same line)) 这个是在jitpack里面 找到的依赖 点击后面就可以导入自己需要的依赖了。

    2024年02月04日
    浏览(38)
  • LeetCode --- 1863. Sum of All Subset XOR Totals 解题报告

    The  XOR total  of an array is defined as the bitwise  XOR  of  all its elements , or  0  if the array is  empty . For example, the  XOR total  of the array  [2,5,6]  is  2 XOR 5 XOR 6 = 1 . Given an array  nums , return  the  sum  of all  XOR totals  for every  subset  of  nums .  Note:  Subsets with the  same  elements should be c

    2024年02月15日
    浏览(57)
  • LeetCode --- 1971. Find if Path Exists in Graph 解题报告

    There is a  bi-directional  graph with  n  vertices, where each vertex is labeled from  0  to  n - 1  ( inclusive ). The edges in the graph are represented as a 2D integer array  edges , where each  edges[i] = [ui, vi]  denotes a bi-directional edge between vertex  ui  and vertex  vi . Every vertex pair is connected by  at most one  edge, and

    2024年02月07日
    浏览(44)
  • mysql: [Warning] Using a password on the command line interface can be insecure.

    最近在写shell脚本,需要查询mysql,然后运行脚本提示了这个,虽然想查询的内容确实查询到了,但是这个警告直接让脚本的级别变成了Error! 这个警告的意思是说在命令行直接使用密码是不安全的。 解决办法: 在命令末尾添加 2/dev/null 是将标准错误输出重定向到空设备文件,

    2024年02月08日
    浏览(44)
  • LeetCode --- 1869. Longer Contiguous Segments of Ones than Zeros 解题报告

    Given a binary string  s , return  true  if the  longest  contiguous segment of  1 \\\' s is  strictly longer  than the  longest  contiguous segment of  0 \\\' s in  s , or return  false  otherwise . For example, in  s = \\\" 11 01 000 10\\\"  the longest continuous segment of  1 s has length  2 , and the longest continuous segment of  0 s has length 

    2024年02月15日
    浏览(33)
  • LeetCode --- 1880. Check if Word Equals Summation of Two Words 解题报告

    The  letter value  of a letter is its position in the alphabet  starting from 0  (i.e.  \\\'a\\\' - 0 ,  \\\'b\\\' - 1 ,  \\\'c\\\' - 2 , etc.). The  numerical value  of some string of lowercase English letters  s  is the  concatenation  of the  letter values  of each letter in  s , which is then  converted  into an integer. For example, if  s = \\\"acb\\\" , we

    2024年02月13日
    浏览(44)
  • 上海市计算机学会竞赛平台(iai.sh.cn)2023一月月赛(丙组)解题报告

    内存限制: 256 Mb时间限制: 1000 ms。 小爱正在完成一个物理实验,为期n天,其中第i天,小爱会记录 a i a_i a i ​ 条实验数据在实验日志中。已知小爱的实验日志每一页最多纪录m条数据,每天做完实验后他都会将日志合上,第二天,他便从第一页开始依次翻页,直到找到第一个

    2024年02月16日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包