[2023] 14届

1.日期统计

题意

1.日期统计 - 蓝桥云课 (lanqiao.cn)

思路

用dfs扫

对每一个位进行限制 花了一个小时

注意把答案枚举出来 对应一下看到底对不对

code

#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int INF = 1e18 + 10;
const int N = 3e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k, ans;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
int a[1010];
int day[20] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int year[20] = {0,2,0,2,3};
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
vector<int> ve;
int sum = 0;

struct node
{
	int y1,y2,d1,d2;
	bool operator<(const node& other) const 
	{
	    if (y1 != other.y1) {
	        return y1 < other.y1;
	    }
	    if (y2 != other.y2) {
	        return y2 < other.y2;
	    }
	    if (d1 != other.d1) {
	        return d1 < other.d1;
	    }
	    return d2 < other.d2;
	}
};
set<node> se;
void dfs(int u)
{
    if(ve.size() == 8)
    {
//        for(auto c:ve) cout << c << ' ';
//        cout << endl;
        node tmp = {ve[4],ve[5],ve[6],ve[7]};
        se.insert(tmp);
        return;
    }
    for(int i = u;i <= n;i ++)
    {
        if(ve.size() < 4)
        {
            if(a[i] == year[ve.size()+1]) 
            {
            	ve.push_back(a[i]);
	            dfs(i + 1);
	            ve.pop_back();
	            continue;
			}
        }
        if(ve.size() == 4)
        {
            if(a[i] == 0 || a[i] == 1)
			{
				ve.push_back(a[i]);
	            dfs(i + 1);
	            ve.pop_back();
	            continue;
			}
        }
        if(ve.size() == 5)
        {
            if(ve.back() == 0)
            {
                if(a[i] != 0)
                {
                    ve.push_back(a[i]);
                    dfs(i + 1);
                    ve.pop_back();
                    continue;
                }
                
            }
            else
            {
                if(a[i] == 1 || a[i] == 2 || a[i] == 0) 
                {
                    ve.push_back(a[i]);
                    dfs(i + 1);
                    ve.pop_back();
                    continue;
                }
            }
        }
        if(ve.size() == 6)
        {
            int now = ve[4] * 10 + ve[5];
            if(a[i] <= day[now] / 10)
            {
                ve.push_back(a[i]);
                dfs(i + 1);
                ve.pop_back();
                continue;
            }
        }
        if(ve.size() == 7)
        {
            int now = ve[4] * 10 + ve[5];
            if(ve[6] * 10 + a[i] <= day[now] && ve[6] * 10 + a[i] > 0)
            {
                ve.push_back(a[i]);
                dfs(i + 1);
                ve.pop_back();
                continue;
            }
        }
    }
}

void gzy()
{
    n = 100;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    for(int i = 1;i <= n;i ++)
    {
        if(a[i] == 2) 
        {
        	ve.push_back(a[i]);
        	dfs(i+1);
        	ve.pop_back();
		}
    }
//    for(auto c:se)
//    {
//    	cout << c.y1 << ' ' << c.y2 << ' ' << c.d1 << ' ' << c.d2 << endl;
//	}
    cout << se.size() << endl;
}     
signed main()
{
    IOS;
    int _ = 1;
    while (_--) gzy();
    return 0;
}

2.01串的熵

题意

竞赛中心 - 蓝桥云课 (lanqiao.cn)

思路

直接枚举 要注意各种小细节，有log2的函数直接用

code

答案：11027421

#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int INF = 1e18 + 10;
const int N = 3e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k, ans;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
int a[1010];
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
vector<int> ve;
int sum = 0;

void gzy()
{
    double n = 23333333;
    double ans = 11625907.5798;
    for(int i = 1;i <= n;i ++)
    {
        double x1 = -(i / n) * log2(i/n) * i;
        double x2 = -((n-i)/n) * log2(n-i)/n * (n-i);
        double res = x1 + x2;
        if((res - ans) <= 1e-3 && i <= n / 2) 
        {
            cout << i << endl;
        }
    }
}                                                                      
signed main()
{
    IOS;
    int _ = 1;
    while (_--) gzy();
    return 0;
}

