投稿
  1. 首页
  2. C

51Nod 2022年 5月月赛题解

code • 2022-5-6 • C • 阅读 40

51Nod 2022年 5月月赛题解,第1张

T1 除数减法

给定一个整数 n，按照如下算法进行 *** 作：
1、如果 n=0，结束算法；
2、找到 n的最小质因子 d ；
3、n−=d并回到 *** 作 1 。

一行一个整数 t 表示测试的数量（1 <= t <= 10000）。
后面 t 行，每行一个整数 n（2 <=  n <= 10^9）。
思路

这题是一个结论题， 先找到最小的一个质因子p1。 （n-p1）/2+1，得到答案后直接输出。

#include
#include
#include
using namespace std;
int findMinFactor(int n)
{
    for (int i = 2; i * i <= n; i ++ )
    {
        if(n % i == 0)
            return i;
    }
    return n;
}
int main()
{
    int t,n;
    cin >> t;
    while(t -- )
    {
        int ans=0;
        scanf("%d", &n);
        int minfac=findMinFactor(n);
        n-=minfac;
        cout << n/2+1 << endl;
    }
    return 0;
}
T2，数组构造 描述

给出 2个数字 x 和 y，以及一个长度 l，你来找一个等差数列，满足以下条件：

  1. 数列中包含 x 和 y

  2. 数列中所有的数均为正数

  3. 数列的长度为 l

  4. 如果有多组满足条件的，找出所有数字之和最小的

    输出这个最小和。

输入 
第一行仅有一个整数 T ( 1 <= T <= 100000 ) ，表示测试数据的组数。
每组数据仅有一行，包含三个整数 l ,x 和 y  (  2 <= l ,x  < y <= 1e6) ，分别表示数列的长度和数列中的两个元素的值。
输出 
对每一组测试数据，输出一个数，对应等差数列的最小和。
数据范围 
( 1 <= T <= 100000 ,  2 <= l ,x ,y <= 1e6）
输入样例 
10
2 1 49
5 20 50
6 20 50
7 20 50 
8 20 50
5 3 8
9 13 22
999997 99997 1000000
2 1 2
3 1 3
输出样例 
50
150
210
224
232
65
117
500000499994
3
6
样例解释

\1. 选 1 49
\2. 选 10 20 30 40 50
\3. 选 20 26 32 38 44 50
\4. 选 3 8 13 18 23
\5. 选 1 4 7 10 13 16 19 22 25

思路

我们考虑这个等差数列的公差，一定是 y−x 的约数，求出所有 y−x 的约数。

对于每一个约数，为了让和更小，需要让首项 fir 最小（0

记录所有约数中最小的最小公差，就是计算结果。

解法一，暴力搜索，TLE。 
#include 
#include 
#include 
using namespace std;
typedef long long LL;

LL solution(LL l, LL x , LL y)
{
    LL sum=6e17;
    // i 代表x到y之间有多少个数,最多有l-2，或者y-x-1。
    for (LL i = min(l-2,y-x-1); i >= 0; i -- )
    {
       if((y-x)%(i+1)==0)
       {
            LL gc = (y-x)/(i+1);// 求出公差
            LL left, j = l-2-i;
            while (x-j*gc<=0)j--;// j 为在x 左边的个数
            left = x-j*gc;  // 求出左端点
            // cout <<"left "<< left << endl;
            LL right = (l-2-i-j)*gc+y;// 求出右端点
            // cout <<"right "<< right << endl;
            if(right > sum || (left+right)*l/2<0) continue;// 预防卡ＬＬ，导致sum<0。
            sum = min(sum, (left+right)*l/2);// 等差数列求解
       }
    }
    return sum;
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        LL l,x,y;
        scanf("%lld%lld%lld",&l, &x, &y);
        printf("%lld\n",solution(l,x,y));
    }
    
    return 0;
}
解法二，优化版。 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;

vector findAllFactors(LL a)// 找到y-x所有的可能的约数。
{
	vector factors;
	for (int i = 1; i * i <= a; i++) 
	{
		if (a % i == 0) 
		{
		    factors.push_back(i);
			if (i != a / i)
			     factors.push_back(a/i);
		}
	}
	//sort(factors.begin(), factors.end());//从小到大排列
	return factors;
}

