首页 > 其他分享 >2024.9.14

2024.9.14

时间：2024-09-14 22:15:24浏览次数：1  
标签：oo itn 14 int 2024.9 样例 long leq

DATE #:202409014

ITEM #:DOC

WEEK #:SATURDAY

DAIL #:捌月拾贰

TAGS 
<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=2617703637&auto=0&height=66" width="330"></iframe>
< BGM = "诀别无尽夏--Youzee Music" >
< theme = oi-contest >
< [NULL] >
< [空] > 
< [空] >

“每个夏天的句号都是窗外要烂掉的绿”

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\%\) 的数据：\(1 \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≤i≤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≤i≤n)\)。我们有很多种使用魔法的方案，使前 \(i\) 条龙力量值相等。请你找到消耗 mp 点数最小的方案，并输出 mp 点数。

输入格式

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

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

输出格式

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

样例输入 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(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   测评类型: 传统型

题目描述

\(\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;
}

标签：oo,itn,14,int,2024.9,样例,long,leq
From： https://www.cnblogs.com/white-ice/p/18414755

相关文章

  • 0914
    CRC码是用来验错的，当2^R≥K+R+1时，CRC码可以纠正1位错误，即单比特错误详见下图纠错编码求解海明码：1）2K≥K+N+1,求解K，信息位（N位）+检验位（K位）组成海明码，注意校验位的位置2）将校验码Pi放在H2(i-1)的位置上3）分组形成检验关系。每个数据位使用多个检验位进行检验，且被检验数据位的海明......
  • 2024.9.14
    今日总结：1:约数个数和这道题主要是一道数学题，主要的推到过程需要用到莫比乌斯反演，但是在求第一步用分块处理出1~n内的f(i)的值，再用线性筛求出u(i)的值和他的前缀和，我卡在了最后一步对原式进行数论分块点击查看代码#include<bits/stdc++.h>usingnamespacestd;constint......
  • 2024.9.13 总结（考 DP）
    （实际上是2024.9.14写的）本来以为是考DS的。（）T1题目里给的那个性质可能是来干扰的。异或上右移一位的数，其实就是除了第一位（最左边的），算贡献的时候都要看这一位异或前一位是不是1。于是随便线性DP，状态里记一下当前位填0还是1就行了。DP数组状态的第一维可以不要，省空......
  • BZOJ4144 Petrol
    最小生成树+最短路+并查集维护题目#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=2e5+100,M=N*2;intn,m,s;inth[N],e[M],ne[M],w[M],idx;intdis[N],pos[N];boolvis[N];intf[N];inta[N]; boolans[N];intq;structNODE{......
  • 2024-09-14：用go语言，给定一个正整数数组 nums，定义一个加密函数 encrypt(x)，其将一个整数
    2024-09-14：用go语言，给定一个正整数数组nums，定义一个加密函数encrypt(x)，其将一个整数x的每一位数字都替换为x中的最大数字，然后返回加密后的数字。例如，encrypt(523)会返回555，encrypt(213)会返回333。现在需要计算数组中所有元素加密后的和，然后返回这个和。输入：nums=[10,2......
  • 360 9.14笔试
    第二题大模拟真的有点折磨了第一题给出m种饮料，每种饮料只有一杯，接下来有n个客人，每个客人有两种想喝的饮料，请问最多能满足多少位客人。数据范围比较小n=20，所以直接暴力求解#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,m;cin>>n>>......
  • 虾皮9.14笔试
    三道都是简化的板子题第一题给出每个位置的过路费，求从左上角到右下角的最小花费是多少。只允许往下或者往右走。数据范围只有100直接暴力搜索即可。intminPathSum(vector<vector<int>>&grid){intm=grid.size();intn=grid[0].size();intres=......
  • 京东9.14笔试
    被美团挂的第二天早上神志不清，第三题写错了距离计算函数，人麻了第一题将数组划分成两个区间，要求区间和乘积最小。经典的前缀和+枚举即完成#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+5;inth[N];intmain(){intn;cin>>n;......
  • 2024.9.13（周五）
    完成机器学习查询数据集的作业数据集名称样本数属性属性个数标签任务Iris数据集150花萼长度,花萼宽度,花瓣长度,花瓣宽度4鸟类（Setosa,Versicolor,Virginica）分类MNIST数据集70,000像素值（28x28像素）784手写数字（0-9）分类Titanic数据集891乘客ID,船舱......
  • SS240914A. 神灵庙(desire)
    SS240914A.神灵庙(desire)问一棵有\(n\)个叶子的任意形态的二叉树，左儿子边权是\(1\)，右儿子边权是\(2\)，给叶子任意顺序附上\(a_i\)的权值，问\(\sumdep_ia_i\)最小。首先如果树的形态确定了，显然是深度大的叶子选小的\(a_i\)。（注：这里的深度都是只带权到根的距离）因为是树......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99