3.冶炼金属

题意

竞赛中心 - 蓝桥云课 (lanqiao.cn)

思路

模拟 贪心

code

#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int INF = 1e18 + 10;
const int N = 3e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k, ans;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
int a[1010];
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
int sum = 0;

void gzy()
{
    cin >> n;
    int maxid = INF,minid = 0;
    for(int i = 1;i <= n;i ++)
    {
        int x,y; cin >> x >> y;
        minid = max((x/(y+1)+1),minid);
        maxid = min(x / y,maxid);
    }
    cout << minid << ' ' << maxid << endl;
}                                                                      
signed main()
{
    IOS;
    int _ = 1;
    while (_--) gzy();
    return 0;
}

4.飞机降落

题意

竞赛中心 - 蓝桥云课 (lanqiao.cn)

思路

全部都要能降落

用dfs 每次推时间 然后如果怎么推都不行就false  记录cnt = n

code

#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int INF = 1e18 + 10;
const int N = 310;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k, ans;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
int a[1010];
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
int t[N],d[N],l[N]; // 到达时间 能wait的时间 和下降需要的时间
bool st[N];// 1 指用过了   0 指没用过
int tnow = 0; // 从零开始
int cnt = 0;
bool flag = 0;
void dfs(int u)
{
    for(int i = 1;i <= n;i ++)
    {
    	if(cnt == n)
        {
            flag = 1;
            return;
        }
        if(st[i]) continue;
        // if(t[i] < tnow && t[i] + d[i] < tnow) return;
        if(t[i] + d[i] >= tnow)
        {
//            tnow += l[i];
			int ji = tnow;
            tnow = max(tnow,t[i]) + l[i];
            st[i] = 1;
            cnt ++;
            
            dfs(i);
            
			tnow = ji;
            st[i] = 0;
            cnt --;
            
        }
        if(cnt == n)
        {
            flag = 1;
            return;
        }
    }
}

void gzy()
{
	flag = 0;
	memset(st,0,sizeof st);
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> t[i] >> d[i] >> l[i];
    for(int i = 1;i <= n;i ++)
    {
        cnt = 1;
        tnow = t[i] + l[i];
        st[i] = 1;
        
        dfs(i);
        
        st[i] = 0;    
        cnt = 1;
    }
    if(flag) cout << "YES\n";
    else cout << "NO\n";
}
signed main()
{
    IOS;
    int _ = 1; cin >> _;
    while (_--) gzy();
    return 0;
}

//
//#include <iostream>
//#include <vector>
//using namespace std;
//
 创建飞机结构体变量
//struct plane
//{
//    int t, d, l;
//};
//bool vis[15];  // true表示飞机降落，false表示飞机未降落
//bool flag;  // 标记是否全部安全降落
//vector<plane> p(15);
 深搜
//void dfs(int m, int cnt, int last)  // last表示此前所有飞机降落所需的单位时间
//{
//    if (cnt == m)
//    {
//        flag = true;
//        return;
//    }
//    for (int i = 0; i < m; i++)
//    {
//        if (!vis[i] && p[i].t + p[i].d >= last)  // 只有来的时刻+盘旋时间 > last 的飞机才可以安全降落
//        {
//            vis[i] = true;
//            dfs(m, cnt + 1, max(last, p[i].t) + p[i].l);
//            vis[i] = false;
//        }
//    }
//}
//
//int main()
//{
//    int T;
//    cin >> T;
//    while (T--)
//    {
//        int N;
//        cin >> N;
//        for (int i = 0; i < N; ++i)
//            cin >> p[i].t >> p[i].d >> p[i].l;
//        flag = false;
//        dfs(N, 0, 0);
//        if (flag)
//            cout << "YES" << endl;
//        else
//            cout << "NO" << endl;
//    }
//    return 0;
//}

5.接龙序列

题意

竞赛中心 - 蓝桥云课 (lanqiao.cn)

