NEUQ-acm第二期训练Week4——代码源div2

这篇具有很好参考价值的文章主要介绍了NEUQ-acm第二期训练Week4——代码源div2。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

501RSA

题目描述

RSA算法选择两个不同质数的积作为模数。现在有两个正整数 A,B,如果它们是不同的质数,则判定为 full credit;否则,如果A⋅B不是任意大于1的整数的平方的整数倍,则判定 partial credit;否则判定为no credit。

输入格式

一行两个正整数 A,B。

输出格式

full credit 或 partial credit 或 no credit。

样例输入1

13 23

样例输出1

full credit

样例输入2

3 3

样例输出2

no credit
数据规模

所有数据保证 2 ≤ A , B ≤ 1 0 12 2≤A,B≤10^{12} 2A,B1012

思路

判断是否为素数,按条件输出,发现判断a*b时数据范围超了;
故判断a与b的因子个数,如果因子出现偶数或者该因子可以是平方的形式,那么就是no credit
怎么统计因子的个数,由于数据太大,用map即可

代码

#include <bits/stdc++.h>
using namespace std;
long long a,b;
//long long x;
bool zhishu(long long s){
    int flag = 0;
    if(s==2)  return true;
    for(long long i = 2; i <= sqrt(s); i++){
        //cout << i << endl;
        //if(i==545527) cout << "@";
        if(s%i==0){
            flag=1;
            //cout << "#" ;
            break;
        }
    }
    if(flag==1)  return false;
    else  return true;
}
map < long long, long long> y;
void yinzi(long long s){
    for(long long i = 2; i <= sqrt(s); i++){
        if(s%i==0){
            y[i]++;
            y[s/i]++;
        }
    }
}
int main(){
    cin >> a >> b;
    //cout << sqrt(a) << endl;
    //zhishu(a);
    if(a!=b && zhishu(a) && zhishu(b))  cout << "full credit" << endl;
    else{
        //x = a*b;
        //cout << x;
        yinzi(a);
        yinzi(b);
        int flag = 0;
        for(auto i = y.begin(); i!=y.end(); i++){
            long long x = sqrt(i->first);
            if(x*x==i->first || i->second>1){
                flag=1;
                //cout << i->second;
                break;
            }
        }
        if(flag==0 && a!=b)  cout << "partial credit" << endl;
        else  cout << "no credit" << endl;
    }
}

502数组操作

题目描述

给你一个有 n n n 个元素的数组 a a a 。你可以对它进行如下操作,次数不限。

从一个偶数大小为 2 k 2k 2k 的数组中选择一些从位置 l l l开始的子数组 ( 1 ≤ l ≤ l + 2 ⋅ k − 1 ≤ n , k ≥ 1 ) (1≤l≤l+2⋅k−1≤n , k≥1) (1ll+2k1n,k1) ,对于 0 0 0 k − 1 k−1 k1(包括)之间的每一个 i i i ,将值 a l + k + i a_{l+k+i} al+k+i 分配给 a l + i a_{l+i} al+i

例如,如果 a = [ 2 , 1 , 3 , 4 , 5 , 3 ] a=[2,1,3,4,5,3] a=[2,1,3,4,5,3] ,然后选择 l = 1 l=1 l=1 k = 2 k=2 k=2 ,应用这个操作,数组将变成 a = [ 3 , 4 , 3 , 4 , 5 , 3 ] a=[3,4,3,4,5,3] a=[3,4,3,4,5,3]

请找出使数组中所有元素相等所需的最少操作数(可能是零)。

输入格式

输入由多个测试用例组成。第一行输入一个整数 t ( 1 ≤ t ≤ 2 × 1 0 4 ) t(1≤t≤2×10^4) t(1t2×104)表示测试用例的数量。

每个测试用例的包含 ( n + 1 ) (n+1) (n+1) 个整数:

第一个整数 n ( 1 ≤ n ≤ 2 × 1 0 5 ) n(1≤n≤2×10^5) n(1n2×105) 表示数组的长度。

此后 n n n 个整数 a 1 , a 2 , . . . , a n ( 1 ≤ a i ≤ n ) a_1,a_2,...,a_n(1≤a_i≤n) a1,a2,...,an(1ain) 表示数组的元素。

输出格式

输出 t t t 行,每行一个整数表示用给定的操作使数组中所有元素相等所需的最小操作数。

样例输入

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

样例输出

0
1
1
2
0
数据规模

保证所有测试用例的 n 之和不超过 200000。

提示

在第一个测试中,所有元素都是相等的,因此不需要任何操作。

在第二个测试中,你可以应用一个操作, k = 1 , l = 1 k=1,l=1 k=1l=1,设置 a 1 ← a 2 a_1←a_2 a1a2 ,通过 1 1 1 个操作,数组变成 [ 1 , 1 ] [1,1] [1,1]

在第三个测试中,你可以应用一个操作, k = 1 , l = 4 k=1,l=4 k=1l=4,设置 a 4 ← a 5 a_4←a_5 a4a5 ,然后数组变成 [ 4 , 4 , 4 , 4 , 4 ] [4,4,4,4,4] [4,4,4,4,4]

在第四个测试中,你可以应用一个操作, k = 1 , l = 3 k=1,l=3 k=1l=3,设置 a 3 ← a 4 a_3←a_4 a3a4 ,数组变成 [ 4 , 2 , 3 , 3 ] [4,2,3,3] [4,2,3,3],然后你可以应用另一个操作, k = 2 , l = 1 k=2,l=1 k=2l=1,设置 a 1 ← a 3 , a 2 ← a 4 a_1←a_3,a_2←a_4 a1a3,a2a4, 数组变成 [ 3 , 3 , 3 , 3 ] [3,3,3,3] [3,3,3,3]

在第五次测试中,只有一个元素,因此不需要任何操作。

思路

最后变成的数组一定是最后一位的值,所以我们倒着来,每次可以使与a[n]相等的后几位数赋给前面的,直到所有的都赋值完

代码

#include <bits/stdc++.h>
using namespace std;
const int Max = 2e5+5;
int t,n;
int a[Max];
int main(){
    cin >> t;
    for(int i = 1; i <= t; i++){
        cin >> n;
        for(int j = 1; j <= n; j++)  cin >> a[j];
        int val = a[n];
        int num =1, ans = 0;
        for(int j = n-1; j >= 1; j--){
            if(a[j]==val) num++;
            else{
                j-=num-1;
                num*=2;
                ans++;
            }
        }
        cout << ans << endl;
    }
}

503A-B 数对

题目描述

给出一串数以及一个数字 C ,要求计算出所有 A−B=C 的数对的个数(不同位置的数字一样的数对算不同的数对)。

输入格式

输入共两行。

第一行,两个整数 N, C。

第二行, N 个整数,作为要求处理的那串数。

输出格式

一行,表示该串数中包含的满足 A−B=C 的数对的个数。

样例输入

4 1
1 1 2 3

样例输出

3
数据范围

1 ≤ N ≤ 2 × 1 0 5 , 1 ≤ C ≤ 2 × 1 0 5 1≤N≤2×10^5, 1≤C≤2×10^5 1N2×105,1C2×105, 题目保证输入的 N 个数范围小于 230。

思路

统计每一个数出现的个数,那么a-b=c的个数就是遍历1~maxx-c,对于每一个i都有a[i]*a[i+c]种搭配使得等式成立,每种结果加起来即可

代码

#include <bits/stdc++.h>
using namespace std;
const int Max = 1e7+5;
int n,c;
int a[Max];
int main(){
    cin >> n >> c;
    int maxx = 0;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        a[x]++;
        maxx = max(maxx,x);
    }
    int ans = 0;
    for(int i = 1; i <= maxx-c; i++){
        if(a[i+c]!=0){
            ans += a[i]*a[i+c];
        }
    }
    cout << ans << endl;
}

504数位计算

题目描述

