快速建站介绍,网络规划设计师 用途,网站建设名词解释与简答题,中国七大网络运营商D A Y 1 DAY 1 DAY1 T 1 T1 T1 V i g e n e ˋ r e 密 码 Vigenre密码 Vigeneˋre密码
16世纪法国外交家Blaise de Vigenre设计了一种多表密码加密算法——Vigenre密码。Vigenre密码的加密解密算法简单易用#xff0c;且破译难度比较高#xff0c;曾在美国南北战争中为南军所… D A Y 1 DAY 1 DAY1 T 1 T1 T1 V i g e n e ˋ r e 密 码 Vigenère密码 Vigeneˋre密码
16世纪法国外交家Blaise de Vigenère设计了一种多表密码加密算法——Vigenère密码。Vigenère密码的加密解密算法简单易用且破译难度比较高曾在美国南北战争中为南军所广泛使用。在密码学中我们称需要加密的信息为明文用M表示称加密后的信息为密文用C表示而密钥是一种参数是将明文转换为密文或将密文转换为明文的算法中输入的数据记为k。 在Vigenère密码中密钥k是一个字母串kk1k2…kn。 当明文Mm1m2…mn时 得到的密文Cc1c2…cn其中cimi®ki 运算®的规则如下表所示
Vigenère加密在操作时需要注意 ®运算忽略参与运算的字母的大小写并保持字母在明文M中的大小写形式 当明文M的长度大于密钥k的长度时将密钥k重复使用。 例如明文MHelloworld密钥kabc时密文CHfnlpyosnd。 Input 输入共2行。 第一行为一个字符串表示密钥k长度不超过100其中仅包含大小写字母。第二行为一个字符串表示经加密后的密文长度不超过1000其中仅包含大小写字母。 Output 输出共1行一个字符串表示输入密钥和密文所对应的明文。 Sample Input CompleteVictory Yvqgpxaimmklongnzfwpvxmniytm Sample Output Wherethereisawillthereisaway 【数据说明】 对于100%的数据输入的密钥的长度不超过100输入的密文的长度不超过 1000且都仅包含英文字母。 考场上遇到这样的水题真是爽的不得了应该算是字符串入门题吧不多bibi代码 #include cstdio
#include iostream
#include cstring
using namespace std;int len1,len2;
string s1,s2,ans;
bool d;int main()
{getline(cin,s1);getline(cin,s2);len1 s1.length();len2 s2.length();for (int i 0; i len1; i ) if (s1[i] A s1[i] Z) s1[i] s1[i] - A a;for (int i 0,j 0,w; i len2; i ,j ){if (j len1) j 0;if (s2[i] a s2[i] z) d 0; else d 1;if (d) w ((s2[i] - A 1) - (s1[j] - a) 26) % 26;else w ((s2[i] - a 1) - (s1[j] - a) 26) % 26;if (w 0) w 26;w --;if (d) ans (w A); else ans (w a);}cout ans; return 0;T 2 T2 T2 国 王 游 戏 国王游戏 国王游戏 恰逢H国国庆国王邀请n位大臣来玩一个有奖游戏。首先他让每个大臣在左、右手上面分别写下一个整数国王自己也在左、右手上各写一个整数。然后让这n位大臣排成一排国王站在队伍的最前面。排好队后所有的大臣都会获得国王奖赏的若干金币每位大臣获得的金币数分别是排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数然后向下取整得到的结果。 国王不希望某一个大臣获得特别多的奖赏所以他想请你帮他重新安排一下队伍的顺序使得获得奖赏最多的大臣所获奖赏尽可能的少。注意国王的位置始终在队伍的最前面。 Input 第一行包含一个整数n表示大臣的人数。 第二行包含两个整数a和b之间用一个空格隔开分别表示国王左手和右手上的整数。 接下来n行每行包含两个整数a和b之间用一个空格隔开分别表示每个大臣左手和右手上的整数。 Output 输出只有一行包含一个整数表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。 Sample Input 3 1 1 2 3 7 4 4 6 Sample Output 2 【输入输出样例说明】 按1、2、3号大臣这样排列队伍获得奖赏最多的大臣所获得金币数为2 按1、3、2这样排列队伍获得奖赏最多的大臣所获得金币数为2 按2、1、3这样排列队伍获得奖赏最多的大臣所获得金币数为2 按2、3、1这样排列队伍获得奖赏最多的大臣所获得金币数为9 按3、1、2这样排列队伍获得奖赏最多的大臣所获得金币数为2 按3、2、1这样排列队伍获得奖赏最多的大臣所获得金币数为9。 因此奖赏最多的大臣最少获得2个金币答案输出2。 【数据说明】 对于20%的数据有1≤ n≤ 100 a、b 8 对于40%的数据有1≤ n≤200 a、b 8 对于60%的数据有1≤ n≤100 对于60%的数据保证答案不超过10^9 对于100%的数据有1 ≤ n ≤1,0000 a、b 10000。 考场乍一看可做性极高啊之前在某谷上做过的。这题就是一个贪心加高精度啊可是毕竟做过太久了想不起来怎么贪心了于是企图考场手推可是推了半天也不明白怎么贪心。心态就崩了啊于是直接打都没打直接看第三题去了。 考后打开某谷深思熟虑一番成功理解了当年自己的想法。 我举一个简单的例子吧对于给定的 a 0 , a 1 , a 2 a_0~,a_1~,a_2~ a0 ,a1 ,a2 和 b 0 , b 1 , b 2 b_0~,b_1~,b_2~ b0 ,b1 ,b2 只有两种情况如下 第一种 a 0 a_0~ a0 | b 0 b_0~ b0 a 1 a_1~ a1 | b 1 b_1~ b1 a 2 a_2~ a2 | b 2 b_2~ b2 第二种 a 0 a_0~ a0 | b 0 b_0~ b0 a 2 a_2~ a2 | b 2 b_2~ b2 a 1 a_1~ a1 | b 1 b_1~ b1 那么我首先定义 k 1 a 0 / b 1 k1 a_0~/ b_1~ k1a0 /b1 k 2 a 0 ∗ a 1 / b 2 k2 a_0~ * a_1~/ b_2~ k2a0 ∗a1 /b2 k 3 a 0 / b 2 k3 a_0~/ b_2~ k3a0 /b2 k 4 a 0 ∗ a 2 / b 1 k4 a_0~ * a_2~/ b_1~ k4a0 ∗a2 /b1 那么对于 a n s 1 m a x ( k 1 , k 2 ) ans1 max(k1,k2) ans1max(k1,k2), a n s 2 m a x ( k 3 , k 4 ) ans2 max(k3,k4) ans2max(k3,k4) 那么首先很显然 k 4 k 1 k4 k1 k4k1 , k 2 k 3 k2 k3 k2k3 所以假设前者为更优解则有 a n s 1 a n s 2 ans1 ans2 ans1ans2 ,因此易得 k 4 k 2 k4 k2 k4k2 即 a 0 ∗ a 1 / b 2 a 0 ∗ a 2 / b 1 a_0~ * a_1~/ b_2~ a_0~ * a_2~/ b_1~ a0 ∗a1 /b2 a0 ∗a2 /b1 ,解得 a 1 ∗ b 1 a 2 ∗ b 2 a_1~ *b_1~ a_2~ * b_2~ a1 ∗b1 a2 ∗b2 因此大功告成以 a i ∗ b i a_i~ * b_i~ ai ∗bi 为关键字排序然后插入高精度即可。 AC Code #include cstdio
#include algorithm
#include cstring
using namespace std;
struct Edge{int a;int b;int ab;
} f[10100];
int anslen1,anslen2,n,ans[20000],c[5],d[20000],l1,l2,anss[20000],m,xx;
bool cmp(Edge x,Edge y)
{return x.ab y.ab;
}
void time(int x)
{int i 0;memset(c,0,sizeof(c));while (x 0){i ;c[i] x % 10;x / 10;}int l1 i;for (int i 1; i l2; i ){d[i] ans[i];}memset(ans,0,sizeof(ans));for (int i 1; i l1; i ){for (int j 1; j l2; j ){ans[i j - 1] (c[i] * d[j]);ans[i j] (ans[i j - 1] / 10);ans[i j - 1] % 10;}}int w l1 l2;while (w 0 ans[w] 0) w --;l2 w;
}
void div(int x)
{int w 0;int j 0;for (int i l2; i 1; i --){j ;w w * 10 ans[i];anss[j] w / x;w % x;}int k 1;while (anss[k] 0 k l2) k ;if (k 1 anss[k] 0) k 0;anslen1 k;anslen2 j;
}
int main()
{scanf(%d,n);for (int i 0; i n; i ){scanf(%d%d,f[i].a,f[i].b);f[i].ab f[i].a * f[i].b;}int i 0;while (f[0].a 0){i ;ans[i] f[0].a % 10;f[0].a / 10;}l2 i;sort(f 1,f 1 n,cmp);for (int i 1; i n - 1; i ){time(f[i].a);}div(f[n].b);bool p false;for (int i anslen1; i anslen2; i ){if (anss[i] ! 0) {p true;break;}}if (p){for (int i anslen1; i anslen2; i ){printf(%d,anss[i]);}} else printf(1);return 0;
}很久前的code了格式真的丑见谅。 T 3 T3 T3 开 车 旅 行 开车旅行 开车旅行 Sample Input1 4 2 3 1 4 3 4 1 3 2 3 3 3 4 3
Sample Output1 1 1 1 2 0 0 0 0 0
【输入输出样例 1 说明】 各个城市的海拔高度以及两个城市间的距离如上图所示。 如果从城市 1 出发可以到达的城市为 2,3,4这几个城市与城市 1 的距离分别为 1,1,2 但是由于城市 3 的海拔高度低于城市 2所以我们认为城市 3 离城市 1 最近城市 2 离城市 1 第二近所以小 A 会走到城市 2。到达城市 2 后前面可以到达的城市为 3,4这两个城 市与城市 2 的距离分别为 2,1所以城市 4 离城市 2 最近因此小 B 会走到城市 4。到达城 市 4 后前面已没有可到达的城市所以旅行结束。 如果从城市 2 出发可以到达的城市为 3,4这两个城市与城市 2 的距离分别为 2,1由 于城市 3 离城市 2 第二近所以小 A 会走到城市 3。到达城市 3 后前面尚未旅行的城市为 4所以城市 4 离城市 3 最近但是如果要到达城市 4则总路程为 2353所以小 B 会 直接在城市 3 结束旅行。 如果从城市 3 出发可以到达的城市为 4由于没有离城市 3 第二近的城市因此旅行 还未开始就结束了。 如果从城市 4 出发没有可以到达的城市因此旅行还未开始就结束了。
Sample Input2 10 4 5 6 1 2 3 7 8 9 10 7 10 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 7
Sample Output2 2 3 2 2 4 2 1 2 4 5 1 5 1 2 1 2 0 0 0 0 0
【输入输出样例 2 说明】
当 X7 时 如果从城市 1 出发则路线为 1 - 2 - 3 - 8 - 9小 A 走的距离为 123小 B 走的 距离为 112。 在城市 1 时距离小 A 最近的城市是 2 和 6但是城市 2 的海拔更高视 为与城市 1 第二近的城市所以小 A 最终选择城市 2走到 9 后小 A 只有城市 10 可以走 没有第 2 选择可以选所以没法做出选择结束旅行 如果从城市 2 出发则路线为 2 - 6 - 7 小 A 和小 B 走的距离分别为 24。 如果从城市 3 出发则路线为 3 - 8 - 9小 A 和小 B 走的距离分别为 21。 如果从城市 4 出发则路线为 4 - 6 - 7小 A 和小 B 走的距离分别为 24。 如果从城市 5 出发则路线为 5 - 7 - 8 小 A 和小 B 走的距离分别为 51。 如果从城市 6 出发则路线为 6 - 8 - 9小 A 和小 B 走的距离分别为 51。 如果从城市 7 出发则路线为 7 - 9 - 10小 A 和小 B 走的距离分别为 21。 如果从城市 8 出发则路线为 8 - 10小 A 和小 B 走的距离分别为 20。 如果从城市 9 出发则路线为 9小 A 和小 B 走的距离分别为 00旅行一开始就结 束了。 如果从城市 10 出发则路线为 10小 A 和小 B 走的距离分别为 00。 从城市 2 或者城市 4 出发小 A 行驶的路程总数与小 B 行驶的路程总数的比值都最小 但是城市 2 的海拔更高所以输出第一行为 2。 对于这种题目考场打了个暴力理论上是可以得三十分的不知为何仅得十分。 考后认真理解了一番题解思路是倍增。思路还是挺暴力的。
设 g [ i ] [ j ] g[i][j] g[i][j]表示的意思为从 i i i这个点出发小A与小B各走 2 j 2^j 2j次所到的点。 d i s a [ i ] [ j ] disa[i][j] disa[i][j]表示的意思为小A从 i i i走 2 j 2^j 2j步所走过的距离。 d i s b [ i ] [ j ] disb[i][j] disb[i][j]同理。 至于转移是倍增最基础的转移只不过转移前的预处理有点麻烦因为题目有只能向东的这个限制条件具体见code。 #include cstdio
#include algorithm
#include cmath
using namespace std;const int maxn 1e5 10;
struct Node{int h,id,l,r;
} f[maxn];
int n,x,s,m,q[maxn],a[maxn],b[maxn],disa[maxn][25],disb[maxn][25],g[maxn][25],ans,suma,sumb;
double minn 2147483647;int read()
{int x 0,w 1;char ch getchar();while (ch 0 || ch 9) {if (ch -) w -1;ch getchar();}while (ch 0 ch 9) {x x * 10 ch - 0;ch getchar();}return x * w;
}bool cmp(Node a,Node b) {return a.h b.h;}bool l_(int w,int l,int r)
{if (!r) return 1;if (!l) return 0;return f[w].h - f[l].h f[r].h - f[w].h;
}int par(int l,int r,int w)
{if (!r) return f[l].id; if (!l) return f[r].id;if (f[w].h - f[l].h f[r].h - f[w].h) return f[l].id; else return f[r].id;
}void make()
{for (int j 1; j 19; j )for (int i 1; i n; i ){g[i][j] g[g[i][j - 1]][j - 1];disa[i][j] disa[i][j - 1] disa[g[i][j - 1]][j - 1];disb[i][j] disb[i][j - 1] disb[g[i][j - 1]][j - 1];}
}void query(int s,int x)
{for (int i 19; i 0; i --)if (g[s][i] suma sumb disa[s][i] disb[s][i] x){suma disa[s][i];sumb disb[s][i];s g[s][i];}if (a[s] suma sumb disa[s][0] x) suma disa[s][0];
}int main()
{n read();for (int i 1; i n; i ) f[i].h read();for (int i 1; i n; i ) f[i].id i;sort(f 1,f 1 n,cmp);for (int i 1; i n; i ) q[f[i].id] i,f[i].l i - 1,f[i].r i 1;f[1].l f[n].r 0;for (int i 1; i n; i ){int w q[i],L f[w].l,R f[w].r;if (l_(w,L,R)) {b[i] f[L].id; a[i] par(f[L].l,R,w);} else {b[i] f[R].id; a[i] par(L,f[R].r,w);}if (L) f[L].r R;if (R) f[R].l L; }for (int i 1; i n; i ){g[i][0] b[a[i]];disa[i][0] abs(f[q[i]].h - f[q[a[i]]].h);disb[i][0] abs(f[q[a[i]]].h - f[q[g[i][0]]].h);}make();x read();for (int i 1; i n; i ){suma sumb 0;query(i,x);if (sumb 1.00 * suma / sumb minn) minn 1.00 * suma / sumb,ans i;}printf(%d\n,ans);m read();while (m --){s read(),x read();suma sumb 0;query(s,x);printf(%d %d\n,suma,sumb);}return 0;
}得分 100 0 10 100 0 10 100010
Ps.新手入门不得不说打一篇考后总结真的好累啊不过也收获匪浅。
