当前位置： 首页 > article >正文

2024.9.14

article 2024/9/21 2:36:12

A. 上海

时间限制: 1 s   内存限制: 512 MB   测评类型: 传统型

题目描述

Shintaro \text{Shintaro} Shintaro 有一个正整数 k k k。

请你判断是否存在正整数 n n n ，使得 n 2 n^2 n2 是 k k k 的倍数，且 n n n 不是 k k k 的倍数。如果存在，则输出最小的 n n n。不存在则输出 − 1 -1 −1。

输入格式

一行一个数 k k k。

输出格式

一行一个数表示答案。

样例输入1

4

样例输出1

2

样例输入2

42

样例输出2

-1

数据范围

  • 对于 50 % 50\% 50% 的数据： 1 ≤ k ≤ 1 0 6 1 \leq k \leq 10^6 1≤k≤106；
  • 对于 100 % 100\% 100% 的数据： 1 ≤ k ≤ 1 0 12 1\leq k\leq10^{12} 1≤k≤1012。

非常简单

//2024.9.14
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define int long long 
#define itn long long 
constexpr itn oo = 100004;
itn n;
int pri[oo],cnt;
bool vis[oo];
int use[oo],is[oo],top;
int out = 1;
__inline int qpow(itn a,int b){itn res=1;while(b){
    if (b&1)res*=a;a*=a;b>>=1;}return res;}
main(void){
    //fre();
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (itn i=2;i<oo-5;i++){
        if (!vis[i]) pri[++cnt] = i;
        for (int j=1;j<=cnt&&pri[j]*i<oo-5;j++){
            vis[i*pri[j]] = 1;
            if (i%pri[j]==0)break;
        }
    }
    //p_(pri,cnt,2);
    int i = 1;
    while (n&&i<=cnt){
        if (n%pri[i]==0){
            is[++top] = pri[i];
            while(n%is[top]==0){
                n/=is[top];
                use[top]++;
            }
        }
        i++;
    }
    for (itn i=1;i<=top;i++){
        if (use[i]>=2)break;
        if (i==top){cout << -1 << '\n';exit(0);}
    }
    for (int i=1;i<=top;i++){
        itn p = (use[i]+1)/2;
        out *= qpow(is[i],p);
    }
    cout << out << '\n';
    exit(0);
}

B. 华二

时间限制: 1 s   内存限制: 512 MB   测评类型: 传统型

题目描述

Ayano \text{Ayano} Ayano 喜欢 GCD。

现在她有一个长度为 n n n 的数列 A = ( a 1 , ⋯ , a n ) A=(a_1,⋯,a_n) A=(a1​,⋯,an​)，其中 1 ≤ a i ≤ 9 1\leq a_i \leq 9 1≤ai​≤9。对于其中相邻的两项的 a i a_i ai​ 和 a i + 1 a_{i+1} ai+1​ ，满足 g c d ( a i , a i + 1 ) = 1 gcd(a_i,a_{i+1})=1 gcd(ai​,ai+1​)=1 时， Ayano \text{Ayano} Ayano 可以通过一次操作交换 a i a_i ai​ 和 a i + 1 a_{i+1} ai+1​ ( 1 ≤ i ≤ n − 1 ) (1≤i≤n−1) (1≤i≤n−1)。

请你计算 Ayano \text{Ayano} Ayano 可以通过这个操作得到多少种数列（包含原数列） ( m o d 998244353 ) \pmod {998244353} (mod998244353)。

输入格式

第一行一个数 n n n ，表示数列的长度。

第二行 n n n 个数，第 i i i 个数表示 a i a_i ai​。

输出格式

一行一个数表示答案。

样例输入 1

3
8 3 2

样例输出 1

3

样例输入 2

9
1 2 3 4 5 6 7 8 9

样例输出 2

3024

数据范围

  • 对于 30 % 30\% 30% 的数据： 2 ≤ n ≤ 10 2\leq n\leq 10 2≤n≤10；
  • 对于另外 10 % 10\% 10% 的数据： a i ≤ 3 a_i\leq 3 ai​≤3；
  • 对于 100 % 100\% 100% 的数据： 2 ≤ n ≤ 100000 2\leq n\leq 100000 2≤n≤100000， 1 ≤ a i ≤ 9 1\leq a_i\leq 9 1≤ai​≤9。

非常有意思的一道计数题，关键在于数量为9

我们通过公因数进行分类

分成2.3

