小白月赛6-题解整理
A-典型的追击问题，较多的坑点，回游有很多种情况，注意分类
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; int main(){ double l,k,a,b; cin>>l>>k>>a>>b; printf("%.2f\n",l/b-l/a); return 0; }
B-水题，模拟就行
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; int a[1000006]; int main(){ int n; while(~scanf("%d",&n)){ for (int i=1;i<=n;i++){ scanf("%d",&a[i]); } int flag=2; int cnt=0; for (int i=1;i<n;i++){ if (flag==2){ if (a[i]<a[i+1]){ flag=1; } if (a[i]>a[i+1]){ flag=3; } continue; } if( flag==1 &&a[i]>a[i+1]){ flag=3; cnt++; continue; } if ( flag==3 && a[i]<a[i+1]){ flag=1; continue; } } printf("%d\n",cnt); } return 0; }
C-典型的树的直径问题-两遍DFS
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #define INF 1e9+7 using namespace std; const int MAXN = 2000000; const int MAXM = 2000000; int n,m; struct EDGE { int v,next,w; }edge[MAXN]; int head[MAXN],e; int q[MAXN],vis[MAXN],d[MAXN]; void init() { e=0; memset(head,-1,sizeof(head)); } void add(int u,int v,int w)//链式前向星部分 { edge[e].v=v; edge[e].w=w;//权重 edge[e].next=head[u];//下一条边 head[u]=e++;//u为节点边的头节点 } void bfs(int src) { for(int i=1;i<=n;i++)vis[i]=0,d[i]=INF; int h=0,t=0; q[t++]=src; vis[src]=1; d[src]=0; while(h<t) { int u=q[h++]; for (int i=head[u];i!=-1;i=edge[i].next) { int v = edge[i].v; int w = edge[i].w; if (d[u]+w<d[v]){ d[v]=d[u]+w; if (!vis[v]) { q[t++]=v; vis[v]=1; } } } } } int main(){ int u,v,w; char k; scanf("%d",&n); init(); for(int i=1;i<=n-1;i++) { scanf("%d%d",&u,&v); add(u,v,1); add(v,u,1); } bfs(1); int pos=-1,mx=-1; for (int i=1;i<=n;i++) if (d[i]>mx) { mx=d[i]; pos=i; } bfs(pos); mx=-1; for (int i=1;i<=n;i++) if (d[i]>mx)mx=d[i]; printf("%d\n",mx+1); return 0; }
D-水题
#include<iostream> #include<stdio.h> #include<string.h> #include<vector> #include<map> using namespace std; char a[1000006]; int pre[1000006]; int main(){ int n,m; map<char,int> p; while(~scanf("%d%d",&n,&m)){ p.clear(); scanf("%s",a); int lena=strlen(a); for (int i=0;i<lena;i++){ p[a[i]]++; pre[i+1]=p[a[i]]; } int tmp; for (int i=1;i<=m;i++){ scanf("%d",&tmp); printf("%d\n",pre[tmp]); } } return 0; }
E-很好的简单搜索
#include<iostream> #include<stdio.h> #include<string.h> #define rep(i,j,k) for(int i=j;i<=k;++i) using namespace std; int vis[1005][1005]; int dx[10]={0,0,1,-1,1,-1,1,-1}; int dy[10]={1,-1,0,0,1,-1,-1,1}; int n,m; bool dfs(int x,int y,int z){ vis[x][y]=z; int xx,yy; int cnt; for (int i=0;i<=7;i++){ xx=x; yy=y; if(i%2==0) cnt=1; for (int j=0;j<=3;j++){ xx=xx+dx[i]; yy=yy+dy[i]; // cout<<xx<<" "<<yy<<" "; if (xx<1 || yy<1 || xx>n || yy>n || vis[xx][yy]!=z){ break; } cnt++; } if (cnt>=5){ return 1; } } return 0; } int main() { while(~scanf("%d %d",&n,&m)) { memset(vis,-1,sizeof(vis)); int id=-1,x,y; rep(i,1,m) { scanf("%d %d",&x,&y); if(id==-1) { if(dfs(x,y,i%2)) id=i; } } if(id==-1) printf("UNK %d\n",m); else if(id%2) printf("HtBest %d\n",id); else printf("WHZ %d\n",id); } return 0; }
F-树状数组，把维护区间和改为维护区间乘积就行
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; int dx[10]={1,-1,1,-1,0,0,-1,1}; int dy[10]={1,-1,0,0,-1,1,1,-1}; int vis[1004][1004]; int n,m; bool dfs(int x,int y,int z){ vis[x][y]=z; int xx,yy,cnt; for (int i=0;i<=7;i++){ xx=x; yy=y; if (i%2==0){ cnt=1; } for(int j=0;j<=3;j++){ xx+=dx[i]; yy+=dy[i]; if (xx<1 || yy<1 || xx>n || yy>n || vis[xx][yy]!=z){ break; } cnt++; } if (cnt>=5){ return 1; } } return 0; } int main() { while(~scanf("%d%d",&n,&m)){ int x,y; int flag=-1; memset(vis,-1,sizeof(vis)); for (int i=1;i<=m;i++){ scanf("%d%d",&x,&y); if (flag==-1){ if (dfs(x,y,i%2)){ flag=i; } } } if (flag==-1){ printf("UNK %d\n",m); }else if (flag%2==0){ printf("WHZ %d\n",flag); }else if (flag%2==1){ printf("HtBest %d\n",flag); } } return 0; }
G-重载set内部排序就行
#include<bits/stdc++.h> using namespace std; int m,k; struct cmp { bool operator() (int a,int b) { if(abs(a-b)<=k) return false; return a<b; } }; set<int,cmp>s; int main() { scanf("%d%d",&m,&k); int x; char op[8]; while(m--) { scanf("%s%d",op,&x); if(op[0]=='a') { if(s.find(x)==s.end()) { s.insert(x); } } else if(op[0]=='d') { s.erase(x); } else { if(s.find(x)!=s.end()) printf("Yes\n"); else printf("No\n"); } } return 0; }
H-裸题最小生成树
#include<iostream> #include<string.h> #include<stdio.h> #include<algorithm> using namespace std; struct node{ int u,v,w; }a[500006]; int p[100006]; int r[100006]; int n,m; int find(int x){return p[x] == x ? x : p[x] = find(p[x]);}//不是根节点 int cmp(node x,node y) { return x.w<y.w; } int Kruskal(){ int ans=0; int num=0; for (int i=1; i<=n; i++)p[i]=i; sort(a+1,a+1+m,cmp); for (int i=1; i<=m; i++) { int x=find(a[i].u);//出发点的根节点 int y=find(a[i].v);//到达点的根节点 if (x!=y)//不是一个根节点 { ans+=a[i].w;//连接 p[x]=y;//y是x的父亲节点 num++;//建立好了n-1条边 } if (num==n-1){ break; } } return ans; } int main() { int tmp1,tmp2,tmp3; while(~scanf("%d%d",&n,&m)) { for (int i=1; i<=m; i++) { scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w); } printf("%d\n",Kruskal()); } return 0; }
I-裸的最短路问题
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #define ll long long using namespace std; const int INF = 0x3f3f3f3f; int a[1005][1005];//邻接表点 ll d[1005];//到出发点距离 int vis[10005];//是否访问过 int n,m,s,t; void Dijkstra(int st) { int minn;//最小值 int p;//边 for (int i=1; i<=n; i++)d[i]=a[st][i];//初始化 每个点到出发点的距离 vis[st]=1; d[st]=0; for (int i=1; i<=n-1; i++) { minn=INF; for (int j=1; j<=n; j++) if (!vis[j] && minn>d[j]) //如果未被访问过 并且到目前点的距离比min更小 { p=j;//更新边 minn=d[j];//更新新的距离 } //循环下来 我们找到了最小的一条边 vis[p]=1;//走过 for (int j=1; j<=n; j++) { if (!vis[j] && d[p]+a[p][j]<d[j]) d[j]=d[p]+a[p][j]; } } if (d[t]!=INF) printf("%d\n",d[t]); else printf("-1\n"); } int main() { int tmp1,tmp2,tmp3; while (~scanf("%d%d%d%d",&n,&m,&s,&t)) { memset(vis,0,sizeof(vis)); memset(a,0x3f,sizeof(a)); for (int i=0; i<m; i++) { scanf("%d%d%d",&tmp1,&tmp2,&tmp3); if (tmp3<a[tmp1][tmp2]){ a[tmp1][tmp2]=tmp3; a[tmp2][tmp1]=tmp3; } } Dijkstra(s); } return 0; }
J-一阶线性递推+逆元/矩阵快速幂
#include<iostream> #include<string.h> #include<algorithm> #include<stdio.h> #define ll long long using namespace std;; const ll mod = 1e9+7; ll pow(ll a,ll b) { ll ans = 1; while(b) { if (b&1) { ans = ans*a%mod; } a = a*a%mod; b/=2; } return ans; } int main() { ios::sync_with_stdio(0); ll n,k,p; ll ans=0; while(~scanf("%lld%lld%lld",&n,&k,&p)) { if (k==1) { ans=(n*(n-1)%mod/2*p+n)%mod; printf("%lld\n",ans); } else { ll inv=pow(k-1,mod-2); ans=(1+p*inv%mod)%mod*((pow(k,n)-1+mod)%mod)%mod*inv%mod; ans=(ans-p*inv%mod*n%mod+mod)%mod; printf("%lld\n",ans); } } return 0; }
投递兆芯等公司10个岗位 >
