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

贴一个AC的代码,算是给后人做点贡献

Posted by houzhe at 2022-01-10 04:35:15 on Problem 3046
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <sstream>
#include <math.h> 
#include <string.h>
#include <algorithm>
#include <numeric>
#include <deque>
#include <climits>

using namespace std;

typedef long long ll;

// const double M_PI = acos(-1.0);
// const double E = 2.71828182845904523536029;

const int MAX_ANT = 10010;
ll MD = 1000000;

ll dp[MAX_ANT];

int main() {
	int t, a, s, b;
	cin >> t >> a >> s >> b;
	vector<int> ants(t + 1);
	for (int i = 0; i < a; i++) {
		int ant; cin >> ant;
		ants[ant]++;
	}

	for (int family = 1; family <= t; family++) {
		int familySize = ants[family];
		for (int set = a; set >= 1; set--) {
			ll setSize = dp[set] - dp[set - 1];
			if (familySize >= set) {
				setSize += 1;
			}

			int s = max(set - familySize - 1, 0);
			int e = set - 1;
			setSize = dp[e] - dp[s] + MD + setSize;
			
			dp[set] = setSize % MD;
		}

		for (int i = 1; i <= a; i++) {
			dp[i] = (dp[i] + dp[i - 1]) % MD;
		}
	}

	cout << (dp[b] - dp[s-1] + MD) % MD << endl;
	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