B - 11/11
难度: ⭐
题目大意
在某个世界一年有n个月, 每个月有di天, 问有多少个日期, 该日期和月份组成的数字都是一样的; eg: 11月的1日, 22月的22日;
解题思路
暴力就行;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10;
int n,m;
int f[N];
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
int x,y;
cin>>x;
if(i<10) y=i;
else{
if(i%10==i/10) y=i%10;
else continue;
}
if(x>=y*10+y) m+=2;
else if(x>=y) m++;
}
cout<<m;
return 0;
}
C - Consecutive
难度: ⭐⭐
题目大意
给定一个字符串和m个询问, 每个询问都是一个区间, 问区间中有多少个连续两个相同字母的情况, "sss"看作2个;
解题思路
用前缀和来做就行, 注意边界问题;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=3e5+10;
int n,m;
int f[N];
signed main(){
cin>>n>>m;
string s;
cin>>s;
s=' '+s;
for(int i=1;i<=n;i++){
if(s[i]==s[i+1]){
f[i]=f[i-1]+1;
}
else f[i]=f[i-1];
}
while(m--){
int l,r;
cin>>l>>r;
cout<<f[r-1]-f[l-1]<<endl;
}
return 0;
}
D - Take ABC
难度: ⭐⭐⭐
题目大意
给定一个字符串, 从前往后遍历, 如果遇到连续的"ABC"就可以清除这三个字母, 注意在清除后新生成的也算; 输出操作后的字符串;
解题思路
跟括号匹配一个思想, 我们用一个堆才存放字母, 如果当前字母是'C', 并且堆中前两个是'A'和'B', 那么就可以把他们删掉; 所以只需要判定'C'即可;
神秘代码
#include<bits/stdc++.h>
//#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 5e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
char f[N];
signed main(){
string s;
cin>>s;
s=' '+s;
for(int i=1;i<s.size();i++){
if(s[i]=='C'){
if(idx>=2&&f[idx-1]=='A'&&f[idx]=='B') idx-=2;
else f[++idx]='C';
}
else f[++idx]=s[i];
}
for(int i=1;i<=idx;i++) cout<<f[i];
return 0;
}
E - Modulo MST
难度: ⭐⭐⭐
题目大意
给定n个点和m条边以及边的权值, 问这个图取模后的最小生成树的边权和是多少;
解题思路
因为本题是问取模后的最小值, 所以不能用之前学过的算法; 因为数据范围很小, 所以可以考虑暴力枚举, 暴力枚举时我们可以借鉴prim的思想, 我们把结点1作为生成树的根节点, 然后我们dfs节点2~n, 对于每个节点, 我们从所有与它相连的节点中挑选一个作为它的父节点; dfs完第n个节点后我们就得检查一下当前得到的生成树是否合法, 需要检查两个点, 一是每个节点都可以到达根节点, 二是没有环; 第一点可以根据dfs中得到的父子关系进行寻找, 第二点只需要在寻找的时候打个标记即可;
在ac后我突然想到以上的过程可以用并查集来优化, 我们只需要把kruskal算法暴力一下, 我们还是从节点1开始dfs, 然后通过并查集把所有节点连到一起, 这样到最后就不需要检查了, 因为并查集会自动避免非法情况, 但是使用并查集会有一个隐藏的坑, 就是关于dfs的回溯问题, 因为大部分并查集的板子会修改在find函数中修改中间节点的父节点来压缩路径, 但是这样回溯时还需要一一修改, 所以我们可以修改为不压缩路径即可;
而且中间还有一个插曲, 我发现在dfs中p[find(u)] = find(i)改成p[u] = find(i)也可以ac, 在模拟后发现我的这种写法是从下往上去建立并查集的链, 所以每次dfs中u都是某条链中最靠上的节点(也就是这条链的祖宗节点), 所以这两种写法是一致的;
神秘代码
//朴素
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 100 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx, k;
int res = 1e17;
int p[N];
bool st[N][N];
int f[N][N];
bool check(){
for(int i=2;i<=n;i++){
int x=i;
map<int,int> mp;
mp[i]=1;
while(1){
if(!p[x]){
if(x!=1) return false;
break;
}
x=p[x];
if(mp[x]) return false;
mp[x]=1;
}
}
return true;
}
void dfs(int u,int sum){
if(u>n){
if(check())res=min(res,sum);
return;
}
for(int i=1;i<=n;i++){
if(st[u][i]){
p[u]=i;
dfs(u+1,(sum+f[u][i])%k);
}
}
}
signed main() {
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
f[a][b] = f[b][a] = c;
st[a][b] = st[b][a] = true;
}
dfs(2,0);
cout<<res;
return 0;
}
//并查集
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 100 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx, k;
int res = 1e17;
int p[N];
bool st[110][110];
int f[110][110];
int find(int u){
if(p[u] != u) return find(p[u]);
else return p[u];
}
void dfs(int u,int sum){
if(u==n){
res=min(res,sum%k);
return;
}
for(int i=1;i<=n;i++){
int a=find(u), b=find(i);
if(st[u][i]&&a!=b){
p[a]=b;
dfs(u+1,sum+f[u][i]);
p[a]=a;
}
}
}
signed main() {
cin >> n >> m >> k;
for(int i=1;i<=n;i++) p[i]=i;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
f[a][b] = f[b][a] = c;
st[a][b] = st[b][a] = true;
}
dfs(1,0);
cout<<res;
return 0;
}
F - Good Set Query
难度: ⭐⭐⭐⭐
题目大意
解题思路
需要用到带权并查集...晚上补
神秘代码