[2023] 14届

news/2024/7/20 22:15:23 标签: 深度优先, 算法

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;
}


http://www.niftyadmin.cn/n/5450755.html

相关文章

Ubuntu20.04下VSCode配置PCL和OpenCV库-C++

Ubuntu20.04下VSCode配置PCL和OpenCV库-C++

Ubuntu20.04 VSCode Cpp PCL OpenCV 准备工作 代码编辑&#xff1a;VSCode 开发语言&#xff1a;C 编译工具&#xff1a;Cmake G 依赖需求&#xff1a;PCL / OpenCV 安装PCL库 sudo apt install libpcl-dev配置OpenCV库 安装依赖 sudo apt-get install build-essenti…
阅读更多...
JAVA使用POI实现Excel单元格合并-02

JAVA使用POI实现Excel单元格合并-02

JAVA使用POI实现Excel单元格合并 实现效果 解释&#xff1a;只要是遇见与前一行相同的数据就合并 引入jar <dependency><groupId>org.apache.poi</groupId><artifactId>poi-ooxml</artifactId><version>5.2.2</version></depe…
阅读更多...
【vscode打开多文件夹】

【vscode打开多文件夹】

1)将文件夹添加到工作空间中 2)文件夹方式展开 3)最终效果 小技巧&#xff1a; 文件夹的位置不对的话&#xff0c;可以拖动进行调整。
阅读更多...
【mybatis】TypeAliasRegistry解读

【mybatis】TypeAliasRegistry解读

引言 在现代软件开发中&#xff0c;对象关系映射&#xff08;ORM&#xff09;框架已成为连接应用程序和数据库的桥梁&#xff0c;而MyBatis以其灵活性和简洁性&#xff0c;在众多Java ORM框架中脱颖而出。它不仅提供了丰富的映射功能&#xff0c;还允许开发者以接近SQL的方式进…
阅读更多...
php反序列化刷题1

php反序列化刷题1

[SWPUCTF 2021 新生赛]ez_unserialize 查看源代码想到robots协议 看这个代码比较简单 直接让adminadmin passwdctf就行了 poc <?php class wllm {public $admin;public $passwd; }$p new wllm(); $p->admin "admin"; $p->passwd "ctf"; ec…
阅读更多...
【牛客】SQL142 对试卷得分做min-max归一化

【牛客】SQL142 对试卷得分做min-max归一化

描述 现有试卷信息表examination_info&#xff08;exam_id试卷ID, tag试卷类别, difficulty试卷难度, duration考试时长, release_time发布时间&#xff09;&#xff1a; idexam_idtagdifficultydurationrelease_time19001SQLhard602020-01-01 10:00:0029002Chard802020-01-0…
阅读更多...
http和socks5代理哪个好？

http和socks5代理哪个好？

HTTP代理和SOCKS5代理各有其优缺点&#xff0c;但就隐蔽性而言&#xff0c;SOCKS5代理通常比HTTP代理更隐蔽。以下是它们的比较&#xff1a; HTTP代理&#xff1a; 透明性较高&#xff1a;HTTP代理在HTTP头中会透露原始客户端的IP地址&#xff0c;这使得它相对不太隐蔽。…
阅读更多...
冒泡排序和选择排序--C语言

冒泡排序和选择排序--C语言

冒泡排序&#xff08;升序&#xff09;&#xff1a; 设计思想&#xff1a; 每两个相邻的数进行比较&#xff0c;大的往后走 详细过程&#xff1a; 例&#xff1a;99 ,100, 88 ,80 ,100, 90, 77, 22, 33, 90 第一遍&#xff1a; 99与100比较&#xff0c;100大&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023