​ 给出一个整数 n n n,请解决下面的问题:

​ 使 f ( x ) = ( 不超过 x 且与 x 具有相同位数的正整数的个数 ) f(x)=(不超过 x 且与 x 具有相同位数的正整数的个数) f(x)=(不超过x且与x具有相同位数的正整数的个数)

​ 求出 f ( 1 ) + f ( 2 ) + . . . + f ( n ) f(1)+f(2)+...+f(n) f(1)+f(2)+...+f(n) ,结果对 998244353 998244353 998244353 取模。

输入格式

​ 一个整数 N。

输出格式

​ 一个整数——上面问题的答案,并对 998244353 取模。

样例输入1

16

样例输出1

73
样例解释

对从 1 到 9 的每个 x,不超过 x 且与 x 具有相同位数的正整数有 1 , 2 , . . , x 1,2,..,x 1,2,..,x,因此, f ( 1 ) = 1 , f ( 2 ) = 2 , . . . , f ( 9 ) = 9 f(1)=1,f(2)=2,...,f(9)=9 f(1)=1,f(2)=2,...,f(9)=9。对从 10 到 16 的每个 x,不超过 x 且与 x 具有相同位数的正整数有 10 , 11 , . . , x , 10,11,..,x, 10,11,..,x因此, f ( 10 ) = 1 , f ( 11 ) = 2 , . . . , f ( 16 ) = 7 f(10)=1,f(11)=2,...,f(16)=7 f(10)=1,f(11)=2,...,f(16)=7。所以答案为 73。

样例输入2

238

样例输出2

13870

样例输入3

999999999999999999

样例输出3

762062362
数据规模

​ 所有数据保证 1 ≤ N < 1 0 18 1≤N<10^{18} 1N<1018,且 N 是整数。

思路

计算1 ~ 9、10 ~ 99、100 ~ 999…
最后剩余的不足一个区间的尾数单独再算一次,累加即可

代码

#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
long long n;
long long ans;
int main(){
    cin >> n;
    long long t = n;
    long long len = 0;
    while(t){
        t/=10;
        len++;
    }
    //cout << len << endl;
    long long w = 9;
    for(int i = 1; i < len; i++){
        ans = (ans +((w%mod+1)*(w%mod)/2)%mod)%mod;
        w*=10;
    }
    w = n - w/9 +1;
    ans = (ans + ((w%mod)*(w%mod+1)/2)%mod)%mod;
    cout << ans << endl;
}

505新国王游戏

题目描述

又到了 H 国国庆, 国王再次邀请 n 位大臣来玩有奖游戏。上次国庆被众臣吐槽国王小气后,国王决定今年大方点,改变游戏规则且不再参与游戏,免得被大臣们质疑。首先, 他让每位大臣在左、 右手上面分别写下一个正整数。然后让这 n 位大臣排成一排。排好队后, 所有的大臣都会获得国王奖赏的若千金币, 每位大臣获得的金币数分别是:排在该大臣后面的所有人的左手上的数的乘积乘以他自己右手上的数。国王希望所有大臣获得的金币数之和最多,所以他想请你帮他重新安排一下队伍的顺序。

简而言之,给定 n 对数 a i , b i a_i,b_i ai,bi,找到一种排列顺序,使得 b 1 × a 2 ∗ a 3 ∗ … a n + b 2 × a 3 ∗ a 4 ∗ … a n + ⋯ + b n b_1×a_2∗a_3∗…a_n+b_2×a_3∗a_4∗…a_n+⋯+b_n b1×a2a3an+b2×a3a4an++bn 最大,求最大值,由于答案可能很大,需要对 1000000007 1000000007 1000000007 取模

输入格式

第一行,包含一个整数 n。 第二行到第 n+1 行,包含两个整数 a i , b i a_i,b_i ai,bi

输出格式

