1.被污染的支票#include #include #include #include using namespace std;int main(){int n;cin>>n;vectorL;mapmp;bool ok=0;int num;for(int i=1;i>num;if(mp[num]==1)ok=1;else{mp[num]=1;L.push_back(num);}}sort(L.begin(),L.end());int x=L.back()*2;//" /> #include #include #include using namespace std;int main(){int ans=0;int num[100]={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 days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};for(int mon=1;mon<=12;mon++){for(int day=1;day<=days[mon];day++){int temp[8]={2,0,2,3,mon/10,mon%10,day/10,day%10};int k=0;for(int i=0;i<100;i++){if(num[i]==temp[k]){k++;}if(k==8){ans++;break;}}}}cout<3.01串的熵#include #include using namespace std;int main(){int n=23333333;for(int i=0;i<=n/2;i++)//0的次数{double a=(i*1.0)/n;double b=((n-i)*1.0)/n;double ans=0;ans-=(a*log2(a)*i+b*log2(b)*(n-i));if(fabs(ans-11625907.5798)<0.0001){cout<<i<<endl;break;}}return 0;}（注意浮点数，double，以及比较大小时使用1e-4）4.冶炼金属#include using namespace std;#define ll long longint main(){ll n,a,b,minn,maxx;maxx=1e9;//要满足最小的minn=0;//要满足最大的cin>>n;for(ll i=0;i>a>>b;minn=max(minn,a/(b+1)+1);maxx=min(maxx,a/b);}cout<<minn<<" "<<maxx;return 0;}//二分#include using namespace std;int a[10000+5];int v[10000+5];int n;bool check_min(int x){for(int i=1;iv[i])return false;}return true;}bool check_max(int x){for(int i=1;i<=n;i++){if(a[i]/x>n;for(int i=1;i>a[i]>>v[i];}int L=1,R=1000000000,minn=0;while(L>1;if(check_min(mid)){minn=mid;R=mid-1;}else L=mid+1;}int maxx=0;L=1,R=1000000000;while(L>1;if(check_max(mid)){maxx=mid;L=mid+1;}else R=mid-1;}cout<<minn<<" "<<maxx<<endl;return 0;}5.飞机降落#include #include #include using namespace std;struct node{int t,d,l;};bool ok=0;vectorv;vectorvis;int n;void dfs(int cnt,int last){if(cnt==n){ok=1;return;}for(int i=0;i=last)//可以降落{vis[i]=1;dfs(cnt+1,max(last,v[i].t)+v[i].l);vis[i]=0;//恢复}}}int main(){int t;cin>>t;while(t--){cin>>n;v.clear();vis.clear();for(int i=1;i>x>>y>>z;v.push_back({x,y,z});vis.push_back(0);}ok=0;dfs(0,0);//0架飞机，0需要时间if(!ok)cout<<"NO"<<endl;else cout<<"YES"<<endl;}return 0;}6.接龙数列这道题其实本质就是求解出数列中最长的接龙数列，计算出最长的接龙数列长度，数列总长度-最长接龙数列长度等于最少删除次数。这就是一个求最优解的问题，然而看到这道题的数据量可以发现，暴力求解一定会超时，因此考虑动态规划。 动态规划最重要的就是状态转移方程，而这个题目就可以定义状态为当前最长接龙数列长度，则dp[i]就是以i为数字最后一位的最长接龙数列长度，设x为当前数字的第一位(如果为接龙数列，也就是前一位数的最后一位)，y为当前数字的最后一位，则转移方程可以写为dp[y]=max(dp[x]+1,dp[y])#include using namespace std;int f[10];//表示在i=0-9中,f[i]为以i数字为连接的最长接龙数列的长度int main(){int n;cin>>n;int ans=0;string s;for(int i=0;i>s;int pre=s[0]-'0',nex=s[s.size()-1]-'0';f[nex]=max(f[nex],f[pre]+1);ans=max(ans,f[nex]);}cout<<n-ans<<endl;//总的-最长长度=删去的return 0;}7.岛屿个数搜索出所有岛屿，这个不难做到。由于岛屿之间互相隔离，则如果岛屿的一个格子在一个环内，那么整个岛屿也都在环内。遍历所有的岛屿，选中当前岛屿的第一个格子，搜索周围海洋，若能搜索到地图的边界外，则此岛屿不在任何一个环内；否则，此岛屿在某个环内，岛屿数量减一。#include #include #include #include using namespace std;#define pii pairconst int N=100;int n,m,ans;vector<vector>vis;string s[N];int dx[8]={-1,1,0,0,-1,1,-1,1};int dy[8]={0,0,-1,1,-1,1,1,-1};bool inmap(int x,int y){if(xn||ym)return 0;return 1;}//bfs统计岛屿的情况void bfs(int x,int y){vis[x][y]=1;queueq;q.push({x,y});while(!q.empty()){auto t=q.front();q.pop();for(int i=0;i<4;i++){int xx=t.first+dx[i];int yy=t.second+dy[i];if(!inmap(xx,yy)||vis[xx][yy]||s[xx][yy]!='1')continue;vis[xx][yy]=1;q.push({xx,yy});}}}bool check(int x,int y)//是否不在环内，即周围是海洋（用是否到边界判断）{vector<vector>fin(n+1,vector(m+1,0));fin[x][y]=1;queueq;q.push({x,y});while(!q.empty()){auto t=q.front();q.pop();//到达边界，证明不在环中if(t.first==1||t.first==n||t.second==1||t.second==m)return 1;for(int i=0;i>t;while(t--){ans=0;cin>>n>>m;for(int i=1;i>s[i];s[i]='2'+s[i];}vis=vector<vector>(n+1,vector(m+1,0));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(!vis[i][j]&&s[i][j]=='1'){bfs(i,j);if(check(i,j))ans++;}}}cout<8.子串简写#include using namespace std;int main(){int k;//最小可以简写的长度cin>>k;string s;char st,ed;cin>>s>>st>>ed;long long ans=0;int st_num=0;for(int i=0,j=k-1;j<s.size();i++,j++){if(s[i]==st)st_num++;if(s[j]==ed)ans+=st_num;}cout<（注意规律，开long long）9.整数删除#includeusing namespace std;//优先队列+双向链表const int N=5e5+10;#define ll long long#define val first#define pos second#define pli pairint n,k;ll a[N],pre[N],nxt[N];priority_queue<pli,vector,greater>q;//小根堆int main(){cin>>n>>k;for(int i=1;i>a[i];q.push({a[i],i});pre[i]=i-1;nxt[i]=i+1;}pre[1]=-1;nxt[n]=-1;while(k--){pli now;do{now=q.top();q.pop();}while(a[now.pos]!=now.val);//保证弹出同一个int PRE=pre[now.pos];int NXT=nxt[now.pos];if(PRE!=-1){a[PRE]+=now.val;q.push({a[PRE],PRE});nxt[PRE]=NXT;}if(NXT!=-1){a[NXT]+=now.val;q.push({a[NXT],NXT});pre[NXT]=PRE;}a[now.pos]=-1;}for(int i=1;i<=n;i++){if(a[i]!=-1)cout<10.景区导游//最近公共祖先。倍增做法 (深搜)#include #include #define ll long longusing namespace std;const int N=1e5+10;vectore[N],w[N];int n,k;ll dep[N],fa[N][20],dist[N],b[N];void dfs(int u,int father){fa[u][0]=father;dep[u]=dep[father]+1;for(int i=1;i<20;i++){fa[u][i]=fa[fa[u][i-1]][i-1];}for(int i=0;i<e[u].size();i++){int v=e[u][i];int t=w[u][i];if(v!=father){dist[v]=dist[u]+t;dfs(v,u);}}}int lca(int u,int v){if(dep[u]=0;i--){if(dep[fa[u][i]]>=dep[v])u=fa[u][i];}if(u==v) return v;for(int i=19;i>=0;i--){if(fa[u][i]!=fa[v][i]){u=fa[u][i],v=fa[v][i];}}return fa[u][0];}ll sol(int x,int y){if(!x||!y) return 0;return dist[x]+dist[y]-2*dist[lca(x,y)];}int main(){cin>>n>>k;for(int i=1;i>x>>y>>t;e[x].push_back(y);e[y].push_back(x);w[x].push_back(t);w[y].push_back(t);}dfs(1,0);ll Dis=0;for(int i=1;i>b[i];Dis+=sol(b[i],b[i-1]);}for(int i=1;i<=k;i++){cout<<Dis-sol(b[i-1],b[i])-sol(b[i],b[i+1])+sol(b[i-1],b[i+1])<<" ";}return 0;}11.砍树#include #include using namespace std;const int N=1e5+10;vectore[N],num[N];int n,m,dep[N],fa[N][21],s[N],ans;void dfs(int u,int Fa){dep[u]=dep[Fa]+1;fa[u][0]=Fa;for(int i=1;i<=20;i++){fa[u][i]=fa[fa[u][i-1]][i-1];}for(auto &v:e[u]){if(v==Fa)continue;dfs(v,u);}}int LCA(int u,int v){if(dep[u]=0;i--){if(dep[fa[u][i]]>=dep[v]){u=fa[u][i];}}if(u==v)return u;for(int i=20;i>=0;i--){if(fa[u][i]!=fa[v][i]){u=fa[u][i];v=fa[v][i];}}return fa[u][0];}void dfs2(int u,int Fa){for(int i=0;i>n>>m;for(int i=1;i>x>>y;e[x].push_back(y);e[y].push_back(x);num[x].push_back(i);num[y].push_back(i);}dfs(1,0);for(int i=1;i>a>>b;s[a]++;s[b]++;s[LCA(a,b)]-=2;}dfs2(1,0);cout<
