首页 / HTML / TopcoderSRM638DIV2(大力出奇迹)_html/css_WEB-ITnose

TopcoderSRM638DIV2(大力出奇迹)_html/css_WEB-ITnose

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了TopcoderSRM638DIV2(大力出奇迹)_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8434字，纯文字阅读大概需要13分钟。

内容图文

水题，就是一个暴力。大力出奇迹。

Problem Statement

There is a narrow passage. Inside the passage there are some wolves. You are given a vector size that contains the sizes of those wolves, from left to right.


The passage is so narrow that some pairs of wolves cannot pass by each other. More precisely, two adjacent wolves may swap places if and only if the sum of their sizes is maxSizeSum or less. Assuming that no wolves leave the passage, what is the number of different permutations of wolves in the passage? Note that two wolves are considered different even if they have the same size.


Compute and return the number of permutations of wolves that can be obtained from their initial order by swapping a pair of wolves zero or more times.

Definition

Class: NarrowPassage2Easy
Method: count
Parameters: vector , int
Returns: int
Method signature: int count(vector size, int maxSizeSum)
(be sure your method is public)

Limits

Time limit (s): 2.000
Memory limit (MB): 256

Constraints

- size will contain between 1 and 6 elements, inclusive.
- Each element in size will be between 1 and 1,000, inclusive.
- maxSizeSum will be between 1 and 1,000, inclusive.

Examples

0) 
{1, 2, 3}
 
Returns: 2
From {1, 2, 3}, you can swap 1 and 2 to get {2, 1, 3}. But you can't get other permutations.
1) 
{1, 2, 3}
 
1000
 
Returns: 6
Here you can swap any two adjacent wolves. Thus, all 3! = 6 permutations are possible.
2) 
{1, 2, 3}
 
Returns: 3
You can get {1, 2, 3}, {2, 1, 3} and {2, 3, 1}.
3) 
{1,1,1,1,1,1}
 
Returns: 720
All of these wolves are different, even though their sizes are the same. Thus, there are 6! different permutations possible.
4) 
{2,4,6,1,3,5}
 
Returns: 60
5) 
{1000}
 
1000
 
Returns: 1
 
#include #include #include #include #include #include #include #include #include #include #include #include #define eps 1e-10///#define M 1000100///#define LL __int64#define LL long long#define INF 0x7fffffff#define PI 3.1415926535898#define zero(x) ((fabs(x)<eps)?0:x)using namespace std;const int maxn = 1000010;int vis[10][10];class NarrowPassage2Easy{public:    int count(vector  size, int maxSizeSum)    {        int len = size.size();        memset(vis, 0, sizeof(vis));        for(int i = 1; i <= len; i++)        {            for(int j = i+1; j <= len; j++)            {                int x = size[i-1]+size[j-1];                if(x > maxSizeSum)                {                    ///vis[i][j] = 1;                    vis[j][i] = 1;                }            }        }        for(int i = 1; i <= len; i++)        {            for(int j = 1; j <= len; j++)            {                cout<<vis[i][j]<<" ";            }            cout<<endl;        }        int sum = 0;        if(len == 1) return 1;        if(len == 2)        {            if(size[0]+size[1] > maxSizeSum) return 1;            return 2;        }        if(len == 3)        {            for(int i = 1; i <= len; i++)            {                for(int j = 1; j <= len; j++)                {                    if(i == j) continue;                    for(int k = 1; k <= len; k++)                    {                        if(k == i || k == j) continue;                        if(vis[i][j] || vis[i][k] || vis[j][k]) continue;                        sum++;                    }                }            }        }        if(len == 4)        {            for(int i1 = 1; i1 <= len; i1++)            {                for(int i2= 1; i2 <= len; i2++)                {                    if(i1 == i2) continue;                    for(int i3 = 1; i3 <= len; i3++)                    {                        if(i1 == i3 || i2 == i3) continue;                        for(int i4 = 1; i4 <= len; i4++)                        {                            if(i1 == i4 || i2 == i4 || i3 == i4) continue;                            if(vis[i1][i2] || vis[i1][i3] || vis[i1][i4]                                       || vis[i2][i3] ||vis[i2][i4]                                       ||vis[i3][i4]) continue;                                sum++;                        }                    }                }            }        }        if(len == 5)        {            for(int i1 = 1; i1 <= len; i1++)            {                for(int i2= 1; i2 <= len; i2++)                {                    if(i1 == i2) continue;                    for(int i3 = 1; i3 <= len; i3++)                    {                        if(i1 == i3 || i2 == i3) continue;                        for(int i4 = 1; i4 <= len; i4++)                        {                            if(i1 == i4 || i2 == i4 || i3 == i4) continue;                            for(int i5 = 1; i5 <= len; i5++)                            {                                if(i1 == i5 || i2 == i5 || i3 == i5 || i4 == i5) continue;                                if(vis[i1][i2] || vis[i1][i3] || vis[i1][i4] || vis[i1][i5]                                       || vis[i2][i3] ||vis[i2][i4] || vis[i2][i5]                                       ||vis[i3][i4] || vis[i3][i5]                                       ||vis[i4][i5]) continue;                                sum++;                            }                        }                    }                }            }        }        if(len == 6)        {            for(int i1 = 1; i1 <= len; i1++)            {                for(int i2= 1; i2 <= len; i2++)                {                    if(i1 == i2) continue;                    for(int i3 = 1; i3 <= len; i3++)                    {                        if(i1 == i3 || i2 == i3) continue;                        for(int i4 = 1; i4 <= len; i4++)                        {                            if(i1 == i4 || i2 == i4 || i3 == i4) continue;                            for(int i5 = 1; i5 <= len; i5++)                            {                                if(i1 == i5 || i2 == i5 || i3 == i5 || i4 == i5) continue;                                for(int i6 = 1; i6 <= len; i6++)                                {                                    if(i1 == i6 || i2 == i6 || i3 == i6 || i4 == i6 || i6 == i5) continue;                                    if(vis[i1][i2] || vis[i1][i3] || vis[i1][i4] || vis[i1][i5] || vis[i1][i6]                                       || vis[i2][i3] ||vis[i2][i4] || vis[i2][i5] || vis[i2][i6]                                       ||vis[i3][i4] || vis[i3][i5] || vis[i3][i6]                                       ||vis[i4][i5] || vis[i4][i6]                                       || vis[i5][i6]) continue;                                   sum ++;                                }                            }                        }                    }                }            }        }        return sum;    }};int main(){    NarrowPassage2Easy a;    vector f;    f.push_back(189);    f.push_back(266);    cout<

内容总结

以上是互联网集市为您收集整理的TopcoderSRM638DIV2(大力出奇迹)_html/css_WEB-ITnose全部内容，希望文章能够帮你解决TopcoderSRM638DIV2(大力出奇迹)_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/399099.html

来源：【匿名】