CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Decoding Baby Boos
另解：使用链表快速合并。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
char s[1000009],a[9],b[9];
int t,r;
int main()
{
for(scanf("%d",&t); t--;)
{
vector<list<int> > l(99);
scanf("%s%d",s,&r);
for(int i=0; s[i]; ++i)
l[s[i]].push_back(i);
for(; r--; l[a[0]].splice(l[a[0]].end(),l[b[0]]))
scanf("%s%s",a,b);
for(int i=0; i<l.size(); ++i)
for(list<int>::iterator it=l[i].begin(); it!=l[i].end(); ++it)
s[*it]=i;
printf("%s\n",s);
}
}
And Or
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
long long t,kase,a,b,ansOr,ansAnd;
int main()
{
for(scanf("%lld", &t); t--;)
{
scanf("%lld%lld",&a,&b);
ansAnd=a,ansOr=a;
for(int i=0; !(a>>i&1)&&i<63; ++i)
if(b-a>=1LL<<i)ansOr|=1LL<<i;
for(; a<=b; a+=a&-a)
ansOr|=a,ansAnd&=a;
printf("Case %lld: %lld %lld\n",++kase,ansOr,ansAnd);
}
}
A game for kids
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define mul(a,b,c) (1LL*(a)*(b)%(c))
using namespace std;
const int M=21092013,H=51;
struct GCD
{
int a[H][H];
GCD()
{
for(int i=1; i<H; ++i)
for(int j=i; j<H; ++j)
a[i][j]=a[j][i]=__gcd(i,j);
}
} gcd;
#define __gcd(i,j) gcd.a[i][j]
struct Graph
{
struct Vertex
{
vector<int> a,f;
int l,h;
Vertex():f(H,0) {}
};
struct Edge
{
int from,to;
};
vector<Vertex> v;
vector<Edge> e;
vector<int> ans;
Graph(int n):v(n),ans(H,0) {}
void add(const Edge &ed)
{
v[ed.from].a.push_back(e.size());
e.push_back(ed);
}
void dfs(int u,int fa)
{
for(int i=0,to,g; i<v[u].a.size(); ++i)
if(to=e[v[u].a[i]].to,to!=fa)
{
dfs(to,u);
for(int j=1; j<H; ++j)
for(int k=1; k<H; ++k)
g=__gcd(j,k),ans[g]=(ans[g]+mul(v[to].f[k],v[u].f[j],M))%M;
for(int k=1; k<H; ++k)
for(int j=v[u].l; j<=v[u].h; ++j)
g=__gcd(j,k),v[u].f[g]=(v[u].f[g]+v[to].f[k])%M;
}
for(int i=v[u].l; i<=v[u].h; ++i)v[u].f[i]=(v[u].f[i]+1)%M;
}
};
int main()
{
int t,n,kase=0;
for(scanf("%d",&t); t--;)
{
printf("Case %d:\n",++kase);
scanf("%d",&n);
Graph g(n);
for(int i=1,u,v; i<n; ++i)
scanf("%d%d",&u,&v),g.add({u-1,v-1}),g.add({v-1,u-1});
for(int i=0; i<n; ++i)scanf("%d",&g.v[i].l);
for(int i=0; i<n; ++i)scanf("%d",&g.v[i].h);
g.dfs(0,-1);
for(int i=1; i<H; ++i)
{
for(int j=0; j<n; ++j)g.ans[i]=(g.ans[i]+g.v[j].f[i])%M;
printf("%d: %d\n",i,g.ans[i]);
}
}
}
Refraction
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
#include<math.h>
double EPS=3e-6,W,H,x,xe,ye,mu;
int t;
int main()
{
for(scanf("%d",&t); t--;)
{
scanf("%lf%lf%lf%lf%lf%lf",&W,&H,&x,&xe,&ye,&mu);
double tanH=(ye-H)/(xe-W),E=asin(1)-atan(tanH),sinCPN=sin(E)/mu,
tanCPN=tan(asin(sinCPN)),h=(tanH*(W-x)-H)/(tanH*tanCPN-1);
if(h-EPS>H)printf("Impossible\n");
else printf("%.4f\n",h);
}
}
Load Balancing
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
#include<math.h>
#define M 161
double f[M][4],d;
int t,n,kase,s[M],p[M][4];
void print(int i,int j)
{
if(!j)return;
print(p[i][j],j-1);
printf(" %d",p[i][j]);
}
int main()
{
for(scanf("%d",&t); t--; printf("Case %d:",++kase),print(M-1,3),printf("\n"))
{
scanf("%d", &n);
for(int i=0; i<M; ++i)s[i]=0;
for(int i=0,c; i<n; ++i)scanf("%d",&c),++s[c];
for(int i=1; i<M; ++i)s[i]+=s[i-1];
for(int i=0; i<M; ++i)
{
f[i][0]=fabs(s[i]-n/4.0),f[i][1]=f[i][2]=f[i][3]=1e9;
for(int j=1; j<4; ++j)
for(int k=0; k<i; ++k)
if(d=fabs(s[i]-s[k]-n/4.0),f[i][j]>f[k][j-1]+d)
f[i][j]=f[p[i][j]=k][j-1]+d;
}
}
}
Maximum Score
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
#define mul(a,b,c) ((a)*(b)%(c))
using namespace std;
typedef unsigned long long ll;
const ll N=1e5+7,M=1e9+7;
pair<ll,ll> p[N];
ll t,n,kase;
int main()
{
for(scanf("%llu",&t); t--;)
{
scanf("%llu",&n);
for(ll i=0; i<n; ++i)
scanf("%llu%llu",&p[i].first,&p[i].second);
sort(p,p+n);
ll sum=p[0].second,ans=sum*p[0].second,per=1;
for(ll i=1; i<n; ++i)
{
sum+=p[i].second;
ans=ans+sum*p[i].second;
per=mul(per,p[i-1].second+1,M);
}
printf("Case %llu: %llu %llu\n",++kase,ans,per);
}
}