Codeforces Beta Round #57 (Div. 2)

http://codeforces.com/contest/61

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 1000005
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; string s1,s2; int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>s1>>s2;
rep(i,,s1.length()){
if(s1[i]==s2[i]){
cout<<;
}
else cout<<;
}
}

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 1000005
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; string s[];
map<string,int>mp; int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
string str;
rep(i,,){
s[i]="";
cin>>str;
rep(j,,str.length()){
if(str[j]>='A'&&str[j]<='Z') str[j]+=;
if(str[j]>='a'&&str[j]<='z') s[i]+=str[j];
}
}
int n;
cin>>n;
string ss;
mp[s[]]=,mp[s[]]=,mp[s[]]=;
mp[s[]+s[]]=;mp[s[]+s[]]=;mp[s[]+s[]]=;mp[s[]+s[]]=;mp[s[]+s[]]=;mp[s[]+s[]]=;
mp[s[]+s[]+s[]]=;mp[s[]+s[]+s[]]=;mp[s[]+s[]+s[]]=;mp[s[]+s[]+s[]]=;mp[s[]+s[]+s[]]=;mp[s[]+s[]+s[]]=;
while(n--){
cin>>str;
ss="";
rep(i,,str.length()){
if(str[i]>='A'&&str[i]<='Z') str[i]+=;
if(str[i]>='a'&&str[i]<='z') ss+=str[i];
}
if(mp[ss]) cout<<"ACC"<<endl;
else cout<<"WA"<<endl;
}
}

C

进制模拟

 #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 1000005
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; string a[]={"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int v[]={,,,,,,,,,,,,};
string val[]; string roman(int n) {
string ret="";
for(int i=;i<;i++)
while(n>=v[i]) {
n-=v[i];
ret += a[i];
}
return ret;
}
void pre() {
for(int i=;i<=;i++)
val[i] = roman(i);
} char c[], B[];
int A; int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
pre();
cin>>A>>B>>c;
long long v = ;
for(int i=;c[i];i++) {
v=v*A + (c[i]>='A'? c[i]-'A'+: c[i]-'');
}
if(B[]=='R') cout<<val[v].c_str()<<endl;
else {
char d[];
int dn=, base = atoi(B);
if(v==) {
d[dn++]=;
}
while(v>) {
d[dn++]=v%base;
v/=base;
}
while(dn-->) cout<<char(d[dn]>=? d[dn]-+'A': d[dn]+'');
cout<<endl;
}
}

D

通过模拟找规律可以发现,最短距离为所有的距离之和*2减去根结点下的最长链

 #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 1000005
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; int n;
vector<pair<int,ll> >ve[]; int dfs(int pos,int pre){
ll Max=;
ll tmp;
ll now;
rep(i,,ve[pos].size()){
if(ve[pos][i].first!=pre){
now=ve[pos][i].second;
tmp=dfs(ve[pos][i].first,pos);
if(tmp+now>Max){
Max=tmp+now;
}
}
}
return Max;
} int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n;
int u,v;
ll w;
ll sum=;
rep(i,,n){
cin>>u>>v>>w;
sum+=w;
ve[u].pb(make_pair(v,w));
ve[v].pb(make_pair(u,w));
}
sum+=sum;
int Max=;
ll tmp;
rep(i,,ve[].size()){
tmp=dfs(ve[][i].first,);
if(tmp+ve[][i].second>Max){
Max=tmp+ve[][i].second;
}
}
cout<<sum-Max<<endl;
}

E

找三元祖,问前面比a[i]大且后面比a[i]小的三元组有多少个

直接上树状树组,离散化后枚举每个点,找出前面比它大的数,然后乘上后面比它小的数即可,会爆int

 #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 rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; int tree[maxn]; int lowbit(int x){
return x&(-x);
} void update(int x){
while(x<maxn){
tree[x]+=;
x+=lowbit(x);
}
} int query(int x){
int ans=;
while(x){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
} int a[maxn];
int n;
vector<int>ve; int getpos(int x){
return lower_bound(ve.begin(),ve.end(),x)-ve.begin()+;
} ll pre[maxn]; int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n;
rep(i,,n+){
cin>>a[i];
ve.pb(a[i]);
}
sort(ve.begin(),ve.end());
ve.erase(unique(ve.begin(),ve.end()),ve.end());
int pos;
update(getpos(a[]));
ll ans=;
rep(i,,n){
pos=getpos(a[i]);
pre[i]=query(maxn-)-query(pos);
// cout<<query(maxn-1)<<" "<<query(pos)<<endl;
update(pos);
///
// cout<<pre[i]<<" "<<((n-i)-(n-pos-pre[i]))<<endl;
ans+=pre[i]*(-i+pos+pre[i]);
}
cout<<ans<<endl;
}
05-11 09:36
查看更多