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];// 求出来sumfor(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;
}
