20231009比赛总结

反思

A

构造题怎么也不会！怒！

B

我是 $s b$ ，点和边的数量不一样，我存边的数组一般开了 $M A XM$ ，一半开了 $M A XN$ ，爆成了 $40 pt s$

C

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

题解

A

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

#include 
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

B

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

#include 
#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

C

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

#include 
#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

D

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

相关阅读:
VideoPlayerWithOpenCVForUnityExample
前端利器躬行记（8）——VSCode插件研发
Django(二)精美博客搭建(11)实现文章列表分页查询及首页简单优化
羧酸研究：Lumiprobe 磺基花青7二羧酸
Quartz之数据库存储(代码案例)
单片机入门：LED数码管
你不知道的JavaScript----promise
.net core appsettings.json 配置 http 无法访问
jetson nano补充：根目录/usr刷机扩容瘦身
【李沐深度学习笔记】线性代数实现

原文地址：https://blog.csdn.net/djx2021/article/details/133718178