skywhite
2分钟前

### 题目描述 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


### 算法

#### 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;
}


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

#### 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

#### 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;
int f[N];

int main(){
cin >> n >> w >> w >> w;
memset(f, 0x3f, sizeof f);
f = 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


### 算法

#### 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  ### 算法

#### 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


### 算法

#### 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;
}


### 题目描述

AcWing 890. 能被整除的数

#### 样例

1000000000 16
9091 3793 4201 7901 3557 6473 6761 3491 5381 6883 9643 9491 6869 4787 1129 8443


### 算法1

#### C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int M = 20,N=1e9+7;
int primes[M];
bool st[N];
int n,m;
// 根据代码中的定义，const int N = 1e9 + 7，这意味着数组st的大小为10亿（1e9）。
// 在大多数情况下，这会导致内存限制超出。因为布尔类型通常占用1字节（8位），所以一个长度为1亿的布尔数组将占用大约800MB的内存。
//int类型是4个字节，若把st设为int将使用更大的内存！
int fun(int x){
int cnt=0;
for(int i=1;i<=x;i++){
if(!st[i])cnt++;
for(int j=0;j<m;j++){
if((long long)primes[j]*i<=x)st[primes[j]*i]=true;
if(i%primes[j]==0)break;
}
}
return n-cnt;
}
int main(){
cin>>n>>m;
// memset(st,false,sizeof st);
//这个系统测评貌似是看你用到了多大内存，而不是看你分配了多大内存，比如我开一个1e9+7的bool数组，
//如果不加这句memset(st,false,sizeof st); 那么当输入的n足够小，是不会导致内存超限的，但是一旦加了这句，就代表我使用了1e9+7的
//bool数组，不管输入的n多小，都会报内存超限。
//
for(int i=0;i<m;i++) cin>>primes[i];
int res = fun(n);
cout<<res;
// 1  3 4 5 6 7 8 9 10
}


## 所以还是得老老实实用容斥原理

18分钟前
//3706
#include <bits/stdc++.h>
using namespace std;

int main(){
int n, res = 0;
cin >> n;
for(int i = 0;i < 1 << n;++ i){
bool f = 1;
for(int j = 1;j < n; ++j){
if(i >> j & 1 && i >> j - 1 & 1){
f = 0;
break;
}
}
if(f) res ++;
}
cout << res;
return 0;
}


22分钟前

# 657.选择练习1 题解

### 题目描述

$B$大于$C$。
$D$大于$A$。
$C$和$D$的总和大于$A$和$B$的总和。
$C$和$D$是正值。
$A$是偶数。

#### 数据范围

$−100≤A,B,C,D≤100$

### 样例

#### 输入样例：

5 6 7 8


#### 输出样例：

Valores nao aceitos


### C++ 代码

#include <cstdio>

using namespace std;

int main() {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
if (b > c && d > a && c + d > a + b && c > 0 && d > 0 && a % 2 == 0) printf("Valores aceitos\n");
else printf("Valores nao aceitos\n");
return 0;
}


# The end~~~

1.完全背包法：f[i][j]表示在不超过j的背包，能放入1到i的数字的总方案数

状态转移方程：f[i][j] = f[i-1][j] + f[i][j - i]

• 推导
f[i][j] = f[i-1][j] + f[i-1][j - i], f[i-1][j - 2i] …
f[i][j-i] = f[i-1][j-i] + f[i-1][j - 2i] + f[i-1][j-3i]
f[i][j] = f[i-1][j] + f[i][j-i]

f[i-1][j]表示一个i数字都没拿，而f[i-1][j - i], f[i-1][j - 2i], f[i-1][j-3i]…表示为依次拿了1，2，3…k个i的数字

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N][N];

int main(){

int n;
cin >> n;

for(int i = 1; i <= n; i ++ ) f[i] = 1;

for(int i = 1; i <= n; i ++ ){
for (int j = 1; j <= n; j ++ ){
f[i][j] = f[i-1][j];
if (j >= i){
f[i][j] = (f[i-1][j] + f[i][j - i]) % mod;
}
}
}

cout << f[n][n] << endl;

return 0;

}



1.1完全背包优化（一维）

 #include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N];

int main(){

int n;
cin >> n;

f = 1;

for(int i = 1; i <= n; i ++ ){
for (int j = i; j <= n; j ++ ){

f[j] = (f[j] + f[j - i]) % mod;   // f[i][j] = f[i-1][j] + f[i][j - i]
// 由于f[i-1][j]表示一个i数字都没拿，不用担心01背包的同一层多拿i的问题。
}
}

cout << f[n] << endl;

return 0;

}



2. 总和是i, 数字个数有j个的所有方案

状态转移方程：f[i][j] = f[i-1][j-1] + f[i-j][j]

• 其中以最小数字至少有一个1 和 最小数字没有1来划分
• f[i-1][j-1]去掉一个1，那么总和减1，数字的个数减1。表示最小数字至少有一个1。
• f[i-j][j] 所有数字减1，总和减1，数字个数不变，还是正整数，合法。表示最小数字没有1。
 #include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N][N];

