计算思维训练-20200707

字数统计: 1.8k字   |   阅读时长≈ 7分钟

Problem F. 安全的密码mark text

时间限制 1000 ms
内存限制 256 MB

题目描述
众所周知，密码安全是互联网时代人们最为关心的事情之一。而 RSA 公钥加密算法是目前最有影响力和最常用的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击。

其实 RSA 公钥加密算法的原理并不复杂，它基于一个十分简单的数论事实：将两个大素数相乘十分容易，而想要对其乘积进行质因数分解却极其困难，因此可以将乘积公开作为加密密钥。

所以 RSA 算法很重要的一个过程就是得到两个大素数相乘结果。

wchhlbt 和 Lazy_sheep 想要模拟一下 RSA 算法的加密过程。现在 wchhlbt拿到了 Lazy_sheep 提供的一份素数相乘的结果，但是 Lazy_sheep 因为别的事情计算的并不认真。 所以 wchhlbt 希望你来帮他判断这些数据的正确性。

输入数据
第一行为一个整数 t (1≤t≤1000)，表示数据的组数。接下来对于每组数据：
第一行为一个整数 n (2≤n≤2×109)。

输出数据
对于每组数据，输出一行：
如果这个数可以分解为两个素数乘积，输出YES，否则输出NO。

样例输入
4
6
8
35
121
样例输出
YES
NO
YES
YES
样例说明
无

算法

一个数学题，绕过了一道弯，写得好的代码应该在二十行左右。
对于每一个N，我们首先要想，如果它是两个素数的乘积，它一定满足什么条件？两个素数的乘积，一定不会是其他素数的倍数。如果一个数是两个大于一百的素数的乘积，它还有可能是2的倍数吗？不可能。这说明什么？如果n是两个素数的乘积，一旦我们找到了n的一个约数x，它的另一个约数就找到了（也就是n/x），而n不会再有其他约数，也就是循环不用继续下去。

那么这道题的做法也就显而易见。我们从2到(int)sqrt(n)循环，一旦找到一个n的约数x，就看n/x是不是素数。是素数，就是YES，不然就是NO。BTW，这里x是不是素数是不用判断的。原因是____.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		bool flag=false;
		ufor (i,2,(int) sqrt(n))
			if (n%i==0)
			{
				if (Sushu(n/i)) flag=true;
				break;
			}
		printf((flag)? "YES\n":"NO\n");
	}
	return 0;
}

思考题：在以上的for循环中，为什么要写两个if，而不是在两个判断之间用&&?

Problem G. 课堂作业-4-4

时间限制 1000 ms
内存限制 64 MB

题目描述
小明刚买了一个机械键盘，但他在用机械键盘打字的时候发现键盘的Home键和End键坏掉了，于是他在打字的时候光标有时会突然跑到行首，有时又会突然跑到行尾，现在给你键盘的输入，求最后屏幕上的字符串。

输入数据
输入数据为一行字符串，字符串只包含小写英文字母,’[‘符号以及’]’符号，’[‘代表按下了Home键，‘]’代表按下了End键，字符串长度不超过100000。

输出数据
输出最后屏幕上的字符串。

样例输入

xiechengxuz[henhao]wan

样例输出

henhaoxiechengxuzwan

样例说明
可能出现多个’[‘和’]’，也可能没有’[‘和’]’

解法

在说解法之前，先来捋一捋这题是什么意思。对于一个更典型的样例

