02:第二次作业,APP案例分析

链接:http://acm.xidian.edu.cn/contest.php?cid=1028

产品:王者荣耀

理由:现中国最火的手游,没有之一。

题目 C: 大大数星星

时间限制: 1 Sec  内存限制: 128 MB
提交: 1928  解决: 655
[提交][状态][讨论版]

一、调研

问题叙述

欣赏数少于真是个传染病,这一天大大和四嫂上午走在旅途抬头看看众多零星,他们发觉个别密密麻麻的布满了整整天空,二姐说他想用线将天空的个别分割开,可是只给大大n根无限长的直线!大大为了让表妹如沐春风,想问问您最多能把简单分割成多少份!

左侧体验:

输入

读入多组数据,处理到文件截止结束!(不抢先5000组)
每组数据一个整数n(0<=n<=10000000)

  作为一款手机端的MOBA\[1\]游玩,王者荣耀给自身的第一映像是娱乐的可操作性、流畅度和界面都做得很好。平时,MOBA类的嬉戏本身只在电脑上玩过,原因是作为一款联机在线竞赛类游戏,对用户来说最着重的是收获游戏激励对抗中的快感和游乐人物的可操作性,我平素以为手机很难知足。然则这款游戏改变了自身的见地。那些娱乐用的屏幕摇杆格局 双轮盘操作\[2\] (左手移动,右手攻击和释放技能)完成了和在PC端用鼠标加键盘操作人物一致的人员控制效果,满意了玩家对人选操作的细致控制的急需。流畅度从网络延迟低到人物攻击、释放技能的动都做的那多少个平整,都给玩家相当清爽的感觉。所有,这款游戏仍旧很好的。

            图片 1   
 图片 2

此时此刻经历的BUG:

  1、十人游玩中,游戏确认机制。当十个都点击进入游戏时,游戏并没有进入英雄采取界面。这类症状,在前头有碰着过五次,之后就差一点平昔不了。

  2、商城的金币数量和铭纹数量显示。假诺伊始钱玩家拥有1700个铭文,当在杂货铺成功买一个标价1600的墓志后,玩家拥有的墓志显示数量仍旧1700,但事实上唯有100重复购入后,会唤醒铭文不足而买入失败,之后才刷新玩家所有的的墓志数量。

  3、游戏人物百里守约。在戏耍中,移动该人士,有几率会赶上该人员影子撕裂的状态(游戏图像变形)。

软件优缺点:

  优点有,关于游戏的可操作性、流畅性,游戏人物丰盛,即时的玩乐语音等等;用户账号可以通过QQ或微信关联,流程简单。

  缺点有,纯粹的尽管对抗游戏,没有故事背景,没有属于自己的嬉戏文化。(例如,说到LOL就会想到瓦Roland大洲,想口号”德玛西亚”;
魔兽 就会想到”为了部落”、”为了联盟”)。

      人民币玩家的优势,打破了娱乐平衡。

采访:(A:博主,B:舍友)

  A:你以为王者荣耀那款游戏咋样?

  B:还行。

  A:很深入的评论。这你怎么喜欢玩那些娱乐啊?

  B:无聊,打发时光。

  A:你最欣赏的英勇是何等?

  B:没有特别欣赏的强悍,我一切都玩。

  A:有没有认为这款游戏有什么毛病呢?

  B:有啊,小学生太多。队友太蠢,带不动。

  A:我说的是这款游戏,不是玩家。

  B:对啊,游戏匹配机制不创建,匹配到的玩家都和本人不在同一档次。还有防沉迷,没把小学生挡住。

  A:你认为那款游戏有没有哪些需要改进的地点?

  B:英雄金币价格太贵,玩一周都买不到一只英雄。铭文不是相似的贵,玩一年揣度都陪不齐,除了RMB玩家。

  A:这您觉得这款游戏的平衡性咋样?

  B:你以为腾讯的玩乐有平衡性。铭文加成就不说了,一个勇猛皮肤起头加10点攻击力或者100生命值,怎么打?

  

  这段采访紧如果想询问到,王者荣耀这款游戏近日设有的通病是如何和对此玩家来说诟病有哪些。对于对舍友的采访,发现的题材有:

  1、小学生泛滥,可以看来游戏的防沉迷系统并不曾完善;

  2、游戏的配合机制,仅仅依据段位匹配玩家,存在误差。

  3、对于游戏的平衡性,道具具有属性加成,使得一些不愿花钱的玩家忿忿不平。

  

  总的来说,这款游戏能成为中国的NO1是有来头的。游戏本身的实力很强。快节奏的游艺对抗,细腻的人物操作,充足的游乐人物,强烈的打击感和收获大捷给给玩家带来的快感使得这款游戏登顶王座。个人如故引进。

