ZS the Coder has drawn an undirected graph of $n$ vertices numbered from $0$ to $n-1$ and m edges between them. Each edge of the graph is weighted, each weight is a positive integer.
The next day, ZS the Coder realized that some of the weights were erased! So he wants to reassign positive integer weight to each of the edges which weights were erased, so that the length of the shortest path between vertices $s$ and $t$ in the resulting graph is exactly $L$. Can you help him?
题意概述
给定一张连通无向图,其中所有边的权值均为自然数。要求将所有权值为$0$的边的权值变成任意一个不大于$10^{18}$的正整数,使得从$s$到$t$的最短路径的长度为$L$。
数据范围:$2 \le n \le 1000, \; 1 \le m \le 10000, \; 1 \le L \le 10^9, \; 0 \le s, t \le n-1$。
As you might remember from the previous round, Vova is currently playing a strategic game known as Rage of Empires.
Vova managed to build a large army, but forgot about the main person in the army – the commander. So he tries to hire a commander, and he wants to choose the person who will be respected by warriors.
Each warrior is represented by his personality – an integer number $p_i$. Each commander has two characteristics — his personality $p_j$ and leadership $l_j$ (both are integer numbers). Warrior $i$ respects commander $j$ only if $p_i \oplus p_j \lt l_j$ ($x \oplus y$ is the bitwise excluding OR of $x$ and $y$).
Initially Vova’s army is empty. There are three different types of events that can happen with the army:
1 $p_i$ – one warrior with personality $p_i$ joins Vova’s army;
2 $p_i$ – one warrior with personality $p_i$ leaves Vova’s army;
3 $p_i$ $l_i$ – Vova tries to hire a commander with personality $p_i$ and leadership $l_i$.
For each event of the third type Vova wants to know how many warriors (counting only those who joined the army and haven’t left yet) respect the commander he tries to hire.
Fox Ciel is participating in a party in Prime Kingdom. There are $n$ foxes there (include Fox Ciel). The $i$-th fox is $a_i$ years old.
They will have dinner around some round tables. You want to distribute foxes such that:
each fox is sitting at some table,
each table has at least 3 foxes sitting around it,
the sum of ages of any two adjacent foxes around each table should be a prime number.
If $k$ foxes $f_1, f_2, \ldots, f_k$ are sitting around table in clockwise order, then for $1 \le i \le k-1$: $f_i$ and $f_{i+1}$ are adjacent, and $f_1$ and $f_k$ are also adjacent.
If it is possible to distribute the foxes in the desired manner, find out a way to do that.
Karen just got home from the supermarket, and is getting ready to go to sleep.
After taking a shower and changing into her pajamas, she looked at her shelf and saw an album. Curious, she opened it and saw a trading card collection.
She recalled that she used to play with those cards as a child, and, although she is now grown-up, she still wonders a few things about it.
Each card has three characteristics: strength, defense and speed. The values of all characteristics of all cards are positive integers. The maximum possible strength any card can have is $p$, the maximum possible defense is $q$ and the maximum possible speed is $r$.
There are $n$ cards in her collection. The $i$-th card has a strength $a_i$, defense $b_i$ and speed $c_i$, respectively.
A card beats another card if at least two of its characteristics are strictly greater than the corresponding characteristics of the other card.
She now wonders how many different cards can beat all the cards in her collection. Two cards are considered different if at least one of their characteristics have different values.
题意概述
给定$n$张牌,每张牌有三个属性$a_i, b_i, c_i$。一张牌能压制另一张牌$\Leftrightarrow$前者的至少两个属性严格大于后者的对应属性。已知三个属性的上限分别为$p, q, r$,问有多少种不同的牌能压制给定的$n$张牌。
数据范围:$1 \le n, p, q, r \le 5 \times 10^5, \; 1 \le a_i \le p, \; 1 \le b_i \le q, \; 1 \le c_i \le r$。
Number of bits in the smallest variable that is not a bit field.
8
SCHAR_MIN
Minimum value for a variable of type signed char.
–128
SCHAR_MAX
Maximum value for a variable of type signed char.
127
UCHAR_MAX
Maximum value for a variable of type unsigned char.
255 (0xff)
CHAR_MIN
Minimum value for a variable of type char.
–128; 0 if /J option used
CHAR_MAX
Maximum value for a variable of type char.
127; 255 if /J option used
MB_LEN_MAX
Maximum number of bytes in a multicharacter constant.
5
SHRT_MIN
Minimum value for a variable of type short.
–32768
SHRT_MAX
Maximum value for a variable of type short.
32767
USHRT_MAX
Maximum value for a variable of type unsigned short.
65535 (0xffff)
INT_MIN
Minimum value for a variable of type int.
–2147483648
INT_MAX
Maximum value for a variable of type int.
2147483647
UINT_MAX
Maximum value for a variable of type unsigned int.
4294967295 (0xffffffff)
LONG_MIN
Minimum value for a variable of type long.
–2147483648
LONG_MAX
Maximum value for a variable of type long.
2147483647
ULONG_MAX
Maximum value for a variable of type unsigned long.
4294967295 (0xffffffff)
_I64_MIN
Minimum value for a variable of type __int64
-9223372036854775808
_I64_MAX
Maximum value for a variable of type __int64
9223372036854775807
_UI64_MAX
Maximum value for a variable of type unsigned __int64
18446744073709551615 (0xffffffffffffffff)
Limits on Floating-Point Constants
Constant
Meaning
Value
FLT_DIG DBL_DIG LDBL_DIG
Number of digits, q, such that a floating-point number with q decimal digits can be rounded into a floating-point representation and back without loss of precision.
6 15 15
FLT_EPSILON DBL_EPSILON LDBL_EPSILON
Smallest positive number x, such that x + 1.0 is not equal to 1.0.
On the way home, Karen decided to stop by the supermarket to buy some groceries.
She needs to buy a lot of goods, but since she is a student her budget is still quite limited. In fact, she can only spend up to $b$ dollars.
The supermarket sells $n$ goods. The $i$-th good can be bought for $c_i$ dollars. Of course, each good can only be bought once.
Lately, the supermarket has been trying to increase its business. Karen, being a loyal customer, was given $n$ coupons. If Karen purchases the $i$-th good, she can use the $i$-th coupon to decrease its price by $d_i$. Of course, a coupon cannot be used without buying the corresponding good.
There is, however, a constraint with the coupons. For all $i \ge 2$, in order to use the $i$-th coupon, Karen must also use the $x_i$-th coupon (which may mean using even more coupons to satisfy the requirement for that coupon).
Karen wants to know the following. What is the maximum number of goods she can buy, without exceeding her budget $b$?
Karen has just arrived at school, and she has a math test today!
The test is about basic addition and subtraction. Unfortunately, the teachers were too busy writing tasks for Codeforces rounds, and had no time to make an actual test. So, they just put one question in the test that is worth all the points.
There are $n$ integers written on a row. Karen must alternately add and subtract each pair of adjacent integers, and write down the sums or differences on the next row. She must repeat this process on the values on the next row, and so on, until only one integer remains. The first operation should be addition.
Note that, if she ended the previous row by adding the integers, she should start the next row by subtracting, and vice versa.
The teachers will simply look at the last integer, and then if it is correct, Karen gets a perfect score, otherwise, she gets a zero for the test.
Karen has studied well for this test, but she is scared that she might make a mistake somewhere and it will cause her final answer to be wrong. If the process is followed, what number can she expect to be written on the last row?
Since this number can be quite large, output only the non-negative remainder after dividing it by $10^9+7$.
On the way to school, Karen became fixated on the puzzle game on her phone!
The game is played as follows. In each level, you have a grid with $n$ rows and $m$ columns. Each cell originally contains the number $0$.
One move consists of choosing one row or column, and adding $1$ to all of the cells in that row or column.
To win the level, after all the moves, the number in the cell at the $i$-th row and $j$-th column should be equal to $g_{i, j}$.
Karen is stuck on one level, and wants to know a way to beat this level using the minimum number of moves. Please, help her with this task!
题意概述
给定一个初始全为$0$的矩阵$s$和一个目标矩阵$g$,两矩阵大小均为$n \times m$。每次操作可以将矩阵$s$中某一行或某一列的数全部加一。求一个能将$s$变成$g$且操作数最少的操作序列。
数据范围:$1 \le n, m \le 100, \; 0 \le g_{i, j} \le 500$。
#include <iostream>
using namespace std;
int n, m, p, q, top, f, a[101][101], ans[100001], mode[100001];
bool check(int t, int mode) {
if (!mode) {
for (int i = 1; i <= m; ++i) if (!a[t][i]) return false;
for (int i = 1; i <= m; ++i) --a[t][i];
return true;
} else {
for (int i = 1; i <= n; ++i) if (!a[i][t]) return false;
for (int i = 1; i <= n; ++i) --a[i][t];
return true;
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
}
}
p = n, q = m;
if (p > q) {
p ^= q ^= p ^= q;
f = 1;
}
for (int i = 1; i <= p; ++i) while (check(i, f)) {
ans[++top] = i;
mode[top] = f;
}
for (int i = 1; i <= q; ++i) while (check(i, !f)) {
ans[++top] = i;
mode[top] = !f;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j]) {
cout << -1 << endl;
return 0;
}
}
}
cout << top << endl;
for (int i = 1; i <= top; ++i) {
if (!mode[i]) cout << "row ";
else cout << "col ";
cout << ans[i] << endl;
}
return 0;
}
Fox Ciel is playing a game. In this game there is an infinite long tape with cells indexed by integers (positive, negative and zero). At the beginning she is standing at the cell $0$.
There are also $n$ cards, each card has $2$ attributes: length $l_i$ and cost $c_i$. If she pays $c_i$ dollars then she can apply $i$-th card. After applying $i$-th card she becomes able to make jumps of length $l_i$, i.e. from cell $x$ to cell $(x-l_i)$ or cell $(x+l_i)$.
She wants to be able to jump to any cell on the tape (possibly, visiting some intermediate cells). For achieving this goal, she wants to buy some cards, paying as little money as possible.
If this is possible, calculate the minimal cost.
#include <iostream>
#include <map>
using namespace std;
int n, l[301], c[301];
map<int, int> f;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> l[i];
}
for (int i = 1; i <= n; ++i) {
cin >> c[i];
}
f[0] = 0;
for (int i = 1; i <= n; ++i) {
for (map<int, int>::iterator iter = f.begin(); iter != f.end(); ++iter) {
int t = gcd(iter->first, l[i]);
if (!f.count(t)) f[t] = iter->second + c[i];
else f[t] = min(f[t], iter->second + c[i]);
}
}
if (!f[1]) cout << -1 << endl;
else cout << f[1] << endl;
return 0;
}
Fox Ciel is going to publish a paper on FOCS (Foxes Operated Computer Systems, pronounce: “Fox”). She heard a rumor: the authors list on the paper is always sorted in the lexicographical order.
After checking some examples, she found out that sometimes it wasn’t true. On some papers authors’ names weren’t sorted in lexicographical order in normal sense. But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!
She wants to know, if there exists an order of letters in Latin alphabet such that the names on the paper she is submitting are following in the lexicographical order. If so, you should find out any such order.
Lexicographical order is defined in following way. When we compare $s$ and $t$, first we find the leftmost position with differing characters: $s_i \neq t_i$. If there is no such position (i.e. $s$ is a prefix of $t$ or vice versa) the shortest string is less. Otherwise, we compare characters $s_i$ and $t_i$ according to their order in alphabet.