【D1T1vigenerepassword】

P1778vigenerepassword

标签：

描写叙述

16世纪法国外交家Blaise de Vigenère设计了一种多表password加密算法——Vigenèrepassword。Vigenèrepassword的加密解密算法简单易用，且破译难度比較高，曾在美国南北战争中为南军所广泛使用。 

在password学中，我们称须要加密的信息为明文。用M表示；称加密后的信息为密文，用C表示；而密钥是一种參数。是将明文转换为密文或将密文转换为明文的算法中输入的数据。记为k。 在Vigenèrepassword中。密钥k是一个字母串。k=k1k2…kn。当明文M=m1m2…mn时。得到的密文C=c1c2…cn，当中ci=(mi-'A'+ki-'A')mod26+'A'。运算?的规则例如以下表所看到的：

Vigenere加密在操作时须要注意： 

1. ?

运算忽略參与运算的字母的大写和小写。并保持字母在明文M中的大写和小写形式； 

2. 当明文M的长度大于密钥k的长度时，将密钥k反复使用。

格式

输入格式

输入共2行。 

第一行为一个字符串，表示密钥k。长度不超过100，当中仅包括大写和小写字母。第二行为一个字符串，表示经加密后的密文，长度不超过1000。当中仅包括大写和小写字母。

输出格式

输出共1行。一个字符串。表示输入密钥和密文所相应的明文。

例子1

例子输入1

CompleteVictoryYvqgpxaimmklongnzfwpvxmniytm

例子输出1

Wherethereisawillthereisaway

限制

每一个測试点1s

提示

对于100%的数据，输入的密钥的长度不超过100，输入的密文的长度不超过1000，且都仅包括英文字母。

来源

Noip2012提高组复赛D

【分析】这难道不是纯模拟？不要讽刺我P的代码啦啦啦~又臭又长。。。

【代码】

var  k,c:ansistring;  kk:char;  p,i,temp,now,l:longint;  map:array['A'..'Z','A'..'Z'] of char;  pq:longint;  q1,q2,j:char;begin  readln(k);  k:=upcase(k);  l:=length(k);  readln(c);  now:=1;  for q1:='A' to 'Z' do    begin      map[q1,'A']:=q1;      pq:=ord(q1);      for q2:='B' to 'Z' do        begin          pq:=pq+1;          if pq>90 then pq:=65;          map[q1,q2]:=chr(pq);        end;    end;  for i:=1 to length(c) do    begin      kk:=k[now];      for j:='A' to 'Z' do        if map[j,kk]=upcase(c[i]) then          begin            if c[i] in ['A'..'Z'] then write(j)            else write(chr(ord(j)+32));          end;      inc(now);      if now>l then now:=1;    end;end.

【D1T2国王游戏】

P1779国王游戏

标签：

描写叙述

恰逢H国国庆，国王邀请n位大臣来玩一个有奖游戏。

首先，他让每一个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。

然后，让这n位大臣排成一排。国王站在队伍的最前面。

排好队后，全部的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数各自是：排在该大臣前面的全部人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。 

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他又一次安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

格式

输入格式

第一行包括一个整数n。表示大臣的人数。 

第二行包括两个整数a和b，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来n行。每行包括两个整数a和b。之间用一个空格隔开，分别表示每一个大臣左手和右手上的整数。

输出格式

输出仅仅有一行，包括一个整数。表示又一次排列后的队伍中获奖赏最多的大臣所获得的金币数。

例子1

例子输入1

3 1 1 2 3 7 4 4 6

例子输出1

2

限制

每一个測试点1s

提示

对于20%的数据，有1≤ n≤ 10，0 < a、b < 8。 

对于40%的数据，有1≤ n≤20，0 < a、b < 8； 

对于60%的数据，有1≤ n≤100。 

对于60%的数据。保证答案不超过10^9； 

对于100%的数据，有1 ≤ n ≤1,000。0 < a、b < 10000。

来源

Noip2012提高组复赛Day1T2

【分析】曾经好像不会证明，然后看题解的。如今又一次做一遍，感觉真是水啊。考虑最后一个大臣，显然他非常可能是金币最多的人。

我们要让他的金币尽量的少。之前的大臣左手的数肯定会乘起来，所以我们要使S/A/B尽量的大。（设S是左手全部数的乘积），即让A*B尽量的大。选完最后一个后，我们把他踢掉，然后再找一个最后的大臣。如此往复。相当于就是对A*B排序。

-----当然我的证明不是非常严谨啦。

【代码】曾经不注重长度的后果。。

