2014-01-17 UVA的几道题

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

12611 - Beautiful Flag

简单题,对于给出的比例,化到最简,否则会wa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
using namespace std;


int main(){
int RA,T;
cin >> T;
for(int cas = 1; cas <= T; cas++){
cin >> RA;
int length = RA * 5;
int width = length / 5 * 3;
int L = length / 20 * 9;
int R = length / 20 * 11;
printf("Case %d:\n",cas);
printf("%d %d\n",-L,width/2);
printf("%d %d\n",R,width/2);
printf("%d %d\n",R,-(width/2));
printf("%d %d\n",-L,-(width/2));
}
return 0;
}

12614 - Earn For Future

也是简单题,不过还想了一下子哈哈,因为一直是做and操作,那么无论怎么做,数字只可能越来越小,所以只需要找到最大的那个数字,输出即可,别的数字怎么做and操作都不可能超过它

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

int main(){
int n,T;
LL Max;
cin >> T;
for(int cas = 1; cas <= T; cas++){
Max = -1LL;
cin >> n;
while(n--){
LL x;
cin >> x;
Max = max(Max,x);
}
printf("Case %d: %lld\n",cas,Max);
}
return 0;
}

12619 - Just Make A Wish

对于给定的面积要怎么计算它有多少种不同矩形,那就是找出面积S有多少个约数

12的约数为1,2,3,4,6,12,方案数就是6

怎么计算一个数字有多少个约数?需要分解质因子

12 = 2 2 3 2的个数是2,3的个数1,所以方案数就是 (2+1)*(1+1)= 6

上面的这些都容易做到,其中对于一个数字n分解质因子的话,直接搞是O(sqrt(n)),这题有10^6次变化

所以每次都这样分解可能吃不消,我们先筛素数,把1000以内的素数保存下来(不需要保存1000000以内的),

方便我们每次分解素因子,效率能提高

接下来就是怎么应对每次的变换,如果每次变换后都重新计算一次,就TLE,做法是充分利用上一次的答案

例:

当前的面积是36 = 2233 方案数为(2+1)(2+1)=9

这次输入的G是3,也就是翻3倍,那么新的面积,分解质因子,就是 2 2 3 3 3,计算方案数就是(2+1)*(3+1)=12

如果这样做的话就是重新计算一次了

可以发现2这个质因子没有变化,我们不需要重复计算,里面上次的方案数9,可以这样计算

9 / (2+1) * (3+1) = 12 ,道理就很明显了,受影响的只是3这个因子,我们把上一次的方案数里面3的部分先除掉,

再乘上现在3个这部分

为了达到这个目的,我们需要一个统计数组来标记当前的面积每个质因子的个数

num[m]表示m这个质因子的数量,num[2]=5表示有5个2

__num[m]表示,对于当前给定的G,我们分解G,统计G里面质因子的情况

若G是整数,__num[m]就是正的,表示要乘上多少个这样的质因子

若G是负数,__num[m]就是负的,表示要除掉多少个这样的质因子

算完这一轮后,m这个因子的数量就是 num[m] = num[m] + __num[m]

对于上一次的方案数ans,计算本次的方案数就是 ans / (num[m]+1) * (num[m]+__num[m]+1)

当然,所有受影响的质因子都是这么做,注意只需要扫描受影响的质因子,如果全部都检查一遍,应该TLE的

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <vector>
#include <iterator>
#include <set>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define MOD 1000000007LL
#define MAX 1000010

bool isp[MAX];
int prime[1000010],pcnt;
int num[MAX],__num[MAX];

LL ANS,pre_res;
vector<int>fn;

void init(){
cl(isp,true);
isp[0] = isp[1] = false;
pcnt = 0;
for(int i = 2; i <= 1000000; i++){
if(!isp[i]) continue;
if(i <= 1000) prime[pcnt++] = i;
for(int j = i+i; j <= 1000000; j += i)
isp[j] = false;
}
}

void fun1(int val,int t){
fn.clear();
for(int i = 0 ; true ; i++){
if(isp[val]){
fn.pb(val);
__num[val] = 0;
__num[val] += t;
return;
}
if(val == 1 || i >= pcnt) break;
if((val % prime[i]) != 0) continue;
int m = prime[i];
fn.pb(m);
__num[m] = 0;
while(val % m == 0){
val /= m;
__num[m] += t;
}
}
}

LL pow_mod(LL a,LL m){
if(m == 1LL) return a;
LL temp = pow_mod(a,m/2);
temp = (temp * temp) % MOD;
if(m&1) temp = (temp * a) % MOD;
return temp;
}

LL cal(){
LL res = pre_res;
int size = fn.size();
for(int i = 0; i < size; i++){
int m = fn[i];
int d = num[m] + __num[m];
if(num[m] == 0){ //说明上一次没有这个因子
res = (res * (LL)(__num[m]+1)) % MOD; //这次肯定是增加的
}
else{
//先除掉 num[m]+1
LL temp = pow_mod( (LL)(num[m]+1) , MOD-2LL);
res = (res * temp) % MOD;
//乘上 d+1
res = (res * (LL)(d+1)) % MOD;
}

num[m] = d;
}
return res;
}

int main(){
init(); //分解出所有素数
int CASE;
scanf("%d",&CASE);
for(int cas = 1; cas <= CASE; cas++){
ANS = 0LL;
pre_res = 1LL;
cl(num,0);
int D;
scanf("%d",&D);
while(D--){
int G;
scanf("%d",&G);
int t = (G > 0 ? 1 : -1);
G = abs(G);
fun1(G,t); //分解
LL now = cal(); //计算当前有多少方案数
ANS = (ANS + now) % MOD;
//printf("%lld %lld %lld\n",pre_res,now,ANS);
pre_res = now;
}
printf("Case %d: %lld\n",cas,ANS);
}
return 0;
}

12616 - Gymman vs Fila

给一个无向图,无重边,无自环,但图不一定连通(连不连通对算法没影响,但是写起来就有点….)

选出3个点,a,b,c,a要和b通信,删掉c这个点的话,a无法与b通信,问这样的三元组有多少

其中 a=1,b=2,c=3 , a=2,b=1,c=3 算两种

当然 a=1,b=4,c=3 , a=1,b=5,c=3 也是不同的

另外,a,b,c必须在同一个连通块上(a,b不在同一个连通块上当然无法通信,但题目不考虑这种)

第一反应,c肯定就是割点了,删掉割点,图会断裂,假设图分为m块,那么a,b一定不在同一块上,那么怎么统计?

假设删掉c,图分为3块,每块的点数分别为2,3,4

方案数为 2 (3 + 4) + 3 (2 + 4) + 4 * (2 + 3)

这样我们的目的就是要知道所有的割点,并且知道删掉每个割点后,图分为几块,每块包含多少点数

求割点容易,求完割点,统计出每个连通分量也不难,但是要建树就要思考一下

用桥来分解无向图然后建树就很简单的,但是用割点来分割无向图得到的连通块就麻烦一些,

因为割点是可以属于多个点连通分量的,导致无法建树,解决方法是拆点(或者说虚构一些顶点)

例如

1是割点

有3个连通分量

1
2
3
I:1,2,3
II:1,4,5
III:1,6,7

我们虚构一个超顶点 1+MAX = 20001
然后 I,II,III,20001 都是之后树上的节点

1
2
3
连接方法就是  I --- 20001
II --- 20001
III --- 20001

显然就是 20001 这个超顶点把所有和1有关的连通块连接起来

并且我们要计算一些值

对于连通块我们记录的是这个连通块上,非割点的数量

对于虚构出来的超顶点,它的值就是1

为什么这样做,因为这样才能做到点数上不重不漏,

I,II,III都包含了1这个点,如果都计算就算了3次,所以都不算,就漏了,所以20001这个超顶点就算一次

我们这样建树后,就可以在树上进行树dp了,这个树dp是很简单的,

无非就是定一个根,遍历,算一下每个树节点下面的值(每个节点都有一个值,上面说了)

