新鲜事
原文
984
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=10000010;
ll n,cnt,ans;
ll sl[maxn],head[maxn];
struct node{
int w,to,nt;
} e[maxn*2];
void add(int x,int y,int z){
cnt++;
e[cnt].to = y;
e[cnt].nt = head[x];
e[cnt].w = z;
head[x] = cnt;
}
void dfs(int x,int fa){
sl[x]=1;
for(int i=head[x];i;i=e[i].nt){
int to=e[i].to;
if(fa==to)
continue;
dfs(to,x);
sl[x] += sl[to];
ans += e[i].w*abs(2*sl[to]-n);
}
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs(1,0);
cout<<ans<<endl;
return 0;
}
新鲜事
原文
3381
#include <iostream>
using namespace std;
int k[27]={1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,1,2,3,1,2,3,4};
int u[27]={1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,8,8,8,8};
int main(){
string a;
while(cin>>a){
int s=k[a[0]-'a'];
for(int i=1;i<a.size();i++){
s+=k[a[i]-'a'];
if(u[a[i]-'a']==u[a[i-1]-'a'])
s+=2;
}
cout<<s<<endl;
}
return 0;
}
新鲜事
原文
239
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int M=20005;
int n,m,len;
int l[M],r[M],op[M],lsh[M*2],fa[M*2],d[M*2];
int val(int v) {
return lower_bound(lsh+1,lsh+1+len,v)-lsh;
}
int get(int x){
if(x==fa[x]) return x;
int root=get(fa[x]);
d[x] ^= d[fa[x]];
return fa[x]=root;
}
void merge(int x,int y,int v){
int fx=fa[x],fy=fa[y];
d[fx] = (v^d[x]^d[y]);
fa[fx]=fy;
}
int main(){
int i;
cin>>n>>m;
for(int i=1; i<=m; i++){
scanf("%d%d",&l[i],&r[i]),r[i]++;
char c[7];
scanf("%s",c);
if(c[0] == 'e')
op[i] = 1;
else
op[i] = 2;
lsh[i] = l[i];
lsh[i+m] = r[i];
}
sort(lsh+1,lsh+1+2*m);
len = unique(lsh+1,lsh+1+2*m) - lsh - 1;
for(i=1;i<=len;i++)
fa[i] = i;
for(i=1;i<=m;i++){
l[i] = val(l[i]);
r[i] = val(r[i]);
}
int flag = 1;
for(i=1;i<=m;i++) {
if(get(l[i]) != get(r[i])){
if(op[i] == 1)
merge(l[i],r[i],0);
else
merge(l[i],r[i],1);
}
else{
int v = d[l[i]]^d[r[i]];
if(v==1 && op[i]==1){
cout<<i-1;
flag=0;
break;
}
else if(v==0 && op[i]==2){
cout<<i-1;
flag = 0;
break;
}
}
}
if(flag)
cout<<m;
return 0;
}
