https://www.luogu.com.cn/problem/AT_abc376_d
问是否含有节点1的环 我一开始做成dfs找环了 很明显
时间过不去 肯定超时的
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6;
int nums = 1e15;
int vis[N],pre[N];
vector<int>e[N];
void dfs(int u,int fa){ //dfs
vis[u] = 1;
for(auto v : e[u]){
if(v==fa) continue; //如果是无向的 a-->b 的同时也有 b-->a,所以直接排除另外的一种情况
if(vis[v]==0){ //如果没有访问就标记当前元素的前一个元素
pre[v] = u;
dfs(v,u); //并且一直递归访问下去
}else if(vis[v]==1){
bool flag=0;
int temp = u,cnt = 1;//环的长度
if(temp==1||v==1)flag=1;
while(temp != v)
{
if(temp==1)flag=1;
// cout<<temp<<" ";
cnt++;
temp =pre[temp];
}
// cout<<v<<"\n";
if(flag)
nums=min(nums,cnt);
}
}
vis[u] = 2;
}
signed main()
{
int n,m;int u,v;
//n为点数 m为边数 u是起点v是终点
cin >> n>>m;
for(int i = 1;i <= m;i++){
cin >> u >> v;
e[u].push_back(v);
// e[v].push_back(u);
}
for(int i = 1;i <= n;i++){ //可能是非联通图
if(vis[i]==0) //每一次可以访问完和该点相连的所有点
dfs(i,-1);
}
if(nums==1e15){
cout<<-1<<endl;return 0;
}
cout << nums << endl; //环数
}
然后改进下 其实就是一个最短路 如果访问到1直接输出距离+1就行
https://www.luogu.com.cn/problem/AT_abc375_d
这是一个三个字符的字符串 我写了一个暴力 但是超时了
https://atcoder.jp/contests/abc375/submissions/58711251
正确的做法是我们枚举中间 然后前后两个必须相同
考虑前缀和 与 后缀和 于是 就做出来了
https://www.luogu.com.cn/problem/AT_abc376_e
我一开始读错题目了 以为必须的是连续的A序列
实际上并不是 只有满足是子集就行
所以S是个随便的组合 所以 我们该如何去做呢
由于是 要求最小我们可以思考到 固定一边 从而控制变量
那么我们该控制a还是b呢 对于这个集合s我们怎么处理呢
不难发现 A只是要最大的 如果我们控制了最大的数 然后 左边就控制住了 只需要去看右边 然后右边是选N个 看看选的N个*Amax是不是最小的 就好了 然后不断枚举 模拟即可 Amax只需要for循环 然后和不断上浮下沉就行 提前塞n个数进去 n+1的时候 再看新进来能不能构成更小 判断即可
for(int i=k;i<=n;i++)
{
sum+=a[i].b;
ans=min(ans,sum*a[i].a);
q.push(a[i].b);
sum-=q.top();
q.pop();
}