负二进制转换
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Problem Description
QAQ学长对于现在大家普遍学习的C语言、Java语言等等很是不屑，他认为二进制指令才是最优美的语言;苦苦思考哲学的QAQ学长
已经不满足正二进制了，他现在研究的是负二进制，他给你一串负二进制表示的编码，希望你告诉他这串负二进制表示的十进制数是
多少。
Input
Output
Sample Input
1011
001101001
Sample Output
-3
220
Hint:
对于第一组样例
ans = 1*(-2)^0 + 0*(-2)^1 + 1*(-2)^2 + 1*(-2)^3 = -3
水题，直接签到。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 int b[
31];
6 char s[
31];
7
8 int main(){
9
10 b[
0] =
1;
11 for (
int i =
1; i <=
22; ++i) b[i] = b[i -
1] * (-
2);
12
13 while (~scanf(
"%s", s)){
14 int ans =
0;
15 for (
int i =
0; i < strlen(s); ++
i)
16 ans += ((
int)s[i] -
48) *
b[i];
17
18 printf(
"%d\n", ans);
19 }
20
21
22
23 return 0;
24
25 }
View Code
反序数
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Problem Description
计算数X的反序数（百度百科：所谓反序数，即有这样成对的数，其特点是其中一个数的个数字排列顺序完全颠倒过来，就变成另一个数）。
Input
多组输入，每组输入占一行，表示一个数X。
Output
对于每组输入，在一行内输出其反序数，每组输出之间留一个空行。
Sample Input
123
321
123456879123
Sample Output
321
123
321987654321
同样，水题。
1 #include <bits/stdc++.h>
2
3
4 using namespace std;
5
6 char s[
100001];
7
8 int main(){
9
10 while (~scanf(
"%s", s)){
11 for (
int i = strlen(s) -
1; i >=
0; --
i) putchar(s[i]);
12 printf(
"\n\n");
13 }
14
15 return 0;
16
17 }
View Code
翻转区间
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Problem Description
Yimi学长非常喜欢翻牌子，但是如今Yimi学长已经不能满足于翻牌子了，他在新研究怎样翻转一个区间。于是他的哥哥Jstyle就来帮助他解决这个难题了，Jstyle规定了一种翻转区间的新规则。
1> 若已知某区间长度为n, 区间编号 i 从 1-n, ai表示标号为i的元素。
2> Jstyle从i = 1开始翻转 [i, n-i+1]这个区间，i <= n-i+1 的时候，他会一直翻转下去。
Jstyle现在给他的弟弟出难题了，他给Yimi一个翻转后的区间，让Yimi求出翻转前的区间是什么。Yimi最近有点ZZ，他希望善良的你帮他解决这个问题。
Input
多组输入，每组输入如下
第一行输入一个整数 n, (1 <= n <= 200000);
第二行输入n个整数 a1, a2, ..., an (-10^9 <= ai <= 10^9)表示翻转后区间内的元素;
Output
多组输出，每组输出n个整数，用空格隔开，表示翻转前的区间元素。（注意最后一个数字后面没有空格）;
Sample Input
7
4 3 7 6 9 1 2
8
6 1 4 2 5 6 9 2
Sample Output
2 3 9 6 7 1 4
2 1 6 2 5 4 9 6
Hint
对于第一组样例：
第0步操作后，区间为 2 3 9 6 7 1 4
第1步操作翻转[1, 7], 区间为 4 1 7 6 9 3 2
第2步操作翻转[2, 6], 区间为 4 3 9 6 7 1 2
第3步操作翻转[3, 5], 区间为 4 3 7 6 9 1 2
第4步操作翻转[4, 4], 区间为 4 3 9 6 7 1 2
结束操作。
思想比较简单，判一下奇偶就可以了。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 #define REP(i,n) for(int i(0); i < (n); ++i)
6 #define rep(i,a,b) for(int i(a); i <= (b); ++i)
7 #define dec(i,a,b) for(int i(a); i >= (b); --i)
8 #define for_edge(i,x) for(int i = H[x]; i; i = X[i])
9
10
11 const int N =
300000 +
10;
12
13 int a[N], l, n, cnt;
14
15 int main(){
16
17 while (~scanf(
"%d", &
n)){
18 rep(i,
1, n) scanf(
"%d", a +
i);
19 l = n /
2; cnt =
0;
20 rep(i,
1, l){
21 ++
cnt;
22 if (cnt &
1) swap(a[i], a[n - i +
1]);
23 }
24 rep(i,
1, n -
1) printf(
"%d ", a[i]); printf(
"%d\n", a[n]);
25 }
26
27
28 return 0;
29
30 }
View Code
养兔兔
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Problem Description
ZKY学长是远近闻名的养兔大户，凭借特殊的养兔技巧能够稳定地控制兔子的繁殖周期：对于每一只新生兔，出生后第六年开始每年年初都会产一只兔崽。
最近，寂寞的ZKY学长又从黑市进了一只新生兔，并使用自己的调教方式对其进行改造。
ZKY学长想要看看以自己的手艺，在第X年能够繁殖到多少只兔子。可惜ZKY学长数学不是很好，所以只能求助于聪明的同学们了。
（从第一年算起，第一年有一只兔子）
Input
多组输入，每组输入占一行，表示第X年。(1<=X<=54)
Output
对于每组输入，在一行内输出该年兔子数。
Sample Input
1
6
8
13
Sample Output
1
2
4
15
递推式f(n)=f(n-1)+f(n-5)因为n<=54，那么答案用long long存就可以了。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 long long f[
101];
6
7 int main(){
8
9
10 for (
int i =
0; i <=
5; ++i) f[i] =
1;
11 for (
int i =
6; i <=
54; ++i) f[i] = f[i -
1] + f[i -
5];
12
13
14 int n;
15 while (~scanf(
"%d", &n)) printf(
"%lld\n", f[n]);
16
17
18
19 return 0;
20
21 }
View Code
Beautiful String
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Problem Description
ACM竞赛围绕字符串的题目数不胜数，这不又来一个字符串的题目需要你去解决。已知：
第0个字符串：U
第1个字符串：DU
第2个字符串：UDDU
第3个字符串：DUUDUDDU
第4个字符串：UDDUDUUDDUUDUDDU
......
相信你已经发现规律了，没错！就是第i个字符串 = 第i-1个字符串的取反 + 第i-1个字符串;取反(U->D, D->U);
现在告诉你n和k，让你求得第n个字符串的第k个字符是多少。(注意字符串编号从0开始);
Input
多组输入，每组输入两个数字n, k;(0 <= n <= 51, 0 <= k < 2^n);
Output
输出up或者down表示所求字符是 U或者D;
Sample Input
3 6
51 123456789012345
Sample Output
down
up
分类讨论当前所求字符在字符串的前一半还是后一半，算出要改变多少次cnt。那么最后看cnt的奇偶性即可。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 long long b[
60];
6 int n;
7 long long l;
8
9 int main(){
10
11
12 b[
0] =
1;
for (
int i =
1; i <=
56; ++i) b[i] = b[i -
1] *
2;
13 while (~scanf(
"%d%lld", &n, &
l)){
14 ++
l;
15 int cnt =
0;
16 for (; n; --n)
if (l > b[n -
1]) l -= b[n -
1];
else ++
cnt;
17 puts(cnt %
2 ?
"down" :
"up");
18 }
19
20 return 0;
21
22 }
View Code
神奇的花瓣
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Problem Description
ZZC学长很具有科研精神，他来自遥远的内蒙古草原，对西安的很多事物都十分好奇。
今天，他又在宿舍一楼阳台下的阴暗角落里发现了一种奇异的花。这种花由六瓣组成，每瓣形状各异。
ZZC学长统计出花瓣共有六种形状，并为这些形状编号。他找到了N朵花，以顺时针方向对每朵花进行观察，但是他的数学跟ZKY学长一样不是很好，你能帮他统计一共有多少朵形状不同的花么？
（hint:123456和612345是一种形状的花）
Input
多组输入，每组第一行数字N，第二行开始N行每行六个数字表示一朵花的形状。（1<=N<=1000000）
Output
对于每组输入，在单独的一行输出一个数，表示多少种形状不同的花。
Sample Input
2
123456
612345
3
135555
124444
355551
Sample Output
1
2
本来想着用字符串的最小表示法做这道题……结果还是写了暴力（因为字符串长度为6）
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5
6 #define rep(i, a, b) for (int i(a); i <= (b); ++i)
7
8 string cs[
12];
9
10 char s[
10];
11 int n;
12
13 set <
string>
mp;
14
15 int main(){
16
17 while (~scanf(
"%d", &
n)){
18 mp.clear();
19 for (
int i =
1; i <= n; ++
i){
20 scanf(
"%s", s);
21 rep(j,
1,
6) cs[j] =
"";
22 int t =
0;
23 rep(j,
0,
5){
24 ++
t;
25 rep(k, j,
5) cs[t] +=
s[k];
26 rep(k,
0, j -
1) cs[t] +=
s[k];
27 }
28
29
30 string ssc = cs[
1];
31 rep(j,
2,
6)
if (ssc > cs[j]) ssc =
cs[j];
32
33 mp.insert(ssc);
34
35
36 }
37
38 printf(
"%d\n", (
int)mp.size());
39
40
41
42 }
43
44 return 0;
45
46 }
View Code
景女神与她的托福
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Problem Description
景女神最近一直在恶补英语，她要为了她的托福做准备。于是，满神给景女神出了一道题，来帮助景女神学习英语。
满神给了景女神一个长度为n的字符串，字符串只包含小写字母 a,b;并且告诉景女神她最多可以改变k个字符(a->b, b->a);满神想知道经过不超过k次的改变后，出现相同字母的字符串(连续)的最大长度是多少。
景女神觉得这个题和她记单词并没有什么关系，于是就学英语去了。但是满神希望聪明的你可以帮助他解决这个问题。
Input
多组输入，每组输入如下
第一行输入两个整数n和k，用空格隔开 (1 <= n <= 100000, 0 <= k <= n);
第二行输入一个字符串。(只包含小写字母 a和b);
Output
多组输出，每组输出一个整数，表示经过不超过k次改变后，出现相同字符的最大字符串长度。
Sample Input
4 2
abba
8 1
aabaabaa
Sample Output
4
5
Hint:
第一组样例：可以得到 aaaa 或者 bbbb;最大长度为4;
第二组样例：可以得到 aaaaabaa 或者 aabaaaaa; 最大长度的字符串是 aaaaa，长度为5;
首先我们不难发现如果要修改字母，只可能进行一种修改，也就是说：修改操作都是把a改成b，或者都把b改成a不可能有些操作是把a改成b，有些操作是把b改成a。维护两个前缀，f[i]表示字符串的第1位带第i位中有几个a， c[i]表示字符串的第1位到第i为中有几个b。（假设字符串从1开始标号）那么现在考虑第i位，确定以s[i]为右端点，用上k次（或少于k次）的修改机会，能得到的相同字母的字符串最左能延伸到哪里。因为前缀都是单调递增的，那么二分就可以了。两种字母都考虑一遍，同时更新答案。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 #define rep(i, a, b) for(int i(a); i <= (b); ++i)
6
7 const int N =
100000 +
10;
8
9 char s[N];
10 int a[N], c[N], f[N];
11 int n, k, l, r, cnt, ans;
12
13 int main(){
14
15 while (~scanf(
"%d%d%s", &n, &k, s +
1)){
16 rep(i,
1, n) a[i] = s[i] ==
'a' ?
0 :
1;
17 memset(c,
0,
sizeof c);
18 memset(f,
0,
sizeof f);
19 rep(i,
1, n)
if (a[i] ==
1) c[i] = c[i -
1] +
1;
else c[i] = c[i -
1];
20 rep(i,
1, n)
if (a[i] ==
0) f[i] = f[i -
1] +
1;
else f[i] = f[i -
1];
21 ans =
0;
22 rep(i,
1, n){
23 l =
1, r =
i;
24 if (l == r) cnt =
l;
25 else{
26 while (l +
1 <
r){
27 int mid = (l + r) /
2;
28 if (c[i] - c[mid -
1] <= k) r = mid;
else l = mid +
1;
29 }
30
31 if (c[i] - c[l -
1] <= k) cnt = l;
else cnt =
r;
32 }
33 ans = max(ans, i - cnt +
1);
34 l =
1, r =
i;
35 if (l == r) cnt =
l;
36 else{
37 while (l +
1 <
r){
38 int mid = (l + r) /
2;
39 if (f[i] - f[mid -
1] <= k) r = mid;
else l = mid +
1;
40 }
41
42 if (f[i] - f[l -
1] <= k) cnt = l;
else cnt =
r;
43 }
44 ans = max(ans, i - cnt +
1);
45 }
46
47 printf(
"%d\n", ans);
48 }
49
50 return 0;
51
52 }
View Code
Poor ZKY
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Problem Description
ZKY学长老家的正方形兔子窝群着火了，火势每天向上下左右四个方向蔓延一个窝。
ZKY学长只知道最初的火情，当他赶到家时已经是第X天了，他想知道现在的状况。
Input
多组输入样例，每组第一行两个数字N和X，接下来一组N*N的符号表示初始兔子窝群，.是未着火的窝，*表示已着火的窝。
每组样例以一个空行隔开。(1<=N<=10,0<=X<=10)
Output
当前兔子窝群状况，每组输出后留一个空行。
Sample Input
3 2
...
...
.*.
4 1
....
.*..
....
....
Sample Output
.*.
***
***
.*..
***.
.*..
....
暴力模拟一下。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 int a[
15][
15], b[
15][
15];
6 char s[
15];
7 int n, x;
8
9 int main(){
10
11 while (~scanf(
"%d%d", &n, &
x)){
12 for (
int i =
1; i <= n; ++
i){
13 scanf(
"%s", s +
1);
14 for (
int j =
1; j <= n; ++
j)
15 a[i][j] = s[j] ==
'.' ?
0 :
1;
16 }
17
18 for (; x; x--
){
19
20 memcpy(b, a,
sizeof a);
21 for (
int i =
1; i <= n; ++
i)
22 for (
int j =
1; j <= n; ++j)
if (a[i][j]){
23 b[i -
1][j] = b[i +
1][j] = b[i][j -
1] = b[i][j +
1] =
1;
24 }
25
26
27 memcpy(a, b,
sizeof b);
28 }
29
30 for (
int i =
1; i <= n; ++
i){
31 for (
int j =
1; j <= n; ++j) putchar(((a[i][j]) ?
'*' :
'.'));
32 putchar(
10);
33
34 }
35 putchar(
10);
36 }
37
38
39
40
41 return 0;
42
43 }
View Code
素数迭代
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Problem Description
定义函数f(i)为i的所有素因子和。
定义g(i)为f(i)的迭代次数，(迭代即f(f(f(...f(i)))))，迭代次数至少为1。
当i为素数(即f(i) = i)的时候停止迭代。
现在给定三个数l, r, p，求[l, r]区间内有多少个数x满足g(x) = p;
Input
多组输入，每组输入三个数，分别代表l, r, p; (2 <= l <= r <= 1000000, 1 <= p <= 1000000)
Output
每组输出一行，根据题意输出一个满足条件的数字;
Sample Input
90 90 3
2 9 1
2 9 2
800 810 4
999999 1000000 2
100000 1000000 1000000
Sample Output
1
4
4
5
2
0
Hint:
对于l = 2, r = 9, p = 2这组数据，根据题意得;
f(2) = 2;
f(3) = 3;
f(4) = 2;
f(5) = 5;
f(6) = 2+3 = 5;
f(7) = 7;
f(8) = 2;
f(9) = 3;
则迭代次数 g(i) = 2 的有g(4), g(6), g(8), g(9), 共有4个，因此输出4;
首先，用类似筛选素数的方法求出f(i)。注意到每次迭代之后，原先的那个数是大幅度减小的，再最坏的情况下也会减小到原来的一半左右。那么可以作出大胆的假设：g(i) <= 30 （1<=i<=1e6）事实上g(i) <= 12 （1<=i<=1e6）那么暴力求g(i)就可以了。接下来我们对询问离线操作。从1道12每次维护一个前缀，将对应的答案塞到询问中即可。p大于12的询问不做处理，那么答案就是0。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 #define rep(i, a, b) for (int i(a); i <= (b); ++i)
6
7 struct query{
8 int l, r, num, ans, id;
9 friend
bool operator < (
const query &a,
const query &
b){
10 return a.num <
b.num;
11 }
12 } q[
500010];
13
14 int p[
1000010];
15 int n;
16 int cnt;
17 int prime[
1000010];
18 int f[
1001000], g[
1000100];
19
20 int ct[
1000010];
21
22 bool cmp(
const query &a,
const query &
b){
23 return a.id <
b.id;
24 }
25
26 int main(){
27
28 memset(p,
0,
sizeof p);
29 rep(i,
2,
1000000)
if (!
p[i]){
30 for (
int j = i + i; j <=
1000000; j +=
i){
31 p[j] =
1;
32 }
33 }
34
35 cnt =
0;
36 rep(i,
2,
1000000)
if (!p[i]) prime[++cnt] =
i;
37
38 memset(f,
0,
sizeof f);
39 rep(i,
1, cnt){
40 for (
int j = prime[i]; j <=
1000000; j +=
prime[i]){
41 f[j] +=
prime[i];
42 }
43 }
44
45 memset(g,
0,
sizeof g);
46 rep(i,
2,
1000000){
47 int et =
1, now =
i;
48 while (now !=
f[now]){
49 ++
et;
50 now =
f[now];
51 }
52
53 g[i] =
et;
54 }
55
56 int aa, bb, cc, n =
0;
57 while (~scanf(
"%d%d%d", &aa, &bb, &
cc)){
58 ++
n;
59 q[n].l = aa, q[n].r = bb, q[n].num = cc; q[n].id =
n;
60 }
61
62 sort(q +
1, q + n +
1);
63 rep(i,
1,
12){
64 memset(ct,
0,
sizeof ct);
65 rep(j,
2,
1000000)
if (g[j] == i) ct[j] = ct[j -
1] +
1;
else ct[j] = ct[j -
1];
66 rep(j,
1, n){
67 if (q[j].num == i) q[j].ans = ct[q[j].r] - ct[q[j].l -
1];
68 }
69 }
70
71 sort(q +
1, q + n +
1, cmp);
72 rep(i,
1, n) printf(
"%d\n", q[i].ans);
73
74 }
View Code
神秘的迷宫
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Problem Description
ZZC学长因为发现了奇异的花朵被神秘组织绑架到了一个阴暗的迷宫，这个迷宫有四种暗门和最多一个出口，每个暗门都有一把钥匙与其对应，粗心的神秘组织成员把一些钥匙散落在迷宫内。
ZZC学长只有找到钥匙才能打开暗门，他醒来后找到一张也是粗心的神秘组织成员留下的地图。
因为刚刚醒来，ZZC学长一分钟之内只能向上下左右走一格，走路的同时，他也能拿起钥匙或者打开暗门，不会影响走路速度。
ZZC学长希望以最快的速度离开迷宫，聪明的同学能帮帮他么？
Input
多组输入，每组输入第一行两个数字N和M表示迷宫的行数和列数。之后N行，每行M个字符描述该迷宫：.表示可以行走的路，#表示出口，*表示迷宫的墙壁，0表示ZZC学长当前位置，
1、2、3、4分别表示每种暗门，5、6、7、8依次对应每种钥匙。(0 < N,M < 1000)
Output
对于每组输入，在一行内输出一个数字，表示离开迷宫的最短时间，若无法找到出口，则输出-1。
Sample Input
3 3
...
.0.
.#.
5 5
*.0.*
.1*5*
.**.*
...**
*#***
Sample Output
1
11
hint:第二个样例里，ZZC学长先用2分钟拿到钥匙5，再用4分钟打开暗门1，最后用5分钟走到出口。
比较基础的加条件BFS，只是这个数据范围可能会MLE……然后发现开100*100的数组就够了。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 #define REP(i, n) for(int i(0); i < (n); ++i)
6 #define rep(i, a, b) for(int i(a); i <= (b); ++i)
7 #define dec(i, a, b) for(int i(a); i >= (b); --i)
8 #define for_edge(i, x) for(int i = H[x]; i; i = X[i])
9
10 #define LL long long
11 #define ULL unsigned long long
12 #define MP make_pair
13 #define PB push_back
14 #define FI first
15 #define SE second
16 #define INF 1 << 30
17
18 const int N =
100000 +
10;
19 const int M =
10000 +
10;
20 const int Q =
1000 +
10;
21 const int A =
30 +
1;
22
23 const int dx[] = {
0,
1,
0, -
1};
24 const int dy[] = {
1,
0, -
1,
0};
25
26 bool h[
102][
102][
1 <<
6];
27 char a[
102][
102];
28 int n, m;
29
30 struct node{
31 int x, y, key, st;
32 bool check(){
return x >=
0 && x < n && y >=
0 && y < m && a[x][y] !=
'*';}
33 bool door(){
return a[x][y] >=
'1' && a[x][y] <=
'4';}
34 bool keyy(){
return a[x][y] >=
'5' && a[x][y] <=
'8';}
35 } start, cur, nx;
36
37 int BFS(){
38 queue <node>
q;
39 while (!
q.empty()) q.pop();
40 memset(h,
false,
sizeof h);
41 h[start.x][start.y][start.key] =
true;
42 q.push(start);
43
44 while (!
q.empty()){
45 cur =
q.front(); q.pop();
46 if (a[cur.x][cur.y] ==
'#')
return cur.st;
47 REP(i,
4){
48 nx = cur; nx.x += dx[i], nx.y += dy[i], ++
nx.st;
49 if (nx.check()){
50 if (nx.door()){
51 int key = a[nx.x][nx.y] -
'1';
52 if (nx.key & (
1 << key) && !
h[nx.x][nx.y][nx.key])
53 h[nx.x][nx.y][nx.key] =
true, q.push(nx);
54 }
55 else
56 if (nx.keyy()){
57 int key =
1 << (a[nx.x][nx.y] -
'5'); nx.key |=
key;
58 if (!h[nx.x][nx.y][nx.key]) h[nx.x][nx.y][nx.key] =
true, q.push(nx);
59 }
60
61 else
62 if (!h[nx.x][nx.y][nx.key]) h[nx.x][nx.y][nx.key] =
true, q.push(nx);
63 }
64 }
65 }
66
67
68 return -
1;
69 }
70
71 int main(){
72
73 while (~scanf(
"%d%d", &n, &
m)){
74 REP(i, n){
75 scanf(
"%s", a[i]);
76 REP(j, m)
if (a[i][j] ==
'0') start.x = i, start.y = j, start.key =
0, start.st =
0;
77 }
78
79
80 printf(
"%d\n", BFS());
81 }
82
83
84
85 return 0;
86
87 }
View Code
这是一道简单题
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/102400K (Java/Other)
Problem Description
“三角形十分的美丽，相信大家小学就学过三角形具有稳定性，三角形也是二维几何中最基本的必不可少的元素之……”，满叔叔走在路上若有所思，突然抬头看到了天空中有很多很亮的星星划过，星星和他们划过的轨迹像极了一个无向图。于是好学的满叔叔，就开始数起了“三角形”，1、2、3……数了好久，满叔叔数的眼泪都掉下来了，所以他哭着请求你来帮他，数有多少个三角形，你这么好心一定不会拒绝吧！满叔叔的三角形的定义：如果存在这样的三个边(A,B)、(B,C)、(A,C)（无向边），则算一个三角形。
满叔叔会告诉你点数（星星个数）n和边数（轨迹个数）m以及每条边的两个点。
注意：两个三角形不同是：当对于两个三角形的边，某个三角形存在一条边在另一个三角形的边中无法找到！
保证数据没有重边和自环。
Input
多组数据。
第一行一个整数T<=10表示数据组数。
对于每组数据的第一行n表示星星个数，m表示星星划过的轨迹的个数，
接下来m行表示每个星星划过的轨迹的端点x,y(1<=x,y<=n)。
1<=n<=100000,1<=m<=min(100000,n*(n-1)/2)
Output
对于每组数据输出一个整数，表示三角形的个数。
Sample Input
1
3 3
1 2
2 3
1 3
Sample Output
1
感人的题目标题……这题很卡常数啊……首先对所有点进行分类。1、度数>sqrt(m)。2、度数<sqrt(m)。剩下的事情就是分类暴力。注意添加边的时候要手写Hash。我还开了fread挂……
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 const int N =
100010;
6
7 #define REP(i, n) for(int i(0); i < (n); ++i)
8 #define rep(i, a, b) for(int i(a); i <= (b); ++i)
9
10 int T, n, m, q, du[N];
11 int x, y, ans;
12
13 vector <
int>
c[N];
14 vector <
int>
d;
15
16 namespace IO{
17 const int MT =
20 *
1024 *
1024;
18 char IO_BUF[MT];
19 int IO_PTR, IO_SZ;
20
21 void begin(){
22 IO_PTR =
0;
23 IO_SZ = fread (IO_BUF,
1, MT, stdin);
24 }
25 template<typename T>
26 inline
bool scan_d (T &
t){
27 while (IO_PTR < IO_SZ && IO_BUF[IO_PTR] !=
'-' && (IO_BUF[IO_PTR] <
'0' || IO_BUF[IO_PTR] >
'9'))IO_PTR ++
;
28 if (IO_PTR >= IO_SZ)
return false;
29 bool sgn =
false;
30 if (IO_BUF[IO_PTR] ==
'-') sgn =
true, IO_PTR ++
;
31 for (t =
0; IO_PTR < IO_SZ &&
'0' <= IO_BUF[IO_PTR] && IO_BUF[IO_PTR] <=
'9'; IO_PTR ++
)
32 t = t *
10 + IO_BUF[IO_PTR] -
'0';
33 if (sgn) t = -
t;
34 return true;
35
36 }
37 inline
bool scan_s (
char s[]){
38 while (IO_PTR < IO_SZ && (IO_BUF[IO_PTR] ==
' ' || IO_BUF[IO_PTR] ==
'\n') ) IO_PTR ++
;
39 if (IO_PTR >= IO_SZ)
return false;
40 int len =
0;
41 while (IO_PTR < IO_SZ && IO_BUF[IO_PTR] !=
' ' && IO_BUF[IO_PTR] !=
'\n')
42 s[len++] = IO_BUF[IO_PTR], IO_PTR ++
;
43 s[len] =
'\0';
44 return true;
45 }
46 };
47
48 namespace Hashmap{
49 const int P =
1000007, seed =
2333;
50 int u[N <<
2], v[N <<
2], nt[N <<
2];
51 int head[P], inum;
52 inline
void init(){
53 inum =
0;
54 memset(u,
0,
sizeof u);
55 memset(v,
0,
sizeof v);
56 memset(nt,
0,
sizeof nt);
57 memset(head,
0,
sizeof head);
58 }
59
60 inline
void add(
int _u,
int _v){
61 int t = (_u * seed + _v) %
P;
62 u[++inum] = _u, v[inum] = _v, nt[inum] = head[t], head[t] =
inum;
63 }
64
65 inline
bool query(
int _u,
int _v){
66 int t = (_u * seed + _v) %
P;
67 for (
int p = head[t]; p; p =
nt[p])
68 if (u[p] == _u && v[p] == _v)
return 1;
69 return 0;
70 }
71 }
72
73 int main(){
74
75 IO::begin();
76 IO::scan_d(T);
77
78 while (T--
){
79 IO::scan_d(n);
80 IO::scan_d(m);
81 Hashmap::init();
82 rep(i,
1, n) c[i].clear();
83 memset(du,
0,
sizeof du);
84 ans =
0;
85 rep(i,
1, m){
86 IO::scan_d(x);
87 IO::scan_d(y);
88 Hashmap::add(x, y);
89 Hashmap::add(y, x);
90 c[x].push_back(y);
91 c[y].push_back(x);
92 ++du[x], ++
du[y];
93 }
94
95 d.clear();
96
97 q = (
int)sqrt((
double)m);
98
99 rep(i,
1, n)
if (du[i] <=
q){
100 REP(j, (
int)c[i].size())
101 if (!(du[c[i][j]] <= q && c[i][j] <
i))
102 rep(k, j +
1, (
int)c[i].size() -
1)
103 if (!(du[c[i][k]] <= q && c[i][k] <
i))
104 if (Hashmap::query(c[i][j], c[i][k])) ++
ans;
105 }
106 else d.push_back(i);
107
108 REP(i, (
int)d.size())
109 rep(j, i +
1, (
int)d.size() -
1){
110 if (Hashmap::query(d[i], d[j]))
111 rep(k, j +
1, (
int)d.size() -
1){
112 if (Hashmap::query(d[j], d[k]))
113 if (Hashmap::query(d[i], d[k])) ++
ans;
114 }
115 }
116
117 printf(
"%d\n", ans);
118 }
119
120
121 return 0;
122
123 }
View Code
转载于:https://www.cnblogs.com/cxhscst2/p/6522154.html