ar  ans,c,d,e,f:array[0..10000] of longint;  a,b:array[0..1000] of longint;  ansk,ck,ek,fk,x,i,j,n,t,k:longint;function da:boolean;var  i:longint;begin  if ek>ansk then exit(true);  if ansk>ek then exit(false);  for i:=ansk downto 1 do    if ans[i]>e[i] then exit(false)                   else exit(true);end;begin  readln(n);  readln(a[0],b[0]);  for i:=1 to n do    readln(a[i],b[i]);  for i:=1 to n-1 do    for j:=i+1 to n do      if a[i]*b[i]>a[j]*b[j] then        begin          t:=a[i];          a[i]:=a[j];          a[j]:=t;          t:=b[i];          b[i]:=b[j];          b[j]:=t;        end;  ck:=1;  c[ck]:=1;  ansk:=0;  ans[ansk]:=0;  for i:=1 to n do    begin      fk:=0;      while a[i-1]>0 do        begin          inc(fk);          f[fk]:=a[i-1] mod 10;          a[i-1]:=a[i-1] div 10;        end;      for j:=1 to ck do        begin          d[j]:=c[j];        end;      fillchar(c,sizeof(c),0);      for j:=1 to ck do        for k:=1 to fk do          c[j+k-1]:=c[j+k-1]+d[j]*f[k];      for j:=1 to ck+fk-1 do        if c[j]>9 then          begin            c[j+1]:=c[j+1]+c[j] div 10;            c[j]:=c[j] mod 10;          end;      ck:=ck+fk-1;      while c[ck+1]>0 do        begin          inc(ck);          c[ck+1]:=c[ck+1]+c[ck] div 10;          c[ck]:=c[ck] mod 10;        end;      x:=0;      ek:=ck;      for j:=ck downto 1 do          begin             e[j]:=(x*10+c[j]) div b[i];             x:=(x*10+c[j]) mod b[i];          end;      while (e[ek]=0) and (ek>1) do        dec(ek);      if da then        begin          ansk:=ek;          for j:=1 to ansk do            ans[j]:=e[j];        end;    end;  for i:=ansk downto 1 do    write(ans[i]);end.

【D1T3开车旅行】

P1780开车旅行

标签：

描写叙述

小A和小B决定利用假期外出旅行。他们将想去的城市从1到N编号。且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不同样，记城市i 的海拔高度为Hi，城市i 和城市j 之间的距离d[i,j]恰好是这两个城市海拔高度之差的绝对值，即d[i,j] = |Hi - Hj|。

旅行过程中。小A和小B轮流开车。第一天小A开车，之后每天轮换一次。他们计划选择一个城市S作为起点，一直向东行驶。而且最多行驶X公里就结束旅行。

小A和小B的驾驶风格不同。小B总是沿着前进方向选择一个近期的城市作为目的地，而小A总是沿着前进方向选择第二近的城市作为目的地（注意：本题中假设当前城市到两个城市的距离同样，则觉得离海拔低的那个城市更近）。

假设当中不论什么一人无法依照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出X公里。他们就会结束旅行。 

在启程之前，小A想知道两个问题： 

1．对于一个给定的X=X0。从哪一个城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值最小（假设小B的行驶路程为0，此时的比值可视为无穷大，且两个无穷大视为相等）。假设从多个城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值都最小。则输出海拔最高的那个城市。 

2. 对随意给定的X=Xi 和出发城市Si，小A开车行驶的路程总数以及小B行驶的路程总数。

格式

输入格式

第一行包括一个整数N。表示城市的数目。

 

第二行有N个整数。每两个整数之间用一个空格隔开，依次表示城市1到城市N的海拔高度，即H1。H2，……。Hn。且每一个Hi 都是不同的。

 

第三行包括一个整数X0。 

第四行为一个整数M。表示给定M组Si和Xi。 

接下来的M行。每行包括2个整数Si 和Xi。表示从城市Si 出发，最多行驶Xi 公里。

输出格式

输出共M+1行。 

第一行包括一个整数S0，表示对于给定的X0。从编号为S0的城市出发，小A开车行驶

的路程总数与小B行驶的路程总数的比值最小。 

接下来的M行，每行包括2个整数，之间用一个空格隔开，依次表示在给定的Si 和Xi 下小A行驶的里程总数和小B行驶的里程总数。

例子1

例子输入1

4 2 3 1 4 3 4 1 3 2 3 3 3 4 3

例子输出1

1 1 1 2 0 0 0 0 0

例子2

