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

2024.9.14

article 2025/2/23 1:00:27

A. 上海

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

题目描述

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

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

输入格式

一行一个数 $k$ 。

输出格式

一行一个数表示答案。

样例输入1
4
样例输出1
2
样例输入2
42
样例输出2
-1
数据范围

对于 $50\%$ 的数据： $\leq k \leq 10^6$ ；
对于 $100\%$ 的数据： $1\leq k\leq10^{12}$ 。

非常简单

//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 测评类型: 传统型

题目描述

$\text{Ayano}$ 喜欢 GCD。

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

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

输入格式

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

第二行 $n$ 个数，第 $i$ 个数表示 $a_i$ 。

输出格式

一行一个数表示答案。

样例输入 1
3
8 3 2
样例输出 1
3
样例输入 2
9
1 2 3 4 5 6 7 8 9
样例输出 2
3024
数据范围

对于 $30\%$ 的数据： $2\leq n\leq 10$ ；
对于另外 $10\%$ 的数据： $a_i\leq 3$ ；
对于 $100\%$ 的数据： $2\leq n\leq 100000$ ， $1\leq a_i\leq 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 测评类型: 传统型

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

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

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

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

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

输入格式

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

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

输出格式

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

样例输入 1
5 3 2
5 1 4 2 3
样例输出 1
0
8
11
13
15
数据范围

对于 $50\%$ 的数据： $n\leq 1000$ ；
对于另外 $20\%$ 的数据： $1\leq x_i\leq 100$ ；
对于 $100\%$ 的数据： $1\leq n\leq 100000$ ， $1\leq a,b\leq 10^4$ ， $1\leq x_i\leq 10^9$ 。

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

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

//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 测评类型: 传统型

题目描述

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

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

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

输入格式

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

接下来 $n - 1$ 行，其中第 $i$ 行两个数 $u_i,v_i$ 用于描述第 $i$ 条边。

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

接下来 $q$ 行，其中第 $i$ 行两个数 $x_i,y_i$ 用于描述第 i $i$ 个询问。

输出格式

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

样例输入1
5
1 2
2 3
2 4
4 5
3
1 3
2 3
3 4
样例输出1
4
18
12
数据范围

对于 $20\%$ 的数据， $n,q\leq 1000$ ；
对于 $50\%$ 的数据， $n,q\leq 100000$ ；
对于 $100\%$ 的数据， $n,q\leq 1000000$ ， $1\leq u_i,v_i,x_i,y_i\leq n$ ， $x_i\neq y_i$ 。

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

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

复杂度 $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;
}