【NOIp】NOIp2012

我会带着你远行 2023-08-17 16:49 85阅读 0赞

# NOIp 2012 #

### day 1 [T1 Vigenère 密码][T1 Vigen_re] ###

标签：模拟

主要是用了ASCII码，字母'A'的ASCII码是41H（0100 0001B），字母'a'的ASCII码是61H（0110 0001B），字母'A'与'a'的二进制后5位是相同的，所以无论是大写字母还是小写字母x，x &31（1 1111B）的值就是x在字母表里的顺序。

简单判一下边界就行了

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

**day 1 [T2 国王游戏][T2]**

标签：贪心，高精度

又是一波证明......

king: a0 b0

player1: a1 b1

player2: a2 b2

这种情况下，$ans\_1=max(a0/b1，a0\*a1/b2)$

king: a0 b0

player2: a2 b2

player1: a1 b1

$ans\_2=max(a0/b2，a0\*a2/b1)$

显然$a0\*a2/b1 > a0/b1$，$a0\*a2/b1 > a0/b1$

如果$ans\_1$<$ans\_2$可知$a0\*a2/b1$>$a0\*a1/b2$ => $a1\*b1<a2\*b2$

即$a1\*b1<a2\*b2$时，$ans\_1$<$ans\_2$

所以将$\{a\_i\}\*\{b\_i\}$较小的放在前面更优

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //
     2 //  main.cpp
     3 //  Luogu
     4 //
     5 //  Created by gengyf on 2019/7/10.
     6 //  Copyright © 2019 yifan Geng. All rights reserved.
     7 //
     8 
     9 #include <bits/stdc++.h>
    10 using namespace std;
    11 int sum[20010],now[20010],ans[20010],add[20010];
    12 int n;
    13 struct Node{
    14     int a,b;
    15     long long ab;
    16 }node[1010];
    17 void multi(int x){
    18     memset(add,0,sizeof(add));
    19     for(int i=1;i<=ans[0];i++){
    20         ans[i]*=x;
    21         add[i+1]+=ans[i]/10;
    22         ans[i]%=10;
    23     }
    24     for(int i=1;i<=ans[0]+4;i++){
    25         ans[i]+=add[i];
    26         if(ans[i]>=10){
    27             ans[i+1]+=ans[i]/10;
    28             ans[i]%=10;
    29         }
    30         if(ans[i]!=0){
    31             ans[0]=max(ans[0],i);
    32         }
    33     }
    34 }
    35 int divid(int x){
    36     memset(add,0,sizeof(add));
    37     int q=0;
    38     for(int i=ans[0];i>=1;i--){
    39         q*=10;
    40         q+=ans[i];
    41         add[i]=q/x;
    42         if(add[0]==0&&add[i]!=0){
    43             add[0]=i;
    44         }
    45         q%=x;
    46     }
    47     return 0;
    48 }
    49 bool compar(){
    50     if(sum[0]==add[0]){
    51         for(int i=add[0];i>=1;i--){
    52             if(add[i]>sum[i]) return 1;
    53             if(add[i]<sum[i]) return 0;
    54         }
    55     }
    56     if(add[0]>sum[0]) return 1;
    57     if(add[0]<sum[0]) return 0;
    58 }
    59 void cp(){
    60     memset(sum,0,sizeof(sum));
    61     for(int i=add[0];i>=0;i--){
    62         sum[i]=add[i];
    63     }
    64 }
    65 bool cmp(Node x,Node y){
    66     return x.ab<y.ab;
    67 }
    68 int main(){
    69     scanf("%d",&n);
    70     for(int i=0;i<=n;i++){
    71         scanf("%d%d",&node[i].a,&node[i].b);
    72         node[i].ab=node[i].a*node[i].b;
    73     }
    74     sort(node+1,node+1+n,cmp);
    75     ans[0]=1;ans[1]=1;
    76     for(int i=1;i<=n;i++){
    77         multi(node[i-1].a);
    78         divid(node[i].b);
    79         if(compar()){
    80             cp();
    81         }
    82     }
    83     for(int i=sum[0];i>=1;i--){
    84         printf("%d",sum[i]);
    85     }
    86     return 0;
    87 }