输出

对此每组输出一个整数,表示最多分割的份数。

二、APP分析

样例输入

0
1
2

软件效率

  即时的六个人或单人PVP和PVC;单人的孤注一掷格局;擂台形式;社区职能;交友功用;战队效用;地区荣誉功能;即时通讯功用;商城功效。

样例输出

1
2
4

软件比较

  采取了代号moba和老百姓超神这两款游戏展开相比

游戏名

王者荣耀

代号moba

全民超神

操作性和流畅性

配置要求

图形

非常高

音效

游戏文化

  王者荣耀与全员超神对比,有着精良的优势,无论哪一方面都稳压对方。

  重点相比较王者荣耀和代号Moba这两款游戏。

  代号moba是知乎现年刚生产的一款moba类手游,其操作都和王者荣耀相差无几,因为都是双轮盘操作。差距比较大是背后三项。

  代号moba相较与王者荣耀的优势是娱乐图像音效方面。不得不说,这款游戏的镜头相比非凡,但针锋相对的,为了维持游戏的流畅性,对于配置会相比较高些。对于游戏文化这或多或少,王者荣耀输的有点体无完肤。代号moba基于阴阳师这个伟大的故事背景,其视频、动漫二次元系列已经是蔓延到全球。可是王者荣耀也有自己的优势,基于QQ和微信这一极大的用户量,很快的就能俘获到一大群玩家。而代号moba打的是心情牌,吸引的是二次元宅迷们的这一群粉丝,用户量和推广方面远没有王者荣耀。

  满分10分

用户体验

9

图形音效

8

个性化

8

核心功能

9

提示

请使用六十四位整数,%lld

演绎出公式,套公式即可:

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

int main()
{
    ll a;
    while(~scanf("%lld",&a)) {
        ll ans = 1 + a*(a+1)/2;
        printf("%lld\n",ans);
    }
    return 0;
}

改进

  希望有关这款软件的改革的地方,紧假设商城的英勇得到机制,金币难以得到。游戏的配合机制,对于态度消极玩家的非凡。

题材 D: 善良的大红

岁月范围: 1 Sec  内存限制: 128 MB
提交: 1302  解决: 628
[提交][状态][讨论版]

三、提议和筹划

  1. 若果自身是团队主管,我会在玩乐性能在高达高水准后,将资源转化对游乐文化的支出。一个嬉戏的正规寿命是4到5年,英雄联盟走了七年,dota出现的时日一向缓慢没有敲定,但也走了十几年。当在技巧达到终点时,往往用文化了保障生命、

 

  1. 当前市面上看似的制品有不少,像老百姓超神、代号moba,不过王者荣耀是做的最好的。

 

  1. 我会设计新的玩乐格局,阵营迎战形式,将具有勇于分配阵营,选用阵营的玩家对见义勇为采纳只可选本阵营英雄。

 

  1. 做该意义,是为了给游戏构建一个整机的背景故事。

 

  1. 用户可以在阵营模式中免费玩自己想要的人物(前提是该人员在此阵营),而不用购买英雄如故到周免英雄轮换。

 

  1. N:玩家想玩自己想玩的英雄人物。A:独立出来的娱乐情势,让玩家拔取阵营,玩到想玩的身先士卒。B:解决了玩家要到周末免费和购进英雄的状态下才能使用英雄的搅扰。C:部分游戏为了吸引玩家,都是一体免费。D:模式上线,布告推出。

 

  1. 用作一个指引,该知道的是软件中的不好,交给队员解决。一向找出软件中欠缺的地点举行优化。

 

  1. 新格局的推出最首要的是故事背景的构想和故事剧情的描绘,游戏对阵跟基础上的同样,美工占最大片段。我会假若唯有5个人,我会分配3个美术,1个开发,1个测试。