思路

30%的用dfs应该可以

100%是DP

就类似于是最大连续子区间

假设 bef是第一位  aft是最后一位

code

#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int INF = 1e18 + 10;
const int N = 1e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
int a[N],f[N];
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
int ans = 0;
void gzy()
{
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    for(int i = 1;i <= n;i ++)
    {
        int len = 0,now = a[i];
        while(now)
        {
            len ++;
            now /= 10;
        }
        // cout << len << endl;
        int ch = 1;
        for(int j = 1;j < len;j ++) ch *= 10;
        int aft = a[i] % 10, bef = a[i] / ch;
        f[aft] = max(f[bef] + 1,f[aft]);
    }
    // for(int i = 0;i <= 9;i ++) cout << f[i] << ' ';
    // cout << endl;
    int maxid = *max_element(f,f+10);
    // cout << maxid << endl;
    cout << n - maxid << endl;
}                                                                      
signed main()
{
    IOS;
    int _ = 1;
    while (_--) gzy();
    return 0;
}

6.岛屿个数

题意

竞赛中心 - 蓝桥云课 (lanqiao.cn)

思路

先把所有最外圈的海标记为2 包括但凡连通的所有海

这样剩下来的海都是0 然后把他们都变成1

每次只需要统计连通块 1 的个数即可

code

#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int INF = 1e18 + 10;
const int N = 1e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
int a[N],f[N];
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
int ans = 0;
string ilen[51];
int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
int dx1[8] = {-1,-1,0,1,1,1,0,-1},dy1[8] = {0,-1,-1,-1,0,1,1,1};
void bfs(int x,int y)
{
    queue<PII> q;
    q.push({x,y});
    while(!q.empty())
    {
        PII tmp = q.front();
        q.pop();
        for(int i = 0;i < 8;i ++)
        {
            int nx = tmp.first + dx1[i];
            int ny = tmp.second + dy1[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && ilen[nx][ny] == '0')
            {
                ilen[nx][ny] = '2';
                q.push({nx,ny});    
            }
        }
    }
}

void bfsd(int x,int y)
{
    queue<PII> q;
    q.push({x,y});
    while(!q.empty())
    {
        PII tmp = q.front();
        q.pop();
        for(int i = 0;i < 4;i ++)
        {
            int nx = tmp.first + dx[i],ny = tmp.second + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && ilen[nx][ny] == '1')
            {
                ilen[nx][ny] = '0';
                q.push({nx,ny});
            }
        }
    }
}

void gzy()
{
    cin >> n >> m;
    for(int i = 0;i < n;i ++) cin >> ilen[i];
    ans = 0;
    // 先把海水打上2的标记
    for(int i = 0;i < m;i ++)
        if(ilen[0][i] == '0') 
        {
            ilen[0][i] = '2';
            bfs(0,i);
        }
    for(int i = 0;i < m;i ++)
        if(ilen[n-1][i] == '0') 
        {
            ilen[n-1][i] = '2';
            bfs(n-1,i);
        }
    for(int i = 0;i < n;i ++)
        if(ilen[i][0] == '0') 
        {
            ilen[i][0] = '2';
            bfs(i,0);
        }
    for(int i = 0;i < n;i ++)
        if(ilen[i][m-1] == '0')
        {
            ilen[i][m-1] = '2';
             bfs(i,m-1);
        }
    // for(int i = 0;i < n;i ++)
    //     cout << ilen[i] << endl;

    // 接下来需要填充岛屿 ---
    for(int i = 0;i < n;i ++)
        for(int j = 0;j < m;j ++)
            if(ilen[i][j] == '0') ilen[i][j] = '1';
    
    // 之后找到1块
    for(int i = 0;i < n;i ++)
    {
        for(int j = 0;j < m;j ++)
        {
            if(ilen[i][j] == '1')
            {
                ilen[i][j] = '0';
                ans ++;
                bfsd(i,j);    
            } 
        }
    }
    // for(int i = 0;i < n;i ++)
    //     cout << ilen[i] << endl;
    cout << ans << endl;
}                                                                      
signed main()
{
    IOS;
    int _ = 1; cin >> _;
    while (_--) gzy();
    return 0;
}