int main(){

int n;
cin >> n;
f = 1;
for (int i = 2; i <= n; i ++ ){
for (int j = 1; j <= i; j ++ ){
f[i][j] = (f[i-1][j-1] + f[i-j][j]) % mod;
}
}

int res;

for (int i = 0; i < n; i ++ ) res = (res + f[n][i+1]) % mod;

cout << res << endl;

return 0;
}


guanchen
34分钟前

### 题目描述

#### 样例

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();

for (int i = b; i > a; i --) {

/* 合群标记默认 false */
boolean hequnFlag = false;

//
for (int j = 2; j <= a && j * j <= i ; j++) {
if(i % j  == 0){
hequnFlag = true;
break;
}
}
if( !hequnFlag ){
// 不合群
System.out.println(i);
return;
}
}
System.out.println(-1);
}

}



### 算法1

blablabla

#### C++ 代码

blablabla


### 算法2

blablabla

#### C++ 代码

blablabla


35分钟前
//3706
#include <bits/stdc++.h>
using namespace std;

int main(){
int n;
cin >> n;
int a = 2, b = 3, c;
if(n == 1) cout << 2;
else if(n == 2) cout << 3;
else{
for(int i = 3;i <= n;i++){
c = a + b;
a = b;
b = c;
}
cout << b;
}
return 0;
}


Zoe_56
45分钟前

• 正整数x无法被 [2,a]范围内的任何整数整除
→ x不属于[2, a]
• [2,b]范围内的最大不合群数
→ x属于(a, b]

→ 素数是不合群数

→ 非素数只要无法被[2,a]范围内的数整除也是不合群数

#include <bits/stdc++.h>
using namespace std;

int main()
{
ios::sync_with_stdio(false);

int a, b; cin >> a >> b;
int Max = -1;

for (int i = b; i > a; i--)
{
bool yes = true;
for (int j = 2; j <= a && j * j <= i; j++)
if (i%j == 0) {
yes = false;
break;
}
if (yes) {
cout << i << endl;
return 0;
}
}
cout << -1 << endl;

return 0;
}


51分钟前

### 题目描述