输出一行,表示按某种排序后的 b 1 × a 2 ∗ a 3 ∗ … a n + b 2 × a 3 ∗ a 4 ∗ … a n + ⋯ + b n b_1×a_2∗a_3∗…a_n+b_2×a_3∗a_4∗…a_n+⋯+b_n b1×a2a3an+b2×a3a4an++bn的最大值对 1000000007 1000000007 1000000007 取模的结果

样例输入

2
1 2
3 4

样例输出

10
说明

只有两种情况:
1.

1 2
3 4

( 2 ∗ 3 ) + 4 = 10 (2∗3)+4=10 (23)+4=10
2.

3 4
1 2

( 4 ∗ 1 ) + 2 = 6 (4∗1)+2=6 (41)+2=6
所以答案为 10

数据限制

对于 100% 的数据,保证 1 ≤ n ≤ 1 0 6 , 1 ≤ a i , b i ≤ 2 30 1≤n≤10^6,1≤a_i,b_i≤2^{30} 1n106,1ai,bi230

思路

先排序,将大臣交换比较哪种情况金币多
排好序后计算结果即可

代码

#include <bits/stdc++.h>
using namespace std;
const int Max = 1e6+5;
const long long  mod = 1000000007;
int n;
struct p{
    long long l,r;
    bool operator<(p b){
        return b.r*(l-1) < r*(b.l-1);
    }
}pai[Max];
long long ans;
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> pai[i].l >> pai[i].r;
    }
    sort(pai+1, pai+n+1);
    for(int i = 1; i <= n; i++){
        ans = (ans*pai[i].l+pai[i].r)%mod;
    }
    cout << ans << endl;
}

507Lusir的游戏

题目描述

Lusir 正在玩一个古老的基于 DOS 的游戏。

游戏中有 N+1 座建筑——从 0 到 N 编号,从左到右排列。编号为 0 的建筑高度为 0 个单位,编号为 i 的建筑高度为 H(i) 个单位。 起初,Lusir 在编号为 0 的建筑处。每一步,它跳到下一个(右边)建筑。假设 Lusir 在第 k 个建筑,且它现在的能量值是 E,下一步它将跳到第 k+1 个建筑。

如果 H ( k + 1 ) > E H(k+1)>E H(k+1)>E,那么 Lusir 就失去 H ( k + 1 ) − E H(k+1)−E H(k+1)E 的能量值,否则他将得到 E − H ( k + 1 ) E−H(k+1) EH(k+1) 的能量值。

游戏目标是到达第 N 个建筑,在这个过程中能量值不能为负数个单位。

现在的问题是 Lusir 至少以多少能量值开始游戏,才可以保证成功完成游戏?

输入格式

第一行输入整数 N。 第二行是 N 个空格分隔的整数, H ( 1 ) , H ( 2 ) , … , H ( N ) H(1),H(2),…,H(N) H(1),H(2),,H(N) 代表建筑物的高度。

输出格式

输出一个整数,表示所需的最少单位的初始能量值上取整后的结果。

数据范围

1 ≤ N , H ( i ) ≤ 1 0 5 1≤N,H(i)≤10^5 1N,H(i)105

输入样例1

5
3 4 3 2 4

输出样例1

4

思路

二分,找最小的最大

代码

#include <bits/stdc++.h>
using namespace std;
const int Max = 1e5+5;
int n;
int h[Max];
int maxx;
bool check(int x){
    for(int i = 1; i <= n; i++){
        x = 2*x-h[i];
        if(x < 0)  return false;
        if(x >= maxx)  return true;
    }
    return true;
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> h[i];
        maxx = max(maxx,h[i]);
    }
    int l = 0, r = maxx+1;
    int mid;
    while(l<r){
        mid = (l+r)/2;
        if(check(mid)) r = mid;
        else  l = mid+1;
    }
    cout << l << endl;
}

601BFS练习1

题目描述

给你一个数字a,每次可以选择下面四种操作中的一种:

把数字a加上一。
把数字a乘以2。
把数字a乘以3。
把数字a减去一。
问把这个a变成b最少需要多少步。