1
[dsafd]af[daf]ewa[]f[ds

它的输出应当是

1
dsdafdsafdafewaf

这是怎么出来的呢？在队首，先有dsafd，然后daf插到它前面去了，接着ds又在它俩前面，所以输出的前面部分是dsdafdsafd。然后是中间部分。这里有一个结论，是中间部分必然在所有的[和]之前。输出中间部分（本样例无）之后，是队尾部分。队尾先有af，然后ewa排在它后面，f也在后面。所以最终输出为dsdafdsafdafewaf。

这题通过和大佬们讨论，本菜鸡获得了三个方法。以下引用均已获得许可。

一、strcat by JJHDL

其实这道题麻烦的地方就在队首而已。然后strcat是一个在时间复杂度上正常，而在代码编写难易程度上出色的一个函数。对于上面那个样例，我们就是把daf用strcat插到前面，再把ds插到前面。这个比较好理解，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int main(void)
{
    scanf("%s",s);
    int len = strlen(s);
    ans[0] = '\0';
    tmp[0] = '\0';
    int top = -1;
    int last = -1;
    for (int i=0;i<len;i++)
    {
        if (s[i]=='[')
        {
            tmp[top+1]='\0';
            if (last==-1){
                strcat(ans,tmp);
            }else{
                strcat(tmp,ans);
                strcpy(ans,tmp);
            }
            top=-1;
            last = 1;
            continue;
        }
        if (s[i]==']')
        {
            tmp[top+1]='\0';
            if (last==-1){
                strcat(ans,tmp);
            }else{
                strcat(tmp,ans);
                strcpy(ans,tmp);
            }
            top = -1;
            last = -1;
            continue;
        }
        tmp[++top] = s[i];
    }
            tmp[top+1]='\0';
            if (last==-1){
                strcat(ans,tmp);
            }else{
                strcat(tmp,ans);
                strcpy(ans,tmp);
            }
    printf("%s\n",ans);
    return 0;
}

该做法与链表类似。

二、倒序存 by GlisCJ

我对于队首的处理方法是这样的：
首先，在样例中，在队首的那几个字符串是 dsafd daf ds 是比较容易得到的。然后我们如何能更直接地存储它们呢？我想到一个方法，就是把每个分开的队首字符串都倒着存，这样会得到dfasd fad sd 。再把这个字符串倒序输出，就是 dsdafdsafd ，也就是我们想要的答案。
这个也比较好理解，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int main()
{
	scanf("%s",s); n=strlen(s);
	int i=0;
	while (i<n)
	{
		while (s[i]=='[')
		{
			int x=0;
			while (s[i]=='[') i++;
			while (i<n && s[i]!=']' && s[i]!='[') a[x++]=s[i++];
			dfor (j,x-1,0) st[cur++]=a[j];
		}
		i++;
	}
	dfor (i,cur-1,0) printf("%c",st[i]);
	i=0;
	while (i<n)
	{
		while (s[i]=='[' || s[i]==']')
		{
			while (s[i]=='[')
			while (i<n && s[i]!=']') i++;			
			while (s[i]==']' && i<n) i++;
		}
		if (i>=n) break;
		putchar(s[i++]);
	}
	return 0;
}

然鹅我实在是太菜惹，把它当成了传统字符串处理题。楼下简直是模板。

三、deque by ZXDL

队首，其实是相当于把一个个字符串不断放在第一位。队尾，其实是相当于把一个个字符串不断放在最后一位。那这就和stl中的deque的push_front()、push_back()操作完全吻合。这道题就像是这种数据结构的模板题，所以代码会非常清晰简明。
这个也比较好理解，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main() {
    char buf[102400];
    std::deque<std::string> input;
    scanf("%[^][\n]", buf);
    input.push_back(std::string(buf));
    char c;
    while (c = getchar(), c != EOF) {
        buf[0] = 0;
        if (c == '[') {
            scanf("%[^][\n]", buf);
            input.push_front(std::string(buf));
        } else if (c == ']') {
            scanf("%[^][\n]", buf);
            input.push_back(std::string(buf));
        }
    }
    for (auto & i : input) {
        std::cout << i;
    }
}

如果还是找不到错误原因的话，可以看看是不是在很多个[[[]]]]]][][][][][[[[]]]]相连的时候出错了。

友情链接：
章鱼哥：https://fishercat.top/
姜总：https://jjhqwq.top/

打赏
  • 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！
  • © 2023 glisses
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信