20231009比赛总结

news/2024/7/7 18:59:44 标签: 算法

反思

A

构造题怎么也不会！怒！

B

我是 s b sb sb，点和边的数量不一样，我存边的数组一般开了 M A X M MAXM MAXM，一半开了 M A X N MAXN MAXN，爆成了 40 p t s 40pts 40pts

C

感觉自己很弱智，其实这题并不太难的呀

题解

A

毒瘤构造题！！！
首先 n , m n,m n,m 中有奇数的情况是好做的，只需要考虑 n , m n,m n,m 全奇的情况
考虑一种答案为 n + m − 4 n+m-4 n+m−4 的构造方案：
?((((((((?
()()()()()
(()()()())
()()()()()
(()()()())
?))))))))?
再考虑一种 n 2 + m − 1 \frac{n}{2}+m-1 2n​+m−1 的构造方案：
(())
()()
(())
()()
然后考虑当 n , m n,m n,m 其中一维较小的时候用方案2，当 n , m > 4 n,m>4 n,m>4 时用构造方案1
上界也不知道怎么证（但 n + m − 4 n+m-4 n+m−4 感觉已经很极限了）

#include <bits/stdc++.h>
using namespace std;
const int N=5100;
int n,m;
char ch[N][N];
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
int main(){
    freopen("butterfly.in","r",stdin);
    freopen("butterfly.out","w",stdout);
    n=read(),m=read();
    if((n&1)&&(m&1)){
        for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) putchar('(');puts("");}
        exit(0);
    }
    if(n&1){
        for(int i=1;i<=n;i++){ for(int j=1;j<=m;j+=2) printf("()");puts("");}
        exit(0);
    }
    if(m&1){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                if(i&1) putchar('(');
                else putchar(')');
            puts("");
        }
        exit(0);
    }
    if(n==2&&m==2){ puts("()");puts("()");exit(0);}
    if(n==4&&m==2){ puts("()");puts("()");puts("()");puts("()");exit(0);}
    if(n==2&&m==4){ puts("((((");puts("))))");exit(0);}
    if(n==4&&m==4){ puts("(())");puts("()()");puts("(())");puts("()()");exit(0);}
    if(n==2){
        for(int i=1;i<=m;i++) putchar('(');puts("");
        for(int i=1;i<=m;i++) putchar(')');puts("");
        exit(0);
    }
    if(m==2){
        for(int i=1;i<=n;i++){ printf("()");puts("");}
        exit(0);
    }
    if(m==4){
        for(int i=1;i<=n;i+=2) puts("(())"),puts("()()");
        exit(0);
    }
    if(n==4){
        for(int i=1;i<=m;i+=2){
            ch[i][1]='(',ch[i][2]='(',ch[i][3]=')',ch[i][4]=')';
            ch[i+1][1]='(',ch[i+1][2]=')',ch[i+1][3]='(',ch[i+1][4]=')';
        }
        for(int i=1;i<=4;i++){
            for(int j=1;j<=m;j++) putchar(ch[j][i]);
            puts("");
        }
        exit(0);
    }
    for(int i=1;i<=m;i++) putchar('(');puts("");
    for(int i=2;i<n;i+=2){
        putchar('(');
        for(int j=1;j<m/2;j++) printf("()");
        putchar(')');puts("");
        for(int j=1;j<=m/2;j++) printf("()");
        puts("");
    }
    for(int i=1;i<=m;i++) putchar(')');
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}

B