你要回答q个询问, b 1 , b 2 , … , b q b_1,b_2,…,b_q b1,b2,,bq,输出把a变成 b 1 , b 2 , … , b q b_1,b_2,…,b_q b1,b2,,bq的最小步数。

输入格式

第一行两个整数a,q。

接下来一行q个整数 b 1 , … , b q b_1,…,b_q b1,,bq

输入格式

输出q个数字,分别表示把a变成 b 1 , b 2 … , b q b_1,b_2…,b_q b1,b2,bq的最小步数。

样例输入

3 10
1 2 3 4 5 6 7 8 9 10

样例输出

2 1 0 1 2 1 2 2 1 2
数据规模

对于所有数据,保证 1 ≤ a , q , b i ≤ 1 0 5 1≤a,q,b_i≤10^5 1a,q,bi105

思路

对1~1e5的数据预处理,队列+bfs
把a变成b,四种操作,到达没走过的b,则赋值步数
否则不做处理

代码

#include <bits/stdc++.h>
using namespace std;
const int Max = 1e5+5;
int a, q, b;
int f[Max];
queue<pair<int, int> > que;
int main() {
	memset(f, -1, sizeof(f));
	cin >> a >> q;
    que.push(make_pair(a,0));
	while (!que.empty()) {
		auto fro = que.front();
		que.pop();
		if(f[fro.first] == -1)  f[fro.first] = fro.second;
		if(fro.first+1 <= Max && f[fro.first+1] == -1) que.push(make_pair(fro.first+1, fro.second+1));
		if(fro.first-1 > 0 && f[fro.first-1] == -1) que.push(make_pair(fro.first-1, fro.second+1));
		if(2*fro.first <= Max && f[2*fro.first] == -1) que.push(make_pair(2*fro.first, fro.second+1));
		if(3*fro.first <= Max && f[3*fro.first] == -1) que.push(make_pair(3*fro.first, fro.second+1));
	}
	for (int i = 0; i < q; i++) {
		cin >> b;
		cout << f[b] << " ";
	}
	return 0;
}

60201序列2

题目描述

又是大家最喜欢的01序列问题了呢

这次的问题非常的简单,cc觉得一个01序列中两个1之间至少要有k个0,现在他要构造出一个长度为n的01序列,请问他有多少种不同的构造方法

这个数字可能会非常大,请你对 1 0 9 + 7 10^9+7 109+7取模

输入格式

一行,给出两个整数n,k

输出格式

一个整数,代表不同的构造方法数

数据范围

1 ≤ n ≤ 1 0 6 1≤n≤10^6 1n106
0 ≤ k < n 0≤k<n 0k<n

样例输入

4 2

样例输出

6

思路

参考自一位大佬
动态转移DP
dp[i]表示序列第i个数为1时序列前i个数的构造方法数。
状态转移:dp[i]=dp[1]+dp[2]+……+dp[i-k-1]+1文章来源地址https://www.toymoban.com/news/detail-605279.html

代码

#include<bits/stdc++.h> 
using namespace std;
const int Max = 1e6+5;
const long long mod = 1e9+7;
int n,k;
long long dp[Max];
long long ans[Max];
int main(){
	cin>>n>>k;
	for(int i=1; i <= n; i++){
		if(i-k-1 > 0)  dp[i]= (ans[i-k-1]+1)%mod;
		else dp[i]=1;
		ans[i]=(ans[i-1]+dp[i])%mod;
	}
	
	cout<<ans[n]+1;
}

