2019佳木斯多校联训 Day1

红太狼 2021-10-24 06:22 172阅读 0赞

非常裸的大模拟,比较简单

思路:用字符串存储数据,然后从后往前查找直到

找到00,25,50,75中的任意一个,然后再用串长相减

判断一下正反关系,AC.

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

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 char a[110];
     4 int num[10];
     5 int ans[5][3];
     6 int ans1=999999,ans2=999999,ans3=999999,ans4=999999;
     7 int main(){
     8     scanf("%s",a+1);
     9     memset(ans,0x7f,sizeof(ans));
    10     //printf("%d",ans[1][1]);
    11     int len=strlen(a+1);
    12     for(register int i=1;i<=len;i++) num[a[i]-'0']++;
    13     if(num[0]>=2||num[0]>=1&&num[5]>=1||num[5]>=1&&num[2]>=1||num[5]>=1&&num[7]>=1){
    14         for(register int i=len;i>=1;i--){
    15             if(a[i]=='2'&&ans[2][1]==2139062143) ans[2][1]=i;
    16             if(a[i]=='5'){
    17                 if(ans[2][2]==2139062143) ans[2][2]=i;
    18                 if(ans[3][1]==2139062143) ans[3][1]=i;
    19                 if(ans[4][2]==2139062143) ans[4][2]=i;
    20             }
    21             if(a[i]=='7'&&ans[4][1]==2139062143) ans[4][1]=i;
    22             if(a[i]=='0'){
    23                 if(ans[3][2]==2139062143) ans[3][2]=i;
    24                 if(ans[1][2]==2139062143) ans[1][2]=i;
    25                 else if(ans[1][1]==2139062143) ans[1][1]=i;
    26             }
    27         }
    28         //for(register int i=0;i<10;i++) printf("%d ",num[i]);printf("\n");
    29         //for(register int i=1;i<=4;i++){
    30         //for(register int j=1;j<=2;j++) printf("%d ",ans[i][j]);printf("\n");}
    31         if(ans[1][2]!=2139062143&&ans[1][1]!=2139062143){
    32             ans1=0;
    33             ans1+=len-max(ans[1][2],ans[1][1]);
    34             ans1+=len-1-min(ans[1][2],ans[1][1]);
    35         }
    36         if(ans[2][2]!=2139062143&&ans[2][1]!=2139062143){
    37             ans2=0;
    38             if(ans[2][2]<ans[2][1]) ans2+=1;
    39             ans2+=len-ans[2][2];
    40             ans2+=len-1-ans[2][1];
    41         }
    42         if(ans[3][2]!=2139062143&&ans[3][1]!=2139062143){
    43             ans3=0;
    44             if(ans[3][2]<ans[3][1]) ans3+=1;
    45             ans3+=len-ans[3][2];
    46             ans3+=len-1-ans[3][1];
    47         }
    48         if(ans[4][2]!=2139062143&&ans[4][1]!=2139062143){
    49             ans4=0;
    50             if(ans[4][2]<ans[4][1]) ans4+=1;
    51             ans4+=len-ans[4][2];
    52             ans4+=len-1-ans[4][1];
    53         }
    54         printf("%d",min(ans1,min(ans2,min(ans3,ans4))));
    55     }
    56     else{
    57         printf("-1");
    58         return 0;
    59     }
    60     return 0;
    61 }

T1-优美的数字

严重起诉出题人数据太水了！！！

正解单调栈,本来是需要判断1~q之间子串的,结果

由于数据太水反而会卡住判断子串的人,而不判断子串的人

全AC了.......

思路:本人二分做法,时间优化一下应该能过,主要介绍一下

二分的判断方式,两层循环外层是起点，内层是枚举所有的串

往前跑,两条都大就跳过,两条都小就更新最小值再跳过,两条

