2.2万

Martito
juanxincai
Koma
acwing_0161

Bear_King

Rezarc

AcWing2AK
whale77

ziuch
Loki
ヅ天使ぺ嫙嵂

mmmmm

19天前

#include<iostream>
using namespace std;

long long sum(long long x)
{
if(x == 0) return 0;
int l = 1,r = 2e6;  //改longlong
while(l < r)
{
int mid = l + r + 1 >> 1;   //改longlong
if(x >= mid * (mid + 1) / 2) l = mid;
else r = mid - 1;
}

long long a = l * (l + 1) / 2 * (l + 1) - l * (l + 1) * (2 * l + 1) / 6;
x -= l * (l + 1) / 2;
a += x * (x + 1) / 2;
return a;
}

int main()
{
int t = 0;
scanf("%d",&t);
while(t--)
{
long long l = 0,r = 0;
scanf("%lld%lld",&l,&r);
printf("%lld\n",sum(r) - sum(l - 1));
}
return 0;
}



20天前

# 第十二届蓝桥杯国赛C++大学B组

25

## 二、纯质数

1903

### Code

#include<iostream>
using namespace std;

bool check(int x)
{
while(x)
{
if(x % 10 == 0 || x % 10 == 1 || x % 10 == 4 || x % 10 == 6 || x % 10 == 8 || x % 10 == 9) return false;
x /= 10;
}
return true;
}

bool is_prime(int x)
{
for(int i = 2;i <= x / i;i ++)
{
if(x % i == 0) return false;
}
return true;
}

int ans;

int main()
{
for(int i = 2;i <= 20210605;i ++)
if(check(i))
if(is_prime(i))
ans ++;

cout<<ans<<endl;
return 0;
}


## 三、完全日期

977

### Code

#include<iostream>
#include<cmath>
using namespace std;

int month[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int ans;

bool check(int i,int j,int k)
{
int x = 0;
while(i){
x += i % 10;
i /= 10;
}
while(j){
x += j % 10;
j /= 10;
}
while(k){
x += k % 10;
k /= 10;
}

int y = sqrt(x);
if(y * y == x) return true;
else return false;
}

int main()
{
for(int i = 2001;i <= 2021;i ++)
for(int j = 1;j <= 12;j ++)
{
int x = month[j];
if(((i % 4 == 0 || i % 100 == 0) && i % 400 != 0) && j == 2)
x = month[j] + 1;

for(int k = 1;k <= x;k ++)
if(check(i,j,k))
ans ++;
}

cout<<ans<<endl;
}


## 四、最小权值

### 问题描述

$W(v) = 1 + 2W(L) + 3W(R) + (C(L)) ^ 2 C(R)$。树的权值定义为树的根结点的权值。

2653631372

### Code

#include<iostream>
#include<cstring>
using namespace std;

long long f[2022];  //f[i]表示权值为i的二叉树的最小权值

int main()
{
memset(f, 0x3f, sizeof f);
f[0] = 0;

for(int i = 1;i <= 2021;i ++)
{
for(int j = 0;j < i;j ++)
f[i] = min(f[i],1 + 2 * f[j] + 3 * f[i - 1 - j] + j * j * (i - 1 - j));
}

cout<<f[2021]<<endl;
return 0;
}



## 五、大写

### Code

#include<iostream>
using namespace std;

int main()
{
char ch;
while(~scanf("%c",&ch))
{
if(ch <= 'z' && ch >= 'a')
printf("%c",ch - 32);
else printf("%c",ch);
}
return 0;
}


## 六、123

### 问题描述

1, 1, 2, 1, 2, 3, 1, 2, 3, 4, …

### Code

#include<iostream>
using namespace std;

long long sum(long long x)
{
if(x == 0) return 0;
long long l = 1,r = 2e6;
while(l < r)
{
long long mid = l + r + 1 >> 1;
if(x >= mid * (mid + 1) / 2) l = mid;
else r = mid - 1;
}

long long a = l * (l + 1) / 2 * (l + 1) - l * (l + 1) * (2 * l + 1) / 6;
x -= l * (l + 1) / 2;
a += x * (x + 1) / 2;
return a;
}

int main()
{
int t = 0;
scanf("%d",&t);
while(t--)
{
long long l = 0,r = 0;
scanf("%lld%lld",&l,&r);
printf("%lld\n",sum(r) - sum(l - 1));
}
return 0;
}



## 七、异或变换

s′1 = s1;
s′i = si-1 ⊕ si。

### Code




## 八、

### Code




25天前

#include<iostream>
using namespace std;

const int N = 1e6 + 10;
int a[N];
int q[N];   //存储长度为i的上升子序列结尾的最小值

int main()
{
int n;
cin>>n;
for(int i = 0;i < n;i ++) cin>>a[i];

int len = 0;    //长度的最大值
q[0] = -2e9;    //处理二分边界
for(int i = 0;i < n;i ++)
{
int l = 0,r = len;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] < a[i]) l = mid;
else r = mid - 1;
}
len = max(len,r + 1);
q[r + 1] = a[i];
}

