首页 > 代码库 > 暑假集训cf50练之7
暑假集训cf50练之7
Codeforces Round #409
第一题很水但是wa了一发，因为没考虑K前面是K的情况
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cassert> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-9; const int N=2000+10,maxn=500+100,inf=0x3f3f3f; bool vis[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin>>s; int ans=0; for(int i=0;i<s.size()-1;i++) { if(s[i]==‘V‘&&s[i+1]==‘K‘) { vis[i]=vis[i+1]=1; ans++,i++; } } for(int i=0;i<s.size()-1;i++) if(!vis[i]&&!vis[i+1]&&s[i]==‘V‘) { cout<<ans+1<<endl; return 0; } for(int i=1;i<s.size();i++) if(!vis[i]&&!vis[i-1]&&s[i]==‘K‘) { cout<<ans+1<<endl; return 0; } cout<<ans<<endl; return 0; }
第二题也很水1a
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cassert> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-9; const int N=100000+10,maxn=500+100,inf=0x3f3f3f; int main() { ios::sync_with_stdio(false); cin.tie(0); string x,z,y=""; cin>>x>>z; bool f=0; for(int i=0;i<x.size();i++) { if(x[i]>=z[i])y+=z[i]; else f=1; } if(f)cout<<-1<<endl; else cout<<y<<endl; return 0; }
第三题因为精度问题，一直wa到最后。。。。最后看别人代码时发现用k记录二分的次数，次数够大就输出-1退出，居然还有这种骚操作，唉，我居然给忘记了
话说一开始就想到二分也不错了，虽然改了很多发还是wa在第74个点
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cassert> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-4; const int N=100000+10,maxn=500+100,inf=0x3f3f3f; double a[N],b[N],p; int n; bool ok(double x) { double s=0,time=0; for(int i=1;i<=n;i++) { if(b[i]-a[i]*x<0) { time+=(a[i]*x-b[i])/p; if(time>x)return 0; } } return 1; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout<<setiosflags(ios::fixed)<<setprecision(8); cin>>n>>p; for(int i=1;i<=n;i++)cin>>a[i]>>b[i]; double l=0.0,r=1e15+10; int ans=0; while(r-l>eps){ ans++; if(ans>100) { cout<<-1<<endl; return 0; } double m=(l+r)/2; if(ok(m))l=m; else r=m; } if(l>1e15)cout<<-1<<endl; else cout<<l<<endl; return 0; }
第四题没想到会这么水，一开始想错了，后来看了样例的解释就明白了，枚举每个点到左右两边的距离的一半的最小值就是答案了
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cassert> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-4; const int N=100000+10,maxn=500+100,inf=0x3f3f3f; double x[N],y[N]; double dis(int a,int b,int c) { double B=sqrt((y[c]-y[a])*(y[c]-y[a])+(x[c]-x[a])*(x[c]-x[a])); double A=(y[c]-y[a])*x[b]-(x[c]-x[a])*y[b]-(y[c]-y[a])*x[c]+(x[c]-x[a])*y[c]; double ans=A/B; if(ans<0)ans=-ans; return ans/2; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout<<setiosflags(ios::fixed)<<setprecision(10); int n; cin>>n; for(int i=1;i<=n;i++)cin>>x[i]>>y[i]; double ans=1e18; for(int i=1;i<=n;i++) { int x1=i-1,x2=i,x3=i+1; if(x1==0)x1=n; if(x3==n+1)x3=1; ans=min(ans,dis(x1,x2,x3)); } cout<<ans<<endl; return 0; }
暑假集训cf50练之7
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。