hdu 6016 Count the Sheep

BestCoder Round #92 B题

（今天突然想起来这道题在做的时候卡了cin 而且似乎也有爆int的坑就拿出来记录一下

（（这道题能用来测试输入输出外挂的性能

中文题意不解释

比赛的时候好多人是爆搜的四层

不过还是有更优雅的做法

那就是把每只羊的link数记录下来

然后根据每次数羊的时候的顺序

母羊A 公羊B 母羊C 公羊D

按照这样处理然后把最后的ans*2就可以了~

 1 #include<bits/stdc++.h>
 2 #define cl(a,b) memset(a,b,sizeof(a))
 3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl
 4 using namespace std;
 5 typedef long long ll;
 6 typedef pair<int,int> pii;
 7 
 8 int main()
 9 {
10     int T;
11     scanf("%d",&T);
12     while(T--)
13     {
14         int n,m,k;
15         scanf("%d%d%d",&n,&m,&k);
16         vector<int>a(n+1,0),b(m+1,0);
17         vector<pii>link;
18         for(int i=0;i<k;i++)
19         {
20             int x,y;
21             scanf("%d%d",&x,&y);
22             a[x]++,b[y]++;
23             link.push_back({x,y});
24         }
25         ll ans=0;
26         for(auto i:link)
27         {
28             ll tmp=1ll*(a[i.first]-1)*(b[i.second]-1);
29             //防止出现负数的判断
30             if(tmp<0) continue;
31             ans+=tmp;
32         }
33         printf("%lld
",ans*2);
34     }
35     return 0;
36 }
37 /*
38 
39 3
40 2 2 4
41 1 1
42 1 2
43 2 1
44 2 2
45 3 1 3
46 1 1
47 2 1
48 3 1
49 3 3 3
50 1 1
51 2 1
52 2 2
53 
54 */

顺便贴一下6015的代码

 1 #include<bits/stdc++.h>
 2 #define cl(a,b) memset(a,b,sizeof(a))
 3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl
 4 using namespace std;
 5 typedef long long ll;
 6 typedef pair<int,int> pii;
 7 
 8 map<string,pii>mp;
 9 
10 int main()
11 {
12     int T;
13     scanf("%d",&T);
14     while(T--)
15     {
16         int n;
17         scanf("%d",&n);
18         mp.clear();
19         for(int i=0;i<n;i++)
20         {
21             string str;
22             int value;
23             cin>>str>>value;
24             mp[str].second=max(value,mp[str].second);
25             if(mp[str].first<mp[str].second)
26             {
27                 swap(mp[str].first,mp[str].second);
28             }
29         }
30         int ans=0;
31         for(auto iter:mp)
32         {
33             ans+=((iter.second).first+(iter.second).second);
34         }
35         printf("%d
",ans);
36     }
37     return 0;
38 }
39 /*
40 
41 2
42 5
43 english 1
44 english 2
45 english 3
46 math 10
47 cook 100
48 2
49 a 1
50 a 2
51 
52 */