### day 1 [T3 开车旅行][T3] ###

标签：倍增，dp，STL，预处理

模拟开车过程，set预处理离城市第一近和第二近的，倍增优化

$g\[i\]\[j\]=g\[g\[i\]\[j-1\]\]\[j-1\]$

$f\[i\]\[j\]\[0\]=f\[i\]\[j-1\]\[0\]+f\[g\[i\]\[j-1\]\]\[j-1\]\[0\]$

$f\[i\]\[j\]\[1\]=f\[i\]\[j-1\]\[1\]+f\[g\[i\]\[j-1\]\]\[j-1\]\[1\]$

code(有注释吧)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 using namespace std;
      3 namespace gengyf{
      4 #define ll long long
      5   inline int read(){
      6     int x=0,f=1;char s=getchar();
      7     while(s<'0'||s>'9'){
         if(s=='-')f=-1;s=getchar();}
      8     while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
      9     return f*x;
     10   }
     11   const int maxn=100010;
     12   struct node{
     13     int num,h;
     14     bool operator < (const node a) const{
     15       return h<a.h;
     16     }
     17   }c[maxn];
     18   set<node>s;
     19   set<node>::iterator it;
     20   ll f[maxn][25][2];
     21   int nxt[maxn][2],g[maxn][25],dis[maxn][21];
     22   int n,x0,m;
     23   /*
     24    g[i][j]从i开始,两人轮流开2^j轮车后最后到达的位置
     25    f[i][j][0]从i开始,两人轮流开2^j轮车后小A走的距离
     26    f[i][j][1]从i开始,两人轮流开2^j轮车后小B走的距离
     27    nxt[i][0]离i第一近的城市编号
     28    nxt[i][1]离i第二近的城市编号
     29    dis[i][0]离i第一近的城市到i的距离
     30    dis[i][1]离i第二近的城市到i的距离
     31    */
     32   void update(node x,node y){
     33     if(!nxt[x.num][0]){
     34       nxt[x.num][0]=y.num;
     35       dis[x.num][0]=abs(x.h-y.h);
     36     }
     37     else if(dis[x.num][0]>abs(x.h-y.h)||(dis[x.num][0]==abs(x.h-y.h)&&y.h<c[nxt[x.num][0]].h)){
     38       nxt[x.num][1]=nxt[x.num][0];
     39       dis[x.num][1]=dis[x.num][0];
     40       nxt[x.num][0]=y.num;
     41       dis[x.num][0]=abs(x.h-y.h);
     42     }
     43     else if(dis[x.num][1]>abs(x.h-y.h)||(dis[x.num][1]==abs(x.h-y.h)&&y.h<c[nxt[x.num][1]].h)){
     44       nxt[x.num][1]=y.num;
     45       dis[x.num][1]=abs(x.h-y.h);
     46     }
     47     else if(!nxt[x.num][1]){
     48       nxt[x.num][1]=y.num;
     49       dis[x.num][1]=abs(x.h-y.h);
     50     }
     51     return;
     52   }
     53   void query(int s,int x,ll &disa,ll &disb){
     54     for(int i=20;i>=0;i--){
     55       if(f[s][i][0]+f[s][i][1]<=x&&g[s][i]){
     56         disa+=f[s][i][0];
     57         disb+=f[s][i][1];
     58         x-=f[s][i][1]+f[s][i][0];
     59         s=g[s][i];
     60       }
     61     }
     62     if(nxt[s][1]&&dis[s][1]<=x){
     63       disa+=dis[s][1];
     64     }
     65   }
     66   int main(){
     67     n=read();
     68     for(int i=1;i<=n;i++){
     69       c[i].h=read();c[i].num=i;
     70     }
     71     for(int i=n;i>=1;i--){
     72       s.insert(c[i]);
     73       it=s.find(c[i]);
     74       if(it!=s.begin()){
     75         it--;
     76         update(c[i],*it);
     77         if(it!=s.begin()){
     78           it--;
     79           update(c[i],*it);
     80           it++;
     81         }
     82         it++;
     83       }
     84       if((++it)!=s.end()){
     85         update(c[i],*it);
     86         if((++it)!=s.end()){
     87           update(c[i],*it);
     88           it--;
     89         }
     90         it--;
     91       }
     92     }
     93     for(int i=1;i<=n;i++){
     94       g[i][0]=nxt[nxt[i][1]][0];
     95       f[i][0][0]=dis[i][1];
     96       f[i][0][1]=dis[nxt[i][1]][0];
     97     }
     98     for(int j=1;j<=20;j++)
     99       for(int i=1;i<=n;i++){
    100         g[i][j]=g[g[i][j-1]][j-1];
    101         f[i][j][0]=f[i][j-1][0]+f[g[i][j-1]][j-1][0];
    102         f[i][j][1]=f[i][j-1][1]+f[g[i][j-1]][j-1][1];
    103       }
    104     x0=read();ll s0=0,a=1e15,b=0;
    105     for(int i=1;i<=n;i++){
    106       ll disa=0,disb=0;
    107       query(i,x0,disa,disb);
    108       if(disb&&(!s0||disa*b<disb*a)){
    109         s0=i;a=disa;b=disb;
    110       }
    111     }
    112     printf("%lld\n",s0);
    113     m=read();
    114     while(m--){
    115       ll disa=0,disb=0;
    116       int s,x;
    117       s=read();x=read();
    118       query(s,x,disa,disb);
    119       printf("%lld %lld\n",disa,disb);
    120     }
    121     return 0;
    122   }
    123 }
    124 signed main(){
    125   gengyf::main();
    126   return 0;
    127 }

