第一次双周赛+基础存图-创新互联
第一次双周赛+基础存图
#include
using namespace std;
char str1[1005],str2[1005];
int a[1005],b[1005],c[2010];
int zhuan(char c) //写个函数把字符转换为十进制
{
if(c>='0' && c<='9')
return c-'0';
else
return c-'A'+10;
}
int main()
{
cin>>str1>>str2;
int len1=strlen(str1);
for(int i=0;i a[i+1]=zhuan(str1[len1-i-1]); int len2=strlen(str2); for(int i=0;i b[i+1]=zhuan(str2[len2-i-1]);//把两个字符串倒序放入 int flag=0;//进位数 for(int i=1;i<=len1;++i) { flag=0;//注意每次清零 for(int j=1;j<=len2;++j) { c[i+j-1]+=a[i]*b[j]+flag; flag=c[i+j-1]/16; c[i+j-1]%=16; } c[i+len2]=flag; }//高精度相乘 int len3=len1+len2; while(c[len3]==0 && len3>1) len3--; for(int i=len3;i>=1;i--) { if(c[i]>=0 && c[i]<=9) cout< else cout<<(char)(c[i]-10+'A'); }//再把这个数转为16进制 return 0; } 查找每一个答案即可 #include using namespace std; int n,m,a[100005],y; bool check(int x) { int t = 0; for (int i = 1; i<= n; i++) { if (a[i]< t)//装不完弹就挂了 return false; if (a[i]<= t + m)//装完弹且在射程内 t += x; else { t += (a[i] - t - m);//装完弹还不在射程内 t += x; } } return true; } int main() { cin>>n>>m; for (int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); int L=0,R=a[n]; while (L+1 { int mid=(L+R)/2; if (check(mid)) L=mid; else R=mid; }//二分答案 cout< } 第四题：反向链表 #include const int X=1e5+5; using namespace std; int main(){ int Data[X],Next[X],list[X]; int FirstAdd,N,K; cin>>FirstAdd>>N>>K; for(int i=0;i { int tmpAdd,tmpData,tmpNext; cin>>tmpAdd>>tmpData>>tmpNext; Data[tmpAdd] = tmpData; Next[tmpAdd] = tmpNext; } int sum=0; // 累计有效结点数 while(FirstAdd!=-1) { // 当尾结点为 -1 时结束 list[sum++] = FirstAdd; // 记录所有Address FirstAdd = Next[FirstAdd]; // 找下一个结点 } for(int i=0;i ){ // 每 K 个结点一个区间 for(int j=0;j { // 反转链表 int t = list[i+j]; list[i+j] = list[i+K-j-1]; list[i+K-j-1] = t; } } for(int i=0;i printf("%05d %d %05d\n",list[i],Data[list[i]],list[i+1]); printf("%05d %d -1\n",list[sum-1],Data[list[sum-1]]); return 0; } #include using namespace std; const double N=1e-7; double a,b,c,d,p,q; int T; double check(double l,double r) { double x1=a*r*r*r+b*r*r+c*r+d;//右边界验证 while(r-l>N) { double mid=(r+l)/2; double x2=a*mid*mid*mid+b*mid*mid+c*mid+d;//判断中点 if (x1*x2<0) l=mid;//两点乘积小于零那么往右找 else r=mid;//否则往左找 } } int main() { cin>>T; while(T--) { cin>>a>>b>>c>>d>>p>>q; double j1=((-2*b)-sqrt(4*b*b-12*a*c)) / (6*a); double j2=((-2*b)+sqrt(4*b*b-12*a*c)) / (6*a); //先求导然后就可以分出三个区间 if (j1>j2) swap(j1,j2);//确保区间区间是递增的 printf("%.6lf %.6lf %.6lf",check(p,j1),check(j1,j2),check(j2,q));//分区间查找一下 } } 看了学长的教学就会了 #include using namespace std; const int N=1005; vector bool vis[N]; int st,ed,sum,cnt[N],n,m,x,y; void dfs(int now) { if (now==ed)//走到终点 { sum++; for (int i=1;i<=n;i++) if (vis[i]) cnt[i]++;//标记走过几次 return; } for (int i=0;i { int to =G[now][i];//下一步 if (!vis[to])//判断没走过 { vis[to]=true;//标记为走过 dfs(to);//接着搜下一步 vis[to]=false;//再次标记为没走过 } } } int main() { cin>>n>>m; for (int i=1;i<=m;i++) { cin>>x>>y; G[x].push_back(y); G[y].push_back(x);//无向图基础存图 } cin>>st>>ed; vis[st]=true;//把起点标记为走过 dfs(st); int ans=0; for (int i=1;i<=n;i++) { if (cnt[i]==sum) ans++; } ans=ans-2;//减去起点和终点 cout< return 0; } 这题知道反向dfs后就简单了，连我都独立搞定了 #include using namespace std; const int N=100005; int u,v,n,m,vis[N],ans[N]; vector void dfs(int x,int y) { if (vis[x]) return; ans[x]=y;//把第几个点序号放入ans数组 vis[x]=true;//标记为走过 for (int i=0;i dfs(G[x][i],y);//把第x行的图搜一遍 } int main() { cin>>n>>m; for (int i=1;i<=m;i++) { cin>>u>>v; G[v].push_back(u); //反向存 } //有向图基础存图 for (int i=n;i>=1;i--) dfs(i,i);//从后往前搜 for (int i=1;i<=n;i++) cout< return 0; } #include using namespace std; const int N = 10010; int n, m; vector bool vis[N]; int a[N],sum[3]; bool dfs(int now, int col) { vis[now] = true;//标记走过 a[now] = col; sum[col]++; for (int i = 0; i< g[now].size(); i++) { int to = g[now][i];//下一步 if (vis[to] && a[to] == a[now]) return false;//相邻了，不行 else if (!vis[to]) { if (!dfs(to, 3 - col)) return false; } } return true; } int main() { cin>>n>>m; for (int i = 1; i<= m; i++) { int u, v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); }//存图 int ans = 0; for (int i = 1; i<= n; i++) if (!vis[i])//没走过 { sum[1] = sum[2] = 0; if (!dfs(i,1)) { printf("Impossible"); return 0; }//没有符合条件的情况 ans += min(sum[1], sum[2]);//加上小的那个 } cout< return 0; } 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文名称：第一次双周赛+基础存图-创新互联
文章网址：http://6mz.cn/article/dpdico.html