Intervals
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5488 Accepted Submission(s): 1999
Problem Description
You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.
Write a program that:
> reads the number of intervals, their endpoints and integers c1, ..., cn from the standard input,
> computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i = 1, 2, ..., n,
> writes the answer to the standard output
Write a program that:
> reads the number of intervals, their endpoints and integers c1, ..., cn from the standard input,
> computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i = 1, 2, ..., n,
> writes the answer to the standard output
Input
The first line of the input contains an integer n (1 <= n <= 50 000) - the number of intervals. The following n lines describe the intervals. The i+1-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50 000 and 1 <= ci <= bi - ai + 1.
Process to the end of file.
Process to the end of file.
Output
The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i = 1, 2, ..., n.
Sample Input
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
Sample Output
6
Author
1384
Recommend
Eddy
倒没想到隐含条件
做含有不等式关系的题时要想到差分约束
设sum(a) 为小于等于a的在集合中的元素
根据
如果需要求的是两个变量差的最大值，那么需要将所有不等式转变成"<="的形式，建图后求最短路；相反，如果需要求的是两个变量差的最小值，那么需要将所有不等式转化成">="，建图后求最长路
建图
注意隐含条件
sum(i) - sum(i - 1) >= 0
sum(i) - sum(i - 1) <= 1
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <cctype> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <bitset> #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i<n; i++) #define lap(i, a, n) for(int i=n; i>=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define rd(a) scanf("%d", &a) #define rlld(a) scanf("%lld", &a) #define rc(a) scanf("%c", &a) #define rs(a) scanf("%s", a) #define rb(a) scanf("%lf", &a) #define rf(a) scanf("%f", &a) #define pd(a) printf("%d ", a) #define plld(a) printf("%lld ", a) #define pc(a) printf("%c ", a) #define ps(a) printf("%s ", a) #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 101000, INF = 0x7fffffff; int head[maxn], nex[maxn << 1], d[maxn], vis[maxn]; int cnt, n, ans[maxn]; struct node { int u, v, w; }Node[maxn << 1]; void add(int u, int v, int w) { Node[cnt].u = u; Node[cnt].v = v; Node[cnt].w = w; nex[cnt] = head[u]; head[u] = cnt++; } bool spfa(int s) { mem(d, -0x3f); queue<int> Q; Q.push(s); vis[s] = 1; d[s] = 0; while(!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = 0; for(int i = head[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(d[v] < d[u] + Node[i].w) { d[v] = d[u] + Node[i].w; if(!vis[v]) { Q.push(v); vis[v] = 1; if(++ans[v] > n) return 1; } } } } return 0; } int main() { while(~scanf("%d", &n)) { mem(head, -1); mem(vis, 0); mem(ans, 0); cnt = 0; int u, v, w; int mx = -INF, mi = INF; for(int i = 1; i <= n; i++) { rd(u), rd(v), rd(w); u++, v++; mx = max(mx, v); mi = min(mi, u); add(u - 1, v, w); } for(int i = mi; i <= mx; i++) { // add(mi, i, 0); add(i - 1, i, 0); add(i, i - 1, -1); } spfa(mi - 1); pd(d[mx]); } return 0; }
World Exhibition
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2440 Accepted Submission(s): 1171
Problem Description
Nowadays, many people want to go to Shanghai to visit the World Exhibition. So there are always a lot of people who are standing along a straight line waiting for entering. Assume that there are N (2 <= N <= 1,000) people numbered 1..N who are standing in the same order as they are numbered. It is possible that two or more person line up at exactly the same location in the condition that those visit it in a group.
There is something interesting. Some like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of X (1 <= X <= 10,000) constraints describes which person like each other and the maximum distance by which they may be separated; a subsequent list of Y constraints (1 <= Y <= 10,000) tells which person dislike each other and the minimum distance by which they must be separated.
Your job is to compute, if possible, the maximum possible distance between person 1 and person N that satisfies the distance constraints.
There is something interesting. Some like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of X (1 <= X <= 10,000) constraints describes which person like each other and the maximum distance by which they may be separated; a subsequent list of Y constraints (1 <= Y <= 10,000) tells which person dislike each other and the minimum distance by which they must be separated.
Your job is to compute, if possible, the maximum possible distance between person 1 and person N that satisfies the distance constraints.
Input
First line: An integer T represents the case of test.
The next line: Three space-separated integers: N, X, and Y.
The next X lines: Each line contains three space-separated positive integers: A, B, and C, with 1 <= A < B <= N. Person A and B must be at most C (1 <= C <= 1,000,000) apart.
The next Y lines: Each line contains three space-separated positive integers: A, B, and C, with 1 <= A < B <= C. Person A and B must be at least C (1 <= C <= 1,000,000) apart.
The next line: Three space-separated integers: N, X, and Y.
The next X lines: Each line contains three space-separated positive integers: A, B, and C, with 1 <= A < B <= N. Person A and B must be at most C (1 <= C <= 1,000,000) apart.
The next Y lines: Each line contains three space-separated positive integers: A, B, and C, with 1 <= A < B <= C. Person A and B must be at least C (1 <= C <= 1,000,000) apart.
Output
For each line: A single integer. If no line-up is possible, output -1. If person 1 and N can be arbitrarily far apart, output -2. Otherwise output the greatest possible distance between person 1 and N.
Sample Input
1
4 2 1
1 3 8
2 4 15
2 3 4
Sample Output
19
Author
alpc20
Source
Recommend
zhouzeyong
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #define rap(i, a, n) for(int i=a; i<=n; i++) #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 10010, INF = 0x7fffffff; int head[maxn], ans[maxn], vis[maxn]; int n, m, cnt, s; int d[maxn]; struct node { int v, next; int w; }Node[maxn*25]; void add(int u, int v, int w) { Node[cnt].v = v; Node[cnt].w = w; Node[cnt].next = head[u]; head[u] = cnt++; } int spfa() { // mem(vis, 0); for(int i = 0; i < maxn; i++) d[i] = INF; queue<int> Q; mem(ans, 0); Q.push(s); vis[s] = 1; d[s] = 0; // mem(vis, 0); // for(int i=1; i<=n; i++) // { // Q.push(i); // d[i] = INF; // vis[i] = 1; // } while(!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = 0; for(int i=head[u]; i!=-1; i=Node[i].next) { node e = Node[i]; if(d[e.v] > d[u] + e.w) { d[e.v] = d[u] + e.w; if(!vis[e.v]) { Q.push(e.v); vis[e.v] = 1; if(++ans[e.v] > n) return 1; } } } } return 0; } void init() { mem(head, -1); cnt = 0; } bool check(int x) { bool flag = 0; for(int i = 0; i < cnt; i++) Node[i].w -= x; if(spfa()) flag = 1; for(int i = 0; i < cnt; i++) Node[i].w += x; return flag; } int main() { int x; int T; scanf("%d", &T); while(T--) { scanf("%d%d%d", &n, &m, &x); init(); int u, v, w, l = 0, r = 0; s = 1; rap(i, 1, m) { scanf("%d%d%d", &u, &v, &w); if(u > v) swap(u, v); add(u, v, w); } rap(i, 1, x) { scanf("%d%d%d", &u, &v, &w); if(u > v) swap(u, v); add(v, u, -w); } if(spfa()) printf("-1 "); else if(d[n] == INF) printf("-2 "); else printf("%d ", d[n]); } return 0; }
King
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2348 Accepted Submission(s): 1052
Problem Description
Once, in one kingdom, there was a queen and that queen was expecting a baby. The queen prayed: ``If my child was a son and if only he was a sound king.'' After nine months her child was born, and indeed, she gave birth to a nice son.
Unfortunately, as it used to happen in royal families, the son was a little retarded. After many years of study he was able just to add integer numbers and to compare whether the result is greater or less than a given integer number. In addition, the numbers had to be written in a sequence and he was able to sum just continuous subsequences of the sequence.
The old king was very unhappy of his son. But he was ready to make everything to enable his son to govern the kingdom after his death. With regards to his son's skills he decided that every problem the king had to decide about had to be presented in a form of a finite sequence of integer numbers and the decision about it would be done by stating an integer constraint (i.e. an upper or lower limit) for the sum of that sequence. In this way there was at least some hope that his son would be able to make some decisions.
After the old king died, the young king began to reign. But very soon, a lot of people became very unsatisfied with his decisions and decided to dethrone him. They tried to do it by proving that his decisions were wrong.
Therefore some conspirators presented to the young king a set of problems that he had to decide about. The set of problems was in the form of subsequences Si = {aSi, aSi+1, ..., aSi+ni} of a sequence S = {a1, a2, ..., an}. The king thought a minute and then decided, i.e. he set for the sum aSi + aSi+1 + ... + aSi+ni of each subsequence Si an integer constraint ki (i.e. aSi + aSi+1 + ... + aSi+ni < ki or aSi + aSi+1 + ... + aSi+ni > ki resp.) and declared these constraints as his decisions.
After a while he realized that some of his decisions were wrong. He could not revoke the declared constraints but trying to save himself he decided to fake the sequence that he was given. He ordered to his advisors to find such a sequence S that would satisfy the constraints he set. Help the advisors of the king and write a program that decides whether such a sequence exists or not.
Unfortunately, as it used to happen in royal families, the son was a little retarded. After many years of study he was able just to add integer numbers and to compare whether the result is greater or less than a given integer number. In addition, the numbers had to be written in a sequence and he was able to sum just continuous subsequences of the sequence.
The old king was very unhappy of his son. But he was ready to make everything to enable his son to govern the kingdom after his death. With regards to his son's skills he decided that every problem the king had to decide about had to be presented in a form of a finite sequence of integer numbers and the decision about it would be done by stating an integer constraint (i.e. an upper or lower limit) for the sum of that sequence. In this way there was at least some hope that his son would be able to make some decisions.
After the old king died, the young king began to reign. But very soon, a lot of people became very unsatisfied with his decisions and decided to dethrone him. They tried to do it by proving that his decisions were wrong.
Therefore some conspirators presented to the young king a set of problems that he had to decide about. The set of problems was in the form of subsequences Si = {aSi, aSi+1, ..., aSi+ni} of a sequence S = {a1, a2, ..., an}. The king thought a minute and then decided, i.e. he set for the sum aSi + aSi+1 + ... + aSi+ni of each subsequence Si an integer constraint ki (i.e. aSi + aSi+1 + ... + aSi+ni < ki or aSi + aSi+1 + ... + aSi+ni > ki resp.) and declared these constraints as his decisions.
After a while he realized that some of his decisions were wrong. He could not revoke the declared constraints but trying to save himself he decided to fake the sequence that he was given. He ordered to his advisors to find such a sequence S that would satisfy the constraints he set. Help the advisors of the king and write a program that decides whether such a sequence exists or not.
Input
The input consists of blocks of lines. Each block except the last corresponds to one set of problems and king's decisions about them. In the first line of the block there are integers n, and m where 0 < n <= 100 is length of the sequence S and 0 < m <= 100 is the number of subsequences Si. Next m lines contain particular decisions coded in the form of quadruples si, ni, oi, ki, where oi represents operator > (coded as gt) or operator < (coded as lt) respectively. The symbols si, ni and ki have the meaning described above. The last block consists of just one line containing 0.
Output
The output contains the lines corresponding to the blocks in the input. A line contains text successful conspiracy when such a sequence does not exist. Otherwise it contains text lamentable kingdom. There is no line in the output corresponding to the last ``null'' block of the input.
Sample Input
4 2
1 2 gt 0
2 2 lt 2
1 2
1 0 gt 0
1 0 lt 0
0
Sample Output
lamentable kingdom
successful conspiracy
Source
Recommend
LL
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #define rap(i, a, n) for(int i=a; i<=n; i++) #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 10010, INF = 0x7fffffff; int head[maxn], ans[maxn], vis[maxn]; int n, m, cnt, s; int d[maxn]; struct node { int v, next; int w; }Node[maxn*25]; void add(int u, int v, int w) { Node[cnt].v = v; Node[cnt].w = w; Node[cnt].next = head[u]; head[u] = cnt++; } int spfa() { mem(vis, 0); mem(d, 0x3f); queue<int> Q; mem(ans, 0); for(int i=0; i<=n; i++) { Q.push(i); d[i] = 0; vis[i] = 1; } while(!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = 0; for(int i=head[u]; i!=-1; i=Node[i].next) { node e = Node[i]; if(d[e.v] > d[u] + e.w) { d[e.v] = d[u] + e.w; if(!vis[e.v]) { Q.push(e.v); vis[e.v] = 1; if(++ans[e.v] > n) return 1; } } } } return 0; } void init() { mem(head, -1); cnt = 0; } bool check(int x) { bool flag = 0; for(int i = 0; i < cnt; i++) Node[i].w -= x; if(spfa()) flag = 1; for(int i = 0; i < cnt; i++) Node[i].w += x; return flag; } int main() { int x; while(scanf("%d", &n) && n) { scanf("%d", &m); init(); int u, v, w, l = 0, r = 0; s = n + 2; char str[3]; rap(i, 1, m) { scanf("%d%d%s%d", &u, &v, str, &w); if(str[0] == 'g') add(u - 1, u + v, - 1 - w); else add(u + v, u - 1, w - 1); } bool flag = spfa(); if(flag) cout << "successful conspiracy" << endl; else cout << "lamentable kingdom" << endl; } return 0; }
THE MATRIX PROBLEM
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9774 Accepted Submission(s): 2508
Problem Description
You have been given a matrix CN*M, each element E of CN*M is positive and no more than 1000, The problem is that if there exist N numbers a1, a2, … an and M numbers b1, b2, …, bm, which satisfies that each elements in row-i multiplied with ai and each elements in column-j divided by bj, after this operation every element in this matrix is between L and U, L indicates the lowerbound and U indicates the upperbound of these elements.
Input
There are several test cases. You should process to the end of file.
Each case includes two parts, in part 1, there are four integers in one line, N,M,L,U, indicating the matrix has N rows and M columns, L is the lowerbound and U is the upperbound (1<=N、M<=400,1<=L<=U<=10000). In part 2, there are N lines, each line includes M integers, and they are the elements of the matrix.
Each case includes two parts, in part 1, there are four integers in one line, N,M,L,U, indicating the matrix has N rows and M columns, L is the lowerbound and U is the upperbound (1<=N、M<=400,1<=L<=U<=10000). In part 2, there are N lines, each line includes M integers, and they are the elements of the matrix.
Output
If there is a solution print "YES", else print "NO".
Sample Input
3 3 1 6
2 3 4
8 2 6
5 2 9
Sample Output
YES
Source
Recommend
lcy
可以得出要求是 L <= num[i][j] * a[i] / b[j] <= U
可以转换一下变成
log(L / num[i][j]) <= log(a[i]) - log(b[i]) <= log(U / num[i][j])
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <cctype> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <bitset> #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i<n; i++) #define lap(i, a, n) for(int i=n; i>=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define rd(a) scanf("%d", &a) #define rlld(a) scanf("%lld", &a) #define rc(a) scanf("%c", &a) #define rs(a) scanf("%s", a) #define rb(a) scanf("%lf", &a) #define rf(a) scanf("%f", &a) #define pd(a) printf("%d ", a) #define plld(a) printf("%lld ", a) #define pc(a) printf("%c ", a) #define ps(a) printf("%s ", a) #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 1100000, INF = 0x7fffffff; int n, m, s; int head[maxn], cnt, nex[maxn << 1], vis[maxn]; int ans[maxn]; double d[maxn]; struct node { int u, v; double w; }Node[maxn << 1]; void add(int u, int v, double w) { Node[cnt].u = u; Node[cnt].v = v; Node[cnt].w = w; nex[cnt] = head[u]; head[u] = cnt++; } int spfa() { for(int i = 0; i < maxn; i++) d[i] = INF; mem(ans, 0); deque<int> Q; Q.push_front(s); mem(vis, 0); vis[s] = 1; d[s] = 0; while(!Q.empty()) { int u = Q.front(); Q.pop_front(); vis[u] = 0; for(int i = head[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(d[v] > d[u] + Node[i].w) { d[v] = d[u] + Node[i].w; if(!vis[v]) { if(Q.empty()) Q.push_front(v); else if(d[v] < d[Q.front()]) Q.push_front(v); else Q.push_back(v); vis[v] = 1; if(++ans[v] > n) return 1; } } } } return 0; } int main() { int l, r; while(scanf("%d%d%d%d", &n, &m, &l, &r) != EOF) { mem(head, -1); cnt = 0; int u, v, x; s = 1; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j ++) { rd(x); add(i, n + j, -log(l / (double) x)); add(n + j, i, log(r / (double) x)); } if(spfa()) cout << "NO" << endl; else cout << "YES" << endl; } return 0; }