发现6比较特殊，两个公因数都有，又发现同公因数之间相对位置不会改变，

我们考虑在中间排列计数即可

//2024.9.14
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define itn long long
#define int long long 
constexpr int oo = 1000006;
constexpr itn op = 1000000;
constexpr itn mod = 998244353;
__inline itn qpow(itn a,int b){itn res=1;while(b){if(b&1)
    res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
int n;
int st[oo];itn fac[oo],ifac[oo];
int cnt1,cnt2,cnt3,cnt6,cnt5,cnt7;
main(void){
    //fre();
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    cin >> n;
    for(int i=1;i<=n;i++)cin >> st[i];
    fac[0]=1;
    for(int i=1;i<=op;i++)fac[i]=fac[i-1]*i%mod;
    ifac[op]=qpow(fac[op],mod-2);
    for(int i=op;i>=1;i--)ifac[i-1]=ifac[i]*i%mod;
    itn out=1;
    for(int i=1;i<=n;i++){
        if(st[i]==1) cnt1++;
        else if(st[i]==5)cnt5++;
        else if(st[i]==7)cnt7++;
        else if(st[i]==2||st[i]==4||st[i]==8)cnt2++,cnt6++;
        else if(st[i]==3||st[i]==9)cnt3++,cnt6++;
        else if(st[i]==6){
            cnt6++;
            out=out*fac[cnt2+cnt3]%mod*ifac[cnt2]%mod*ifac[cnt3]%mod;
            cnt2=cnt3=0;
        }
    }
    out=out*fac[cnt2+cnt3]%mod*ifac[cnt2]%mod*ifac[cnt3]%mod;
    out=out*fac[cnt1+cnt6+cnt5+cnt7]%mod*ifac[cnt1]%mod*ifac[cnt6]%mod*ifac[cnt5]%mod*ifac[cnt7]%mod;
    cout << out << '\n';
    exit (0);
}

C. 高爸

时间限制: 1 s   内存限制: 512 MB   测评类型: 传统型

Shintaro \text{Shintaro} Shintaro 有 n n n 条龙。 第 i i i 条龙的力量值是 x i x_i xi​。现在 Shintaro \text{Shintaro} Shintaro 想与这些龙交朋友。

Shintaro \text{Shintaro} Shintaro 会使用以下两种魔法来平衡龙的力量值（使某些龙的力量值相等），以免与他交朋友的龙互相打架。

强化魔法：消耗 a a a 点 p，使某条龙的力量值增加1点。

弱化魔法：消耗 b b b 点 p，使某条龙的力量值降低1点。

在第 i i i 次, Shintaro \text{Shintaro} Shintaro 想与前 i i i 条龙交朋友 ( 1 ≤ i ≤ n ) (1≤i≤n) (1≤i≤n)。我们有很多种使用魔法的方案，使前 i i i 条龙力量值相等。请你找到消耗 mp 点数最小的方案，并输出 mp 点数。

输入格式

第一行三个数 n n n a a a b b b ，表示龙的条数，强化魔法消耗的 m p mp mp 点数，弱化魔法消耗的 m p mp mp 点数。

第二行 n n n 个数，第 i i i 个数 x i x_i xi​ 表示第 i i i 条龙的力量值。

输出格式

共 n n n 行，第 i i i 行输出一个整数表示使前 i i i 条龙力量值相等所需的最小 m p mp mp 点数。

样例输入 1

5 3 2
5 1 4 2 3

样例输出 1

0
8
11
13
15

数据范围

  • 对于 50 % 50\% 50% 的数据： n ≤ 1000 n\leq 1000 n≤1000；
  • 对于另外 20 % 20\% 20% 的数据： 1 ≤ x i ≤ 100 1\leq x_i\leq 100 1≤xi​≤100；
  • 对于 100 % 100\% 100% 的数据： 1 ≤ n ≤ 100000 1\leq n\leq 100000 1≤n≤100000， 1 ≤ a , b ≤ 1 0 4 1\leq a,b\leq 10^4 1≤a,b≤104， 1 ≤ x i ≤ 1 0 9 1\leq x_i\leq 10^9 1≤xi​≤109。

不难发现力量为其中一条龙时一定会最优，50%时考虑枚举那一条龙的权值

100%时，对前面加入的权值进行排序，考虑在之前的结束值左右移动，选择更优的，复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

//2024.9.14
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define int long long 
#define itn long long 
constexpr int oo = 1e5+10;
constexpr int inf = 0x3f3f3f3f3f3f3f3f;
int n,st[oo],a,b;
int res;
priority_queue<int>ql;
priority_queue<int,vector<int>,greater<int>>qr;
main(void){
    //fre();
    cin.tie(0)->ios::sync_with_stdio(0);
    cin >> n >> a >> b;
    for(int i=1;i<=n;i++) cin>>st[i];
    int p=st[1],cnt=0;
    for(int i=1;i<=n;i++){
        if(st[i]<p){
            res+=(p-st[i])*a;
            ql.push(st[i]);
        }
        if(st[i]>p){
            res+=(st[i]-p)*b;
            qr.push(st[i]);
        }
        if(st[i]==p) cnt++;
        int ansl=inf,ansr=inf;
        if(ql.size()){
            int t=ql.top(),s=ql.size();
            ansl=res+(p-t)*(i-s)*b-(p-t)*s*a;
        }
        if(qr.size()){
            int t=qr.top(),s=qr.size();
            ansr=res+(t-p)*(i-s)*a-(t-p)*s*b;
        }
        if(ansr>=ansl){
            if(ansl<res){
                while(cnt--)qr.push(p);
                cnt=0; p=ql.top();
                while(ql.size()&&ql.top()==p)ql.pop(),cnt++;
                res=ansl;
            }
        }
        else{
            if(ansr<res){
                while(cnt--)ql.push(p);
                cnt=0;
                p=qr.top();
                while(qr.size()&&qr.top()==p)qr.pop(),cnt++;
                res=ansr;
            }
        }
        cout << res << "\n";
    }
    exit (0);
}

D. 金牌

时间限制: 2 s   内存限制: 512 MB   测评类型: 传统型

题目描述

Ayano \text{Ayano} Ayano 有一棵 n n n 个顶点的树（编号从 1 1 1 到 n n n )。 这棵树有 n − 1 n−1 n−1 条边，第 i i i 条边连接顶点 u i u_i ui​ 和顶点 v i v_i vi​。 由于Ayano Ayano \text{Ayano} Ayano 非常喜欢这棵树，树上的每条路径都被赋予了价值。具体地，这棵树上长度为 d d d 的简单路径的价值是 2 d 2^d 2d。

现在 Ayano \text{Ayano} Ayano 对你发出了 q q q 次询问，每次给出两个正整数 x , y x,y x,y ，请你回答所有通过顶点 x x x 和 y y y 的简单路径的价值之和   m o d   998244353 \bmod 998244353 mod998244353。

注：简单路径是指路径上的各顶点均不互相重复的路径，路径的长度是指一条路径经过的边的条数。

输入格式

第一行一个数 n n n ，表示顶点个数。

接下来 n − 1 n-1 n−1 行，其中第 i i i 行两个数 u i , v i u_i,v_i ui​,vi​ 用于描述第 i i i 条边。

接下来一行一个数 q q q ，表示询问次数。

接下来 q q q 行，其中第 i i i 行两个数 x i , y i x_i,y_i xi​,yi​ 用于描述第 i i i i 个询问。

输出格式

共 q q q 行，第 i i i 行表示第 i i i 次询问的答案。

样例输入1

5
1 2
2 3
2 4
4 5
3
1 3
2 3
3 4

样例输出1

4
18
12

数据范围

  • 对于 20 % 20\% 20% 的数据， n , q ≤ 1000 n,q\leq 1000 n,q≤1000；
  • 对于 50 % 50\% 50% 的数据， n , q ≤ 100000 n,q\leq 100000 n,q≤100000；
  • 对于 100 % 100\% 100% 的数据， n , q ≤ 1000000 n,q\leq 1000000 n,q≤1000000， 1 ≤ u i , v i , x i , y i ≤ n 1\leq u_i,v_i,x_i,y_i\leq n 1≤ui​,vi​,xi​,yi​≤n， x i ≠ y i x_i\neq y_i xi​=yi​。

提示：本题数据量较大，建议使用快速的读写方式。

考虑把一条路径对答案的贡献分成三部分， x x x 的子树内（ y y y 为根时）， y y y 的子树内（ x x x 为根时）， x x x 和 y y y 之间的路径。那么相同部分可以相加，最后乘起来就行了。对于前两部分可以换根或者预处理讨论，第三部分需要 Tarjan 求 LCA。

复杂度 O ( n ) O(n) O(n)。

//2024.9.14
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define itn long long 
#define int long long 
constexpr int oo = 1000010;
constexpr itn op = 2000010;
constexpr int mod = 998244353;
int n,q;int head[oo],st[op],ne[op];
itn mi[oo],idx,dis[oo],sz[oo];
int tp[oo],son[oo],fa[oo];
int f[oo],g[oo],dfn[oo],rdfn[oo],tim;
void add(int u,int v){st[idx]=v,ne[idx]=head[u],head[u]=idx++;}
void getdis(int x,int pr){
	dis[x]=dis[pr]+1,sz[x]=f[x]=1;
	for(int i=head[x],y;~i;i=ne[i])
		if((y=st[i])^pr){
			fa[y]=x,getdis(y,x),sz[x]+=sz[y],f[x]=(f[x]+2*f[y])%mod;
			if(sz[y]>sz[son[x]]) son[x]=y;
		}
}
void gettop(int x,int c){
	tp[x]=c,rdfn[dfn[x]=++tim]=x;
	if(!son[x]) return;
	g[son[x]]=(2*g[x]+3*(mod-f[son[x]]))%mod,gettop(son[x],c);
	for(int i=head[x],y;~i;i=ne[i])
		if((y=st[i])!=fa[x]&&y!=son[x])
			g[y]=(2*g[x]+3*(mod-f[y]))%mod,gettop(y,y);
}
int lca(int u,int v){
	while(tp[u]^tp[v])
		if(dis[tp[u]]>=dis[tp[v]]) u=fa[tp[u]];
		else v=fa[tp[v]];
	return dis[u]>=dis[v]?v:u;
}
int kth(int u,int k){
	while(dis[u]-k<dis[tp[u]]) k-=dis[u]-dis[fa[tp[u]]],u=fa[tp[u]];
	return rdfn[dfn[u]-k];
}
main(void){
    //fre();
    cin.tie(0)->sync_with_stdio(0);
	cin >> n;mi[0]=1;
    memset(head,-1,sizeof(head));
	for(int i=1,u,v;i<n;++i){
        cin >> u >>v ;
        add(u,v),add(v,u);
        mi[i]=mi[i-1]*2%mod;
    }
	getdis(1,0);g[1]=f[1],gettop(1,1);
    cin >> q;
	for(int i=1,u,v,t;i<=q;++i){
		cin >> u >> v;t=lca(u,v);
		if(t==v) u^=v^=u^=v;
		if(t==u) cout << ((g[u]+2*(mod-f[kth(v,dis[v]-dis[u]-1)]))*f[v]%mod*mi[dis[v]-dis[u]]%mod) << '\n';
		else cout << (f[u]*f[v]%mod*mi[dis[u]+dis[v]-2*dis[t]]%mod) << '\n'; 
	}
	return 0;
}

http://www.kler.cn/news/309648.html

相关文章：

  • python怎么写csv文件
  • 特效【生日视频制作】小车汽车黄金色版悍马车身AE模板修改文字软件生成器教程特效素材【AE模板】
  • Python | Leetcode Python题解之第406题根据身高重建队列
  • 三维数字图像相关法（3D-DIC）用于复合材料力学性能测试
  • 量化交易backtrader实践(一)_数据获取篇(3)_爬取数据
  • 直播开播极速流，如何有效接入？
  • RK3588人工智能学习笔记-rknn_server代理服务使用介绍
  • 清理C盘缓存，如何针对Windows10系统，专业地调整和优化C盘缓存设置
  • ESP-01S,ESP8266设置客户端透传模式
  • Nginx节点健康检查与自动上下线管理脚本，推送告警到企业微信
  • 解决Windows桌面或文件夹不自动刷新
  • 五种嵌入式中常见网络协议栈
  • 探索物联网 (IoT)：从概念到应用
  • [性能]高速收发的TCP/MQTT通信
  • docker时区修改
  • linux网络编程1
  • iOS六大设计原则设计模式
  • c++9月18日
  • [C++] 剖析多态的原理及实现
  • 深入了解单元测试框架：JUnit 5、Mockito和 AssertJ
  • 前端项目优化：极致最优 vs 相对最优 —— 深入探索与实践
  • App Fiddler抓包配置
  • arm
  • 一种没有注释的语言
  • python画图|3D直方图基础教程
  • CSP-J/S赛前知识点大全3.1.1：初赛易错重难点（题目）
  • C++如何处理内存碎片问题
  • java -- JDBC
  • 鸿蒙Harmony应用开发，数据驾驶舱页面的实现
  • 技术美术一百问（02）