题目整理:UVA 11977 - 11896

本文从WordPress迁移而来, 查看全部WordPress迁移文章

H: uva 11984 A Change in Thermal Unit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <cstring>
using namespace std;

int main(){
int T;
double c,f,d;
scanf("%d",&T);
for(int cas = 1; cas <= T; cas++){
scanf("%lf%lf",&c,&d);
f = 9.0 / 5.0 * c + d;
c = f / (9.0 / 5.0);
printf("Case %d: %.2lf\n",cas,c);
}
return 0;
}

C. uva 11979 Hamming Base

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 2010

int n,m,a[N][N],b[N];

int main(){
int T;
scanf("%d",&T);
for(int cas = 1; cas <= T; cas++){
scanf("%d%d",&n,&m);
for(int i = 0 ; i < n; i++)
for(int j = 0; j < m; j++)
scanf("%d",&a[i][j]);
int ans = 0;
for(int j = 0; j < m; j++){
for(int i = 0; i < n; i++)
b[i] = a[i][j];
sort(b,b+n);
for(int i = 0; i < n; i++)
ans += abs(i-b[i]);
}
printf("Case %d: %d\n",cas,ans);

}
return 0;
}

J. uva 11986 Save from Radiation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
using namespace std;
#define LL long long

int main(){
int T;
LL n;
scanf("%d",&T);
for(int cas = 1; cas <= T; cas++){
scanf("%lld",&n);
int ans = 0;
while(n){
n >>= 1; ans++;
}
printf("Case %d: %d\n",cas,ans);
}
return 0;
}

E. uva 11981 Corrupted Friendship

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
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 100010
#define LL long long
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

vector<int>e[N];
int n,cnt[N]; LL ans;

void dfs(int u,int dep){
cnt[u] = 0;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
dfs(v,dep+1);
cnt[u] += cnt[v];
}
cnt[u]++;
ans += (n-dep-cnt[u]);
}

int main(){
int T,cas = 0;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i = 1; i <= n; i++)
e[i].clear();
for(int i = 1; i < n; i++){
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v);
}
ans = 0;
dfs(1,0);
printf("Case %d: %d %lld\n",++cas,n-1,ans/2);
}
return 0;
}

I. uva 11985 Prime Independence

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <cstdio>
#include <cstring>
using namespace std;
#define N 40010
#define M 10000010
#define MAX 500010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int a[N],n;
int used[MAX]; //输入中用了哪些数字
bool prime[MAX]; //标记数字是素数
int fac[MAX][30],fn[MAX]; //每个数字有多少种不同的质因子
int cnt[MAX]; //记录每个数字的质因子个数(个数不是种数)
int p[MAX],pn; //保存素数
bool vis[N]; //二分图匹配
int tot,head[N],match[N];
struct edge{
int u,v,next;
}e[M];

void init(){
pn = 0; cl(prime,true); cl(fn,0); cl(cnt,0);
for(int i = 2; i <= 1000; i++)
if(prime[i]){
p[pn++] = i;
for(int j = i+i; j <= 1000; j += i)
prime[j] = false;
}
for(int i = 2; i < MAX; i++){
for(int j = 0; j < pn && p[j] < i; j++)
if(i % p[j] == 0){
cnt[i] = cnt[i/p[j]] + 1;
break;
}
if(cnt[i] == 0) cnt[i]++;
int x = i;
for(int j = 0; j < pn && p[j]*p[j] <= x; j++)
if(x % p[j] == 0){
fac[i][fn[i]++] = p[j];
while(x % p[j] == 0) x /= p[j];
}
if(x > 1) fac[i][fn[i]++] = x;
}
/*
for(int i = 2; i < MAX; i++){
int x = i;
for(int j = 0; j < pn && p[j]*p[j] <= x; j++)
if(x % p[j] == 0){
fac[i][fn[i]++] = p[j];
while(x % p[j] == 0) x /= p[j];
}
if(x > 1) fac[i][fn[i]++] = x;
}
*/
/*
for(int i = 2; i <= 30; i++){
printf("%d : %d\n",i,cnt[i]);
for(int j = 0 ; j < fn[i]; j++)
printf("%d ",fac[i][j]);
puts("");
}
for(int i = 499990; i <= 500000; i++){
printf("%d : %d\n",i,cnt[i]);
for(int j = 0 ; j < fn[i]; j++)
printf("%d ",fac[i][j]);
puts("");
}
*/
}

inline void add(int u,int v){
e[tot].u = u; e[tot].v = v;
e[tot].next = head[u]; head[u] = tot++;
}

int dfs(int u){
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(!vis[v]){
vis[v] = true;
if(match[v] == -1 || dfs(match[v])){
match[v] = u; return 1;
}
}
}
return 0;
}

int MaxMatch(){
int ans = 0;
cl(match,-1);
for(int u = 1; u <= n; u++){
cl(vis,false);
ans += dfs(u);
}
return ans;
}

int main(){
init();
int T,cas = 0;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
cl(used,-1);
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
used[a[i]] = i;
}
/*
for(int i = 1; i <= n; i++){
printf("%d : ",a[i]);
printf("cnt = %d\n",cnt[a[i]]);
for(int k = 0 ; k < fn[a[i]]; k++)
printf("%d ",fac[a[i]][k]);
puts("");
}
*/
tot = 0; cl(head,-1);
for(int i = 1; i <= n; i++){
for(int j = 0; j < fn[a[i]]; j++){
int s = a[i] / fac[a[i]][j];
if(used[s] == -1) continue;
if(cnt[a[i]] & 1) add(used[a[i]] , used[s]);
else add(used[s] , used[a[i]]);
}
}

int ans = MaxMatch();
printf("Case %d: %d\n",++cas,n-ans);
}
return 0;
}