首页 > 代码库 > Codeforces Round #367 (Div. 2) ABCD
Codeforces Round #367 (Div. 2) ABCD
A. Beru-taxi
题解:
水，求下距离就行了
代码:
#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 #define INF 2097152typedef pair<int,int> P;const double eps=1e-9;const int maxn=1050;const int mod=1e9+7;ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}//-----------------------------------------------------------------------------double sum(int a,int b,int c,int d){ return(sqrt((d-b)*(d-b)+(c-a)*(c-a)));}int main(){ int a,b; double c,d,e,tim=mod; cin>>a>>b; int n; cin>>n; for(int i=1;i<=n;i++) { cin>>c>>d>>e; tim=min(tim,sum(a,b,c,d)/e); } cout<<setprecision(20)<<tim<<endl;}
B. Barnicle
题解:
水，求小于等mi的个数，二分即可
代码:
#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 #define INF 2097152typedef pair<int,int> P;const double eps=1e-9;const int maxn=100010;const int mod=100100;ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}//-----------------------------------------------------------------------------int a[maxn];int main(){ int n,q,m; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); scanf("%d",&q); for(int i=1;i<=q;i++) { scanf("%d",&m); int num=upper_bound(a+1,a+n+1,m)-a; num--; printf("%d\n",num); }}
C. Hard problem
题解:
简单dp，当时状态不好没有做出来。
dp[i][j] 表示第i个字符反转还是不反转时的最小花费。线性dp就行了
代码:
#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 #define INF 1e18typedef pair<int,int> P;const double eps=1e-9;const int maxnnode=11000;const int maxn=100000+10;const ll mod=1000000007;ll c[maxn];string a[maxn],b[maxn];ll dp[maxn][2];int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>c[i]; for(int i=1;i<=n;i++) { cin>>a[i]; reverse(a[i].begin(),a[i].end()); b[i]=a[i]; reverse(a[i].begin(),a[i].end()); } for(int i=1;i<=n;i++) for(int j=0;j<2;j++) dp[i][j]=INF; dp[1][0]=0;dp[1][1]=c[1]; int flag=1; for(int i=2;i<=n;i++){ int Flag=0; if(a[i]>=a[i-1]&&a[i]>=b[i-1]) dp[i][0]=min(dp[i-1][0],dp[i-1][1]),Flag=1; if(a[i]>=a[i-1]&&a[i]<b[i-1]) dp[i][0]=dp[i-1][0],Flag=1; if(a[i]<a[i-1]&&a[i]>=b[i-1]) dp[i][0]=dp[i-1][1],Flag=1; if(b[i]>=a[i-1]&&b[i]>=b[i-1]) dp[i][1]=min(dp[i-1][0],dp[i-1][1])+c[i],Flag=1; if(b[i]>=a[i-1]&&b[i]<b[i-1]) dp[i][1]=dp[i-1][0]+c[i],Flag=1; if(b[i]<a[i-1]&&b[i]>=b[i-1]) dp[i][1]=dp[i-1][1]+c[i],Flag=1; if(!Flag){ flag=0; break; } } if(flag){ if(min(dp[n][1],dp[n][0])>=INF) cout<<-1<<endl; else cout<<min(dp[n][1],dp[n][0])<<endl; } else cout<<-1<<endl;}
D. Vasiliy‘s Multiset
题解:
字典树典型题，，我字典树还不是很熟练啊。不怎么会灵活应用。。
关于位运算符也不是太熟悉
其实就是将数分为二进制的形式，然后从高位向地位保存在字典树种。
在保存的过程中，所经过的每个节点都记录次数
那么"+"就是Insert(x,1);
"-"就是Insert(x,-1);
代码:
#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 #define INF 1e18typedef pair<int,int> P;const double eps=1e-9;const int maxnnode=11000;const int maxn=1e7+10;const ll mod=1000000007;struct Trie{ int ch[maxn][2]; int val[maxn]; int sz; void Clear(){sz=1;CLR(ch[0]);CLR(val);} void Insert(int x,int id){ int u=0; for(int i=29;~i;--i){ int y=x>>i&1; if(!ch[u][y]){ CLR(ch[sz]); val[sz]=0; ch[u][y]=sz++; } u=ch[u][y]; val[u]+=id; } } int Check(int x){ int ret=0,u=0; for(int i=29;~i;--i){ int y=x>>i&1; if(!ch[u][y]||!val[ch[u][y]]) y^=1; else ret|=1<<i; u=ch[u][y]; } return ret; }};Trie T;int main(){ int q; scanf("%d",&q); T.Clear(); T.Insert(0,1); for(int i=1;i<=q;i++){ char c; int t; scanf(" %c %d",&c,&t); if(c==‘+‘) T.Insert(t,1); if(c==‘-‘) T.Insert(t,-1); if(c==‘?‘) printf("%d\n",T.Check(~t)); }}
Codeforces Round #367 (Div. 2) ABCD
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。