tags:
- NOIP
- 模拟
- 倍增
- 高精
- Python
categories: - 信息学竞赛
- 总结
Luogu P1079 Vigenère 密码
Solution
表示并不是很懂其他人发的题解.
我是这么想的, 既然是题目要求用密文转明文而且转换规则一定的, 所以就可以用明文转密文的逆过程来完成.
首先要搞明白明文是怎么变成密文的, 通过这个表可以观察到, 如果明文的一个字符是 ch1 ,密钥为 ch2 , 那么密文 ch3 对应的就是 ch1 在字母表中偏移 |ch2| 位, 例如 ( ext{ch1=A,ch2=B, ch3=ch1+|ch2|=A+B-A=B}) , 如果偏移之后超过了 'Z', 那么就从'A'继续开始, 相当于这是一个环, 'Z'的后面是'A'.
不难发现密文是明文在字母表中进行的偏移, 那么将密文转换为明文只需要将这个过程反过来就好了.只需要将密文减去一个密钥的偏移.例如 ( ext{ch3=F,ch2=C, ch1=ch3-|ch2|=F-(C-A)=D}).
知道了这个规则之后就不难写出程序了, 上面如果将其进行偏移出来比( ext{A})小就利用取余来处理, 具体可以看代码
int cha=B-'A';
return 'A'+(A-cha-'A'+26)%26;
还需要注意几个问题:
- 明文和密文对应的大小写是一致的.
- 最好一开始把密文和明文都变成是大写, 这样好转化, 最后转化回来.
- 第( ext{ i })位密文对应的密钥为第( ext{i}mod ext{len2})位, 同样利用取余.
- cctype库中几个函数, ( ext{islower(),tolower(),isupper(),islower()})比较好用, 参数为一个字符.
Code
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 1005
using namespace std;
char a[N],b[N];
int s,r,l;
inline char Change(char A,char B){
int cha=B-'A';
return 'A'+(A-cha-'A'+26)%26;//将密文在字母表中进行一定偏移
}
int main(){
scanf("%s%s",a,b);'
r=strlen(a),l=strlen(b);
int flag=0;
for(int i=0;i<l;++i){
if(islower(b[i]))flag=1;
if(isupper(b[i]))flag=2;//记录一下密文一开始的大小写
if(islower(b[i]))b[i]=toupper(b[i]);//将密文和密钥都转化为大写
if(islower(a[i%r]))a[i%r]=toupper(a[i%r]);
char ch=Change(b[i],a[i%r]);//得到明文的一个字符
if(flag==1)ch=tolower(ch);//再明文将其转化为密文一开始的大小写
if(flag==2)ch=toupper(ch);
putchar(ch);//输出这个字符
}
return 0;
}
Luogu P1080 国王游戏
Solution
首先题目我们需要对大臣进行一定的排序, 使得获得最多奖赏的大臣奖赏最少, 前面的题解已经写的很清楚了, 如果大臣 ( ext{a,b}) , ( ext{a}) 排在 ( ext{b}) 前面的条件是 ( ext{a.left} imes ext{a.right}< ext{b.left} imes ext{b.right}).
那么做法就比较显然了, 只需要对所有人的左右手乘起来排个序就好.然后统计答案, 最头疼的地方是需要用高精, 我自然是非常头疼, 但是可以不用c++啊, 可以用 Python 水一波啊, 毕竟人家最擅长的就是科学运算.
但是在用 Python 开心的写了一波之后发现只得了60分.竟然还 WA 了一个点, 真是没办法忍受, 然后想方设法得到了 RE 的数据, 发现了 RE 的原因.
OverflowError: integer division result too large for a float
百度之后发现是因为Python的浮点数是c语言的float, 所以会出锅.
然后就想自己写一个整数除法, 先取余, 然后二分除法的结果.结果又出现了类似的问题.醉了.
然后又百度, 好像是找到三种解决方案
- ( ext{from \_\_future\_\_ import division})
- ( ext{divmod()})函数
- ( ext{decimal})模块
- ( ext{a//b}), 等效于a整除b, 不会产生浮点运算, 但是不如第二种快, 不知道为什么.
可以自己百度具体的使用方法.我使用的第二种方法, 实际上( ext{divmod(a,b)})返回( ext{(int(a/b), a mod b)})
在通过上述艰难过程后, 终于通过了...
Code
#表示Python的注释
class Minister:#定义了一个类
def __init__(self, left, right, lefttimesright):#初始化函数
self.left = left
self.right = right
self.lefttimesright = lefttimesright
def __repr__(self):
return repr((self.left, self.right, self.lefttimesright))
n=int(input());#input()读入一行
wang=list(map(int,input().split()));#将读入的一行转化为[a,b,...], []为列表list
s=[]
for i in range(0,n):
guo=list(map(int,input().split()));
s.append(Minister(guo[0],guo[1],guo[0]*guo[1]));
ss=sorted(s, key=lambda student: student.lefttimesright)#将排序后的结果赋值给ss
lei=wang[0]
i=0
ans=0
while i<n:
jieguo=divmod(lei,ss[i].right)#jieguo=(a//b,a%b),jieguo[0]=a//b
#print(jieguo[0])
if jieguo[0]>ans:
ans=jieguo[0];
lei*=ss[i].left;
i=i+1;
print(ans)#输出