———————————分割线——————————————–

  [1] MOBA是Multiplayer Online Battle
Arena
Games的简写,意为多少人共同在线竞赛游艺。一般都会以MOBAGAMES一起落笔。在MOBA游戏中,玩家平常被分为两队,两队在疏散的游乐地图中互相竞争,每个玩家都经过一个RTS风格的界面控制单个角色。1998年,《星际争霸》横空出世,而顿时还绑定了地图编辑器,利用这些效率强大的地形图编辑器,某个玩家打造出一张名为AeonOfStrife的RPG地图(dota的前身),成为富有MOBA游戏的前期雏形。———搜狗百科

  [2] 双轮盘MOBA手游《自由之战》研发集团独创的操作系统,通俗解释就是玩家一手通过转盘控制人物移动,另一手通过转盘控制人物技能,是一种“人物朝向和技巧朝向分离”的重要设计。它出现不仅匡助MOBA游戏完成了从PC端到活动端的完美传承,也为眼前市面上流行的MOBA产品奠定了操作基础。

 

问题叙述

大红知道学弟学妹做题可能很麻烦,特地准备了一道小点心,你看看这道问题会不会有点熟谙呢?

输入一个整数n(n>=1 && n <=26),输出如下的n层字母三角形。

切切实实参看输入输出样例。

输入

多组数据,每行一个正整数,n(n>=1 && n <= 26)

请处理到文件截至。

输出

对于每一个输入的正整数,打印对应的假名三角形。注意每行的空格哦,当n==26时,最后一行行首恰好没有空格。

样例输入

1
2
3

样例输出

                         A
                         A
                        ABA
                         A
                        ABA
                       ABCBA

打印图形:

import java.util.*;
public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){
            int a = sc.nextInt();
            int m,n;
//          System.out.println(a);
            for(int q = 1; q <= a; q++) {

                int cnt = 26 - q;
                for(int k = 1; k <= cnt; k++) {
                    System.out.print(" ");
                }
                m = 0;
                for(int j = cnt+1; j <= 26; j++) {   

                    System.out.print((char)('A'+m));
                    m++;
                }
                n = q-2;;
                for(int t = 1; t < q; t++) {
                    System.out.print((char)('A'+n));
                    n--;
                }
                System.out.println();
            }
        }
}
}

问题 E: 虢莔薅参预运动会

时光限定: 1 Sec  内存限制: 128 MB
提交: 2800  解决: 480
[提交][状态][讨论版]

题材叙述

又到了金色的青春,一年一度的运动会就要来了,虢莔薅同学是班里的体育委员,于是他早日的就订好了运动会的时候和女对象出去玩的计划!不对,是刷题的计划!不过今日他的导员找到了她,让她当做班级代表插足10项比赛!虢莔薅听了说:“这会死的!”,导员哈哈大笑说:“多吃点高钙片就好了”。经过了1个钟头的猛烈争持,多少人到底达成协议,只要导员做出虢莔薅出的题虢莔薅就参预,否则就让他去刷题!于是虢莔薅说出了题:求sum(i^2)%p,1<=i<=n,p是一个素数。(sum表示求和,%表示求余)为了班级的荣誉,你快帮帮导员做出这一个题吗!

输入

多组数据处理到文件截至。(不超越50组)
每行一组数据,包含五个正整数n(1<=n<=10^15),p(2<=p<=10^9)。

输出

对于每组数据,输出一个数,表示sum(i^2)%p的值