7.字串简写

题意

竞赛中心 - 蓝桥云课 (lanqiao.cn)

思路

最简单的一题了 哎比第一题简单多了

code

#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int INF = 1e18 + 10;
const int N = 1e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
int a[N],f[N];
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
int ans = 0;
void gzy()
{
    string st;
    cin >> k >> st;
    n = st.size();
    char be,af; cin >> be >> af;
    // cout << be << ' ' << af << endl;
    vector<int> vbe,vaf;
    for(int i = 0;i < n;i ++)
    {
        // if(st[i] == be) vbe.push_back(i);
        if(st[i] == af) vaf.push_back(i);
    }
    // for(auto c:vaf) cout << c << ' ';
    // cout << endl;
    int sum = 0,len = vaf.size();
    for(int i = 0;i < n;i ++)
    {
        if(st[i] == be)
        {
            if(lower_bound(vaf.begin(),vaf.end(),i + k - 1) != vaf.end())
            {
                int idx = lower_bound(vaf.begin(),vaf.end(),i + k - 1) - vaf.begin();
                // cout << idx << endl;
                sum += len - idx;
            }
        }
    }
    cout << sum << endl;
}                                                                      
signed main()
{
    IOS;
    int _ = 1;
    while (_--) gzy();
    return 0;
}

8.整数删除

题意

竞赛中心 - 蓝桥云课 (lanqiao.cn)

思路

优先队列维护 注意到k次就停！

code

#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int INF = 1e18 + 10;
const int cmp = 1e17;
const int N = 5e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
int a[N],f[N];
PII b[N];
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
void gzy()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i ++) 
    {
        cin >> a[i];
        b[i] = {a[i],i};
    }
    priority_queue<PII,vector<PII>,greater<PII> > q;
    for(int i = 1;i <= n;i ++) q.push(b[i]);
    while(k > 0)
    {
        PII t = q.top();
        q.pop();
        int val = t.first, idx = t.second;
        if(t.first != a[t.second])
        {
             q.push({a[idx],idx});
             continue;
        }
        int l = idx-1,r = idx + 1;
        while(l >= 1 && a[l] == INF)
        {
            l --;
        }
        if(l >= 1) a[l] += a[idx];
        while(r <= n && a[r] == INF)
        {
            r ++;
        }
        if(r <= n) a[r] += a[idx];
        a[idx] = INF;
        k --;
        // for(int i = 1;i <= n;i ++)
        // {
        //     if(a[i] < cmp) cout << a[i] << ' ';
        // }
        // cout << endl;
    }
    for(int i = 1;i <= n;i ++)
    {
        if(a[i] < cmp) cout << a[i] << ' ';
    } 
    // cout << endl;
}                                                                      
signed main()
{
    IOS;
    int _ = 1;
    while (_--) gzy();
    return 0;
}

9.景区导游

题意

竞赛中心 - 蓝桥云课 (lanqiao.cn)

思路

40%的数据 dfs过

dfs模拟最短路 记录在数组预处理一下

code

//https://www.lanqiao.cn/problems/3516/learning/?subject_code=1&group_code=4&match_num=14&match_flow=1&origin=cup&page=1
#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int INF = 1e18 + 10;
const int cmp = 1e17;
const int N = 5e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
int a[N],f[N];
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
// PII dist[N];  //存放两点间距离
map<PII,int> dist;
vector<vector<PII>> ve(N); // 存放下一个点的idx和距离
int ido[N];
int sum = 0,minid = INF;
void dfs(int now,int gol,int fa,int cost)
{
    if(now == gol)
    {
        minid = min(cost,minid);
        return;
    }
    for(PII tmp:ve[now])
    {
        int nxt = tmp.first, mny = tmp.second;
        if(nxt != fa)
        {
            dfs(nxt,gol,now,cost + mny);
        }
    }
}

