4.29训练题解

发布时间:2017-7-9 7:19:06编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"4.29训练题解",主要涉及到4.29训练题解方面的内容,对于4.29训练题解感兴趣的同学可以参考一下。

 1 #include<bits/stdc++.h> 2  3 using namespace std; 4  5 char a[100]; 6 int f[100],n,ans; 7 int main() 8 { 9     scanf("%s",a+1);10     n=strlen(a+1);11     f[1]=0;12     for (int i=1; i<=n; i++)13     {14         for (int j=i; j; j--)15             if (a[i]>a[j]) f[i]=max(f[i],f[j]);16         f[i]++;17         if (f[i]>ans) ans=f[i];18     }19     printf("%d\n",26-ans);20 }
View Code

gym101201B

一类类似spfa的dp,用f[x][y][k]表示到指令符第k位走到(x,y)所需要的修改次数

然后用spfa的形式进行转移即可(训练的时候简直不知道自己在写什么)

 1 #include<bits/stdc++.h> 2 #define mp make_pair 3 #define pi pair<int,int> 4 using namespace std; 5 const int dx[4]={-1,1,0,0}; 6 const int dy[4]={0,0,-1,1}; 7 int f[60][60][60],v[60][60],a[60][60],bx,by,ex,ey,n,m,l; 8 pi q[2000010]; 9 char s[60];10 11 void bfs(int k)12 {13     int h=1,r=0;14     for (int i=1; i<=n; i++)15         for (int j=1; j<=m; j++)16             if (a[i][j])17             {18                 q[++r]=mp(i,j);19                 v[i][j]=1;20             }21 22     while (h<=r)23     {24         int i=q[h].first,j=q[h].second;25         v[i][j]=0; h++;26         for (int w=0; w<4; w++)27         {28             int x=i+dx[w],y=j+dy[w];29             if (!a[x][y]) continue;30             if (f[x][y][k]>f[i][j][k]+1)31             {32                 f[x][y][k]=f[i][j][k]+1;33                 if (!v[x][y])34                 {35                     q[++r]=mp(x,y);36                     v[x][y]=1;37                 }38             }39         }40     }41 }42 43 int main()44 {45     scanf("%d%d",&n,&m);46     for (int i=1; i<=n; i++)47     {48         scanf("%s",s+1);49         for (int j=1; j<=m; j++)50         {51             if (s[j]!='#') a[i][j]=1;52             if (s[j]=='R')53             {54                 bx=i;55                 by=j;56             }57             if (s[j]=='E')58             {59                 ex=i;60                 ey=j;61             }62         }63     }64     scanf("%s",s+1);65     l=strlen(s+1);66     for (int i=1; i<=n; i++)67         for (int j=1; j<=m; j++)68             for (int k=0; k<=l+1; k++) f[i][j][k]=1e9;69     int ans=1e9;70     f[bx][by][0]=0;71     for (int k=1; k<=l+1; k++)72     {73         bfs(k-1);74         ans=min(ans,f[ex][ey][k-1]);75         if (k==l+1) break;76         for (int i=1; i<=n; i++)77             for (int j=1; j<=m; j++)78                 if (a[i][j])79                 {80                     int pw;81                     if (s[k]=='L') pw=2;82                     if (s[k]=='R') pw=3;83                     if (s[k]=='U') pw=0;84                     if (s[k]=='D') pw=1;85                     int x=i+dx[pw],y=j+dy[pw];86                     if (a[x][y]) f[x][y][k]=min(f[i][j][k-1],f[x][y][k]);87                     else f[i][j][k]=min(f[i][j][k-1],f[i][j][k]);88                     f[i][j][k]=min(f[i][j][k-1]+1,f[i][j][k]);89                 }90     }91     printf("%d\n",ans);92 }
View Code

gym101201C

