【D1T1vigenere密码】

【分析】这难道不是纯模拟？不要讽刺我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;
{function same(ch1,ch2:char):boolean;
begin
  if ((ch1 in [‘A‘..‘Z‘]) and (ch2 in [‘A‘..‘Z‘])) or
  ((ch1 in [‘a‘..‘z‘]) and (ch2 in [‘a‘..‘z‘])) then exit(true);
  exit(false);
end;
function change:char;
var
  ch:char;
begin
  ch:=chr(p);
  if same(ch,c[i]) then
    change:=ch
  else begin
    if ch in [‘A‘..‘Z‘] then
      change:=chr(p+32)
    else change:=chr(p-32);
  end;
end; }

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国王游戏】

【分析】以前好像不会证明，然后看题解的。现在重新做一遍，感觉真是水啊。考虑最后一个大臣，显然他很可能是金币最多的人。我们要让他的金币尽量的少。之前的大臣左手的数肯定会乘起来，所以我们要使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开车旅行】

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

首先是拼预处理。如何快速预处理一个点之后第一个和第二个比他大的点。

以前我曾和SKYDEC做过讨论的，详见此。

之后随便来点倍增就行了。我想法太天真，于是写了两端倍增。先倍增预处理出2^j后A和B分别到哪里（显然只要一个数组，因为奇偶性决定A还是B），再分别预处理A和B走了多少的距离。

第一问就是O（N）枚举，找到一个最优的。第二问就直接求解了。

为了避免溢出，各种细节。调的我都快吐血了。

【代码】

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define N 100005
#define INF 2000000000000ll
using 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<B.x;}
}a[N];
inline int work(int P,int Q)
{
  if (P==-1&&Q==-1) return -1;
  if (P==-1) return a[Q].id;if (Q==-1) return a[P].id;
  if ((LL)a[now].x-(LL)a[P].x<=(LL)a[Q].x-(LL)a[now].x) return a[P].id;return a[Q].id;
}
inline void Init_order()
{
  sort(a+1,a+n+1);
  for (int i=1;i<=n;i++) pos[a[i].id]=i,a[i].R=i+1,a[i].L=i-1;
  a[1].L=a[n].R=-1;
  for (int i=1;i<=n;i++)
  {
    now=pos[i];int Left=a[now].L,Right=a[now].R;
    first[i]=work(Left,Right);
    if (first[i]==-1) second[i]=-1;
    else if (a[Left].id==first[i]) second[i]=work(a[Left].L,Right);
                              else second[i]=work(Left,a[Right].R);
    a[Left].R=Right;a[Right].L=Left;
  }
}
void Init_where()
{
  for (int i=1;i<=n;i++) w[i][0]=second[i],w[i][1]=first[w[i][0]];
  for (int j=2;j<=17;j++)
    for (int i=1;i<=n;i++)
      if (w[i][j-1]>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<Div) Div=temp,ans=i;
  }
  printf("%d\n",ans);scanf("%d",&Q);
  while (Q--)
  {
    scanf("%d%I64d",&X,&S);
    find(X,S);printf("%I64d %I64d\n",disA,disB);
  }
  return 0;
}

【D2T1同余方程】

【分析】简单数论

【代码】

var
x,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】

【分析】一眼题。但是线段树会T。（这个用zkw貌似很麻烦？@syc1999）其实二分加判定就行了233。

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

【代码】

#include<cstdio>
#include<cstring>
#define N 1000005
using 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疫情控制】

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

前几天盯上了此题。开始自己的方法连官方数据都没过。于是开始借鉴别人的想法。网上的想法大同小异，后来我越改越混乱，越改越没有主见。好不容易过了官方数据，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<cstdio>
#include<algorithm>
#define INF 500000000000005ll
#define N 50005
using 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<B.y;}
}p[N],q[N];
int f[N][17],belong[N],can[N],use[N],minn[N],node[N],army[N],end[N];
LL dis[N][17],deep[N],sum;int n,i,x,y,z,Num,need,m,cnt;
inline void add(int u,int v,int w){a[++cnt].go=v;a[cnt].next=end[u];a[cnt].s=w;end[u]=cnt;}
void dfs(int k,int who)
{
  for (int i=end[k];i;i=a[i].next)
  {
    int go=a[i].go;if (go==f[k][0]) continue;
    if (k==1) who=go;belong[go]=who;
    f[go][0]=k;dis[go][0]=(LL)a[i].s;
    deep[go]=deep[k]+(LL)a[i].s;dfs(go,who);
  }
}
inline void mul()
{
  for (int j=1;j<=16;j++)
    for (int i=1;i<=n;i++)
    {
      f[i][j]=f[f[i][j-1]][j-1];
      dis[i][j]=dis[i][j-1]+dis[f[i][j-1]][j-1];
    }
}
inline int calc(int k,LL T)
{
  for (int i=16;i>=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<deep[army[i]]) can[max(calc(army[i],Time),belong[army[i]])]=Num;
  for (int i=1;i<=need;i++)
    find(node[i]);
  for (int i=1;i<=m;i++)
  {
    int k=army[i];if (Time<deep[k]) continue;
    if (Time-deep[k]<dis[belong[k]][0]&&can[belong[k]]!=Num) {can[belong[k]]=Num;continue;}
    p[++P]=(arr){belong[k],Time-deep[k]};
  }
  sort(p+1,p+P+1);
  for (int i=1;i<=need;i++)
  {
     if (can[node[i]]==Num) continue;
     q[++Q]=(arr){node[i],dis[node[i]][0]};
     use[node[i]]=Num;
  }
  sort(q+1,q+Q+1);
  int j=1;
  for (int i=1;i<=P;i++)
  {
    if (use[p[i].x]==Num) {use[p[i].x]=0;continue;}
    for (;j<=Q&&use[q[j].x]!=Num;j++);if (j>Q) return 1;
    if (p[i].y<q[j].y) continue;use[q[j].x]=0;
  }
  for (;j<=Q&&use[q[j].x]!=Num;j++);
  return j>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<n;i++)
  {
    scanf("%d%d%d",&x,&y,&z);
    add(x,y,z);add(y,x,z);
    sum+=(LL)z;
    if (x==1) node[++need]=y;
    if (y==1) node[++need]=x;
  }
  scanf("%d",&m);if (m<need) {puts("-1");return 0;}
  for (i=1;i<=m;i++)
    scanf("%d",&army[i]);
  dfs(1,0);mul();
  printf("%I64d",erfen(0,sum));
  return 0;
}