Codeforces Beta Round #67 (Div. 2)
http://codeforces.com/contest/75
A
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
int a,b,c;
cin>>a>>b;
c=a+b;
int ccc=;
int aa=,bb=,cc;
int p=;
while(a){
int tmp=a%;
if(tmp!=){
aa+=(tmp)*p;
p*=;
}
a/=;
}
p=;
while(b){
int tmp=b%;
if(tmp!=){
bb+=(tmp)*p;
p*=;
}
b/=;
}
p=;
while(c){
int tmp=c%;
if(tmp!=){
ccc+=(tmp)*p;
p*=;
}
c/=;
}
cc=aa+bb;
if(cc==ccc) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
B
模拟
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
string me;
cin>>me;
int n;
cin>>n;
map<string,int>M,S{{"posted",},{"commented",},{"likes",}};
for(string a,b,c,x;cin>>a>>b>>c>>x;M[a],M[c])
{
if(c=="on")c=x,cin>>x;
c.pop_back();c.pop_back();
if(a==me)M[c]+=S[b];
if(c==me)M[a]+=S[b];
}
vector<pair<int,string>>V;
for(map<string,int>::iterator it=M.begin();it!=M.end();it++)V.emplace_back(-it->second,it->first);
sort(V.begin(),V.end());
for(int i=;i<V.size();i++)if(V[i].second!=me)cout<<V[i].second<<endl;
}
C
二分+gcd
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; int aa,bb,l,r,x,y;
int a[]; int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>aa>>bb;
int n;
cin>>n;
int gcd=__gcd(aa,bb);
int co=;
int gg=sqrt(gcd);
a[co++]=;
for(int i=;i<=gg;i++){
if(gcd%i==){
a[co++]=i;
if(gcd/i!=gg){
a[co++]=gcd/i;
}
}
}
a[co++]=gcd;
sort(a+,a+co);
int mid;
for(int i=;i<=n;i++){
cin>>x>>y;
l=,r=co-;
while(l<=r){
mid=l+r>>;
if(a[mid]<=y) l=mid+;
else {
r=mid-;
}
}
if(a[r]>y) r--;
if(a[r]>=x&&a[r]<=y) cout<<a[r]<<endl;
else cout<<-<<endl;
}
}
D
应该是最大子段和的加强版吧，把最大前缀和，最大后缀和，最大子区间和求出来，然后找最大值
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; ll maxl[],maxr[],sum[],dp[],Right; int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
int num;
int x;
for(int i=;i<=n;i++){
cin>>num;
maxl[i]=dp[i]=-0x3f3f3f3f;
Right=;
for(int j=;j<=num;j++){
cin>>x;
sum[i]+=x;
maxl[i]=max(sum[i],maxl[i]);
Right+=x;
dp[i]=max(dp[i],Right);
if(Right<) Right=;
}
maxr[i]=Right;
}
ll ans=-0x3f3f3f3f;
Right=;
for(int i=;i<=m;i++){
cin>>x;
ans=max(max(ans,dp[x]),Right+maxl[x]);
Right=max(Right+sum[x],maxr[x]);
}
cout<<ans<<endl;
}
E
几何，分类讨论即可
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; struct Point{
double x,y;
}a[],h[],s,e;
double ans;
int p[],n,m; double dis(Point a, Point b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
} double cross(Point s, Point a, Point b) {
return (a.x - s.x) * (b.y - s.y) - (b.x - s.x) * (a.y - s.y);
} void check(Point a, Point b, Point c, Point d, int i) {
double t1 = cross(a, c, b), t2 = cross(a, b, d), t3 = cross(c, a, d), t4 = cross(c, d, b);
if (fabs(t1) < eps && fabs(t2) < eps) return ;
if (fabs(dis(a, c) + dis(c, b) - dis(a, b)) < eps) {
h[m] = c; p[m] = i; ++m; return ;
}
if (t1 * t2 > eps && t3 * t4 > eps) {
h[m].x = (t1 * d.x + t2 * c.x) / (t1 + t2);
h[m].y = (t1 * d.y + t2 * c.y) / (t1 + t2);
p[m] = i; ++m;
}
} double getl(int st, int en, int x, int y) {
double res; st = (st + ) % n; res = ;
for (int i = st; i != en; i = (i + ) % n)
res += dis(a[i], a[(i + ) % n]);
return res + dis(h[x], a[st]) + dis(a[en], h[y]);
} int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
// std::ios::sync_with_stdio(false);
cin>>s.x>>s.y>>e.x>>e.y>>n;
for (int i = ; i < n; ++i) cin>>a[i].x>>a[i].y;
for (int i = ; i < n; ++i) check(s, e, a[i], a[(i + ) % n], i);
if (m == ) {
if (dis(s, h[]) > dis(s, h[])) swap(h[], h[]), swap(p[], p[]);
ans = min(getl(p[], p[], , ), getl(p[], p[], , ));
ans = min(ans, dis(h[], h[]) * );
ans += dis(s, h[]) + dis(h[], e);
}
else ans = dis(s, e);
printf("%.7f\n",ans);
}