CTU 2011/CTU 2012 部分题解...

网友投稿 275 2022-08-25

CTU 2011/CTU 2012 部分题解...

题目、数据、标程、解题报告(捷克语):

​​CTU2011   ​​

​​CTU2012​​

Collatz Conjecture

题意:

有这么一个运算: f(x)= 1、当x为偶数 x/2   , 2、当x为奇数 x*3+1 。现在保证2^58内的数都可以通过这种运算最终到达1...现在给出两个数A,B问最先出来相同的数十什么..A是什么时候变成的..B是什么时候变成的...

题解:

暴力枚举就好.关键是Hash...手写了一个Hash类..实际上就是模了一个数后..若同一个位置有多个数..则挂链表...

Program:

#include#include#include#include#include#include#include#include#include#define ll long long#define oo 1<<29#define pi acos(-1.0)#define MAXN 22341 using namespace std; struct HASH{ struct node { ll x,step,next; }P[MAXN*100]; int ne,_next[MAXN+5]; void initial() { ne=0; memset(_next,0,sizeof(_next)); } void insert(ll x,ll step) { ll t=x%MAXN; P[++ne].next=_next[t],_next[t]=ne,P[ne].x=x,P[ne].step=step; } ll find(ll x) { ll t=x%MAXN; for (t=_next[t];t;t=P[t].next) if (P[t].x==x) return P[t].step; return -1; }}HA,HB;int main(){ ll A,B,a,b,step; while (~scanf("%lld%lld",&a,&b) && a) { A=a,B=b,HA.initial(),HB.initial(); step=0,HA.insert(A,0),HB.insert(B,0); while (HA.find(B)<0 && HB.find(A)<0) { step++; if (B!=1) { if (B%2) B=B*3+1; else B=B/2; HB.insert(B,step); } if (A!=1) { if (A%2) A=A*3+1; else A=A/2; HA.insert(A,step); } } ll A0t,A1t,B0t,B1t,M; A0t=A1t=B0t=B1t=oo; if (HB.find(A)>=0) A0t=step,B0t=HB.find(A),M=A; if (HA.find(B)>=0) A1t=HA.find(B),B1t=step; if (A0t+B0t>A1t+B1t) swap(A0t,A1t),swap(B0t,B1t),M=B; printf("%lld needs %lld steps, %lld needs %lld steps, they meet at %lld\n",a,A0t,b,B0t,M); } return 0;}

Text Encryption

题意:

现在要对字符串进行转换.转换方式是按照所给的串重新构造一个串..首先这个串不含空格和小写字母(所有的字母转化为大写)给定一个数M..第一次将%M=0的从0开始放好..接着再将%M=1从M开始放好..依次将所有的字符放好..

题解:

直接模拟..

Program:

#include#include#include#include#include#include#include#include#include#define ll long long#define oo 1<<29#define pi acos(-1.0)#define MAXN 1005 using namespace std;char ss[MAXN],s[MAXN],ans[MAXN];int main(){ int M,i,t,p,len,L; while (~scanf("%d",&M) && M) { memset(s,0,sizeof(s)); gets(ss); gets(ss),len=strlen(ss),L=0; for (i=0;i='a' && ss[i]<='z') s[L++]=ss[i]-'a'+'A'; else s[L++]=ss[i]; } len=L; memset(ans,0,sizeof(ans)),i=0; for (p=0;p

Invasion

题意:

给了一个无相图(不超过10000个点...100000条边)...现在外星人要在某些点上建立据点..而距离据点距离小于 K的点就不能生存了..现在给出无向图..再以此给出M个外星人到来的顺序..请输出每个外星人到达后..还有多少个点可以生存...

题解:

基本上裸的SPFA...只是dis数组只要初始化一次就好...

Program:

#include#include#include#include#include#include#include#include#include#define ll long long#define oo 1<<29#define pi acos(-1.0)#define MAXN 10005#define MAXM 200005using namespace std; struct node{ int v,d,next;}edge[MAXM];int ne,_next[MAXN];void addedge(int u,int v,int d){ edge[++ne].next=_next[u],_next[u]=ne; edge[ne].v=v,edge[ne].d=d;}bool f[MAXN],inQ[MAXN];int dis[MAXN];queue Q;int SPFA(int u,int d){ int ans=0,v,k; while (!Q.empty()) Q.pop(); memset(inQ,false,sizeof(inQ)); Q.push(u),dis[u]=0; while (!Q.empty()) { u=Q.front(),Q.pop(),inQ[u]=false; if (dis[u]>=d) continue; if (!f[u]) f[u]=true,ans++; for (k=_next[u];k;k=edge[k].next) { v=edge[k].v; if (dis[v]==-1 || dis[v]>dis[u]+edge[k].d) { dis[v]=dis[u]+edge[k].d; if (!inQ[v]) inQ[v]=true,Q.push(v); } } } return ans;}int main(){ int N,M,A,K,u,v,d,ans; while (~scanf("%d%d%d%d",&N,&M,&A,&K) && N) { ne=0,memset(_next,0,sizeof(_next)); while (M--) { scanf("%d%d%d",&u,&v,&d); addedge(u,v,d),addedge(v,u,d); } memset(f,false,sizeof(f)),ans=N; memset(dis,-1,sizeof(dis)); while (A--) { scanf("%d",&u); ans-=SPFA(u,K); printf("%d\n",ans); } printf("\n"); } return 0;}

Intergalactic Mortgage

题意:

现在找银行贷款了X元..每年利率为r%(会利滚利)..现在每个月还银行Y元..问N年后..能否还清贷款..

题解:

推出公式:  Xn=(X0+Y/-r/1200)*(1+r)^(12*n)...只要判断Xn的正负即可...(r=0单独讨论)...非常暴力..次方这么多居然还有精度..

#include#include#include#include#include#include#include#include#include#define ll long long#define oo 1<<29#define pi acos(-1.0)#define eps 1e-11#define MAXN 1005 using namespace std;int main(){ int n,i; double x,y,r,A,F; while (~scanf("%lf%lf%d%lf",&x,&y,&n,&r) && n) { if (abs(r)

Ambiguous Result

题意:

给出一个表达式..只有+与*号..现在可以任意加括号..问能得到的最小值和最大值分别是多少..

题解:

简单的区间DP

Program:

#include#include#include#include#include#include#include#include#include#define ll long long#define oo 1<<29#define pi acos(-1.0)#define MAXN 105using namespace std;ll dp[MAXN][MAXN][2],tp[MAXN],h[MAXN];void dfs(int l,int r){ if (l==r) { dp[l][r][0]=dp[l][r][1]=h[l]; return; } if (r-1==l) { if (!tp[l]) dp[l][r][0]=dp[l][r][1]=h[l]+h[r]; else dp[l][r][0]=dp[l][r][1]=h[l]*h[r]; return; } for (int mid=l;middp[l][mid][0]+dp[mid+1][r][0]) dp[l][r][0]=dp[l][mid][0]+dp[mid+1][r][0]; if (dp[l][r][1]<0 || dp[l][r][1]dp[l][mid][0]*dp[mid+1][r][0]) dp[l][r][0]=dp[l][mid][0]*dp[mid+1][r][0]; if (dp[l][r][1]<0 || dp[l][r][1]='0' && s[i]<='9') h[n]=h[n]*10+s[i]-'0',i++; if (s[i]=='+') tp[n]=0; else tp[n]=1; } memset(dp,-1,sizeof(dp)); dfs(1,n); printf("%lld %lld\n",dp[1][n][0],dp[1][n][1]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：数据
上一篇:跟着“种草笔记”买买买？当心碰上虚假营销！
下一篇:hadoop由于NodeManager无法启动而导致执行Jar包出现running job卡住的解决方案之一...
相关文章

 发表评论

暂时没有评论，来抢沙发吧~