【NOIp】NOIp2009

缺乏、安全感 2023-08-17 16:49 112阅读 0赞

# NOIp2009 #

### [T1 潜伏者][T1] ###

标签：STL，字符串

这题怕不是两个map水过去......

开两个map分别存加密信息->原信息和原信息->加密信息

用这两个map统计是否出现情况3，即该字符在加密信息中已经出现过却和当前位置所对应的原信息不符

或反过来

再扫一遍看看是否有字母未出现过(情况2)

如果没有出现上述状况，对应输出即可

code

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

### [T2 Hankson 的趣味题][T2 Hankson] ###

标签：数论

并不算简单的颓推式子

gcd(a0,x)=a1易证得gcd(a0/a1,x/a1)=1 ①

lcm(b0,x)=b1 -> gcd(x,b0)=b0\*x/lcm(b0,x)=b0\*x/b1

由①得 gcd(x/(b0\*x/b1),b0/(b0\*x/b1))=1 -> gcd(b1/b0,b1/x)=1 ②

由此我们发现x只能是a1的倍数和b1的约数

所以枚举b1的每个约数判断是否为a1的倍数且满足①②即可

code

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

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4     inline int read(){
     5         int x=0,f=1;char s=getchar();
     6         while(s<'0'||s>'9'){
         if(s=='-')f=-1;s=getchar();}
     7         while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
     8         return x*f;
     9     }
    10     int n,a0,a1,b0,b1,ans;
    11     int gcd(int a,int b){
    12         return b==0?a:gcd(b,a%b);
    13     }
    14     int main() {
    15         int n;
    16         n=read();
    17         while(n--) {
    18             int a0,a1,b0,b1;
    19             a0=read();a1=read();b0=read();b1=read();
    20             int p=a0/a1,q=b1/b0,ans=0;
    21             for(int x=1;x*x<=b1;x++)
    22                 if(b1%x==0){
    23                     if(x%a1==0&&gcd(x/a1,p)==1&&gcd(q,b1/x)==1) ans++;
    24                     int y=b1/x;
    25                     if(x==y) continue;
    26                     if(y%a1==0&&gcd(y/a1,p)==1&&gcd(q,b1/y)==1) ans++;
    27                 }
    28             printf("%d\n",ans);
    29         }
    30         return 0;
    31     }
    32 }
    33 int main(){
    34     gengyf::main();
    35     return 0;
    36 }

### [T3 最优贸易][T3] ###

标签：dp

正经dp

f\[i\]表示当前点能取到的最大价值，ans\[i\]表示从1号点到i点最大价值

如果在i点的价值加上i,j两点间的差价(v\[i\]-v\[j\])比在j点的价值优，我们没理由不去赚这个差价

$f\[i\]=max(f\[i\],v\[i\]-v\[j\]+f\[j\])$

同理，如果在j点的代价优于i点的代价或答案，那么也要更新i

$ans\[i\]=max(ans\[i\],max(ans\[j\],f\[i\])$

code(有注释)

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

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4 #define pb push_back
     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 x*f;
    10     }
    11     const int N=1e5+10;
    12     int n,m,v[N],ans[N],f[N];
    13     vector<int> a[N];//存图
    14     vector<int>::iterator j;
    15     int main() {
    16         n=read();m=read();
    17         for(int i=1;i<=n;i++){
    18             v[i]=read();
    19         }
    20         for(int i=1;i<=m;i++){
    21             int x,y,z;
    22             x=read();y=read();z=read();
    23             a[y].pb(x);
    24             if(z==2){
    25                 a[x].pb(y);
    26             }
    27         }
    28         for(int i=1;i<=n;i++){
         //从每个点开始遍历
    29             for(j=a[i].begin();j!=a[i].end();j++){
         //这个点i能走到的点j
    30                 f[i]=max(f[i],v[i]-v[*j]+f[*j]);//更新代价
    31                 ans[i]=max(ans[i],max(ans[*j],f[*j]));//更新答案
    32             }
    33         }
    34         printf("%d\n",ans[n]);
    35         return 0;
    36     }
    37 }
    38 int main(){
    39     gengyf::main();
    40     return 0;
    41 }

话说最开始dp写挂了想找篇题解对对拍，结果发现题解全是spfa（震惊

翻了好几页才看到思路一样的QAQ

换了一种存图方式差点不会写，嘤

### [T4 靶形数独][T4] ###

标签：搜索

用三个数组记录行，列，每一宫的数字状况

优化：①从0少的行开始搜②如果后面全是9也比ans劣就返回

code

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

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4     inline int read(){
     5         int x=0,f=1;char s=getchar();
     6         while(s<'0'||s>'9'){
         if(s=='-')f=-1;s=getchar();}
     7         while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
     8         return x*f;
     9     }
    10     const int val[9][9]={
    11         6,6,6,6,6,6,6,6,6,
    12         6,7,7,7,7,7,7,7,6,
    13         6,7,8,8,8,8,8,7,6,
    14         6,7,8,9,9,9,8,7,6,
    15         6,7,8,9,10,9,8,7,6,
    16         6,7,8,9,9,9,8,7,6,
    17         6,7,8,8,8,8,8,7,6,
    18         6,7,7,7,7,7,7,7,6,
    19         6,6,6,6,6,6,6,6,6
    20     };
    21     int a[10][10],x[10][10],y[10][10],c[10][10],num[10],rnk[10],ans;
    22     void dfs(int now,int sum,int last){
    23         if(now==81){
    24             ans=max(ans,sum);return ;
    25         }
    26         if(sum+9+last*9<=ans)return ;
    27         int i=rnk[now/9],j=now%9,b=i/3*3+j/3;
    28         if(a[i][j])dfs(now+1,sum+a[i][j]*val[i][j],last-a[i][j]);
    29         else {
    30             for(int k=1;k<=9;k++){
    31                 if(!x[i][k]&&!y[j][k]&&!c[b][k]){
    32                     x[i][k]=y[j][k]=c[b][k]=1;
    33                     dfs(now+1,sum+k*val[i][j],last-k);
    34                     x[i][k]=y[j][k]=c[b][k]=0;
    35                 }
    36             }
    37         }
    38     }
    39     bool cmp(int a,int b){
    40         return num[a]<num[b];
    41     }
    42     int main() {
    43         ans=-1;
    44         for(int i=0;i<9;i++){
    45             rnk[i]=i;
    46             for(int j=0;j<9;j++){
    47                 a[i][j]=read();
    48                 if(a[i][j]){
    49                     x[i][a[i][j]]=y[j][a[i][j]]=c[i/3*3+j/3][a[i][j]]=1;
    50                 }
    51                 else num[i]++;
    52             }
    53         }
    54         sort(rnk,rnk+9,cmp);
    55         dfs(0,0,405);
    56         printf("%d",ans);
    57         return 0;
    58     }
    59 }
    60 int main(){
    61     gengyf::main();
    62     return 0;
    63 }

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

总结：这一年的题目难度明显提高了，不像前几年那么好想了（说明ccf出题水平上升了，更注重算法而非模拟暴力

![1658269-20190909220118780-758218044.png][]

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

[T1]: https://www.luogu.org/problem/P1071
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/3fef10779690465d9892f79f0cda991d.png
[T2 Hankson]: https://www.luogu.org/problem/P1072
[T3]: https://www.luogu.org/problem/P1073
[T4]: https://www.luogu.org/problem/P1074
[1658269-20190909220118780-758218044.png]: /images/20230809/6b5edc9a73e442b386acab71db42e3c9.png