例子输入2

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

例子输出2

2 3 2 2 4 2 1 2 4 5 1 5 1 2 1 2 0 0 0 0 0

限制

每一个測试点1s

提示

对于30%的数据，有1≤N≤20。1≤M≤20； 

对于40%的数据，有1≤N≤100。1≤M≤100。 

对于50%的数据，有1≤N≤100。1≤M≤1,000。

对于70%的数据，有1≤N≤1,000，1≤M≤10,000。 

对于100%的数据，有1≤N≤100,000，1≤M≤10,000，-1,000,000,000≤Hi≤1,000,000,000，0≤X0≤1,000,000,000，1≤Si≤N。0≤Xi≤1,000,000,000，数据保证Hi 互不同样。

来源

Noip2012提高组复赛Day1T3

【分析】话说这题目真TM的拗口。我開始把A和B的操作搞反了233。

首先是拼预处理。

怎样高速预处理一个点之后第一个和第二个比他大的点。

曾经我曾和SKYDEC做过讨论的。。

之后随便来点倍增即可了。我想法太天真，于是写了两端倍增。

先倍增预处理出2^j后A和B分别到哪里（显然仅仅要一个数组，由于奇偶性决定A还是B），再分别预处理A和B走了多少的距离。

第一问就是O（N）枚举，找到一个最优的。

第二问就直接求解了。

为了避免溢出。各种细节。

调的我都快吐血了。

【代码】