LL solution(LL l, LL x , LL y)
{
    LL sum=6e17;
    vector C = findAllFactors(y-x);
    // 遍历所有的约数
    for(auto gc:C)
    {
        LL i = (y-x) / gc -1;//表示在x到y中间的数有i个数。
        if( i+2 > l) continue;// 如果xy中间的数量+2大于l，则退出这层循环。
        LL j = x/gc;// 表示在x左边的最多的个数。
        if(x%gc == 0) j--; // 表示在x左边的个数。
        if(j<0)j=0;// 考虑到， j 可能一开始为0，如果j<0 则让j = 0；
        j = min(l-2-i,j);// 在x左边的数
        LL left = x-j*gc;//左端点
        LL right = left+(l-1)*gc;// 右端点
        if(right > sum || (left+right)*l/2<0) continue;// 预防卡ＬＬ，导致sum<0。
        sum = min(sum, (left+right)*l/2); 
        // cout<< gc <<" "<< left << " " << right << endl;
        
    }
    return sum;
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        LL l,x,y;
        scanf("%lld%lld%lld",&l, &x, &y);
        printf("%lld\n",solution(l,x,y));
    }
    // auto C = findAllFactors(999999);
    // for (auto c:C ) cout<
T3 字符串删除

给你一个 01 字符串 s，如果 si=1 且 si+1=0，则可以删除其中一个，问经过若干次删除 *** 作后，使字符串最短，且字典序最小的字符串，请输出这个字符串。

输入 
第一行仅有一个正整数  t  ( 1 <=  t <= 1000  )，表示测试数据的组数。
对于每组测试数据，包括一个由字符 0 和字符 1 组成的字符串s，s的长度小于1000。
输出 
共有 t 行，依次对应各组测试数据的结果。
数据范围 
1 <=  t <= 1000
输入样例 
5
0001111111
0101
11001101
1110000000
1
输出样例 
0001111111
001
01
0
1
样例解释

在第一个样例中，不能执行任何动作。

在第二个样例中，应该擦除 s2。

在第三个样例中，按照以下顺序删除： 11001101 →→ 1100101 →→ 110101 →→ 10101 →→ 1101 →→ 101 →→ 01

思路

我们先考虑有哪些是无法消除掉的，首先前缀的 0是无法消除掉的，后缀的 1 也是无法消除掉的。

例如：00100110011

前面 2 个 0 ，后面 2 个 1 是无法消除的。

一连串的 11…1100…0011…1100…00 最终都可以转为 1 或 0，我们先认为转换后的字符是 ?。

除了前缀 0 ，后缀 1，中间的部分一定是多个这样的串组成的（也可能是 0 个，比如：00110011）。

那么多个这样的串最终都可以转为多个 ?。我们发现，多个 ? 我们可以通过选择变化成不同的 01，最终都转为一个 0。

因此我们保留前缀 0 后缀 1 ，剩下的中间部分如果存在，则变成一个 0（字典序最小），否则什么都不必添加。

#include 
#include 
#include 
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t --)
    {
        string s;
        cin >> s;
        if(s.size()==1) 
        {
            cout << s <=0; i--)
        {
            if(s[i]=='0')break;
            else b1+=s[i];
        }
        if(f0.size() + b1.size() == s.size())// 如果前后中间没有东西不加0.
            cout << f0 << b1 << endl;
        else 
            cout << f0 << 0 << b1 << endl;
        
    }
    
    return 0;
}
T4 机器翻译V2 
第一行输入一个n(n<=100000)，表示词典中单词的个数。
接下来n行，每行两个单词，表示原始单词以及这个单词对应的意思。
接下来一行，输入一段文本，表示需要翻译的文章。
(每个单词长度不超过5且单词间以空格隔开，整个文本单词个数不超过100000)
输入样例 
3
a ds
c de
b fr
c b a
输出样例 
de fr ds
样例解释

cc 被翻译成 dede，bb 被翻译成 frfr，aa 被翻译成 dsds，因此：c b ac b a 对应 de fr dsde fr ds。

#include 
#include 
#include 
#include 
#include 

using namespace std;

unordered_map p;
int main()
{
    int n;
    string a,b;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a >> b;
        p[a]=b;
    }
    
    for (int i = 1; i <= n; i ++ )
    {
        string x;
        cin >> x;
        cout << p[x] << ' ';
    }
    return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/793579.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-05-06
下一篇 2022-05-06

发表评论

登录后才能评论

评论列表（0条）

保存