• 计算 $\Delta = b ^ 2 - 4ac$，则:
1. 若 $\Delta < 0$，则该一元二次方程无实数解；
2. 否则 $\Delta \geq 0$，此时该一元二次方程有两个实数解 $x_{1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$；
• 其中，$\sqrt \Delta$ 表示 $\Delta$ 的算数平方根，即使得 $s^2 = \Delta$ 的唯一非负实数 $s$。
• 特别的，当 $\Delta = 0$ 时，这两个实数解相等；当 $\Delta > 0$ 时，这两个实数解互异。

• $x ^ 2 + x + 1 = 0$ 无实数解，因为 $\Delta = 1 ^ 2 - 4 \times 1 \times 1 = -3 < 0$；
• $x ^ 2 - 2x + 1 = 0$ 有两相等实数解 $x_{1, 2} = 1$；
• $x ^ 2 - 3x + 2 = 0$ 有两互异实数解 $x_1 = 1, x_2 = 2$；

• 由有理数的定义，存在唯一的两个整数 $p$ 和 $q$，满足 $q > 0$，$\gcd(p, q) = 1$ 且 $v = \frac pq$。
• 若 $q = 1$，则输出 {p}，否则输出 {p}/{q}，其中 {n} 代表整数 $n$ 的值；
• 例如：
• 当 $v = -0.5$ 时，$p$ 和 $q$ 的值分别为 $-1$ 和 $2$，则应输出 -1/2
• 当 $v = 0$ 时，$p$ 和 $q$ 的值分别为 $0$ 和 $1$，则应输出 0

1. 若 $\Delta = b ^ 2 - 4ac < 0$，则表明方程无实数解，此时你应当输出 NO
2. 否则 $\Delta \geq 0$，此时方程有两解（可能相等），记其中较大者为 $x$，则：
1. 若 $x$ 为有理数，则按有理数的格式输出 $x$。
2. 否则根据上文公式，$x$ 可以被唯一表示为 $x = q_1 + q_2 \sqrt r$ 的形式，其中：
• $q_1, q_2$ 为有理数，且 $q_2 > 0$；
• $r$ 为正整数且 $r > 1$，且不存在正整数 $d > 1$ 使 $d ^ 2 \mid r$（即 $r$ 不应是 $d ^ 2$ 的倍数）；

1. 若 $q_1 \neq 0$，则按有理数的格式输出 $q_1$，并再输出一个加号 +
2. 否则跳过这一步输出；

1. 若 $q_2 = 1$，则输出 sqrt({r})
2. 否则若 $q_2$ 为整数，则输出 {q2}*sqrt({r})
3. 否则若 $q_3 = \frac{1}{q_2}$ 为整数，则输出 sqrt({r})/{q3}
4. 否则可以证明存在唯一整数 $c, d$ 满足 $c, d > 1, \gcd(c, d) = 1$ 且 $q _ 2 = \frac cd$，此时输出 {c}*sqrt({r})/{d}

#### 数据范围 • 特殊性质 $A$：保证 $b = 0$；
• 特殊性质 $B$：保证 $c = 0$；
• 特殊性质 $C$：如果方程有解，那么方程的两个解都是整数。

#### 输入样例：

9 1000
1 -1 0
1 -2 1
1 5 4
4 4 1
1 0 -432
1 -3 1
2 -4 1
1 7 1


#### 输出样例：

NO
/
*()
/+()/
+()/
/+*()/


### 算法1

##### (大模拟) $O(n^2)$

• 计算 $\Delta = b ^ 2 - 4ac$，则:
1. 若 $\Delta < 0$，则该一元二次方程无实数解，此时我们输出 NO。记得需要回车。
2. 否则 $\Delta \geq 0$，此时该一元二次方程有两个实数解 $x_{1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$；而题目中我们只需要求较大的 $x$ 即可。

（$1$） $\Delta = 0$

（$2$） $\Delta \geq 0$

1. 此时 $p$ 的定义与上文定义有些许不同，表现为没有 $\pm \sqrt \Delta$。
2. $sd$ 中的 $\sqrt \Delta$ 没有 $\pm$，原因后面讲。
3. $sd$ 变量属性为 $long \ long$，原因后面讲。

① ${sd}^2 = \Delta$，即 $\Delta$ 为 完全平方数

$Q:$ 为什么此处 $p$ 不先加上 $sd$ 再进行$\underline{负号转移}$ （指将分母的负号移到分子上） ？

$A:$ 按问题中所说的方法不能保证 $x$ 为较大解。

② ${sd}^2 \not= \Delta$，即此时 $\Delta$ 不为 完全平方数

$$x = \frac{p}{q} + \frac{ \pm \sqrt{\Delta}}{q}$$

1. 当 $p = 0$ 时 $\frac{p}{q} = 0$ （显而易见），不需要输出
2. 在遵循上述条件 $1$ 的情况下，如果 $q = 1$ ，不需要输出 $/q$

$Q:$ 如何化简呢？
$A:$ 定义 $d1 = 1$，$d2 = \Delta$。

$Q:$ 为什么 $q$ 赋值时 取了绝对值。（此处见代码 $q = abs(2 * a)$）
$A:$ 与之前 $sd$ 为什么不加 $\pm$ 差不多，是 $x$ 需输出较大值的问题。

• 当 $q$ 为负数时，我们 上方 $\pm \sqrt{\Delta}$ 取 $- \sqrt{\Delta}$ 时整个分式为正数，显然比负数大
• 当 $q$ 为正数时，我们 上方 $\pm \sqrt{\Delta}$ 取 $+ \sqrt{\Delta}$ 时整个分式为正数，显然比负数大

1. $q = d1$时，$q$ 与 $d1$ 抵消，直接输出 sqrt(d2)即可；
2. $q = 1$时，不需要输出 $/q$；
3. $d1 = 1$时，不需要输出 $d1$。

#### C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 1e3 + 10;
long long t,M;
int main(){
scanf("%lld%lld",&t,&M); // 读入，当然 M 在代码中并没有什么用处（
while(t --){ // 多测
long long a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
long long delta = b * b - 4 * a * c; // 计算 delta
if(delta < 0) printf("NO\n"); // 无解
else if(delta == 0){ // delta = 0 的情况
long long p = -b,q = 2 * a;
long long g = __gcd(abs(p),abs(q));
p /= g;
q /= g;
if(q < 0){
p = -p;
q = -q;
}
if(q == 1) printf("%lld\n",p);
else printf("%lld/%lld\n",p,q);
}
else{ // delta >= 0 的情况
long long p = -b,q = 2 * a;
long long sd = (long long)sqrt(delta);
if(sd * sd == delta){ // delta 为 完全平方数
if(q < 0){
p = -p;
q = -q;
}
p += sd;
long long g = __gcd(abs(p),abs(q));
p /= g;
q /= g;
if(q == 1) printf("%lld\n",p);
else printf("%lld/%lld\n",p,q);
}
else{ // delta 不为 完全平方数
long long g = __gcd(abs(p),abs(q)); // 前一个分式的处理
p /= g;
q /= g;
if(q < 0){
p = -p;
q = -q;
}
if(p != 0){
if(q == 1) printf("%lld+",p);
else printf("%lld/%lld+",p,q);
}
long long d1 = 1,d2 = delta;
q = abs(2 * a); // 后一个分式的处理
for(long long i = sd;i >= 1;i --){
long long j = i * i;
if(d2 % j == 0){
d2 /= j;
d1 *= i;
break;
}
}
int gdq = __gcd(abs(d1),abs(q));
q /= gdq;
d1 /= gdq;
if(q < 0){
q = -q;
d1 = -d1;
}
if(q == d1) printf("sqrt(%lld)\n",d2);
else if(q == 1) printf("%lld*sqrt(%lld)\n",d1,d2);
else if(d1 == 1) printf("sqrt(%lld)/%lld\n",d2,q);
else printf("%lld*sqrt(%lld)/%lld\n",d1,d2,q);
}
}
}
return 0;
}


$$（共 355 行）$$

1小时前

# include[HTML_REMOVED]

using namespace std;
int main(){
int a,b;
cin>>a>>b;
cout<<a+b;
return 0;

}