#include
     
      #include
      
       #include
       
        #include
        
         #define N 100005#define INF 2000000000000llusing namespace std;typedef long long LL;int pos[N],H[N],first[N],second[N],w[N][18];LL A[N][18],B[N][18],disA,disB,S;int n,i,Q,X,ans,now;double temp,Div;const double eps=1e-10;struct MM{  int x,id,L,R;  friend inline int operator <(const MM &A,const MM &B){return A.x
         
          0) w[i][j]=w[w[i][j-1]][j-1];}void Init_dis(){  for (int i=1;i<=n;i++)   {    if (w[i][0]>0) A[i][1]=abs(H[i]-H[w[i][0]]);    if (w[i][0]>0&&w[i][1]>0) B[i][1]=abs(H[w[i][0]]-H[w[i][1]]);  }  for (int j=2;j<=17;j++)    for (int i=1;i<=n;i++)    {      A[i][j]=A[i][j-1];      if (w[i][j-1]>0) A[i][j]+=A[w[i][j-1]][j-1];      B[i][j]=B[i][j-1];      if (w[i][j-1]>0) B[i][j]+=B[w[i][j-1]][j-1];    }}inline void find(int start,LL cnt){  disA=disB=0;  for (int i=17;i;i--)    if (w[start][i]>0&&A[start][i]+B[start][i]<=cnt)    {      cnt-=A[start][i];cnt-=B[start][i];      disA+=A[start][i];disB+=B[start][i];      start=w[start][i];    }  if (second[start]>0&&abs(H[second[start]]-H[start])<=cnt)    disA+=abs(H[second[start]]-H[start]);}int main(){  scanf("%d",&n);  for (i=1;i<=n;i++)      scanf("%d",&a[i].x),H[i]=a[i].x,a[i].id=i;  Init_order();  Init_where();  Init_dis();  scanf("%I64d",&S);ans=0;Div=INF+1;  for (i=1;i<=n;i++)  {    find(i,S);    if (disB==0) temp=INF;else temp=disA*1./disB;    if (fabs(temp-Div)<=eps) {if (H[i]>H[ans]) ans=i;}    else if (temp
         
        
       
      
     

【D2T1同余方程】

P1781同余方程

标签：

描写叙述

求关于x的同余方程ax ≡ 1 (mod b)的最小正整数解。

格式

输入格式

输入仅仅有一行。包括两个正整数a, b，用一个空格隔开。

输出格式

输出仅仅有一行，包括一个正整数x0，即最小正整数解。

输入数据保证一定有解。

例子1

例子输入1

3 10

例子输出1

7

限制

每一个測试点1s

提示

对于40%的数据，2 ≤b≤ 1,000； 

对于60%的数据，2 ≤b≤ 50,000,000。 

对于100%的数据，2 ≤a, b≤ 2,000,000,000。

来源

Noip2012提高组复赛Day2T1

【分析】简单数论

【代码】

varx,y,a,b,d:int64;procedure gcd(a,b:int64);var  t:int64;begin  if (a mod b = 0) then    begin      x:=0;y:=1;    end  else    begin      gcd(b,a mod b);      t:=x;      x:=y;      y:=t-(a div b)*y;    end;end;begin  readln(a,b);  d:=b;  gcd(a,b);  writeln((x mod d+d) mod d);end.

【D2T2】

P1782借教室

标签：

描写叙述

在大学期间。常常须要租借教室。

大到院系举办活动。小到学习小组自习讨论，都须要向学校申请借教室。

教室的大小功能不同。借教室人的身份不同。借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决问题。我们须要处理接下来n天的借教室信息，当中第i天学校有ri个教室可供租借。共同拥有m份订单。每份订单用三个正整数描写叙述。分别为dj,sj,tj，表示某租借者须要从第sj天到第tj天租借教室（包含第sj天和第tj天）。每天须要租借dj个教室。 

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们仅仅须要每天提供dj个教室。而它们详细是哪些教室，每天是否是同样的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要依照订单的先后顺序依次为每份订单分配教室。

假设在分配的过程中遇到一份订单无法全然满足，则须要停止教室的分配。通知当前申请人改动订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。

如今我们须要知道，是否会有订单无法全然满足。假设有。须要通知哪一个申请人改动订单。

格式

输入格式

第一行包括两个正整数n,m，表示天数和订单的数量。 

第二行包括n个正整数，当中第i个数为ri。表示第i天可用于租借的教室数量。

 

接下来有m行。每行包括三个正整数dj,sj,tj，表示租借的数量，租借開始、结束分别在第几天。

 

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1開始的整数编号。

输出格式

假设全部订单均可满足。则输出仅仅有一行，包括一个整数0。否则（订单无法全然满足）输出两行，第一行输出一个负整数-1。第二行输出须要改动订单的申请人编号。

例子1

例子输入1

4 3 2 5 4 3 2 1 3 3 2 4 4 2 4

例子输出1

-12

限制

每一个測试点1s

提示

对于10%的数据，有1≤ n,m≤ 10。 

对于30%的数据，有1≤ n,m≤1000； 

对于70%的数据，有1≤ n,m≤ 10^5。 

对于100%的数据，有1≤n,m≤10^6,0≤ri,dj≤10^9,1≤sj≤tj≤n。

来源

Noip2012提高组复赛Day2T2

【分析】一眼题。可是线段树会T。

（这个用zkw貌似非常麻烦？@syc1999）事实上二分加判定即可了233。

不想用凌神的标号法了。直接memset水过。

【代码】

#include
     
      #include
      
       #define N 1000005using namespace std;int P[N],a[N],num[N],L[N],R[N],n,m,i,ans;inline int Read(){  char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar());  int x=0;for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';  return x;}inline int check(int D){  memset(P,0,sizeof(P));  for (int i=1;i<=D;i++)    P[L[i]]-=num[i],P[R[i]+1]+=num[i];  for (int i=1;i<=n;i++)     if ((P[i]+=P[i-1])+a[i]<0) return 0;  return 1;}inline int erfen(){  int l=1,r=m+1;  while (l!=r)  {    int mid=(l+r)>>1;    if (check(mid)) l=mid+1;else r=mid;  }  if (r==m+1) return 0;return r;}int main(){  n=Read();m=Read();  for (i=1;i<=n;i++) a[i]=Read();  for (i=1;i<=m;i++)    num[i]=Read(),L[i]=Read(),R[i]=Read();  ans=erfen();  if (ans) printf("-1\n%d",ans);else printf("0");  return 0;}
      
     

【D2T3疫情控制】

P1783疫情控制

标签：

描写叙述

H国有n个城市，这n个城市用n-1条双向道路相互连通构成一棵树，1号城市是首都，也是树中的根节点。 

H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点。边境城市也能够建立检查点。但特别要注意的是，首都是不能建立检查点的。 

如今。在H国的一些城市中已经驻扎有军队，且一个城市能够驻扎多个军队。

一支军队能够在有道路连接的城市间移动。并在除首都以外的随意一个城市建立检查点，且仅仅能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到还有一个城市所须要的时间等于道路的长度（单位：小时）。 

请问最少须要多少个小时才干控制疫情。注意：不同的军队能够同一时候移动。

格式

输入格式

第一行一个整数n。表示城市个数。 

接下来的n-1行，每行3个整数。u、v、w，每两个整数之间用一个空格隔开，表示从城市u到城市v有一条长为w的道路。数据保证输入的是一棵树。且根节点编号为1。 

接下来一行一个整数m，表示军队个数。 

接下来一行m个整数，每两个整数之间用一个空格隔开。分别表示这m个军队所驻扎的城市的编号。

输出格式

共一行，包括一个整数，表示控制疫情所须要的最少时间。

假设无法控制疫情则输出-1。

例子1

例子输入1

4 1 2 1 1 3 2 3 4 3 2 2 2

例子输出1

3

限制

每一个測试点2s

提示

保证军队不会驻扎在首都。

 

对于20%的数据，2≤ n≤ 10； 

对于40%的数据，2 ≤n≤50。0<w <10^5； 

对于60%的数据。2 ≤ n≤1000，0<w <10^6； 

对于80%的数据，2 ≤ n≤10,000； 

对于100%的数据，2≤m≤n≤50,000。0<w <10^9。

来源

Noip2012提高组复赛Day2T3

【过程】这道题调到吐血。

前几天盯上了此题。開始自己的方法连官方数据都没过。于是開始借鉴别人的想法。网上的想法大同小异。后来我越改越混乱。越改越没有主见。

好不easy过了官方数据，VJ上WA了5个点后弃疗。

一直放在那里，今天才发现的=自己细致想了想方法。应该完美了。開始改。

结果一阵猛调还是和前几天的一样。

開始和网上的拍。

连续找了2个代码（都是百度搜索前几位）都是秒拍出错，并且= =出错的是他们。。

。于是我找来了哲教的代码。

又是秒拍？定睛一看，哲教。呵呵。他表示无压力改好给我。

过了一会了拍出了错误。激动ing：哲教，你逗我？

他表示：我知道哪里错了，但不屑和你这仅仅蒟蒻说。。

。

于是我又開始漫长的找其它代码对拍。总算找到一个代码和我飞起。。。于是立马调大数据，5分钟后。。

。

2333。出来了！果然是我错了！

你瞧为什么错了？在调用倍增的时候语句打反了。

嘻嘻。官方数据，你是有多弱啊2333。。

。

【思路】最后还是自己想的2333.

二分+判定是肯定要的。

贪心的想，把全部军队移到1的全部儿子那里。

我们称1的儿子为“目标点”。

先倍增预处理。求出每一个军队能否跑到根节点。

假设不能。那么算出他向上跑到哪里。在那儿打个标记。

（能的等会再说）

然后dfs一遍。

假设一个点的全部子节点都打上了标记，那么它也打上标记。

这样，我们就知道一些目标点已经不须要军队过去（就是已经被打上了标记的）。

之后就是贪心思想了，扫描每个能够到根的军队。

假设它不能从根回到自己经过的目标点并且那个目标点须要军队驻扎的话，就把军队停在那里。

为什么是停在那里呢？证明见下。

否则就把这仅仅军队增加数组p，其值为它到根节点后剩下的时间。

把须要军队的目标点塞入数组q，其值是它与1的距离。

然后对于p和q，先排序，再从小往大匹配。

对于当前的军队，先推断它走出来的目标点是否已经有军队了。

假设没有的话。显然要他去，由于他一定能去，并且眼下他最没用。

否则的话。就找一个距离最短的目标点过去（当然也可能一个都过不去喽）。

【证明】设军队x的经过的目标点是a，且他到根后回不到x。设他去了目标点b，设到a的军队是y。

显然我们能够让y去b。他一定能去。

【代码】

#include
     
      #include
      
       #define INF 500000000000005ll#define N 50005using namespace std;typedef long long LL;struct adj{int go,next,s;}a[N*2];struct arr{  int x;LL y;  friend inline int operator < (const arr &A,const arr &B){return A.y
       
        =0;i--)    if (f[k][i]&&dis[k][i]<=T)      T-=dis[k][i],k=f[k][i];  return k;}void find(int k){  if (can[k]==Num) return;int flag=0;  for (int i=end[k];i;i=a[i].next)  {    int go=a[i].go;if (go==f[k][0]) continue;    find(go);if (can[go]!=Num) return;flag=1;  }  if (flag) can[k]=Num;}inline int check(LL Time){  Num++;int P=0,Q=0;p[0].y=INF;  for (int i=1;i<=m;i++)    if (Time
        
         Q) return 1;    if (p[i].y
         
          Q;}LL erfen(LL l,LL r){  if (l==r) return l;  LL mid=(l+r)>>1ll;  if (check(mid))     return erfen(l,mid);  return erfen(mid+1,r);}int main(){  scanf("%d",&n);  for (i=1;i
         
        
       
      
     

版权声明：本文博主原创文章，博客，未经同意不得转载。