图是一棵仙人掌
那么问题就是求仙人掌两点之间最大流之和
考虑 最大流=最小割，所以两点之间要么割一条树边，要么割两条环边
如果割掉一个环，考虑最小的环边一定会割，所以只要把最小的环边边权加在其他环边上，然后就变成了一棵树的问题了，用并查集维护即可
时间复杂度 O ( n ) O(n) O(n)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=300100,M=1000100,wxq=998244353;
struct Lines{ int x,y,z;}E[M];
int n,m,p,fa[N],s1[N],s2[N];
int fu[N],fl[N],dfn[N],dfs_clock;
int e[M],ne[M],w[M],h[N],idx;
bool tag[M];
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
void add(int x,int y,int z){ e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;}
void solve_cir(int x,int y,int ln){
    int mn=ln;
    for(int i=y;i!=x;i=fu[i]) if(w[fl[i]]<w[mn]) mn=fl[i];
    for(int i=y;i!=x;i=fu[i]) if(fl[i]!=mn) w[fl[i]]+=w[mn],w[fl[i]^1]+=w[mn];
    if(ln!=mn) w[ln]+=w[mn],w[ln^1]+=w[mn];
    tag[mn]=tag[mn^1]=1;
}
void tarjan(int u,int from){
    dfn[u]=++dfs_clock;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(!dfn[v]) fl[v]=i,fu[v]=u,tarjan(v,i);
    }
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];
        if(dfn[u]<dfn[v]&&fl[v]!=i) solve_cir(u,v,i);
    }
}
int get_father(int x){ return x==fa[x]?x:fa[x]=get_father(fa[x]);}
int qmi(int a,int b){
    int res=1;
    for(;b;b>>=1){
        if(b&1) res=res*a%wxq;
        a=a*a%wxq;
    }
    return res;
}
signed main(){
    freopen("sakura.in","r",stdin);
    freopen("sakura.out","w",stdout);
    n=read(),m=read(),p=read();
    memset(h,-1,sizeof(h));
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }
    tarjan(1,m*5);
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=h[i];~j;j=ne[j]) if(i<e[j]&&!tag[j]) E[++cnt]={i,e[j],w[j]};
    }
    sort(E+1,E+cnt+1,[](const Lines &i,const Lines &j){ return i.z>j.z;});
    for(int i=1;i<=n;i++) fa[i]=i,s1[i]=qmi(p,(i-1)*n),s2[i]=qmi(p,i);
    int ans=0;
    for(int i=1;i<=cnt;i++){
        int fax=get_father(E[i].x),fay=get_father(E[i].y);
        assert(fax!=fay);
        ans=(ans+(s1[fax]*s2[fay]+s2[fax]*s1[fay])%wxq*E[i].z)%wxq;
        fa[fax]=fay,s1[fay]=(s1[fay]+s1[fax])%wxq,s2[fay]=(s2[fay]+s2[fax])%wxq;
    }
    printf("%lld\n",ans);
    fprintf(stderr,"%d ms\n",int64_t(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}

C

先把 a i ! a_i! ai​! 质因数分解，令分解后 x x x 的指数为 t o t x tot_x totx​
然后从大到小枚举 b b b，找最大的 c c c，这是暴力的做法，时间复杂度 O ( n 2 ) O(n^2) O(n2)
考虑我们不需要每次都更新 t o t x tot_x totx​，而是打 t a g tag tag，即 t o t x tot_x totx​ 的实际值是 t o t x − t a g × y x tot_x-tag\times y_x totx​−tag×yx​， y x y_x yx​ 表示 b ! b! b! 的质因数分解
考虑每次会更新至多 l o g log log 个 y y y 值，考虑暴力修改这些 y y y 值，然后让 t o t x tot_x totx​ 与 t a g , y x tag,y_x tag,yx​ 匹配，然后维护最小值就可以用 s e t set set 了
时间复杂度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=300100;
int n,tag,tot[N],y[N],tms[N];
int pr[N],v[N],cnt;
multiset<int> se;
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
void sieve(int n){
    for(int i=2;i<=n;i++){
        if(!v[i]) v[i]=i,pr[++cnt]=i;
        for(int j=1;j<=cnt&&pr[j]<=n/i;j++){
            v[pr[j]*i]=pr[j];
            if(v[i]==pr[j]) break;
        }
    }
}
void dec(int x){
/*
(tot[x]-tag*y[x]) / y[x]
(tot[x]-?*(y[x]-1)) / y[x]
*/
    se.erase(se.find(tot[x]/y[x]));
    tot[x]-=tag*y[x],y[x]--;
    tot[x]+=tag*y[x];
    if(y[x]) se.insert(tot[x]/y[x]);
}
signed main(){
    freopen("secure.in","r",stdin);
    freopen("secure.out","w",stdout);
    int B=300010;
    sieve(B);
    n=read();
    for(int i=1;i<=n;i++) tms[read()]++;
    for(int i=B;i>=1;i--) tms[i]+=tms[i+1];
    for(int i=2;i<=B;i++){
        int x=i;
        while(x>1) tot[v[x]]+=tms[i],x/=v[x];
    }
    for(int i=1;i<=B;i++){
        int x=i;
        while(x>1) y[v[x]]++,x/=v[x];
    }
    for(int i=1;i<=B;i++) if(y[i]) se.insert(tot[i]/y[i]);
    vector<pair<int,int> > ans;
    for(int i=B;i>1;i--){
        auto beg=se.begin();
        if((*beg)-tag>0) ans.push_back({i,(*beg)-tag}),tag=*beg;
        int x=i;
        while(x>1) dec(v[x]),x/=v[x];
    }
    printf("%lld\n",ans.size());
    for(auto i:ans) printf("%lld %lld\n",i.first,i.second);
    fprintf(stderr,"%d ms\n",int64_t(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}

D

d p dp dp 套 d p dp dp，不会，摆了


http://www.niftyadmin.cn/n/5076638.html

相关文章

感染了后缀为.faust勒索病毒如何应对？数据能够恢复吗？

感染了后缀为.faust勒索病毒如何应对？数据能够恢复吗？

导言&#xff1a; 随着科技的不断发展&#xff0c;网络威胁也在不断演进。其中之一&#xff0c;被称为[support2022cock.li].faust、.[tsai.shenmailfence.com].faust勒索病毒的恶意软件威胁已经成为网络安全领域的一个重要问题。这种勒索病毒可以加密您的数据文件&#xff0c…
阅读更多...
C++ 笔记索引

C++ 笔记索引

C 参考手册访问地址 环境 VS coda 配置 VS coda C、python运行与Dbug配置 C、python、VS code插件安装与SSH使用 (不推荐) w10系统一般只用vs w10系统 如何使用 C、cmake、opencv、 语言基础 C main函数 测试例子 C常用基本类型、数组、复制内存 memcpy C if、else、switc…
阅读更多...
王杰C++day3

王杰C++day3

#include <iostream>using namespace std;class Per { private:string name;int age;int *height;int *weight; public://有参构造函数Per(string n,int a,int h,int w):name(n),age(a),height(new int(h)),weight(new int(w)){cout << "p有参" <<…
阅读更多...
YOLOv8血细胞检测（9）：SEAM注意力机制，提升遮挡小目标检测性能

YOLOv8血细胞检测（9）：SEAM注意力机制，提升遮挡小目标检测性能

💡💡💡本文改进：SEAM注意力机制，较好的解决了小目标中遮挡问题； SEAM | 亲测在血细胞检测项目中涨点，map@0.5 从原始0.895提升至0.902 收录专栏： 💡💡💡YOLO医学影像检测：http://t.csdnimg.cn/N4zBP ✨✨✨实战医学影像检测项目，通过创新点验证涨点可…
阅读更多...
ssti 前置学习

ssti 前置学习

python venv环境 可以把它想象成一个容器&#xff0c;该容器供你用来存放你的Python脚本以及安装各种Python第三方模块&#xff0c;容器里的环境和本机是完全分开的 创建venv环境安装flask #apt install python3.10-venv #cd /opt #python3 -m venv flask1 #cd /opt 选…
阅读更多...
底部Taber的抽取

底部Taber的抽取

1.会抽取一个布局样式 2.布局样式里面抽取一个底部样式 这个是layout的代码 <template><view class"layout-wrapper"><view class"layout-content"><slot></slot></view><!-- 底部 --><Tabbar :activeInde…
阅读更多...
翻译：网站整站翻译 / 网站国际化 / 极简实现

翻译：网站整站翻译 / 网站国际化 / 极简实现

一、本文目标 以极简单的方法实现整站翻译&#xff0c;轻松实现国际化。 二、js 文件 https://res.zvo.cn/translate/translate.js 三、代码 代码放在浏览器控制台即可实现 var head document.getElementsByTagName(head)[0];var script document.createElement(script);sc…
阅读更多...
Python操作Hive数据仓库

Python操作Hive数据仓库

Python连接Hive 1、Python如何连接Hive&#xff1f;2、Python连接Hive数据仓库 1、Python如何连接Hive&#xff1f; Python连接Hive需要使用Impala查询引擎 由于Hadoop集群节点间使用RPC通信&#xff0c;所以需要配置Thrift依赖环境 Thrift是一个轻量级、跨语言的RPC框架&…
阅读更多...
最新文章

Copyright @ 2022~2023