cout<<len<<endl;
return 0;
}


28天前

# $DP$

## 斜率优化DP

29天前
#include<iostream>
#include <unordered_map>
using namespace std;

const int MOD = 1e9 + 7;
unordered_map<int,int> primes;

int main()
{
int n;
cin>>n;
for(int i = 0;i < n;i ++)
{
int x;
cin>>x;
for(int j = 2;j <= x / j;j ++)
while(x % j == 0)   //while不要错写为if
{
primes[j] ++;
x /= j;
}
if(x > 1) primes[x] ++;
}

long long cnt = 1;
for(auto q : primes) cnt = cnt * (q.second + 1) % MOD;  //cnt *= (q.second + 1) % MOD错误，注意运算符优先级

cout<<cnt<<endl;
return 0;
}


30天前

# 第十一届蓝桥杯国赛C++大学B组

## 一、美丽的2

563

### Code

#include<iostream>
using namespace std;

bool check(int x)
{
while(x)
{
if(x % 10 == 2) return true;
x /= 10;
}
return false;
}

int main()
{
int ans = 0;
for(int i = 1;i <= 2020;i ++)
ans += check(i);

cout<<ans<<endl;
return 0;
}


## 二、扩散

20312088

### Code

#include<iostream>
#include<queue>
#include<cstring>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
const int N = 6500;
const int M = 2020; //偏移量
int dist[N][N];
bool st[N][N];
int ans = 4;    //初始时有4个黑点

void bfs()
{
int cnt = 0;
q.push({0 + M,0 + M});
q.push({2020 + M,11 + M});
q.push({11 + M,14 + M});
q.push({2000 + M,2000 + M});
st[0 + M][0 + M] = true;
st[2020 + M][11 + M] = true;
st[11 + M][14 + M] = true;
st[2000 + M][2000 + M] = true;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

while(q.size())
{
PII t = q.front();
q.pop();

if(dist[t.x][t.y] >= 2020) return;

for(int i = 0;i < 4;i ++)
{
int a = t.x + dx[i],b = t.y + dy[i];
if(a < 0 || a > 6100 || b < 0 || b > 6100) continue;
if(st[a][b]) continue;
if(dist[a][b] != -1) continue;

dist[a][b] = dist[t.x][t.y] + 1;
st[a][b] = true;
q.push({a,b});
ans ++;
}
}
}

int main()
{
memset(dist,-1,sizeof dist);
dist[0 + M][0 + M] = 0;
dist[2020 + M][11 + M] = 0;
dist[11 + M][14 + M] = 0;
dist[2000 + M][2000 + M] = 0;

bfs();
cout<<ans<<endl;
return 0;
}



## 三、阶乘约数

### 答案

39001250856960000

### Code

#include<iostream>
#include <unordered_map>
using namespace std;

unordered_map<int,int> primes;

int main()
{
for(int i = 1;i <= 100;i ++)
{
int x = i;
for(int j = 2;j <= x / j;j ++)
while(x % j == 0)   //while不要错写为if
{
primes[j] ++;
x /= j;
}
if(x > 1) primes[x] ++;
}

long long cnt = 1;
for(auto q : primes) cnt = cnt * (q.second + 1);

cout<<cnt<<endl;
return 0;
}


## 四、本质上升序列

3616159

### Code

#include<iostream>
#include<iostream>
using namespace std;

int f[210];

int main()
{

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

for(int i = 0;i < 200;i ++)
for(int j = 0;j < i;j ++)
{
if(s[i] > s[j]) f[i] += f[j];
if(s[i] == s[j]) f[i] -= f[j];
}

int ans = 0;
for(int i = 0;i < 200;i ++) ans += f[i];

cout<<ans<<endl;
return 0;
}


## 五、玩具蛇

552

### Code

#include<iostream>
#include<cstring>
using namespace std;

int g[5][5];
int st[5][5];
int ans = 0;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x,int y,int u)
{
if(u == 15)
{
ans ++;
return;
}

for(int i = 0;i < 4;i ++)
{
int a = x + dx[i],b = y + dy[i];
if(a < 0 || a >= 4 || b < 0 || b >= 4) continue;
if(st[a][b]) continue;

st[a][b] = 1;
dfs(a,b,u + 1);
st[a][b] = 0;
}

}

int main()
{
for(int i = 0;i < 4;i ++)
for(int j = 0;j < 4;j ++)
{
st[i][j] = 1;
dfs(i,j,0);
memset(st, 0, sizeof st);
}

cout<<ans<<endl;
return 0;
}


## 七、游园安排

### 问题描述

L 星球游乐园非常有趣，吸引着各个星球的游客前来游玩。

WoAiLanQiaoBei

AiLanQiao

### Code（过70%数据）

#include<iostream>
#include<vector>
#include<string>
using namespace std;

const int N = 1e5 + 10;
vector<string> q;
int len[N];
string f[N];

int main()
{
string s;
cin>>s;

for(int i = 0;i < s.size();i ++)
if(s[i] >= 'A' && s[i] <= 'Z')
{
int j = i + 1;
while(s[j] >= 'a' && s[i] <= 'z') j ++;
q.push_back(s.substr(i,j - i ));
}

for(int i = 0;i < q.size();i ++)    //初始化
{
len[i] = 1;
f[i] = q[i];
}

for(int i = 0;i < q.size();i ++)
for(int j = 0;j < i;j ++)
if(q[i] > q[j])
if(len[j] + 1 > len[i])
{
len[i] = len[j] + 1;
f[i] = f[j] + q[i];
}
else if(len[j] + 1 == len[i])   //注意else if不能写成if
{
len[i] = len[j];
f[i] = min(f[i],f[j] + q[i]);
}

string ans;
int maxv = 0;
for(int i = 0;i < q.size();i ++)
if(maxv <= len[i]) maxv = len[i],ans = f[i];    //长度相同时后者为答案

cout<<ans<<endl;
return 0;
}


## 八、答疑

### 问题描述

1. 首先进入办公室，编号为 i的同学需要 si毫秒的时间。
2. 然后同学问问题老师解答，编号为 i的同学需要 ai毫秒的时间。
3. 答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可以忽略。
4. 最后同学收拾东西离开办公室，需要 ei毫秒的时间。一般需要 10秒、20秒或 30秒，即 ei取值为 10000，20000 或 30000 。

#### 样例输入

3
10000 10000 10000
20000 50000 20000
30000 20000 30000

280000

### Code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int,int> PII;
int q[1010][5];
vector<PII> p;
long long ans;

int main()
{
int n;
cin>>n;
for(int i = 0;i < n;i ++)
{
int a,b,c;
cin>>a>>b>>c;
q[i][0] = a,q[i][1] = b,q[i][2] = c;
p.push_back({a + b + c,i});
}

sort(p.begin(),p.end());

int res = 0;
for(int i = 0;i < p.size();i ++)
{
int cnt = 0;
cnt = q[p[i].second][0] + q[p[i].second][1];
ans += res + cnt;
res += cnt + q[p[i].second][2];
}

cout<<ans<<endl;

return 0;
}


1个月前

# 第十届蓝桥杯国赛C++大学B组

## 一、平方序列

### 题目描述

• $2019 < X < Y$
• $2019^2,X^2,Y^2$组成等差序列

7020

### Code

#include<iostream>
using namespace std;

int main()
{
for(int i = 2020;i < 10000;i ++)
for(int j = i + 1;j < 10000;j ++)
if(i * i * 2 == 2019 * 2019 + j * j)
{
cout<<i + j<<endl;
return 0;
}
}


## 二、质数拆分

55965365465060

### Code

#include<iostream>
#include<algorithm>
using namespace std;

long long f[2020][2020];
int q[2020];
int x = 0;

bool check(int x)   //判断素数
{
for(int i = 2;i <= x / i;i ++)
if(x % i == 0)
return false;
return true;
}

int main()
{
for(int i = 2;i <= 2019;i ++)
if(check(i))
q[++ x] = i;

f[0][0] = 1;
for(int i = 1;i <= x;i ++)  //DP
for(int j = 0;j <= 2019;j ++)
{
if(j < q[i])
f[i][j] = f[i - 1][j];
else
f[i][j] = f[i - 1][j] + f[i - 1][j - q[i]];
}

cout<<f[x][2019]<<endl;
return 0;
}


## 三、拼接

### 问题描述

• 以对角线上的每一个点为起点，在搜索的过程中同时标记搜索点和其关于$y=x$对称点(将右边旋转向上后拼接在一起)，当触及边界时，就完成了一次分割。

2444

### Code

#include<iostream>
#include<cstring>
using namespace std;

int st[100][100];
int ans;

void dfs(int x,int y)
{
if(x == 0 || y == 7)
{
ans ++;
return;
}

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
for(int i = 0;i < 4;i ++)
{
int a = x + dx[i],b = y + dy[i];
if(a < 0 || a > 7 || b < 0 || b > 7 || a == b) continue;
if(st[a][b]) continue;

st[a][b] = 1;
dfs(a,b);
st[a][b] = 0;
}
}

int main()
{
for(int i = 0;i <= 7;i ++)
{
memset(st, 0, sizeof st);
st[i][i] = 1;
dfs(i,i);
}

cout<<ans<<endl;
return 0;
}


## 四、求值

### Code

#include<iostream>
#include<cmath>
using namespace std;

int main()
{
for(int i = 1;i < 100000;i ++)
{
int cnt = 0;
for(int j = 1;j <= i / j;j ++)
{
if(i % j == 0)
cnt ++;
if(cnt == 50)
{
cout<<i<<endl;
return 0;
}
}
}
return 0;
}


## 五、路径计数

### 问题描述

• 总长度不超过 12；
• 最后回到左上角；
• 路线不自交；
• 不走出 5 x 5 的方格矩阵范围之外。

• 注意格子为 5 X 5 时格点为 6 X 6
• 注意特判步数为2时不符合条件

206

### Code

#include<iostream>
using namespace std;

int st[10][10];
int ans;

void dfs(int x,int y,int u)
{
if(u > 12) return;
if(x == 0 && y == 0 && st[x][y] == 1 && u > 2)  //特别注意 u > 2
{
ans ++;
return;
}

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

for(int i = 0;i < 4;i ++)
{
int a = x + dx[i],b = y + dy[i];

if(a < 0 || a > 5 || b < 0 || b > 5) continue;
if(st[a][b]) continue;

st[a][b] = 1;
dfs(a,b,u + 1);
st[a][b] = 0;
}
}

int main()
{
dfs(0,0,0);
cout<<ans<<endl;
return 0;
}


## 六、最优包含

S和T的长度小于等于1000。

### Code

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int f[1010][1010];

int main()
{
string a,b;
cin>>a>>b;
a = "0" + a;
b = "0" + b;

int n = a.size() - 1;
int m = b.size() - 1;

memset(f,0x3f,sizeof f);    //初始化
f[0][0] = 0;
for(int i = 1;i <= n;i ++) f[i][0] = 0; //S[1~i]中一定包含空串(T[1 ~ 0])

for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
if(a[i] == b[j])
f[i][j] = min(f[i][j],f[i - 1][j - 1]);
else
f[i][j] = min(f[i - 1][j - 1] + 1,f[i - 1][j]);

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

return 0;
}


## 七、排列数

### 暴力代码

#include<iostream>
#include<algorithm>
using namespace std;

int q[510];
int n,k;

int main()
{
cin>>n>>k;
for(int i = 0;i < n;i ++) q[i] = i + 1;

int ans = 0;
do{
int cnt = 0;
for(int i = 0;i < n;i ++)
{
if(i == 0 || i == n - 1) continue;
if(q[i] > q[i - 1] && q[i] > q[i + 1]) cnt ++;
if(q[i] < q[i - 1] && q[i] < q[i + 1]) cnt ++;
}
if(cnt == k - 1) ans ++;
}while(next_permutation(q,q + n));

cout<<ans % 123456<<endl;
return 0;
}


1个月前

# 字串变换

BFS — 双向广搜

## 题目描述

• 同时从起点和终点开始一层一层搜索，直到两端相遇，从而达到优化效果。
例如两个五层的完全二叉树结点数量远远低于一个十层的完全二叉树。

