首页 > 其他分享 >ARC165 做题记录

ARC165 做题记录

时间：2023-09-18 17:27:38浏览次数：42  
标签：ch 记录 int void ARC165 long write define

有点结论场的感觉了。

A

题面

简单题。证明一个结论，只要 \(n\not=p^q(p \text{是} n \text{的一个质因子})\)，都是有解的，反之无解。

先证明 \(n=p^q\) 无解，假定 \(n\) 分解为 \(p^a\times p^b(a\le b,a+b=q)\)，此时两数的 \(\mathop{\mathrm{lcm}}\) 为 \(p^b\)。若 \(b=q\)，则 \(p^b+1>p^b\)，不满足条件 \(1\)；若 \(b\not=q\)，\(\mathop{\mathrm{lcm}}\not=n\)，不满足条件 \(2\)，无解。

若 \(n\not=p^q\)，则 \(n=k\times p^q(k>1)\)，将 \(n\) 拆成 \(k\) 和 \(p^q\)。因为 \(k>2\)，所以 \(k+p^q\) 小于 \(n\)，这时候只要补 \(1\) 就行了。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
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;
int x;
int get_min(int x){
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            return i;
        }
    }
    return 0;
}
void solve(){
    read(x);
    int y=get_min(x);
    while(y&&x%y==0){
        x/=y;
    }
    if(y!=0&&x!=1){
        puts("Yes");
    }
    else{
        puts("No");
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

B

题面

如果存在一个长度为 \(k\) 的上升子串，显然不用修改。

剩下的因为至少改变一个位置，答案的字典序肯定变小，所以尽量把修改的第一个位置往后移。可以发现这个位置再往后也必须在后 \(k\) 个数之间，于是就有了一个想法，将后 \(k\) 个数直接排序，但这个是错误的做法，因为后面可能改变的位置不只有一个，反而会使得第一个改变的位置更靠前。因此我们又会去想怎么使得修改的位置在后 \(k\) 个数之中更靠后，这时改的数最少是最有优势的。假定 \([n-k+1,i]\) 要参与排序，此时加入一个 \(a_{i+1}\)，若 \(a_{i+1}\) 大于 \([n-k+1,i]\) 中的最大值，则无事发生，反之会使答案更小。

综合上面的分析，可以知道的是我们要找的区间右端点 \(i\) 是满足 \(i\in [n-k+1,n)\)，\([i-k+1,n-k]\) 是一个上升区间，\([n-k+1,i]\) 中的最小值大于 \(a_{n-k}\) 的最小的 \(i\)，如果没有这样的 \(i\)，直接排序 \([n-k+1,n]\) 即可。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
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=5e5+10;
int n,k,a[N],b[N],mn[N],mx[N];
void solve(){
    read(n),read(k);
    for(int i=1;i<=n;i++){
        read(a[i]);
        if(a[i]>a[i-1]){
            b[i]=1;
        }
        b[i]+=b[i-1];
    }
    bool flag=0;
    b[0]=1;
    for(int i=k;i<=n;i++){
        if(b[i]-b[i-k+1]==k-1){
            flag=1;
        }
    }
    if(flag){
        for(int i=1;i<=n;i++){
            write_space(a[i]);
        }
        return;
    }
    mn[n-k+1]=a[n-k+1];
    for(int i=n-k+2;i<=n;i++){
        mn[i]=min(a[i],mn[i-1]);
    }
    int pos=n-k+1;
    for(int i=1;i<=n;i++){
        int r=i+k-1;
        if(r>=n){
            break;
        }
        if(r<n-k+1){
            continue;
        }
        // cerr<<b[n-k]<<' '<<b[i]<<' '<<n-k-i<<' '<<i<<' '<<n-k<<' '<<endl;
        if(b[n-k]-b[i]==n-k-i&&a[n-k]<mn[r] ){
            pos=i;
            break;
        }
    }
    sort(a+pos,a+pos+k);
    for(int i=1;i<=n;i++){
        write_space(a[i]);
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

C

题面

如果两个同色点相连，则距离为边的大小；如果两个同色点不相连，则只有中间有且只有一个异色点时可能产生贡献。

后者的答案可以对于每个度数至少为 \(2\) 的点，计算与之相连的边中边权最小的两条边的边权和的最小值。

为了使前者的答案最大，可以按照边权从小到大加边，每条边是限制两个点的颜色不同，如果加了一条边后，一个点有两个颜色，则这条边两端的点颜色一定相同，前者的答案就为这条边的边权。

最后答案为两个答案中的最小值。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e18;
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=4e5+10;
int ans=inf,n,m,fa[N];
struct edge{
    int u,v,w;
}e[N];
vector<pii>G[N];
int getfa(int x){
    if(fa[x]!=x){
        fa[x]=getfa(fa[x]);
    }
    return fa[x];
}
void merge(int u,int v){
    u=getfa(u),v=getfa(v);
    if(u!=v){
        fa[v]=u;
    }
}
bool cmp(edge x,edge y){
    return x.w<y.w;
}
void solve(){
    read(n),read(m);
    for(int i=1;i<=m;i++){
        read(e[i].u),read(e[i].v),read(e[i].w);
        G[e[i].u].pb(mp(e[i].w,e[i].v));
        G[e[i].v].pb(mp(e[i].w,e[i].u));
    }
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;i++){
        sort(G[i].begin(),G[i].end());
        if(G[i].size()>=2){
            ans=min(ans,G[i][0].first+G[i][1].first);
        }
    }
    for(int i=1;i<=n*2;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        if(e[i].w>ans){
            break;
        }
        merge(e[i].u,e[i].v+n);
        merge(e[i].u+n,e[i].v);
        if(getfa(e[i].u)==getfa(e[i].u+n)||getfa(e[i].v)==getfa(e[i].v+n)){
            ans=e[i].w;
            break;
        }
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

D

题面

如果要满足一个条件，那么一定要满足 \(val_{a_i}\le val_{c_i}\)。考虑将每个位置看作一个点，连一条从 \(a_i\) 到 \(c_i\) 的边表示 \(val_{a_i}\le val_{c_i}\)。如果此时得到的图是一张 DAG，那么显然有解，否则同一个强连通分量中的点的权值必须相同。对于一个限制，若 \(val_{a_i}=val_{c_i}\)，限制转化为 \((a_i+1,b_i,c_i+1,d_i)\)，如果存在第二个区间是空区间且第一个区间不是空区间，则无解。因为如果不能判断是否有解，则至少缩掉一个点，总复杂度为 \(O(n^2)\)。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
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=2e3+10;
int n,m,a[N],b[N],c[N],d[N];
int fa[N];
int low[N],dfn[N],in_stack[N],idx,top,stk[N],col_cnt;
vector<int>col[N],e[N];
int getfa(int x){
    if(fa[x]!=x){
        fa[x]=getfa(fa[x]);
    }
    return fa[x];
}
bool check(){
    for(int i=1;i<=n;i++){
        fa[i]=getfa(i);
        if(fa[i]!=fa[1]){
            return 0;
        }
    }
    return 1;
}
void clear(){
    for(int i=1;i<=n;i++){
        dfn[i]=low[i]=in_stack[i]=0;
        vector<int>().swap(col[i]);
        vector<int>().swap(e[i]);
    }
    idx=top=col_cnt=0;
}
void tarjan(int u){
    dfn[u]=low[u]=++idx;
    stk[++top]=u;
    in_stack[u]=1;
    for(auto v:e[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in_stack[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        col_cnt++;
        while(1){
            int v=stk[top--];
            col[col_cnt].pb(v);
            in_stack[v]=0;
            if(v==u){
                break;
            }
        }
    }
}
bool chk(){
    for(int i=1;i<=col_cnt;i++){
        if(col[i].size()>=2){
            return 0;
        }
    }
    return 1;
}
void solve(){
    read(n),read(m);
    for(int i=1;i<=m;i++){
        read(a[i]),read(b[i]),read(c[i]),read(d[i]);
    }
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int t=1;t<=n&&!check();t++){
        // cerr<<t<<endl;
        clear();
        for(int i=1;i<=m;i++){
            if(a[i]<=b[i]&&c[i]<=d[i]){
                e[getfa(a[i])].pb(getfa(c[i]));
            }
        }
        for(int i=1;i<=n;i++){
            if(getfa(i)==i&&!dfn[i]){
                tarjan(i);
            }
        }
        if(chk()){
            puts("Yes");
            return;
        }
        for(int i=1;i<=col_cnt;i++){
            for(auto x:col[i]){
                int u=getfa(col[i][0]),v=getfa(x);
                // cerr<<col[i][0]<<' '<<x<<' '<<u<<' '<<v<<endl;
                if(u!=v){
                    fa[v]=u;
                }
            }
        }
        for(int i=1;i<=m;i++){
            while(a[i]<=b[i]&&c[i]<=d[i]&&getfa(a[i])==getfa(c[i])){
                a[i]++;
                c[i]++;
            }
            if((a[i]>b[i]||c[i]>d[i])&&b[i]-a[i]>=d[i]-c[i]){
                puts("No");
                return;
            }
        }
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

E、F

等什么时候再补题再说吧。

标签：ch,记录,int,void,ARC165,long,write,define
From： https://www.cnblogs.com/luoshen0/p/17710949.html

相关文章

  • C语言学习记录---函数3
    函数的声明与定义头文件（.h）#ifndef_ADD_H_//防止头文件被多次引用，占用空间，引起浪费#define_ADD_H_intAdd(intx,inty);//声明#endif函数定义（源文件.c）intAdd(intx,inty){returnx+y;}执行任务（源文件1.c）#include"add.h"//引用头文件intmain(){inta......
  • 错误记录——mysql5.7连接失败，服务无法启动
    起因：上周安装完mysql后，成功新建了数据库，一切都是正常的，于是就先搁置一旁。今天周一过来，却突然发现无法连接mysql了。过程：第一反应是服务没有启动，毕竟重启了电脑，说不定是服务没有自动启动，于是打开了服务管理器，却发现没有mysql对应的服务。既然没有，那我就自己手动创建一......
  • struts2.1 + Spring 3.X + hibernate3.X架构搭建问题记录
    目前正在试图搭建一个SSH的架构，之前在myeclipse8.6+ssh(struts2.1，spring2.5,hibernate3） +mysql+tomcat6.0做过例子，当时有老师带着，遇到问题也都解决了。而且，自己练习单表的增删改查时也能独立完成了。但是现在换成了myeclipse2014+orcle后，就是通不过去，郁闷中：现在想一遍解......
  • 程序创建更改主记录并添加WBS元素BOM
    调用CCAP_ECN_CREATE实现该功能。REPORTZTEST."ifsy-datum='20160110'."updatetadirsetsrcsystem='DEV'wheresrcsystem='DV1'."commitwork."endif.DATA:LS_CHANGE_HEADERTYPEAENR_API01.DAT......
  • 数据结构学习记录（三）
    图一、知识要点1、图的基本概念图的定义和术语图的定义图（Graph）是由两个集合构成，一个是非空但有限的顶点集合V，另一个是表述顶点之间边的集合E（可能是$\emptyset$）。图可表示为G=(V,E).每条边是一顶点对(v,w)且v，w$\in$V。通常用|V|表示顶点的数量，|E|表示边的数量。......
  • 处理数据库中重复记录的方法
    数据库中的重复记录 ，一般都有可能包含垃圾数据，我们必然要处理它。其实处理它无外乎：查询，标记，删除。处理的方法也很多的，用sql语句都可以处理。有时也可以借助临时表。但是无论知道几种方法都不重要，只要会做就行了。即使茴香豆的茴字有一百种写法。我们还只是这......
  • 算法问题记录
    1. 故障量值跳变问题   原因：发生丢帧，数据取走不及时导致缓冲区中数据越积累越多。     解决方法：赶快把数据取走......
  • 怎样在触发器中删除刚刚录入但是不合法的记录？
    建立一个临时表：CREATEGLOBALTEMPORARYTABLEnorthsnow_tmp(northsnow_idvarchar2(20))ONCOMMITDELETEROWS;在业务表上创建一个行级触发器：createorreplacetriggertrg_northsnowafterinsertontb_northsnowforeachrow......
  • C语言学习记录 ----函数2
    #include<stdio.h>#include<string.h>#include<windows.h>#include<stdlib.h>#include<time.h>#include<math.h>判断素数intis_prime(intn){intj=0;for(j=2;j<=sqrt(n);j++){if(0==n%j)......
  • OpenAI原生GPT问答记录直接导入博客方法
    OpenAI原生GPT问答记录直接导入博客方法一般常见的方法是截图放在博客，但是这种方法有点过于粗糙，浪费阅读者流量资源不说，还显得十分不专业。但是对于原生GPT来说，在网页内全选复制并不能达成我们想要的效果，甚至有时候很难区分哪些是用户哪些是AI的话。于是本篇文章应运而生，Openai......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99