第16届国赛蓝桥杯大赛C/C++大学B组
·
目录
一.新型锁
题目链接:https://www.lanqiao.cn/problems/21263/learning/
1.题目讲解
又因为2025 => 3 ^ 4 * 5 ^ 2
2.代码实现
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 2100,mod = 1e9 + 7;
LL f[N][2][2];
int main()
{
int n = 2025;
f[1][0][0] = 8,f[1][0][1] = 4,f[1][1][0] = 2,f[1][1][1] = 1;
for(int i = 2;i <= n;i++)
{
f[i][0][0] = (f[i - 1][1][1] * 8) % mod;
f[i][0][1] = (f[i - 1][1][1] + f[i - 1][1][0]) % mod * 4 % mod;
f[i][1][0] = (f[i - 1][1][1] + f[i - 1][0][1]) % mod * 2 % mod;
f[i][1][1] = (((f[i - 1][0][0] + f[i - 1][0][1]) % mod + f[i - 1][1][0]) % mod + f[i - 1][1][1]) % mod;
}
LL ret = 0;
ret = (ret + f[n][0][0]) % mod;
ret = (ret + f[n][0][1]) % mod;
ret = (ret + f[n][1][0]) % mod;
ret = (ret + f[n][1][1]) % mod;
cout << ret << endl;
return 0;
}二.互质藏卡
题目链接:https://www.lanqiao.cn/problems/21262/learning/
1.题目讲解
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 2e4 + 10,mod = 1e9 + 7;
int n = 17600;
int p[N],cnt;
bool st[N];
int main()
{
for(int i = 2;i <= n;i++)
{
if(!st[i])
{
p[++cnt] = i;
}
for(int j = 1;1ll * i * p[j] <= n;j++)
{
st[i * p[j]] = true;
if(i % p[j] == 0) break;
}
}
cout << cnt << endl;
return 0;
}
运行代码,我们能看到,质数一共是有2024个
我们是要在其中选择2025个并且他们的gcd是1,所以我们只要找出是一个数中只含有一个质数的数字即可
我们可以按照以上来进行选择
2.代码实现
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 2e4 + 10,mod = 1e9 + 7;
int n = 17600;
int p[N],cnt;
bool st[N];
int main()
{
for(int i = 2;i <= n;i++)
{
if(!st[i])
{
p[++cnt] = i;
}
for(int j = 1;1ll * i * p[j] <= n;j++)
{
st[i * p[j]] = true;
if(i % p[j] == 0) break;
}
}
LL ret = 1;
for(int i = 1;i <= cnt;i++)
{
LL x = p[i],y = 0;
while(x <= n)
{
y++;
x *= p[i];
}
ret = (ret * y) % mod;
}
cout << ret << endl;
return 0;
}三.数字轮盘
题目链接:https://www.lanqiao.cn/problems/21261/learning/
1.题目讲解
很明显,我们能推出,一次恢复操作就是将最后面的两个转移到最前面
2.代码实现
#include <iostream>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
int n,k;
cin >> n >> k;
k %= n;
if(k == 0)
{
cout << 0 << endl;
}
else if((n - k) % 2 == 0)
{
cout << (n - k) / 2 << endl;
}
else if((n + n - k) % 2 == 0)
{
cout << (n + n - k) / 2 << endl;
}
else
{
cout << -1 << endl;
}
}
return 0;
}四.斐波那契字符串
题目链接:https://www.lanqiao.cn/problems/21260/learning/
1.题目讲解
2.代码实现
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10,mod = 1e9 + 7;
LL f[N],g[N],h[N];
//g[i]表示0的个数
//h[i]表示1的个数
//f[i]表示逆序对总个数
int main()
{
g[1] = 1;
h[2] = 1;
for(int i = 3;i <= 1e5;i++)
{
f[i] = ((f[i - 2] + f[i - 1]) % mod + (h[i - 2] * g[i - 1]) % mod) % mod;
g[i] = (g[i - 2] + g[i - 1]) % mod;
h[i] = (h[i - 2] + h[i - 1]) % mod;
}
int T;
cin >> T;
while(T--)
{
int n;
cin >> n;
cout << f[n] << endl;
}
return 0;
}五.项链排列
题目链接:https://www.lanqiao.cn/problems/21259/learning/
1.题目讲解
2.代码实现
#include <iostream>
using namespace std;
int main()
{
int a,b,c;
cin >> a >> b >> c;
if(c == 0)
{
if(a == 0)
{
while(b--)
{
cout << "Q";
}
}
else if(b == 0)
{
while(a--)
{
cout << "L";
}
}
else
{
cout << -1;
}
}
else
{
int m = min(a,b) * 2 - (a == b ? 1 : 0);
if(c > m)
{
cout << -1;
}
else if(c == m)
{
if(a == b)
{
while(a--)
{
cout << "LQ";
}
}
else if(a < b)
{
b -= a;
while(a--)
{
cout << "QL";
}
while(b--)
{
cout << "Q";
}
}
else
{
a -= b;
while(a--)
{
cout << "L";
}
while(b--)
{
cout << "QL";
}
}
}
else
{
int x = (c - 1) / 2;
if(c % 2 == 1)
{
a -= x;
b -= x;
while(a--)
{
cout << "L";
}
while(x--)
{
cout << "QL";
}
while(b--)
{
cout << "Q";
}
}
else
{
a -= (x + 1);
b -= (x);
while(a--)
{
cout << "L";
}
while(x--)
{
cout << "QL";
}
while(b--)
{
cout << "Q";
}
cout << "L";
}
}
}
return 0;
}六.蓝桥星数字
题目链接:https://www.lanqiao.cn/problems/21258/learning/
1.题目讲解
2.代码实现
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
LL n;
LL a[20],cnt;
LL f[20][10];
LL dfs(int pos,int prev,bool limit,bool zero)
{
if(!pos)
{
return 1;
}
if(!limit && !zero && ~f[pos][prev])
{
return f[pos][prev];
}
LL ret = 0,up = limit ? a[pos] : 9;
for(int i = 0;i <= up;i++)
{
if(zero)
{
ret += dfs(pos - 1,i,limit && (i == a[pos]),zero && !i);
}
else if((prev ^ i) & 1)
{
ret += dfs(pos - 1,i,limit && (i == a[pos]),zero && !i);
}
}
if(!limit && !zero)
{
f[pos][prev] = ret;
}
return ret;
}
bool check(LL x)
{
cnt = 0;
memset(f,-1,sizeof(f));
while(x)
{
a[++cnt] = x % 10;
x /= 10;
}
return dfs(cnt,0,1,1) - 10 >= n;
}
int main()
{
cin >> n;
LL l = 10,r = 1e18;
while(l < r)
{
LL mid = (l + r) >> 1;
if(check(mid))
{
r = mid;
}
else
{
l = mid + 1;
}
}
cout << l << endl;
return 0;
}七.翻倍
题目链接:https://www.lanqiao.cn/problems/21257/learning/
1.题目讲解
2.代码实现
#include <iostream>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int n,a[N],f[N],ret;
signed main()
{
cin >> n;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
}
for(int i = 2;i <= n;i++)
{
f[i] = f[i - 1];
int x = a[i - 1];
int y = a[i];
while(x > y)
{
y <<= 1;
f[i]++;
}
while(x * 2 <= y && f[i])
{
x <<= 1;
f[i]--;
}
ret += f[i];
}
cout << ret << endl;
return 0;
}八.近似回文字符串
题目链接:https://www.lanqiao.cn/problems/21256/learning/
1.题目讲解
我们可以预处理出来g数组用于统计对应的26的次方
2.代码实现
#include <iostream>
using namespace std;
#define int long long
const int N = 1e5 + 10,mod = 1e9 + 7;
int n;
int f[N],g[N];
signed main()
{
cin >> n;
g[0] = 1;
for(int i = 1;i <= n;i++)
{
g[i] = g[i - 1] * 26 % mod;
}
f[0] = 1;f[1] = 26;
for(int i = 2;i <= n;i++)
{
int a = 26 * f[i - 2] % mod;
int b = 2 * 25 * g[i / 2] % mod;
int c = (i % 2 == 1) ? 0 : 26 * 25;
f[i] = ((a + b - c) % mod + mod) % mod;
}
cout << (f[n] - g[(n + 1) / 2] + mod) % mod << endl;
return 0;
}九.子串去重
题目链接:https://www.lanqiao.cn/problems/21255/learning/
1.题目讲解
2.代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10,M = 30;
string s;
int n,m;
int f[N][M];
struct node
{
char ch;
int id;
}a[M],b[M];
int c1,c2;
bool cmp(node& a,node& b)
{
return a.id < b.id;
}
int main()
{
cin >> s >> m;
n = s.size();
s = " " + s;
//预处理
for(int j = 0;j < 26;j++)
{
f[n + 1][j] = n + 1;
}
for(int i = n;i >= 1;i--)
{
for(int j = 0;j < 26;j++)
{
f[i][j] = f[i + 1][j];
}
f[i][s[i] - 'a'] = i;
}
while(m--)
{
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
c1 = c2 = 0;
for(int j = 0;j < 26;j++)
{
if(f[x1][j] <= y1)
{
a[++c1] = {j + 'a',f[x1][j]};
}
if(f[x2][j] <= y2)
{
b[++c2] = {j + 'a',f[x2][j]};
}
}
sort(a + 1,a + c1 + 1,cmp);
sort(b + 1,b + c2 + 1,cmp);
int ret = abs(c1 - c2);
for(int i = 1;i <= min(c1,c2);i++)
{
if(a[i].ch != b[i].ch)
{
ret++;
}
}
cout << ret << endl;
}
return 0;
}十.涂格子
题目链接:https://www.lanqiao.cn/problems/21254/learning/
1.题目讲解
2.代码实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10, mod = 998244353;
int n, m, k;
struct Q
{
int x, y, c;
}q[N];
int dx[N], c1, dy[N], c2;
vector<pair<int, int>> edges[N << 1];
int col[N << 1]; bool st[N << 1];
LL qpow(LL a, LL b)
{
LL ret = 1;
while(b)
{
if(b & 1) ret = ret * a % mod;
b >>= 1;
a = a * a % mod;
}
return ret;
}
bool dfs(int x)
{
st[x] = true;
for(auto& t : edges[x])
{
int y = t.first, c = t.second;
if(st[y])
{
if((col[x] ^ col[y]) != c) return false;
continue;
}
col[y] = col[x] ^ c;
if(!dfs(y)) return false;
}
return true;
}
int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= k; i++)
{
cin >> q[i].x >> q[i].y >> q[i].c;
dx[++c1] = q[i].x;
dy[++c2] = q[i].y;
}
sort(dx + 1, dx + 1 + c1);
c1 = unique(dx + 1, dx + 1 + c1) - dx - 1;
sort(dy + 1, dy + 1 + c2);
c2 = unique(dy + 1, dy + 1 + c2) - dy - 1;
LL t = n + m - 1 - c1 - c2;
for(int i = 1; i <= k; i++)
{
int x = lower_bound(dx + 1, dx + 1 + c1, q[i].x) - dx;
int y = lower_bound(dy + 1, dy + 1 + c2, q[i].y) - dy;
int c = q[i].c;
edges[x].push_back({y + c1, c});
edges[y + c1].push_back({x, c});
}
for(int i = 1; i <= c1 + c2; i++)
{
if(st[i]) continue;
if(dfs(i)) t++;
else
{
cout << 0 << endl;
return 0;
}
}
cout << qpow(2, t) << endl;
return 0;
}更多推荐
16
0- 0
已为社区贡献2条内容
所有评论(0)