Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学暑期课《ACM/ICPC竞赛训练》面向全球招生!

理论最高复杂度是假的,实际算出来每次转移最多只有377*377

Posted by Techiah at 2018-05-16 20:53:41 on Problem 3254
=.=我感觉加了一堆set和map试图剪枝反而增加了复杂度,纯暴力能跑得快很多
打precal表的时间比实际跑算法都长,打出来一看只有377个元素。。。
第一次没对结果取模,改后 63MS 800K AC
代码

#define _CRT_SECURE_NO_WARNINGS
#pragma _attribute_((optimize("-O2")))
#pragma comment(linker, "/STACK:102400000,102400000")

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <cstdio>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <sstream>
#include <ctime>
#include <complex>
#include <iomanip>
//#define Endl endl
//#define int long long

//#define Local

using namespace std;
set<int> precal;

int now;

const int md = 1e8;

void pre(int p, int l)
{
	if (p == 12)
	{
		precal.insert(now);
		return;
	}
	if (l)
	{
		now <<= 1;
		pre(p + 1, 0);
		now >>= 1;
	}
	else
	{
		now <<= 1;
		pre(p + 1, 0);
		now >>= 1;
		now <<= 1;
		now++;
		pre(p + 1, 1);
		now >>= 1;
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	//freopen("input1.txt", "r", stdin);
	//freopen("output1.txt", "w", stdout);

	int n, m;
	cin >> n >> m;

	map<int, int> cal[4100];

	pre(0, 0);
	pre(0, 1);

	now = 0;
	for (int i = 0; i < m; i++)
	{
		now <<= 1;
		int tmp;
		cin >> tmp;
		now += tmp;
	}
	for (set<int>::iterator it = precal.begin(); it != precal.end(); ++it)
	{
		if ((*it | now) == now)
			cal[0].insert({ *it,1 });
	}

	for (int i = 1; i < n; i++)
	{
		now = 0;
		for (int j = 0; j < m; j++)
		{
			now <<= 1;
			int tmp;
			cin >> tmp;
			now += tmp;
		}
		for (set<int>::iterator it = precal.begin(); it != precal.end(); ++it)
		{
			if (*it > now)
				break;
			if ((*it | now) == now)
				for (map<int, int>::iterator j = cal[i - 1].begin(); j != cal[i - 1].end(); ++j)
					if ((j->first&*it) == 0)
						cal[i][*it] += j->second, cal[i][*it] %= md;
		}
	}
	int cont = 0;
	for (map<int, int>::iterator j = cal[n - 1].begin(); j != cal[n - 1].end(); ++j)
		cont += j->second, cont %= md;
	cout << cont << endl;


#ifdef Local
	cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
#endif
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator