网站有版权吗,wordpress如何关闭网站,wordpress电影分享主题,危机公关文章目录 1 日期统计2 01串的熵3 冶炼金属4 飞机降落5 接龙数列6 岛屿个数7 子串简写8 整数删除9 景区导游10 砍树 前言#xff1a;时隔一年#xff0c;再次做这套题(去年参赛选手)#xff0c;差点道心不稳T_T#xff0c;故作此补题#xff01; 1 日期统计
没写出来… 文章目录 1 日期统计2 01串的熵3 冶炼金属4 飞机降落5 接龙数列6 岛屿个数7 子串简写8 整数删除9 景区导游10 砍树 前言时隔一年再次做这套题(去年参赛选手)差点道心不稳T_T故作此补题 1 日期统计
没写出来看题解知道了一种暴力的思想枚举所有2023年的日期看看有没有满足条件的数。关于如何提取题中的数字可以复制到excel当中然后ctrlH将空格替换为英文逗号
#includebits/stdc.h
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
typedef pairint,int PII;
const int N 2e510, INF 0x3f3f3f3f;
int a[N]{0,5,6,8,6,9,1,6,1,2,4,9,1,9,8,2,3,6,4,7,7,5,9,5,0,3,8,7,5,8,1,5,8,6,1,8,3,0,3,7,9,2,7,0,5,8,8,5,7,0,9,9,1,9,4,4,6,8,6,3,3,8,5,1,6,3,4,6,7,0,7,8,2,7,6,8,9,5,6,5,6,1,4,0,1,0,0,9,4,8,0,9,1,2,8,5,0,2,5,3,3};
int mon[13]{0,31,28,31,30,31,30,31,31,30,31,30,31};
int n100,ans;void solve() {for(int m1;m12;m) //枚举所有日期for(int d1;dmon[m];d){int tar[9]{0,2,0,2,3,m/10,m%10,d/10,d%10}; //当前日期int num1;for(int i1;i100;i){ //看看有没有符合条件的if(a[i]tar[num]){num;if(num9){ans; break;}}}}coutans;
}signed main() {
// IOS;int T1;
// cinT;while(T--) {solve();}return 0;
}2 01串的熵
因为0的出现次数比1的出现次数少所以我们可以枚举0的个数1的个数即为01串的长度减去0的个数。然后根据公式即可求得
#includebits/stdc.h
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
const int N 2e510, INF 0x3f3f3f3f;
int len23333333,cnt;
double res,tar11625907.5798; void solve() {for(int i0;ilen;i){ //0的数量 int jlen-i; //1的数量 res-1.0*(1.0*i/len)*i*(log(1.0*i/len)/log(2))(-1)*(1.0*j/len)*j*(log(1.0*j/len)/log(2));if(restar){printf(%.4f %.4f\n,res,tar);coutiendl; break;}}}signed main() {
// IOS;int T1;
// cinT;while(T--) {solve();}return 0;
}3 冶炼金属
读完题目后我们可以枚举答案来求得V的最大值和最小值即用到二分答案。
#includebits/stdc.h
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
const int N 1e410, INF 0x3f3f3f3f;
int n,a[N],b[N];
int res1,res2;bool check1(int x){for(int i1;in;i){int numa[i]/x; //转换的个数if(numb[i]) return false;}return true;
}int calc1(){int l0,r1e910;while(l1r){int midlr1;if(check1(mid)) rmid; //满足条件缩小范围求最小值else lmid;}return r;
}bool check2(int x){for(int i1;in;i){int numa[i]/x;if(numb[i]) return false;}return true;
}int calc2(){int l0,r1e910;while(l1r){int midlr1;if(check2(mid)) lmid;else rmid;}return l;
}void solve() {cinn;for(int i1;in;i)cina[i]b[i];res1calc1(); //最小值res2calc2(); //最大值coutres1 res2;
}signed main() {
// IOS;int T1;
// cinT;while(T--) {solve();}return 0;
}4 飞机降落
N的数据范围只有10我们可以暴力枚举所有飞机降落的顺序如果有一个满足就符合要求。用全排列函数next_permutation函数可以实现这一操作
#includebits/stdc.h
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
const int N 1e310, INF 0x3f3f3f3f;
struct node{int t,d,l;
}a[N];
int n,id[N]; void solve() {cinn;for(int i1;in;i){int t,d,l; cintdl;a[i]{t,d,l}; id[i]i;}do{int now0,flag1;for(int i1;in;i){int ta[id[i]].t,da[id[i]].d,la[id[i]].l;if(tdnow){ //不符合flag0;break;} else{if(tnow) nowtl;else nowl;}}if(flag){coutYESendl;return;}}while(next_permutation(id1,id1n)); coutNOendl;
}signed main() {
// IOS;int T1;cinT;while(T--) {solve();}return 0;
}5 接龙数列
可以将问题转化为求最长的符合要求的接龙序列然后用总个数减去最长的接龙序列的长度。这就需要dp来解决了
#includebits/stdc.h
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
const int N 1e510, INF 0x3f3f3f3f;
int n,num0;
int x,dp[N];
//dp[i]表示以i为结尾的最长接龙序列的长度 void solve(){cinn;string s;for(int i0;in;i){cins;int xs[0]-0,ys[s.size()-1]-0; //取出第一位和最后一位 dp[y]max(dp[y],dp[x]1);nummax(num,dp[y]);}coutn-num;
}signed main() {
// IOS;int T1;
// cinT;while(T--) {solve();}return 0;
}6 岛屿个数
连通块图的遍历问题可以将所有的连通块染色每一种颜色代表一个连通块。然后检查所有的岛屿是不是子岛屿即该岛屿是否在“环”的内部如何判断是否在环的内部呢如果该岛屿内的任意一个点可以走到边界或边界之外说明该岛屿不在环内可以把其它的岛屿看作障碍物如果在环内则不可能到达边界点判断是否为子岛屿时需要沿着8个方向走
#includebits/stdc.h
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
#define fi first
#define se second
typedef pairint,int PII;
const int N 1e310, INF 0x3f3f3f3f;
char g[N][N];
int m,n,cnt,ans;
int c[N][N];
int dx[]{0,1,0,-1,-1,1,1,-1};
int dy[]{1,0,-1,0,1,1,-1,-1};
setint s;void bfs(int sx,int sy){cnt; //该连通块染色为cntqueuePII q;q.push({sx,sy});while(q.size()){auto tq.front(); q.pop();c[t.fi][t.se]cnt;for(int i0;i4;i){int txt.fidx[i];int tyt.sedy[i];if(tx0||txm||ty0||tyn) continue;if(c[tx][ty]||g[tx][ty]0) continue;q.push({tx,ty});}}
}bool vis[N][N],flag;
//判断是否在环内
bool check(int x,int y,int col){if(flag) return true;for(int i0;i8;i){int txxdx[i];int tyydy[i];if(c[tx][ty]!colc[tx][ty]) continue;
// if(col3) couttx ty flagendl;if(tx1||ty1||txm||tyn){ //到达边界不在环内flag1;return true;}if(vis[tx][ty]) continue; //已访问过vis[tx][ty]1;if(check(tx,ty,col)) return true;}return false; //在环内
}void solve() {cinmn;for(int i1;im;i)for(int j1;jn;j)cing[i][j];cnt0; ans0; s.clear(); //多组样例注意清空!memset(c,0,sizeof(c));for(int i1;im;i)for(int j1;jn;j){if(!c[i][j]g[i][j]1){bfs(i,j);}}
// coutendl;
// for(int i1;im;i){
// for(int j1;jn;j)
// coutc[i][j];
// coutendl;
// }setint s; //set去重for(int i1;im;i)for(int j1;jn;j){
// couti j c[i][j]endl;if(g[i][j]1!s.count(c[i][j])check(i,j,c[i][j])){s.insert(c[i][j]);}memset(vis,0,sizeof(vis)); flag0;}couts.size()endl;
}signed main() {
// IOS;int T1;cinT;while(T--) {solve();}return 0;
}7 子串简写
我们可以记录两个字符a,b的所有位置然后枚举第一个字符a二分找到第一个符合要求的字符b的位置之后所有的字符b都是符合要求的累加所有答案即可复杂度为O(n log(n))
#includebits/stdc.h
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
#define lb lower_bound
typedef pairint,int PII;
const int N 2e510, INF 0x3f3f3f3f;
int k,ans;
string s;
setint s1;
vectorint a;
char c1,c2;void solve() {
// freopen(in.txt,r,stdin); cinksc1c2;for(int i0;is.size();i){if(s[i]c1) s1.insert(i); //保存所有位置if(s[i]c2) a.push_back(i);}for(auto i:s1){int cntlb(a.begin(),a.end(),ik-1)-a.begin(); //二分查找ansa.size()-cnt;}
// freopen(out.txt,w,stdout); coutans;
}signed main() {
// IOS;int T1;
// cinT;while(T--) {solve();}return 0;
}8 整数删除
优先队列链表每次取出数列中的最小值可以用优先队列实现。删除和相邻两数加上被删除的值这两个操作用链表来实现。代码见蓝桥发题解的大佬
9 景区导游
不会T_T用LCA来求解
10 砍树
树上差分模板题