写链表的都是神仙

### day 2 [T1 同余方程][T1] ###

标签：数论

对于方程$a\*x≡1(mod b)$，等价于$a\*x+b\*y=1$

用exgcd解线性方程，见[我之前的博客][Link 1]（不要脸行为

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //
     2 //  main.cpp
     3 //  Luogu
     4 //
     5 //  Created by gengyf on 2019/5/7.
     6 //  Copyright © 2019 yifan Geng. All rights reserved.
     7 //
     8 
     9 #include<cstdio>
    10 #include<iostream>
    11 #include<cstring>
    12 #include<string>
    13 //#include<bits/stdc++.h>
    14 using namespace std;
    15 long long a,b,x,y;
    16 void exgcd(long xx,long yy){
    17     if(yy==0){
    18         x=1;y=0;return ;
    19     }
    20     exgcd(yy,xx%yy);
    21     long long tx=x;
    22     x=y;
    23     y=tx-xx/yy*y;
    24 }
    25 int main(){
    26     scanf("%lld%lld",&a,&b);
    27     exgcd(a,b);
    28     while(x<0){
    29         x+=b;
    30         x%=b;
    31     }
    32     printf("%lld\n",x);
    33 }

### day 2 [T2 借教室][T2 1] ###

标签：二分

利用差分的思想，当一个区间+x时，只需在l处+x，r+1处-x