void gzy()
{
    int x,y,z;
    cin >> n >> k; // k个
    for(int i = 1;i < n;i ++)
    {
        cin >> x >> y >> z;
        ve[x].push_back({y,z});
        ve[y].push_back({x,z});
    }
    for(int i = 1;i <= k;i ++) cin >> ido[i];
    // 求出来sum
    for(int i = 1;i < k;i ++)
    {
        minid = INF;
        dfs(ido[i],ido[i+1],0,0);
        dist[{ido[i],ido[i+1]}] = minid;
        sum += minid;
    }
    // cout << sum << endl;
    for(int i = 1;i <= k;i ++)
    {
        int ans;
        if(i == 1)
            ans = sum - dist[{ido[i],ido[i+1]}];
        else if(i == k)
             ans = sum - dist[{ido[i-1],ido[i]}];

        else
        {
            minid = INF;
            dfs(ido[i-1],ido[i+1],0,0);
            ans = sum - dist[{ido[i-1],ido[i]}] - dist[{ido[i],ido[i+1]}] + minid;
        }
        cout << ans << ' ';
    }
}                                                                      
signed main()
{
    IOS;
    int _ = 1;
    while (_--) gzy();
    return 0;
}

10.砍树

题意

竞赛中心 - 蓝桥云课 (lanqiao.cn)

思路

30%的数据：枚举每一次要删除哪个边 然后跑dfs

code

#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<char,int> PCI;
const int INF = 1e18 + 10;
const int N = 3e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k, ans;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
int sum = 0;
PII ed[N],shu[N];
bool flag = 1;
vector<vector<int>> ve(N);
void dfs(int u,int v,int end,int now,int fa)
{ 
	if(!flag) return;
    for(int c:ve[now])
    {
        if(c != fa)
        {
            if((c == u && now == v) || (c == v && now == u)) continue;
            if(c == end)
            {
                flag = 0;
                return;
            }
            dfs(u,v,end,c,now);
        }
    }
}