简单贪心即可

 1 #include<bits/stdc++.h> 2  3 using namespace std; 4 int v[100010],s,ans,n,m,k; 5 int main() 6 { 7     scanf("%d%d%d",&n,&m,&k); 8     for (int i=1; i<=m; i++) 9     {10         int x;11         scanf("%d",&x);12         v[x]=1;13     }14     for (int i=1; i<=k; i++)15         s+=v[i];16     if (s<=1)17     {18         int j=k;19         while (j&&v[j]) j--;20         v[j]=1; ans++; s++;21         if (s<=1)22         {23             while (j&&v[j]) j--;24             v[j]=1; ans++; s++;25         }26     }27     for (int i=k+1; i<=n; i++)28     {29         s=s-v[i-k]+v[i];30         if (s<=1)31         {32             int j=i;33             while (j>i-k&&v[j]) j--;34             v[j]=1; ans++; s++;35             if (s<=1)36             {37                 while (j>i-k&&v[j]) j--;38                 v[j]=1; ans++; s++;39             }40         }41     }42     printf("%d\n",ans);43 }
View Code

gym101201D

还未补

gym101201E

还未补

gym101201F

把每个灯照行还是列看作状态,任意两个同行(或同列)的灯不能同时照同行(或同列)

——经典的2sat问题

 1 #include<bits/stdc++.h> 2 #define mp make_pair 3 #define pi pair<int,int> 4 #define fi first 5 #define se second 6 using namespace std; 7 vector<int> g[2010]; 8 int x[1010],y[1010],f[2010],dfn[2010],low[2010],st[2010],n,r,l,h,t,s,m,be[2010]; 9 pi q[2010];10 void tarjan(int x)11 {12      dfn[x]=low[x]=++h;13      st[++t]=x;14      f[x]=1;15      for (int i=0; i<g[x].size(); i++)16      {17          int y=g[x][i];18          if (!dfn[y])19          {20             tarjan(y);21             low[x]=min(low[x],low[y]);22          }23          else if (f[y]) low[x]=min(low[x],low[y]);24      }25      if (low[x]==dfn[x])26      {27         s++;28         while (st[t+1]!=x)29         {30             int y=st[t--];31             be[y]=s; f[y]=0;32         }33      }34 }35 36 int main()37 {38     scanf("%d%d%d",&n,&r,&m);39     for (int i=1; i<=m; i++)40         scanf("%d%d",&x[i],&y[i]);41 42     for (int i=1; i<=m; i++)43         for (int j=1; j<=m; j++)44             if (i!=j)45             {46                 if (x[i]==x[j]&&abs(y[i]-y[j])<=2*r)47                 {48                     g[i+m].push_back(j);49                     g[j+m].push_back(i);50                 }51                 if (y[i]==y[j]&&abs(x[i]-x[j])<=2*r)52                 {53                     g[i].push_back(j+m);54                     g[j].push_back(i+m);55                 }56             }57 58     for (int i=1; i<=m*2; i++)59         if (!dfn[i])60         {61             h=t=0;62             tarjan(i);63         }64 65     for (int i=1; i<=m; i++)66         if (be[i]==be[i+m])67         {68             puts("NO");69             return 0;70         }71     puts("YES");72 }
View Code

gym101201G

首先把确定的拎出来,不确定的地方要使海岛尽可能多,那必定是将一格作为一个海岛