样例输入

1 7
2 11
3 13

样例输出

1
5
1

优秀大数运算,即使卡时间怎么破:

import java.util.*;
import java.math.*;
import java.text.*;
public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){
                BigInteger a = sc.nextBigInteger();
                BigInteger b = sc.nextBigInteger();
                BigInteger ans = a.multiply(a.add(BigInteger.valueOf(1))).multiply(a.multiply(BigInteger.valueOf(2)).add(BigInteger.valueOf(1))).divide(BigInteger.valueOf(6)).mod(b);
                System.out.println(ans.toString());
            }
        }
}

题材 G: 锘爷考驾照

时刻限定: 1 Sec  内存限制: 128 MB
提交: 1762  解决: 415
[提交][状态][讨论版]

题材叙述

世家都清楚,锘爷是XDUdp第一人,所以锘爷决定要去考驾照!(那很有逻辑吗),他为了五遍考到驾照,于是买了一辆越野车从该校开回家来磨炼开车,在中途就会有成百上千高山和低谷(低谷可能比地平面低)。经过一段时间的查证,现在她现已知晓了最短的路径,我们借使这是一条直线,并且她必然会走这条直线。可是这也太远了,锘爷想找一段开车的日子小睡,为了更喜笑颜开的打瞌睡,于是锘爷总括了这条路径上有着的深山和山谷的冲天,他想清楚长度为length的旅途中度之和纤维的一段是稍微?

输入

多组数据(不领先50组),处理到文件结束。
对于每组数据,读入一个整数n,length(1<=length<=n<=200000)n表示山峰和低谷数,length表示诺爷打瞌睡的长短。
接下去是n个整数h(i),表示低度,abs(h(i))<=200000。

输出

对此每组数据,输出一个平头表示长度为length中度和的矮小值。

样例输入

3 2
1 2 3
5 3
1 -1 -1 2 -5

样例输出

3
-4

留意看清题目,暴力不是dp,EOF为止:

#include <iostream>
#include <cstdio>

using namespace std;
int n;
const int INF_MAX = 0x3f3f3f3f;

int main() {
    int len;
    while(~scanf("%d%d",&n,&len)) {
    int a[n];
    for(int i = 0; i < n; i++) {
        scanf("%d",&a[i]);
    }
    int sum = 0;
    for(int i = 0; i < len; i++) {
        sum+=a[i];
    }
    int tmp = sum;
    for(int i = len; i < n; i++) {
        sum+=a[i];
        sum-=a[i-len];
        if(sum<tmp)
            tmp = sum;
    }
    cout<<tmp<<endl;
    }
}

问题 J: V8与女友

时刻限定: 1 Sec  内存限制: 128 MB
提交: 1240  解决: 254
[提交][状态][讨论版]

题材叙述

这是漫长的公元前2333年,V8还有女对象的一世。

他和她的女朋友分别是五个离开遥远的部落的元首,这时候从不前些天兴旺的交通工具和路网,V8每趟希望团圆的时候,都要跋山涉水不远万里去相会她的朋友,辛酸的很。经过很频繁的旅途,V8精通了他得以走的拥有的路的门道图,毕竟作为首领,不可以离开自己的领地太久,所以V8希望你给她找出一条目前的路,并且输出一次往返所急需的最长时间,V8并不会在对方领地停留,说个你好就回来了,需要的光阴为0。