一条大一条小break,return false;

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

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 int a[100010],b[100010];
     4 int n,a1,b1;
     5 bool ac;
     6 inline int read(){
     7     int x=0,f=1;
     8     char ch=getchar();
     9     while(ch<'0'||ch>'9'){
    10         if(ch=='-')
    11             f=-1;
    12         ch=getchar();
    13     }
    14     while(ch>='0'&&ch<='9'){
    15         x=(x<<1)+(x<<3)+(ch^48);
    16         ch=getchar();
    17     }
    18     return x*f;
    19 }
    20 inline bool check(int x){
    21     for(register int i=1;i<x;i++){
    22         a1=a[i],b1=b[i];
    23         for(register int j=i+1;j<=x;j++){
    24             if(a[j]>=a1&&b[j]>=b1) continue;
    25             else if(a[j]<=a1&&b[j]<=b1){a1=a[j],b1=b[j];continue;}
    26             else if(a[j]>a1&&b[j]<b1||a[j]<a1&&b[j]>b1){
         return false;}
    27         }
    28     }
    29     return true;
    30 }
    31 int ef(int l,int r){
    32     if(l==r) return l;
    33     int mid=(l+r)>>1;
    34     if(check(mid+1)) ef(mid+1,r);
    35     else ef(l,mid);
    36 }
    37 int main(){
    38     scanf("%d",&n);
    39     for(register int i=1;i<=n;i++) a[i]=read();
    40     for(register int i=1;i<=n;i++) b[i]=read();
    41     printf("%d",ef(1,n));
    42     return 0;
    43 }

T2-优美的数组(二分做法)

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

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int maxn=100000+10;
     4 int a[maxn];
     5 int b[maxn];
     6 int q1[maxn],t1=0;
     7 int q2[maxn],t2=0;
     8 inline int read(){
     9     int ans=0;
    10     bool b=0;
    11     char c=getchar();
    12     while(c<'0'||c>'9')
    13     {
    14         if(c=='-') b=1;
    15         c=getchar();
    16     }
    17     while(c>='0'&&c<='9')
    18     {
    19         ans=(ans<<1)+(ans<<3)+c-'0';
    20         c=getchar();
    21     }
    22     if(!b) return ans;
    23     return -ans;
    24 }
    25 int main(){
    26     int n=read();
    27     for(int i=1;i<=n;i++)
    28     a[i]=read();
    29     for(int i=1;i<=n;i++)
    30     b[i]=read();
    31     int num=1;
    32     while(num<=n){
    33         while(a[q1[t1]]>a[num]) t1--;
    34         q1[++t1]=num;
    35         while(b[q2[t2]]>b[num]) t2--;
    36         q2[++t2]=num;
    37         if(q1[t1]!=q2[t2]||t1!=t2) break;
    38         num++;
    39     }
    40     printf("%d",num-1);
    41     return 0;
    42 }

T2-优美的数组(正解单调栈)

还行,真的就还行...

虽然我调了2个小时.......

思路:k显然是个没啥用的东西,用并查集把需要互相揍的几个人

绑在一起,形成一个堆,然后统计每个堆里出现过最多的数,把这个堆里

不是这个元素的其他值全部变为这个元素,ans加上这个差值就行

一个只有一个元素的堆直接跳过,跑完就完事了~~~

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

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 int n,m,k,ans,x,y,qwq,ac=1,wa,tle,re;
     4 int level[100010];
     5 int sum[100010];
     6 int num[100010];
     7 bool vis[100010];
     8 int f[100010];
     9 int lala[100010];
    10 int getf(int x){
    11     if(f[x]==x) return x;
    12     return f[x]=getf(f[x]);
    13 }
    14 int main(){
    15     scanf("%d%d%d",&n,&m,&k);
    16     for(register int i=1;i<=n;i++) f[i]=i;
    17     for(register int i=1;i<=n;i++) scanf("%d",&level[i]);
    18     for(register int i=1;i<=m;i++){
    19         scanf("%d%d",&x,&y);
    20         if(x>y) swap(x,y);
    21         f[getf(x)]=getf(y);
    22     }
    23     for(register int i=1;i<=n;i++) f[i]=getf(i);
    24     for(register int i=1;i<=n;i++){
    25         if(!vis[f[i]]) vis[f[i]]=1,lala[++re]=f[i];
    26         sum[f[i]]++;
    27     }
    28     for(register int i=1;i<=re;i++){
    29         if(sum[lala[i]]==1) continue;
    30         memset(num,0,sizeof(num));
    31         wa=0;
    32         for(register int j=1;j<=n;j++) if(f[j]==lala[i]) num[level[j]]++;
    33         for(register int j=1;j<=n;j++){
    34             if(num[j]>wa){
    35                 wa=num[j];
    36             }
    37         }
    38         ans+=sum[lala[i]]-wa;
    39     }
    40     printf("%d",ans);
    41     return 0;
    42 }

T3-优美的数对

Day1  score:230  rank 11

end;

转载于:https://www.cnblogs.com/liuhailin/p/11252249.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211023/8e9f4ffe1a284ddd98df6f236a43fdd4.png