然后算一下每个节点往父亲方面(上面)的值,其实就是总剪掉即可,这时候就知道为什么图不连通麻烦了…

做完树dp后就可以计算了,solve函数内

这题再次感受到,点双连通分量,边双连通分量是不同的东西,只是双连通分量是不准确的,就连缩点过程,tarjan的写法都不同,另外belong,com我是用set实现的,在这种写法下,set才能保证算法的正确性,视题目需要,一般可以用数组或vector实现

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <vector>
#include <set>
using namespace std;
#define LL long long
#define mp make_pair
#define pb push_back
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define MAX 20000
#define M 100010

//com[id]:连通分量号为id的块中,包含了哪些原图中的点
set<int>com[MAX+10];
//belong[u]:原图中的点u属于哪些连通分量,若是非割点,只属于一个,如果是割点,可能属于多块
set<int>belong[MAX+10];
//缩点后,再拆点(虚构),建树,点数可能变为原来的2倍
vector<int>tree[MAX+MAX+10];
//统计每个连通块内,原图非割点的数量,或者说是缩点后每个树节点里,原图非割点的数量
int comnum[MAX+MAX+10];

//构图
int n,tot,head[MAX+10];
struct edge{
int u,v,next;
bool used; //通用写法,有无重边都可处理
}e[M+M+10];

//Tarjan
int root,dcnt,bcnt,top,dfn[MAX+10],low[MAX],stack[M+M+10];
int iscut[MAX+10]; //是否为割点
vector<int>cp; //保存所有割点

//树dp,down[u],u节点下面有多少节点,即有多少子孙后代
int down[MAX+MAX+10];
//树dp,up[u],u节点往父亲方向有多少节点
int up[MAX+MAX+10];
//树dp,这题比较蛋疼,是森林,不是一棵树,所有要记录每个节点所处的树一个都多少节点
int TOT[MAX+MAX+10];
//树dp,记录父亲
int fa[MAX+MAX+10];
//在树dp过程中记录本次遍历了哪些节点,和总数,标记数组
int totnum,tmp_save[MAX+MAX+10],len;
bool vis[MAX+MAX+10];

void test(){
puts("-------- belong ---------");
for(int i = 1; i <= n; i++){
printf("%d : ",i);
set<int>::iterator it;
for(it = belong[i].begin(); it != belong[i].end(); it++)
printf("%d ",*it);
puts("");
}

puts("--------- com ----------");
for(int i = 1; i <= bcnt; i++){
printf("[%d] : ",i);
set<int>::iterator it;
for(it = com[i].begin(); it != com[i].end(); it++)
printf("%d ",*it);
puts("");
}

puts("-------- comnum ---------");
for(int i = 1; i <= bcnt; i++)
printf("[%d] : %d\n",i,comnum[i]);
puts("");

puts("--------- cp ----------");
for(int i = 0; i < cp.size(); i++)
printf("%d ",cp[i]);
puts("");

puts("--------- tree --------");
for(int i = 1; i <= bcnt; i++){
printf("%d : ",i);
for(int k = 0; k < tree[i].size(); k++)
printf("%d ",tree[i][k]);
puts("");
}
for(int i = 0; i < cp.size(); i++){
int CP = cp[i];
int __uu__ = CP + MAX;
printf("%d : ",__uu__);
for(int k = 0; k < tree[__uu__].size(); k++)
printf("%d ",tree[__uu__][k]);
puts("");
}
}

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

void get_bcc(int key){
++bcnt;
while(true){
int k = stack[top--];
int u = e[k].u , v = e[k].v;
//belong[u].pb(bcnt);
//belong[v].pb(bcnt);
belong[u].insert(bcnt);
belong[v].insert(bcnt);
com[bcnt].insert(u);
com[bcnt].insert(v);
if(u == key) break;
}
}