虽说无论是您求出来有多快,最后V8仍然认为自己在半路花费的岁月太多,拔取了舍小家而为大家(手动滑稽。

输入

率先行一个正整数t,表示数据的组数(t <=10)。

从此将来对于每组数据,第一行一个正整数k,表示这么些地图(无向图)的路径数(k<=10000)。

然后有k行,每一行六个正整数,s,t,v。表示路的六个端点和这条路需要的时间(s,t,v
<=100)。

第k+1行为多少个数,v,m,表示V8和她爱人的所在地。

输出

对此每组数据,输出一行一个正整数,为V8一个来回最短的大运(数据保证有通路)。

样例输入

1
4
1 2 1
1 3 1
2 4 2
3 4 1
1 4

样例输出

4

dij特斯拉,双向图,结果*2即可:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 2000+5;
int mp[maxn][maxn];
int vis1[maxn];
int vis2[maxn];
int dis1[maxn];
int dis2[maxn];
const int inf = 0x3f3f3f3f;
int main()
{
    //freopen("in.txt","r",stdin);
    int T;
    cin>>T;
    while(T--) {
        int m;
        cin>>m;
        memset(dis1,inf,sizeof(dis1));
//        memset(dis2,inf,sizeof(dis2));
        for(int i = 1; i < maxn; i++) {
            for(int j = 1; j < maxn; j++) {
                    if(i==j) mp[i][j] = 0;
                    else mp[i][j] = inf;
            }
        }
        int a,b,c;
        while(m--) {

            cin>>a>>b>>c;
            mp[a][b] = mp[b][a] = c;
        }
        int Maxn = max(a,b);
        int s,e;
        cin>>s>>e;
        for(int i = 1; i <= Maxn; i++) {
                dis1[i] = mp[s][i];
                vis1[i] = 0;
//                dis2[i] = mp[e][i];

            }
        vis1[s] = 1;
//        vis2[e] = 1;
//        int Min2 = inf;
        int u1;
//        int u2;
        for(int i = 1; i <= Maxn; i++) {
            int Min1 = inf;
            for(int j = 1; j <= Maxn; j++) {
                if(!vis1[j]&&dis1[j]<Min1) {
                    u1=j;
                    Min1 = dis1[j];
                }
//                if(!vis2[j]&&dis2[j]<=Min2) {
//                    u2 = j;
//                    Min2 = dis2[j];
//                }
            }
            vis1[u1] = 1;
//            vis2[u2] = 1;
            for(int j = 1; j <= Maxn; j++) {
                if(!vis1[j]&&dis1[j]>mp[u1][j]+dis1[u1])
                    dis1[j] = mp[u1][j]+dis1[u1];
//                if(!vis2[j]&&dis2[j]>mp[u2][j]+dis2[u2])
//                    dis2[j] = mp[u2][j]+dis2[u2];
            }
        }
        cout<<dis1[e]*2<<endl;
    }
    return 0;
}

题材 F: 总结相似字符串

岁月范围: 1 Sec  内存限制: 128 MB
提交: 1742  解决: 259
[提交][状态][讨论版]

题目叙述

给N个字符串,请将他们以同样的重组要素(即构成的元素序列雷同,每种元素的个数也如出一辙)来分类,分类后遵照原来出现的逐条输出!

输入

多组数据,最多100组数据,每组最多N<5000个字符串,每个字符串长度最多|s|<=8,保证都是小写字母

输出

出口多行,每行为等同品种的字符串组

样例输入

6
eat tea tan ate nat bat

样例输出

eat tea ate
tan nat
bat

字符串处理:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int maxn = 5000+5;

int cmp(char a,char b) {
return a < b;
}
int flag[maxn];
struct Node {
    char s[10];
    int id;
    }node1[maxn],node2[maxn];

int main() {
//   freopen("in.txt","r",stdin);
   int n;
   while(cin>>n) {
   memset(node1,0,sizeof(node1));
   memset(node2,0,sizeof(node2));
   memset(flag,0,sizeof(flag));
   for(int i = 0; i < n; i++) {
        scanf("%s",node1[i].s);
        node1[i].id = i;
        node2[i] = node1[i];
        sort(node1[i].s,node1[i].s+strlen(node1[i].s),cmp);
   }
        for(int i = 0; i < n; i++) {
            if(flag[i]) continue;
            printf("%s",node2[i].s);
            for(int j = i+1; j < n; j++) {
                if(!strcmp(node1[j].s,node1[i].s)) {
                    printf(" %s",node2[j].s);
                    flag[j] = 1;
                }
            }
                    cout<<endl;

        }
   }
    return 0;
}

问题 B: 笑爷买房

时刻限定: 1 Sec  内存限制: 128 MB
提交: 1035  解决: 243
[提交][状态][讨论版]

问题叙述

笑爷打算在迪拜市三环买一套房。

现在笑爷手上有局部房源的户型图,她想明白每套房子的室内面积是有点。
房子的墙壁由’#’表示,一平方米的地头由一个’*’表示。请总计被墙壁包围住的本土面积是有点平方米。

输入

一个由#和*整合的字符矩阵,行列数均不领先50。(不自然是矩形)

输出

输出房屋有稍许平方米并换行。

样例输入

#*#######
##******#
*#######*

样例输出

6

典型BFS:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int MAXN = 52;

int xx[4] = {1, 0 ,-1, 0}, yy[4] = {0, 1, 0, -1}, n = 0, m, imax = 0;
char g[MAXN][MAXN];
struct Qarray {
    int x, y;
    Qarray(int xx, int yy) {
        x = xx;
        y = yy;
    }
};
queue<Qarray> que;

void bfs(int i, int j) {
    int f = 1, res = 0;
    Qarray ns(i,j);
    que.push(ns);
    g[i][j] = '#';
    while (!que.empty()) {
        res++;
        ns = que.front();
        que.pop();
        if (ns.x == 0 || ns.x == n-1 || ns.y == 0 || ns.y == m-1)
            f = 0;
        for(int k = 0; k < 4; k++) {
            int xi = ns.x+xx[k], yi = ns.y+yy[k];
            if (g[xi][yi] == '*') {
                que.push(Qarray(xi, yi));
                g[xi][yi] = '#';
            }
        }
    }
    if (f) imax += res;
}

int main() {
    //freopen("in.txt", "r", stdin);
    while(~scanf("%s", g[n]))
        n++;
    m = strlen(g[0]);
    for(int i = 1; i < n-1; i++)
        for(int j = 1; j < m-1; j++)
            if (g[i][j] == '*')
                bfs(i, j);
    printf("%d\n", imax);
    return 0;
}

题材 H: 杰师傅与锘爷

时光限定: 1 Sec  内存限制: 128 MB
提交: 699  解决: 186
[提交][状态][讨论版]

题材叙述

吃惊!XDUACM实验室中忆起了啪啪啪的响声,杰师傅在边际沉默。这声音不是键盘声,而是鼠标声!“你萌别打dota了,快去刷题”杰师傅大喊,然则她看了一眼被吓到的锘爷,于是妥协了,就给锘锘出了一道游戏比赛,让锘爷洋洋得意。那多少个是一个回合制游戏,有两群orz熊猫分别为a,b只,每五遍合,锘爷和杰师傅轮流举办操作,每一次操作可以kill掉s个率先群orz熊猫,或者kill掉t个第二群orz熊猫,其中1<=s<=c,1<=t<=d。最终什么人取不了,算什么人输!(即就是轮到某个人取了,然而两堆都是0个,不能操作)有爱心的杰师傅决定让锘爷先手,那么请你告诉锘爷他是不是能赢,能赢的话输出“NUO!”,无法的话输出“NO!”,没有引号。杰师傅和锘爷相对聪明,有必胜策略的话,他们不会出错!

输入

多组数据(不超越100组),处理到文件停止。
每组数据一行,三个整数a,b,c,d,1<=c<=a<=1000, 1<=d<=b<=1000

输出

对此每组数据输出一行,锘爷能赢的话输出“NUO!”,不可能的话输出“NO!”,没有引号。

样例输入

1 1 1 1
3 2 1 2

样例输出

NO!
NUO!

出色巴什博弈:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int MAXN = 52;

int main() {
    int a, b, c, d;
    while(~scanf("%d%d%d%d", &a, &b, &c, &d)) {
        if ((a%(c+1)) != (b%(d+1))) printf("NUO!\n");
        else printf("NO!\n");
    }
    return 0;
}

题材 A: 大红数星星

时光限定: 3 Sec  内存限制: 128 MB
提交: 1066  解决: 67
[提交][状态][讨论版]

题材叙述

“三角形极度的漂亮,相信我们小学就学过三角具有稳定性,三角形也是二维几何中最主题的不可或缺的要素之……”,大红走在路上若有所思,突然抬头看看了天上中有成百上千很亮的有限划过,星星和他们划过的轨迹像极了一个无向图。于是好学的大红,就从头数起了“三角形”,1、2、3……数了旷日持久,大红数的泪水都掉下来了,所以她哭着哀求你来帮她,你如此好心一定不会拒绝啊!大红的三角形的定义:即使存在这么的多少个边(A,B)、(B,C)、(A,C)(无向边),则算一个三角。
大红会告诉你这么些图G=(V,E),点数(星星个数)n和边数(轨迹个数)m以及每条边的六个点。

五个三角不同是:当对于两个三角的边,某个三角形存在一条边在另一个三角的边中无法找到!

输入

多组数据。
首先行一个整数T<=10表示数据组数。
对于每组数据的首先行n表示星星个数,m表示星星划过的轨道的个数,
接下去m行表示每个星星划过的轨道的端点x,y(1<=x,y<=n)。
1<=n<=100000,1<=m<=min(100000,n*(n-1)/2)

输出

对此每组数据输出一个平头,表示三角形的个数。

样例输入

1
3 3
1 2
2 3
1 3

样例输出

1

提示

保证数据没有重边和自环。

压轴题,卡时间,技巧暴力:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5;
const int hash_base = 1000007;
int n, m, cur;
struct node{
    LL data;
    int next;
}list[hash_base];
int table[hash_base];

int get_hash(int u, int v) {
    LL h = ((LL)u)*n+v;
    return (int)(h%hash_base);
}

void insert(int u, int v) {
    int h = get_hash(u, v);
    list[cur].data = ((LL)u)*n+v;
    list[cur].next = table[h];
    table[h] = cur;
    cur++;
}

bool find_edge(int u, int v) {
    LL h = ((LL)u)*n+v;
    int k = get_hash(u, v);
    int q = table[k];
    while(q != -1) {
        if(list[q].data == h) return true;
        q = list[q].next;
    }
    return false;
}

void in(int &a) {
    char ch;
    while((ch=getchar()) < '0' || ch > '9');
    for(a = 0; ch >= '0' && ch <= '9'; ch = getchar())
        a = a*10 + ch - '0';
}

vector<int>G[maxn];
int d[maxn];

bool is_ok(int u, int v) {
    if(find_edge(u, v) || find_edge(v, u)) return true;
    return false;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        memset(d, 0, sizeof(d));
        cur = 0;
        for(int i = 0; i <= hash_base; ++i) {
            table[i] = -1;
            list[i].next = -1;
        }
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i) G[i].clear();
        int u, v;
        for(int i = 0; i < m; ++i) {
            in(u); in(v);
            G[u].push_back(v);
            G[v].push_back(u);
            d[v]++;
            d[u]++;
            insert(u, v);
        } 
        int ans = 0, div = sqrt(m);
        int p[maxn], cnt = 0;
        for(int i = 1; i <= n; ++i) {
            if(d[i] <= div) {
                for(int j = 0; j < G[i].size(); ++j) if(i <= G[i][j] || d[G[i][j]] > div)
                    for(int k = j+1; k < G[i].size(); ++k) if(G[i][k] >= i || d[G[i][k]] > div){
                        u = G[i][j], v = G[i][k];
                        if(is_ok(u, v)) ans++;
                    }
            }
            else p[cnt++] = i;
        }
        for(int i = 0; i < cnt; ++i)
            for(int j = i+1; j < cnt; ++j) if(is_ok(p[i], p[j]))
                for(int k = j+1; k < cnt; ++k) {
                    if(is_ok(p[i], p[k]) && is_ok(p[j], p[k])) ans++;
                }
        printf("%d\n", ans);
    }
    return 0;
}

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*
*
Website