ARC165 做题记录-526互联

有点结论场的感觉了。

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

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

ARC

165

arc 165

adjacent 165f make arc

题解at_arc 165 arc

题解equals 165a arc

165f arc

comparison substring 165d arc