void tarjan(int u){
dfn[u] = low[u] = ++dcnt;
//stack[++top] = u;
int son = 0;
for(int k = head[u]; k != -1; k = e[k].next){
if(e[k].used) continue;
e[k].used = e[k^1].used = true; //有无重边都可以处理
stack[++top] = k;
int v = e[k].v;
if(!dfn[v]){
son++;
tarjan(v);
low[u] = min(low[u] , low[v]);
//当u为本次遍历的根时,该条件不足以说明u是割点,因此最后有个特判
if(low[v] >= dfn[u]){
iscut[u] = true;
get_bcc(u); //从栈中取出连通分量
}
}
else low[u] = min(low[u],dfn[v]);
}
//特判
if(u == root && son < 2) iscut[u] = false;
//最后才保存割点
if(iscut[u]) cp.pb(u);
}

void BCC(){
cl(dfn,0);
cl(iscut,false);
cp.clear();
dcnt = bcnt = top = 0;
for(int i = 1; i <= n; i++){
belong[i].clear();
com[i].clear();
}
for(int u = 1; u <= n; u++){
if(dfn[u]) continue;
root = u;
tarjan(u);
}
}

void cal(){
cl(comnum,0);
for(int i = 1; i <= bcnt; i++)
comnum[i] = com[i].size();
for(int i = 0; i < cp.size(); i++){
int CP = cp[i];
int __uu__ = CP + MAX;
comnum[__uu__] = 1; //这个节点,要算上一次,做到不重不漏
}
for(int u = 1; u <= n; u++){
if(!iscut[u]) continue;
set<int>::iterator it;
for(it = belong[u].begin(); it != belong[u].end(); it++){
int id = *it;
comnum[id]--;
}
}
}

void rebuild(){

for(int i = 1; i <= bcnt; i++)
tree[i].clear();
for(int i = 0; i < cp.size(); i++){
int CP = cp[i];
int __uu__ = CP + MAX;
tree[__uu__].clear();
}

//for(int i = 0; i <= MAX+MAX+5; i++)
// tree[i].clear();
int size = cp.size();
for(int i = 0; i < size; i++){
int CP = cp[i];
int __uu__ = CP + MAX; //虚构一个树节点__uu__
set<int>::iterator it;
for(it = belong[CP].begin(); it != belong[CP].end(); it++){
//看看哪些块中包含了这个割点
//用__uu__将这个块连起来
int id = *it; //块
tree[__uu__].pb(id);
tree[id].pb(__uu__);
}
}
}

void dfs(int u,int par){
vis[u] = true;
fa[u] = par;
totnum += comnum[u];
tmp_save[len++] = u;
for(int i = 0; i < tree[u].size(); i++){
int v = tree[u][i];
if(vis[v]) continue;
dfs(v,u);
down[u] += (comnum[v] + down[v]);
}
}

void treedp(){
cl(vis,false);
cl(down,0);
cl(fa,-1);
for(int i = 0; i < cp.size(); i++){
int CP = cp[i];
int __uu__ = CP + MAX;
if(vis[__uu__]) continue;
totnum = 0; len = 0;
dfs(__uu__,-1); //直接从这些虚节点开始dp
for(int k = 0; k < len; k++){
int u = tmp_save[k];
TOT[u] = totnum;
up[u] = totnum - down[u] - comnum[u];
}
}
}

LL solve(){
LL ans = 0LL;
for(int i = 0; i < cp.size(); i++){
int CP = cp[i];
int __uu__ = CP + MAX;
for(int k = 0; k < tree[__uu__].size(); k++){
int v = tree[__uu__][k];
LL L,R;
if(v == fa[__uu__]) L = up[__uu__];
else L = down[v] + comnum[v];
R = TOT[__uu__] - L - 1;
ans += L*R;
}
}
return ans;
}

int main(){
int CASE;
scanf("%d",&CASE);
for(int cas = 1; cas <= CASE; cas++){
int m;
scanf("%d%d",&n,&m);
tot = 0; cl(head,-1);
while(m--){
int u,v;
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
BCC(); //求点双连通分量
cal(); //先做一个处理,算出每个块中,非割点的数量
rebuild(); //缩点后,进行拆点,然后建树
//test();
treedp(); //树dp
LL ans = solve(); //最后计算答案
printf("Case %d: %lld\n",cas,ans);
//test();
}
return 0;
}