NWU现场赛——解题报告

负二进制转换

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
", 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("

");
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
", 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

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
", 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

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
", (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
", 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
", 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
", 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

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] == '
') ) 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] != '
')
 42                 s[len++] = IO_BUF[IO_PTR], IO_PTR ++;
 43             s[len] = '';
 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
", ans);
118     }
119 
120 
121     return 0;
122 
123 }

View Code