不难想到将图黑白染色做而二分图的最大独立集

 1 #include<bits/stdc++.h> 2  3 using namespace std; 4 const int dx[4]={-1,1,0,0}; 5 const int dy[4]={0,0,-1,1}; 6 char s[100]; 7 int f[1610],b[60][60],a[60][60],v[60][60],cy[1610],cx[1610],n,m,ans,t; 8 vector<int> g[1610]; 9 void dfs(int i,int j)10 {11     v[i][j]=1;12     for (int k=0; k<4; k++)13     {14         int x=i+dx[k],y=j+dy[k];15         if (x==0||x>n||y>m||y==0) continue;16         if (v[x][y]) continue;17         if (a[x][y]==-1) a[x][y]=0;18         if (a[x][y]==1) dfs(x,y);19     }20 }21 22 int work(int x)23 {24     for (int i=0; i<g[x].size(); i++)25     {26         int y=g[x][i];27         if (!f[y])28         {29             f[y]=1;30             if (!cy[y]||work(cy[y]))31             {32                 cx[x]=y;33                 cy[y]=x;34                 return 1;35             }36         }37     }38     return 0;39 }40 41 int main()42 {43     //freopen("1.in","r",stdin);44     scanf("%d%d",&n,&m);45     for (int i=1; i<=n; i++)46     {47         scanf("%s",s+1);48         for (int j=1; j<=m; j++)49         {50             if (s[j]=='W') a[i][j]=0;51             if (s[j]=='C') a[i][j]=-1;52             if (s[j]=='L') a[i][j]=1;53         }54     }55     for (int i=1; i<=n; i++)56         for (int j=1; j<=m; j++)57             if (!v[i][j]&&a[i][j]==1)58             {59                 ans++;60                 dfs(i,j);61             }62 63     for (int i=1; i<=n; i++)64         for (int j=1; j<=m; j++)65             if (a[i][j]==-1) b[i][j]=++t;66     for (int i=1; i<=n; i++)67         for (int j=1; j<=m; j++)68             if ((i+j)%2==0)69             {70                 for (int k=0; k<4; k++)71                 {72                     int x=i+dx[k],y=j+dy[k];73                     if (b[x][y]) g[b[i][j]].push_back(b[x][y]);74                 }75             }76     int s=0;77     for (int i=1; i<=t; i++)78         if (g[i].size())79         {80             if (!cx[i])81             {82                 memset(f,0,sizeof(f));83                 s+=work(i);84             }85         }86     printf("%d\n",ans+t-s);87 }
View Code

gym101201H

经典的区间最大不重合拼接问题,离散化后树状数组优化dp

 1 #include<bits/stdc++.h> 2  3 using namespace std; 4 typedef long long ll; 5 struct node{ll l,r;} a[200010]; 6 ll n,ans,c[400010],b[400010]; 7 int sz,m,t; 8 bool cmp(node a,node b) 9 {10     return a.r<b.r;11 }12 13 ll ask(int x)14 {15     ll s=0;16     for (int i=x; i; i-=i&(-i))17         s=max(s,c[i]);18     return s;19 }20 21 void work(int x,ll w)22 {23     for (int i=x; i<=sz; i+=i&(-i))24         c[i]=max(c[i],w);25 }26 27 int main()28 {29     scanf("%lld%d",&n,&m);30     for (int i=1; i<=m; i++)31     {32         scanf("%lld%lld",&a[i].l,&a[i].r);33         b[++t]=a[i].l;34         b[++t]=a[i].r;35     }36     sort(a+1,a+1+m,cmp);37     sort(b+1,b+1+t);38     sz=unique(b+1,b+1+t)-b-1;39     ll ans=0;40     for (int i=1; i<=m; i++)41     {42         int x=lower_bound(b+1,b+1+sz,a[i].l)-b;43         int y=lower_bound(b+1,b+1+sz,a[i].r)-b;44         ll tmp=ask(x-1)+a[i].r-a[i].l+1;45         ans=max(ans,tmp);46         work(y,tmp);47     }48     printf("%lld\n",n-ans);49 }
View Code

gym101201I

这题想了半天简直蠢,贪心