void gzy()
{
    cin >> n >> m;
    for(int i = 1;i < n;i ++)
    {
        int x,y; cin >> x >> y;
        shu[i].first = x,shu[i].second = y;
        ve[x].push_back(y);
        ve[y].push_back(x);
    }
    for(int i = 1;i <= m;i ++)
        cin >> ed[i].first >> ed[i].second;
    ans = -1;
    for(int i = 1;i < n;i ++)
    {
        flag = 1;
        for(int j = 1;j <= m;j ++)
        {
            dfs(shu[i].first,shu[i].second,ed[j].second,ed[j].first,0); // 删第几条边 然后现在需要判断第j个的连通性
            if(flag == 0) break;
        }
        if(flag) 
        {
            ans = i;
            flag = 0;
        }
    }
    cout << ans << endl;
}                                                                      
signed main()
{
    IOS;
    int _ = 1;
    while (_--) gzy();
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/489532.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

电脑桌面记事本便签软件，记事本软件哪个好用

电脑桌面记事本便签软件，记事本软件哪个好用

正在电脑前忙碌工作&#xff0c;突然想起今晚有个重要的会议&#xff0c;或者是明天有一个重要的任务需要完成&#xff0c;但是手头的工作又无法让你离开电脑&#xff0c;这时候&#xff0c;你多么希望有一个便捷的电脑桌面记事本便签软件&#xff0c;可以让你快速记录下这些重…
阅读更多...
Python时间

Python时间

UTC ~ 北京时间 【差8小时】 格式化日期时间为字符串:strftime 时间戳-1970.1.1到现在的秒数:time.time() AttributeError: partially initialized module ‘datetime’ has no attribute ‘fromtimestamp’ (most likely due to a circular import) 改正&#xff1a;文件名和…
阅读更多...
【C++】隐藏的this指针

【C++】隐藏的this指针

文章目录 1.this指针的引出2.this指针的特性 1.this指针的引出 我们通过日期类来学习this指针&#xff0c;首先我们先定义一个日期类。 class Date { public:void Display(){cout << _year << "-" << _month << "-" << _d…
阅读更多...
1688商品API接口数据采集助力电商ERP

1688商品API接口数据采集助力电商ERP

1688商品API接口数据采集可以帮助电商供应链ERP系统搭建&#xff0c;提供所需的商品信息和数据。 通过使用1688商品API接口&#xff0c;可以直接从1688网站上抓取商品信息&#xff0c;包括商品名称、价格、库存、属性等。这样&#xff0c;可以省去手动复制粘贴的步骤&#xff…
阅读更多...
矩阵的归一化技术

矩阵的归一化技术

矩阵的归一化&#xff08;Normalization&#xff09;是将矩阵中的元素缩放到一个特定的范围或者标准&#xff0c;使得在进行比较、评估或计算时能够保持数值稳定性和可比性。这个过程在数据预处理、机器学习、图像处理等领域中非常重要。归一化有助于改善算法的收敛速度和精度&…
阅读更多...
elasticsearch 教程（一）程序建立索引

elasticsearch 教程（一）程序建立索引

elasticsearch 教程&#xff08;一&#xff09;程序建立索引 从elasticsearch 8.x开始&#xff0c;除了通过kibana建立索引之外&#xff0c;还可以在Java程序定义索引。待程序运行时&#xff0c;会先检测是否建立索引&#xff0c;如果已建立索引&#xff0c;即使程序中定义的索…
阅读更多...
百能云板开启1-6层陶瓷pcb板定制服务

百能云板开启1-6层陶瓷pcb板定制服务

普通PCB通常是由铜箔和基板粘合而成&#xff0c;而基板材质大多数为玻璃纤维&#xff08;FR-4&#xff09;&#xff0c;酚醛树脂&#xff08;FR-3&#xff09;等材质&#xff0c;粘合剂通常是酚醛、环氧等。在PCB加工过程中由于热应力、化学因素、生产工艺不当等原因&#xff0…
阅读更多...
哈希冲突解决的几种方式

哈希冲突解决的几种方式

目录 哈希冲突 哈希冲突-避免方式1-哈希函数的设计 1. 直接定制法--(常用) 2. 除留余数法--(常用) 3. 平方取中法--(了解) 哈希冲突-避免方式2-负载因子调节 哈希冲突-解决方式1-闭散列 1.线性探测 2.二次探测 哈希冲突-解决方式2-开散列(哈希桶) 哈希冲突 在上文中…
阅读更多...
【Java程序设计】【C00383】基于（JavaWeb）Springboot的水产养殖系统（有论文）

【Java程序设计】【C00383】基于（JavaWeb）Springboot的水产养殖系统（有论文）

【C00383】基于&#xff08;JavaWeb&#xff09;Springboot的水产养殖系统&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 博主介绍&#xff1a;java高级开发&#xff0c;从事互联网行业六年&#xff0c;已经做了六年的毕业设计程序开发&#xff0c…
阅读更多...
SketchUp草图大师模型网：哪家更值得信赖？

SketchUp草图大师模型网：哪家更值得信赖？

草图大师模型网是一个提供模型下载和分享的平台&#xff0c;用户可以在上面找到大量的SU模型&#xff0c;并学习一些草图大师的使用技巧。那么&#xff0c;SketchUp草图大师模型网哪家更值得信赖呢?下面将从多个角度进行比较和分析。 首先&#xff0c;我们要看看草图大师模型网…
阅读更多...
python关于字符串基础学习

python关于字符串基础学习

字符串 python字符串是不可改变的 Python不支持单字符类型&#xff0c;单字符也是作为一个字符串使用的。 字符串编码 python3直接支持Unicode,可以表示世界上任何书面语言的字符 python3的字符默认就是16位Unicode编码&#xff0c;ASCII是Unicode的子集 使用内置函数 ord()…
阅读更多...
2.4 如何运行Python程序

2.4 如何运行Python程序

如何运行Python程序&#xff1f; Python是一种解释型的脚本编程语言&#xff0c;这样的编程语言一般支持两种代码运行方式&#xff1a; 1) 交互式编程 在命令行窗口中直接输入代码&#xff0c;按下回车键就可以运行代码&#xff0c;并立即看到输出结果&#xff1b;执行完一行…
阅读更多...
c++初步

c++初步

作业&#xff1a; 定义自己的命名空间&#xff0c;其中有string类型的变量&#xff0c;再定义两个函数&#xff0c;一个函数完成字符串的输入&#xff0c;一个函数完成求字符串长度&#xff0c;再定义一个全局函数完成对该字符串的反转 #include <iostream> #include &…
阅读更多...
虚拟 DOM 的优缺点有哪些

虚拟 DOM 的优缺点有哪些

虚拟DOM&#xff08;Virtual DOM&#xff09;技术作为现代前端开发中的重要组成部分&#xff0c;已经成为了众多流行前端框架的核心特性。它的引入为前端开发带来了诸多优势&#xff0c;同时也需要我们认真思考其潜在的考量。下面简单的介绍一下虚拟DOM技术的优势与缺点&#x…
阅读更多...
ESCTF-OSINT赛题WP

ESCTF-OSINT赛题WP

这你做不出来?check ESCTF{湖北大学_嘉会园食堂} 这个识图可以发现是 淡水渔人码头 但是 osint 你要发现所有信息 聊天记录说国外 同时 提示给了美国 你综合搜索 美国 渔人码头 在美国旧金山的渔人码头&#xff08;英语&#xff1a;Fisherman’s Wharf&#xff09;是一个著名旅…
阅读更多...
rust中字符串String常用方法和注意事项

rust中字符串String常用方法和注意事项

Rust 中通常说的字符串指的是&#xff1a;String 和 &str(字符串字面值、或者叫字符串切片)这两种类型。str是rust中基础字符串类型&#xff0c;String是标准库里面的类型。Rust 中的字符串本质上是&#xff1a;Byte的集合&#xff08;Vec<u8>&#xff09; 基础类型…
阅读更多...
使用EasyYapi插件简化导出yapi接口

使用EasyYapi插件简化导出yapi接口

安装 &#xff1a; 关键配置&#xff1a; 其中的token在这里拿&#xff1a; 使用&#xff1a; 导出当前Controller下的所有api&#xff1a;使用下图命令可仅导出指定的api: 附&#xff1a;配置部分参考了idea&#xff1a;使用easyYapi插件导出yapi接口
阅读更多...
docker--docker网络（四）

docker--docker网络（四）

1. docker网络模式 docker安装成功后&#xff0c;会自动创建三个网络&#xff0c;可以通过如下的方式查看&#xff1a; lisenubuntu:~$ sudo docker network ls [sudo] password for lisen: NETWORK ID NAME DRIVER SCOPE 8994fe397802…
阅读更多...
将谷歌 Gemma AI大模型 部署安装本地教程（可离线使用）

将谷歌 Gemma AI大模型 部署安装本地教程（可离线使用）

CSDN 成就一亿技术人&#xff01; 作者主页&#xff1a;点击&#xff01; ————前言———— 谷歌 Gemma 是一个基于 Python 的图像分析工具&#xff0c;提供快速和准确的物体检测、定位、分类和风格迁移功能。它使用 TensorFlow Lite 模型&#xff0c;使它可以快速运行在…
阅读更多...
金和OA C6 IncentivePlanFulfill.aspx SQL注入漏洞复现

金和OA C6 IncentivePlanFulfill.aspx SQL注入漏洞复现

0x01 产品简介 金和网络是专业信息化服务商,为城市监管部门提供了互联网+监管解决方案,为企事业单位提供组织协同OA系统开发平台,电子政务一体化平台,智慧电商平台等服务。 0x02 漏洞概述 金和OA C6 IncentivePlanFulfill.aspx接口处存在SQL注入漏洞，攻击者除了可以利用 SQ…
阅读更多...
最新文章

Copyright @ 2022~2023