网站备案必须在公司注册地,张家港市住房城乡建设局网站,签订网站制作合同注意事项,网站建设技术人员工作总结【题目链接】:http://codeforces.com/contest/534/problem/D 【题意】 n个人依次进入一个房间; 进进来的人会和房间里面没有组队的人握一次手; (这里的握手只计算主动握手的那个人的握手次数); (任意时刻,任意3个人都能组队)#xff1b; 给出每个人的握手信息; 问你n个… 【题目链接】:http://codeforces.com/contest/534/problem/D 【题意】 n个人依次进入一个房间; 进进来的人会和房间里面没有组队的人握一次手; (这里的握手只计算主动握手的那个人的握手次数); (任意时刻,任意3个人都能组队) 给出每个人的握手信息; 问你n个人进入房间的顺序是怎么样的。 【题解】 一开始房间里面一个人都没有; 这个时候,看看哪个人握手的次数为0; - 房间里面变成了两个人,然后看看哪个人的握手次数为2 - 房间里面变成了三个人,然后看看哪个人的握手次数为3 - … 然后如果遇到没有和房间里面的人数相符合的握手数; 就尝试去掉3个人(这3个人就相当于是去掉了); 然后再看看有没有和房间里面人数相对应的握手次数; 以此类推; 如果已经没办法减少人数了,且还有人没有进入房间,且没有人和房间里面的人数的握手数相对应; 则输出无解信息. 【完整代码】 #include bits/stdc.h
using namespace std;
#define lson l,m,rt1
#define rson m1,r,rt1|1
#define LL long long
#define rep1(i,a,b) for (int i a;i b;i)
#define rep2(i,a,b) for (int i a;i b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf(%d,x)
#define rel(x) scanf(%lld,x)
#define ref(x) scanf(%lf,x)typedef pairint, int pii;
typedef pairLL, LL pll;const int dx[9] { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] { 0,0,0,-1,1,-1,1,-1,1 };
const double pi acos(-1.0);
const int N 2e5100;int n;
vector int v[N],ans;
int bo[N],num,tot;int main()
{//freopen(F:\\rush.txt, r, stdin);rei(n);rep1(i, 1, n){int x;rei(x);bo[x];v[x].push_back(i);}while (tot n){if (!bo[num]){while (num 3){num - 3;if (bo[num]) break;}if (!bo[num])return puts(Impossible),0;}bo[num]--;ans.push_back(v[num].back());v[num].pop_back();num, tot;}puts(Possible);rep1(i, 0, tot - 1){printf(%d, ans[i]);if (i tot - 1)puts();elseputchar( );}//printf(\n%.2lf sec \n, (double)clock() / CLOCKS_PER_SEC);return 0;
} 转载于:https://www.cnblogs.com/AWCXV/p/7626510.html
