Prime Path

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number $1033$ for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number $8179$ is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an $8$, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from $1033$ to $8179$ by a path of prime numbers where only one digit is changed from one prime to the next prime.

阅读全文 »

第六章——字符串操作

  • 字符串以单(双)引号开始,单(双)引号结束

  • 在字符串开始的引号之前加上r,可以将字符串称为原始字符串,打印出字符串中所有的\之类的转义字符

    阅读全文 »

第五章——字典和结构化数据

字典

  • 字典的索引被称为,键及其关联的值称为键-值。字典输入的时候要带花括号{},在使用的时候和列表一样使用中括号[]

    阅读全文 »

第三章——函数

  • None表示没有值,是NoneType数据类型的唯一值。print的返回值就是None

  • print()函数有可选的变元endsep,分别指定在参数末尾打印什么,在参数之间打印什么来隔开它们

    阅读全文 »

快速幂相关

快速幂(二分幂)

时间复杂度:$O(logn)$

1
2
3
4
5
6
7
8
9
10
11
int Pow(int a,int b,int c)
{
int res=1;
while(b>0)
{
if(b&1) res=res*a%c;
a=a*a%c;
b>>=1;
}
return res;
}//复杂度O(logn)
阅读全文 »

DP

01背包(每种物品只有一个)

1
2
3
4
5
6
7
8
9
10
11
//n 物品数量,v 背包容量 
//size 单个物品体积,value 单个物品价值
void bag01()
{
for(int i=0;i<n;i++)
for(int j=v;j>=size[i];j--)
{
dp[j]=max(dp[j],dp[j-size[i]]+value[i]);
}
cout<<dp[v]<<endl;
}
阅读全文 »
0%