到了这里,关于NEUQ-acm第二期训练Week4——代码源div2的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法刷题 week4

    1.斐波那契数列 题目 题解 (递推 + 滚动变量) O(n) 这题的数据范围很小,我们直接模拟即可。 当数据范围很大时,就需要采用其他方式了,可以参考 求解斐波那契数列的若干方法 。 F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N 1. 斐波那契数列由 0 和 1 开始,之后的斐波那契数就

    2024年02月07日
    浏览(38)
  • 安全与认证Week4

    目录 目录 Web Security (TLS/SSL) 各层安全协议 Transport Layer Security (TLS)传输层安全性(TLS) SSL和TLS的联系与区别 TLS connectionsession 连接与会话 题目2答案点 TLS ArchitectureTLS架构(5个协议) 题目1答案点 Handshake Protocol(握手协议) 其它几个协议,包括后面的示例 题目10答案点 Handshake

    2024年02月02日
    浏览(38)
  • HGame 2023 Week4 部分Writeup

    文章同时发布于我的博客:https://blog.vvbbnn00.cn/archives/hgame2023week4-bu-fen-writeup 第四周的比赛难度较高,同时也出现了不少颇为有趣的题目。可惜笔者比较菜,做出来的题目数量并不是很多,不过里面确实有几道题值得好好讲讲。不多废话了,抓紧端上来吧(喜)。 注:本周C

    2024年02月03日
    浏览(49)
  • 0xGame week4-WEB wp

    完结撒花!!!学到了很多很多,算是我这个WEB菜鸡过渡期的一个见证吧。 0xGame虽然也没做出来几道(大嘘),但是 一步步跟着复现也学了很多好玩的知识点和思路,希望下次能进化成WEBak哥hhhhhh~~~~ 来看最后一周,全是java框架,麻了。 整体不难,hint把解题方法基本写脸上

    2024年02月05日
    浏览(69)
  • NewStarCTF 2023 公开赛道 WEEK4|CRYPTO 部分WP

    1、题目信息 提示: \\\"Schmidt Samoa\\\" 附件信息 2、解题方法 学了一个新技巧,哈哈哈。 简介 : Schmidt-Samoa密码系统,像rabin加密一样,其安全性基于整数因式分解的难度。但 Rabin 解密时会得到四个解,而 Schmidt-Samor 得到的是唯一解。 密钥生成 1.选取两个大的质数p和q并进行计算

    2024年02月08日
    浏览(45)
  • [BUUCTF NewStarCTF 2023 公开赛道] week4 crypto/pwn

    再补完这个就基本上完了. Schmidt-Samoa密码系统看上去很像RSA,其中N=pqq, 给的e=N给了d NTRU又一个格的基本应用   当E.order() == p时   p-1光滑时的分解 此题先是p-1光滑分解,然后是e=3*0x10000先求3次根再用rabin求16次    求误差,虽然被分成3个数组,但本质上是一个,可以连到一起求解. 

    2024年02月07日
    浏览(38)
  • 剑指offer题解合集——Week4day2

    题目链接:二叉树中和为某一值的路径 AC代码 思路: 整体思路

    2024年01月15日
    浏览(46)
  • 前端架构师-week4-脚手架命令注册和执行过程开发

    基于 Commander 完成脚手架命令注册和命令执行过程开发 ·如何设计高性能脚手架(缓存 + 多进程 实现这一点) ·Node 多进程开发 ·javascript 面向对象的实战技巧(达到可扩展 高复用) ·图解高性能脚手架架构设计方法 ·封装通用的 Package 和 Command 类 ·基于缓存 + Node 多进程实现

    2024年02月01日
    浏览(56)
  • 前端架构师-week4-封装通用的npm包管理类Package

    目录 脚手架命令本地调试功能支持 动态执行库exec模块创建 创建 npm 模块通用类 Package Package 类的属性、方法定义及构造函数逻辑开发 Package 类获取入口文件路径功能开发(pkg-dir应用+解决不同操作系统路径兼容问题)  利用 npminstall 库安装 npm 模块 Package 类判断模块是否存在

    2024年02月03日
    浏览(42)
  • 【北邮国院大三下】Cybersecurity Law 网络安全法 Week4

    北邮国院大三电商在读,随课程进行整理知识点。仅整理PPT中相对重要的知识点,内容驳杂并不做期末突击复习用。个人认为相对不重要的细小的知识点不列在其中。如有错误请指出。转载请注明出处,祝您学习愉快。 编辑软件为Effie,如需要pdf/docx/effiesheet/markdown格式的文件

    2024年02月11日
    浏览(74)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包