显然如果一个人不能满足，后面都不能满足，如果可以满足，前面一定都能满足，符合二分性质

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //
     2 //  main.cpp
     3 //  Luogu
     4 //
     5 //  Created by gengyf on 2019/7/11.
     6 //  Copyright © 2019 yifan Geng. All rights reserved.
     7 //
     8 
     9 #include <bits/stdc++.h>
    10 using namespace std;
    11 #define maxn 1000010
    12 int d[maxn],s[maxn],t[maxn];
    13 int b[maxn],n,m,need[maxn],a[maxn];
    14 bool check(int x){
    15     memset(b,0,sizeof(b));
    16     for(int i=1;i<=x;i++){
    17         b[s[i]]+=d[i];
    18         b[t[i]+1]-=d[i];
    19     }
    20     for(int i=1;i<=n;i++){
    21         need[i]=need[i-1]+b[i];
    22         if(need[i]>a[i])return 0;
    23     }
    24     return 1;
    25 }
    26 int main(){
    27     scanf("%d%d",&n,&m);
    28     for(int i=1;i<=n;i++){
    29         scanf("%d",&a[i]);
    30     }
    31     for(int i=1;i<=m;i++){
    32         scanf("%d%d%d",&d[i],&s[i],&t[i]);
    33     }
    34     int l=1,r=m;
    35     if(check(m)){
    36         printf("0\n");
    37         return 0;
    38     }
    39     while(l<r){
    40         int mid=(l+r)/2;
    41         if(check(mid)){
    42             l=mid+1;
    43         }
    44         else r=mid;
    45     }
    46     printf("-1\n%d",l);
    47     return 0;
    48 }

### day 2 [T3 疫情控制][T3 1] ###

标签：倍增，贪心

离根越近，能被叶节点到根的路径经过的越多，所以要在时间允许的范围内尽量把军队向根靠近

上提军队用倍增优化，要求的是最短的移动最多的军队所需时间，二分求解

## 如果调了很久调不出来，那就重构 ##

