题目描述 A - Tomorrow link
In the calendar of AtCoder Kingdom, a year consists of $M$ months from month $1$ to month $M$, and each month consists of $D$ days from day $1$ to day $D$.What day follows year $y$, month $m$, day $d$ in this calendar?
Constraints
- $1000≤y≤9000$
- $1≤m≤M≤99$
- $1≤d≤D≤99$
- All input values are integers.
样例
blablabla
算法
(签到题) $O(1)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int m, d;
int ny, nm, nd;
int main(){
cin >> m >> d;
cin >> ny >> nm >> nd;
nd += 1;
if(nd > d) nd -= d, nm += 1;
if(nm > m) nm -= m, ny += 1;
cout << ny << ' ' << nm << ' ' << nd << endl;
return 0;
}
题目描述 B - Buy One Carton of Milk link
A supermarket sells egg packs.
A pack of $6$ eggs costs $S$ yen, a pack of $8$ eggs costs $M$ yen, and a pack of $12$ eggs costs $L$ yen.
When you can buy any number of each pack, find the minimum amount of money required to purchase at least $N$ eggs.
Constraints
- $1≤N≤100$
- $1≤S,M,L≤10^4$
- All input values are integers.
样例
blablabla
算法1
(枚举) $O(n^3)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, s, m, l;
int main(){
cin >> n >> s >> m >> l;
int minAmount = 0x3f3f3f3f;
for (int num6 = 0; num6 <= n; ++num6){
for (int num8 = 0; num8 <= n; ++num8){
for (int num12 = 0; num12 <= n; ++num12){
if (num6 * 6 + num8 * 8 + num12 * 12 >= n) {
int amount = num6 * s + num8 * m + num12 * l;
minAmount = min(minAmount, amount);
}
}
}
}
cout << minAmount << endl;
return 0;
}
算法2
(背包) $O(n)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n, s, m, l;
int v[] = {0, 6, 8, 12}, w[5];
int f[N];
int main(){
cin >> n >> w[1] >> w[2] >> w[3];
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 1; i <= 3; i ++ )
for (int j = 0; j <= n; j ++ )
f[j] = min(f[j], f[max(j - v[i], 0)] + w[i]);
cout << f[n] << endl;
return 0;
}
题目描述 C - Sum of Numbers Greater Than Me link
You are given a sequence $A$=$(A_1,…,A_N)$ of length $N$.
For each $i$=$1,…,N,$ solve the following problem.
Problem: Find the sum of all elements in $A$ that are greater than $A_i$.
Constraints
- $1000≤y≤9000$
- $1≤m≤M≤99$
- $1≤d≤D≤99$
- All input values are integers.
样例
blablabla
算法
$(后缀和+upperbound)$ $O(nlogn)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e6 + 10;
typedef long long LL;
int n;
LL a[N], s[N], b[N];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]), b[i] = a[i];
sort(b + 1, b + 1 + n);
for(int i = n; i >= 1; i -- ){
s[i] = s[i + 1] + b[i];
}
for(int i = 1; i <= n; i ++ ){
int idx = upper_bound(b + 1, b + 1 + n, a[i]) - b;
printf("%lld ", s[idx]);
}
return 0;
}
题目描述 D - Tile Pattern link
There is a grid with $10^9$by $10^9$ squares. Let $(i,j)$ denote the square at the ${(i+1)}$th row from the top and the ${(j+1)}$th column from the left $(0≤i,j<10^9)$. (Note the unusual index assignment.)
Each square is $black$ or $white$. The color of the square $(i,j)$ is represented by a character P[i%N][j%N] , where ${‘B’}$ means black, and ${‘W’}$ means white. Here, $a%b$ denotes the remainder when $a$ is divided by $b$.
Answer $Q$ queries.
Each query gives you four integers $A,B,C,D$ and asks you to find the number of $black$ squares contained in the rectangular area with $(A,B)$ as the top-left corner and $(C,D)$ as the bottom-right corner.
Constraints
- $1≤N≤1000$
- $P$$[i]$$[j]$ is $W$ or $B$.
- $1≤Q≤2×10^5$
- $0≤A≤C<10^9$
- $0≤B≤D<10^9$
- $N,Q,A,B,C,D$ are all integers.
样例
Sample Input
3 2
WWB
BBW
WBW
1 2 3 4
0 3 4 5
Sample Output
4
7
算法
$(二维前缀和)$ $O(n^2)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const LL N = 1010;
LL n, q;
char p[N][N];
LL dp[N][N];
LL A, B, C, D;
LL f(LL x, LL y){
//完整的n*n的矩形区域中的黑块数
LL res = (x / n) * (y / n) * dp[n][n];
//块(x, y)的与整数个区域n*n的右下角块 将区域分成了四个部分
//如第一个样例的第一个询问:
//(1, 1)到(3, 3)的矩形区域为区域n*n的整数倍,为左上角蓝色方框区域
//(4, 4)到(4, 5)的区域为右下角紫色方框区域
//(4, 1)到(4, 3)的区域为左下角粉色方框区域
//(1, 4)到(3, 5)的区域为右上角橙色方框区域
//这里求右下角部分的黑块数
res += dp[x % n][y % n];
//这里求左下角部分的黑块数
res += dp[x % n][n] * (y / n);
//这里求右上角部分的黑块数
res += dp[n][y % n] * (x / n);
return res;
}
int main(){
scanf("%lld%lld", &n, &q);
//相当于这里的i,j是指正方形小块的坐标,从1开始
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ ){
cin >> p[i][j];
dp[i][j] = (p[i][j] == 'B') + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
}
//而下面用于询问的A,B,C,D是线交点的坐标,从0开始
//那么实际对应的正方形小块的坐标还要在横纵方向上加1
//而求前缀和的话,A,B就不需要加了而C,D则还要加1
while(q -- ){
scanf("%lld%lld%lld%lld", &A, &B, &C, &D);
C ++, D ++;
printf("%lld\n", f(C, D) - f(A, D) - f(C, B) + f(A, B));
}
return 0;
}
题目描述 E - Set Meal link
AtCoder cafeteria sells meals consisting of a main dish and a side dish.
There are $N$ types of main dishes, called main dish 1, main dish 2, $…$, main dish N. Main dish i costs
$a_i$ yen.
There are $M$ types of side dishes, called side dish 1, side dish 2, $…$, side dish M. Side dish i costs
$b_i$yen.
A set meal is composed by choosing one main dish and one side dish. The price of a set meal is the sum of the prices of the chosen main dish and side dish.
However, for $L$ distinct pairs $(c_1,d_1),…,(c_L,d_L)$, the set meal consisting of main dish $c_i$ and side dish $d_i$ is not offered because they do not go well together.
That is, $NM−L$ set meals are offered. (The constraints guarantee that at least one set meal is offered.)
Find the price of the most expensive set meal offered.
Constraints
- $1≤N,M≤10^5$
- $0≤L≤min(10^5,NM−1)$
- $1≤a_i,b_i≤10^9$
- $1≤c_i≤N$
- $1≤d_j≤M$
- $(c_i,d_i)\not=(c_j,d_j)\ $ $if\ i\not=j$
- All input values are integers.
样例
blablabla
算法
$O(nm)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
const LL N = 1e5 + 10;
LL n, m, l;
vector<pair<LL, LL> > a, b;
map<pair<LL, LL>, LL> pr;
LL x, c, d;
LL ans;
int main(){
scanf("%lld%lld%lld", &n, &m, &l);
for(int i = 0; i < n; i ++ ){
scanf("%lld", &x);
a.push_back({x, i + 1});
}
for(int i = 0; i < m; i ++ ){
scanf("%lld", &x);
b.push_back({x, i + 1});
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for(int i = 0; i < l; i ++ ){
scanf("%lld%lld", &c, &d);
pr[{c,d}] = 1;
}
for(int i = a.size() - 1; i >= 0; i -- ){
auto t1 = a[i];
for(int j = b.size() - 1; j >= 0; j -- ){
auto t2 = b[j];
if(pr[{t1.second, t2.second}] == 1) continue;
if(t1.first + t2.first > ans) ans = t1.first + t2.first;
else break;
}
}
printf("%lld\n", ans);
return 0;
}