每次肯定送尽可能最远的最优,然后做一些计算即可

 1 #include<bits/stdc++.h> 2  3 using namespace std; 4 typedef long long ll; 5 struct node{int x,c;} a[100010]; 6 bool cmp(node a,node b) 7 { 8     return a.x<b.x; 9 }10 ll ans;11 int n,k;12 int main()13 {14     scanf("%d%d",&n,&k);15     for (int i=1; i<=n; i++)16         scanf("%d%d",&a[i].x,&a[i].c);17     sort(a+1,a+1+n,cmp);18     int i=n;19     while (i)20     {21         if (a[i].x<0) break;22         ll ti=(a[i].c+k-1)/k;23         ans+=abs(a[i].x)*ti;24         ll s=ti*k;25         while (i&&a[i].x>=0&&s)26         {27             if (a[i].c<=s)28             {29                 s-=a[i].c;30                 i--;31             }32             else {33                 a[i].c-=s;34                 break;35             }36         }37     }38     i=1;39     while (i<=n)40     {41         if (a[i].x>0) break;42         ll ti=(a[i].c+k-1)/k;43         ans+=abs(a[i].x)*ti;44         ll s=ti*k;45         while (i<=n&&a[i].x<0&&s)46         {47             if (a[i].c<=s)48             {49                 s-=a[i].c;50                 i++;51             }52             else {53                 a[i].c-=s;54                 break;55             }56         }57     }58     printf("%lld\n",ans*2);59 }
View Code

gym101201J

一道训练时大量人通过我不会的题……

多次询问一个数依次对区间每个数取模的结果

考虑到每次取模,如果x>a[i]那x%a[i]<=x/2,因此最多模log级别的数

我们每次模完当前数,只要找下面第一个小于x的数即可

这可以用二分+st表预处理区间最小值解决,复杂度是log方的

 1 #include<bits/stdc++.h> 2  3 using namespace std; 4 typedef long long ll; 5 int l2[1200010],d[25],n,q; 6 ll f[200010][20],a[200010]; 7 ll ask(int l,int r) 8 { 9     int k=l2[r-l+1];10     return min(f[l][k],f[r-d[k]+1][k]);11 }12 13 ll get(int l,int r,ll v)14 {15     int s=n+1;16     while (l<=r)17     {18         int m=(l+r)>>1;19         if (ask(l,m)>v) l=m+1;20         else {21             s=m;22             r=m-1;23         }24     }25     return s;26 }27 28 int main()29 {30     d[0]=1;31     for (int i=1; i<=20; i++)32     {33         d[i]=d[i-1]*2;34         for (int j=(1<<(i-1)); j<(1<<i); j++)35             l2[j]=i-1;36     }37     scanf("%d%d",&n,&q);38     for (int i=1; i<=n; i++)39     {40         scanf("%lld",&a[i]);41         f[i][0]=a[i];42     }43     for (int j=1; (1<<j)<n; j++)44         for (int i=1; i<=n; i++)45             if (i+d[j]-1<=n) f[i][j]=min(f[i][j-1],f[i+d[j-1]][j-1]);46             else break;47 48     for (int i=1; i<=q; i++)49     {50         ll v; int l,r;51         scanf("%lld%d%d",&v,&l,&r);52         while (l<=r)53         {54             v%=a[l];55             if (!v) break;56             l=get(l+1,r,v);57         }58         printf("%lld\n",v);59     }60 }
View Code

gym101201K

又一道训练时大量人通过我不会的题+1

其实是一道很简单的题,最重要的一点是最后的期望胜场数=∑至少胜i场的概率*i

那么在2^i的区间脱颖而出,概率显然是C(2^k-r,2^i-1) / C(2^k,2^i-1)

注意一下精度问题

 1 #include<bits/stdc++.h> 2 int k,n,m,r; 3  4 int main() 5 { 6     scanf("%d%d",&k,&r); 7     n=(1<<k)-1; m=(1<<k)-r; 8     double p=1.0,ans=0; 9     for (int k=1; (1<<k)-1<=m; k++)10     {11         int sm=m-(1<<k)+2, em=m-(1<<(k-1))+1;12         int sn=n-(1<<k)+2;13         for (int mm=sm,nn=sn; mm<=em; mm++,nn++)14             p*=1.0*mm/nn;15         ans+=p;16     }17     printf("%.5lf\n", ans);18 }
View Code

gym101201L

还未补


上一篇:gulp将多张小图自动合成雪碧图 - 沪
下一篇:Tomcat的免安装配置

相关文章

关键词: 4.29训练题解

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款