code(大概是有注释,如果没有那就是咕了)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 using namespace std;
      3 namespace gengyf{
      4 #define ll long long
      5   inline int read(){
      6     int x=0,f=1;char s=getchar();
      7     while(s<'0'||s>'9'){
         if(s=='-')f=-1;s=getchar();}
      8     while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
      9     return f*x;
     10   }
     11   const int maxn=50010;
     12   struct edge{
     13     int nxt,to,w;
     14   }e[maxn*4];
     15   int n,m,q[maxn];
     16   int head[maxn],cnt,d[maxn],f[maxn][25],t;
     17   bool st[maxn],need[maxn],fl;
     18   ll dis[maxn][25],tim[maxn],ned[maxn],ans;
     19   pair<ll,int>h[maxn];
     20   //q[]输入军队,f[i][j]存i的2^j祖先是谁,dis[i][j]存i到i的2^j祖先的路径长度
     21   //d[]深度,st[]驻扎军队,need[]需要驻扎,tim[]军队剩余时间,ned[]仍需驻扎
     22   void add(int from,int to,int w){
     23     e[++cnt].to=to;e[cnt].nxt=head[from];
     24     head[from]=cnt;e[cnt].w=w;
     25   }
     26   void dfs(){
     27     queue<int>q;
     28     q.push(1);d[1]=1;
     29     while(q.size()){
     30       int x=q.front();q.pop();
     31       for(int i=head[x];i;i=e[i].nxt){
     32         int y=e[i].to;
     33         if(d[y])continue;
     34         d[y]=d[x]+1;
     35         f[y][0]=x;dis[y][0]=e[i].w;
     36         for(int j=1;j<=t;j++){
         //倍增
     37           f[y][j]=f[f[y][j-1]][j-1];
     38           dis[y][j]=dis[y][j-1]+dis[f[y][j-1]][j-1];
     39         }
     40         q.push(y);
     41       }
     42     }
     43   }
     44   bool dfs2(int x){
     45     bool pson=0;//判断是否为叶节点
     46     if(st[x])return 1;//是否已经驻扎
     47     for(int i=head[x];i;i=e[i].nxt){
     48       int y=e[i].to;
     49       if(d[x]>d[y])continue;
     50       pson=1;//不是叶节点
     51       if(!dfs2(y)){
     52         return 0;
     53       }
     54     }
     55     if(!pson)return 0;//当前节点是叶子节点且未被驻扎
     56     return 1;//没有遇到路径未被驻扎的叶子节点
     57   }
     58   bool check(ll lim){
         //lim当前实现
     59     memset(st,0,sizeof(st));
     60     memset(tim,0,sizeof(tim));
     61     memset(need,0,sizeof(need));
     62     memset(h,0,sizeof(h));
     63     memset(ned,0,sizeof(ned));
     64     int atot=0,btot=0,ctot=1;
     65     for(int i=1;i<=m;i++){
     66       ll x=q[i],tot=0;//tot总共用多少时间
     67       for(int j=t;j>=0;j--)
     68         if(f[x][j]>1 && tot+dis[x][j]<=lim){
         //若终点在根节点之前且不会超过时限
     69           tot+=dis[x][j];
     70           x=f[x][j];
     71         }
     72       if(f[x][0]==1 && tot+dis[x][0]<=lim)//若当前节点为根节点的子节点且该军队可以在时限内到达根节点
     73         h[++ctot]=make_pair(lim-tot-dis[x][0],x);//存储闲置军队
     74       else
     75         st[x]=1;//标记驻扎
     76     }
     77     for(int i=head[1];i;i=e[i].nxt){
         //遍历整棵树
     78       if(!dfs2(e[i].to)){
         //若需要被驻扎
     79         need[e[i].to]=1;
     80       }
     81     }
     82     sort(h+1,h+1+ctot);
     83     for(int i=1;i<=ctot;i++){
         //遍历所有闲置的军队
     84       if(need[h[i].second] && h[i].first<dis[h[i].second][0])//若该军队所处的节点需要被驻扎且该军队无法到达根节点并返回
     85         need[h[i].second]=0;
     86       else tim[++atot]=h[i].first;//存储军队的剩余时间
     87     }
     88     for(int i=head[1];i;i=e[i].nxt){
     89       if(need[e[i].to]){
         //如果仍需要被驻扎
     90         ned[++btot]=dis[e[i].to][0];
     91       }
     92     }
     93     if(atot<btot)return 0;//如果剩余的军队比需要被驻扎的节点还少，不可行，直接返回0
     94     sort(tim+1,tim+atot+1);
     95     sort(ned+1,ned+btot+1);
     96     int i=1,j=1;
     97     while(i<=btot&&j<=atot){
     98       if(tim[j]>=ned[i]){
         //可行
     99         i++;j++;
    100       }
    101       else j++;
    102     }
    103     if(i>btot)return 1;//所有需要被驻扎的节点都已被驻扎
    104     return 0;
    105   }
    106   int main(){
    107     ll l=0,r=0;
    108     n=read();
    109     t=log2(n)+1;//倍增
    110     for(int i=1;i<n;i++){
    111       int u,v,w;
    112       u=read();v=read();w=read();
    113       add(u,v,w);add(v,u,w);
    114       r+=w;
    115     }
    116     dfs();
    117     cin>>m;
    118     for(int i=1;i<=m;i++){
    119       q[i]=read();
    120     }
    121     while(l<=r){
    122       ll mid=(l+r)>>1;
    123       if(check(mid)){
    124         r=mid-1;ans=mid;fl=1;//fl有解
    125       }
    126       else l=mid+1;
    127     }
    128     if(!fl){
    129       printf("-1\n");
    130     }
    131     else printf("%lld",ans);
    132     return 0;
    133   }
    134 }
    135 signed main(){
    136   gengyf::main();
    137   return 0;
    138 }

--------------------

![1658269-20190918190625158-1322648537.png][]

我太难了

转载于:https://www.cnblogs.com/gengyf/p/11544297.html

[T1 Vigen_re]: https://www.luogu.com.cn/problem/P1079
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/28313702fd214560b50152b14a790258.png
[T2]: https://www.luogu.com.cn/problem/P1080
[T3]: https://www.luogu.com.cn/problem/P1081
[T1]: https://www.luogu.com.cn/problem/P1082
[Link 1]: https://www.cnblogs.com/gengyf/p/10828272.html
[T2 1]: https://www.luogu.com.cn/problem/P1083
[T3 1]: https://www.luogu.com.cn/problem/P1084
[1658269-20190918190625158-1322648537.png]: /images/20230809/f9d06a912bdb46468b0b179affc14130.png