• substr()用法
字符串.substr(参数1,参数2)
参数一如果是0或正整数，则代表字符串截取的起始下标
参数二字符串截取字符的个数（正整数）
字符串.substr(参数);
参数如果是0或正整数：字符串截取的起始下标，默认截取至字符串结尾

## Code(TLE了)

#include<iostream>
#include <queue>
#include<unordered_map>
using namespace std;

string a[10],b[10];
int n;

int extend(queue<string> &qfirst,unordered_map<string,int> &dfirst,unordered_map<string,int> &dsecond,string a[],string b[])
{
while(qfirst.size())
{
string t = qfirst.front();
qfirst.pop();

for(int i = 0;i < t.size();i ++)        //遍历所有变换规则
for(int j = 0;j < n;j ++)
if(t.substr(i,a[j].size()) == a[j])
{
string s = t.substr(0,i) + b[j] + t.substr(i + a[j].size());
if(dsecond.count(s)) return dfirst[t] + 1 + dsecond[s];
if(dfirst.count(s)) continue;
dfirst[s] = dfirst[t] + 1;
qfirst.push(s);
}
}
return 11;
}

int bfs(string A,string B)
{
queue<string> qfront,qback;
unordered_map<string,int> dfront,dback;

qfront.push(A),dfront[A] = 0;
qback.push(B),dback[B] = 0;

while(!qfront.empty() || !qback.empty())    //若其中一个搜索完(队列为空)时，则首尾路线不相交。
{
int t = 0;
if(qfront.size() <= qback.size())       //均衡首位的搜索层数
t = extend(qfront,dfront,dback,a,b);
else
t = extend(qback,dback,dfront,b,a);

if(t <= 10) return t;
}
return 11;
}

int main()
{
string A,B;
cin>>A>>B;
while(cin>>a[n]>>b[n]) n ++;

int t = bfs(A,B);
if(t <= 10) cout<<t<<endl;
return 0;
}


1个月前

1个月前

# 电路维修

BFS — 双端队列广搜

## 题目描述

• 格点的横纵坐标之和为奇数的点无法到达
因为起点从(0,0)开始而且横坐标变化1纵坐标对应变化1(电线只能斜着联通)，变化之和为偶数。

• 注意格点的坐标系和格子的坐标系不同，要关联起来就要做一个映射(引入ix[]，iy[])。

• 从左上角 格子外 开始搜索，若改变原本格子中的状态对应边权为1，若不改变原本格子的状态对应边权为0，搜索到电线联通右下角的(n,m)位置，就可以得到最小边权即最小步数。

## Code

#include<iostream>
#include<cstring>
#include<deque>
#define x first
#define y second
using namespace std;

typedef pair<int, int> PII;
const int N = 510;
bool st[N][N];      //判断到达该格点的最小步数是否确定
int dist[N][N];     //记录到达该格点的最小步数
char g[N][N];       //记录格子中电线的状态

int n,m;

int bfs()
{
deque<PII> q;
memset(dist,0x3f,sizeof dist);
memset(st,0,sizeof st);

q.push_front({0,0});
dist[0][0] = 0;     //从左上角格子外开始扩展

int dx[] = {-1,-1,1,1},dy[] = {-1,1,1,-1};
int ix[] = {-1,-1,0,0},iy[] = {-1,0,0,-1};      //注意格点与格子的区别
char ch[5] = {"\\/\\/"};

while(!q.empty())
{
PII t = q.front();
q.pop_front();

if(t.x == n && t.y == m) return dist[n][m];

if(st[t.x][t.y]) continue;
st[t.x][t.y] = true;    //出队时确定最小步数

for(int i = 0;i < 4;i ++)
{
int a = t.x + dx[i],b = t.y + dy[i];
int ga = t.x + ix[i],gb = t.y + iy[i];
if(a < 0 || a > n || b < 0 || b > m) continue;  //最终电线要联通(n,m)点

int w = (g[ga][gb] != ch[i]);
int d = dist[t.x][t.y] + w;

if(d < dist[a][b])      //用已经确定最小步数的节点更新未确定最小步数的节点
{
dist[a][b] = d;
if(!w) q.push_front({a,b});     //边权为0加入队首
else q.push_back({a,b});        //边权为1加入队尾
}
}
}
}

int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i = 0;i < n;i ++) cin>>g[i];

if(n + m & 1) cout<<"NO SOLUTION"<<endl;    //终点横纵坐标之和为奇数时不可到达
else cout<<bfs()<<endl;
}
return 0;
}