codeforces 236 div.1

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

A.

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

int main() {
int T,n,p,tot;
cin >> T;
while (T--) {
cin >> n >> p;
tot = 2*n + p;
for (int i = 1; i <= n && tot; i++)
for (int j = i+1; j <= n && tot; j++) {
cout << i << " " << j << endl;
tot--;
}
}
return 0;
}

B.

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
/*
题意:
注意那个除去gcd的操作是可以做多次的,但是显然是对不同的前缀区间做,
对同一个前缀区间做了一次后,以后再做就没意义了(以后gcd都是1)
另外,如果要对不同的前缀区间做这种操作,一定要先选长的前缀区间做
如果先对前面的前缀区间做了,后面的都不起作用了(gcd都是1)

例如 4 4 4 2
如果对[4,4,4]做了一次操作,数组变为 1 1 1 2
再对[1,1,1,2]做一次操作,gcd=1,无意义
这是比较明显的,因为越靠前gcd越大,后面的gcd其实是前面gcd的一个部分
先除掉后面的,前面还有剩余,除掉前面的,后面就没剩余了
所以这题,如果要将多个这种生效,一定是要从后往前做

另外一个是对于给出来的f(s)公式,容易看出是统计s的质因子个数,质因子在bad里面的-1,不在bad的+1,计算f(s)就是个分解的过程,很快完成

最后就是考虑除去gcd的操作对整个答案的影响,既然f(s)是统计质因子的过程,除去gcd就是除去一些因子,
如果这些因子在bad里面,除去了答案会更大(有的话,是-1,除去了变成了+1),
如果不在bad里面,答案会减少,也是对于每次除了gcd的操作,判断一下它是否能使答案更大,是的话除去;
因为是从后往前的,不会影响后面的操作
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define LL long long
#define MAXN 5010
#define MAXP 100010

bool vis[MAXP];
int pn,primer[MAXP];
int n,m,a[MAXN],g[MAXN];
set<int>fac;

inline int cal(int x) {
int ans = 0;
for (int i = 0; i < pn && primer[i]<=x; i++)
if (!(x % primer[i])) {
int cnt = 0;
while (!(x % primer[i])) cnt++, x /= primer[i];
if (fac.find(primer[i]) != fac.end()) ans -= cnt;
else ans += cnt;
}
if (x > 1) {
if(fac.find(x) != fac.end()) ans--;
else ans++;
}
return ans;
}

inline int gcd(int a,int b) {
while (b) {
a %= b, b ^= a, a ^= b, b ^= a;
}
return a;
}

inline void init() {
pn = 0;
memset(vis,false,sizeof(vis));
for (int i = 2; i < MAXP; i++) if (!vis[i]) {
primer[pn++] = i;
for (int j = i+i; j < MAXP; j += i) vis[j] = true;
}
}

int main() {
init();
int x;
while (scanf("%d%d", &n,&m) != EOF) {
fac.clear();
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < m; i++) {
scanf("%d", &x);
fac.insert(x);
}
int ans = 0;
for (int i = 0; i < n; i++)
ans += cal(a[i]);
//cout << ans << endl;
g[0] = a[0];
for (int i = 0; i < n; i++)
g[i] = gcd(g[i-1],a[i]);
int pre = 1;
for (int i = n-1; i >= 0; i--) {
int cnt = cal(g[i] / pre);
if (cnt < 0) ans -= (i+1) * cnt, pre = g[i];
}
printf("%d\n",ans);
}
return 0;
}

C.

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
/*
矩阵相乘的一个常见的意义是
A^k,A[i][j] 表示有向图 从点i走到点j有k步,边可以重复走,能走出的方案数
若A[i][j] = 0,显然说明i到j是不可达的(当k足够大仍然是0的时候)
A[i][i] = 1,说明自己走到自己是可以的(处于原地也是可以的)

本题不限定k,只要求所有A[i][j] = 1,即任意两点都是任意可达的,
那就是整个图如果是一个强连通分量,则满足
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define MAXN 2010
#define pb push_back

class SCC;
SCC *G;

class SCC {
public:
int n;
vector<int>e[MAXN];
int dcnt,bcnt,dfn[MAXN],low[MAXN],belong[MAXN];
int stack[MAXN],top;
bool ins[MAXN];

public:

void reset(int _n) {
n = _n;
for (int i = 0; i < n; i++)
e[i].clear();
}

void build() {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
int x;
scanf("%d", &x);
if (x) e[i].pb(j);
}
}

void tarjan(int u) {
dfn[u] = low[u] = ++dcnt;
stack[++top] = u;
ins[u] = true;
int size = e[u].size();
for (int i = 0; i < size; i++) {
int v = e[u][i];
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(ins[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
while (true) {
int x = stack[top--];
belong[x] = dfn[u];
if (x == u) break;
}
}
}

void scc() {
dcnt = bcnt = 0;
memset(dfn,0,sizeof(dfn));
memset(ins,false,sizeof(ins));
for (int i = 0; i < n; i++)
if (!dfn[i]) tarjan(i);
}

bool isScc() {
for (int i = 1; i < n; i++)
if (belong[i] != belong[i-1]) return false;
return true;
}
};

int main() {
G = new SCC();
int n;
while (scanf("%d", &n) != EOF) {
G->reset(n);
G->build();
G->scc();
puts(G->isScc() ? "YES" : "NO");
}
delete G;
return 0;
}