轉圈游戲

傳送門

Solution

快速冪

Code

//By Menteur_Hxy #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define F(i,a,b) for(register int i=(a);i<=(b);i++) using namespace std; typedef long long LL;LL read() {LL x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; }LL n,m,k,ans;LL qpow(LL a,LL b,LL MOD) {LL res=1;while(b) {if(b&1) res=res*a%MOD;a=a*a%MOD; b>>=1;}return res; }int main() {n=read(),m=read(),k=read(),ans=read();(ans+=m*qpow(10,k,n)%n)%=n;printf("%lld\n",ans);return 0; }

火柴排隊

傳送門

Solution

建立映射關系，求逆序對個數

Code

//By Menteur_Hxy #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define F(i,a,b) for(register int i=(a);i<=(b);i++) #define R(i,a,b) for(register int i=(b);i>=(a);i--) using namespace std; typedef long long LL;LL read() {LL x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; }const LL N=100010,MOD=99999997; int n; int to[N],C[N]; LL ans; struct Dat{LL id,da;}A[N],B[N];struct BIT{LL da[N];BIT() {memset(da,0,sizeof(da));}void upd(int x,int k) {for(;x<=N;x+=(x&-x)) da[x]+=k;}LL qry(int x) {LL res=0;for(;x>0;x-=(x&-x)) res+=da[x];return res;} }T;bool cmp(Dat a,Dat b) {return a.da<b.da;}int main() {n=read();F(i,1,n) A[i].id=i,A[i].da=read();F(i,1,n) B[i].id=i,B[i].da=read();sort(A+1,A+1+n,cmp);sort(B+1,B+1+n,cmp);F(i,1,n) C[B[i].id]=A[i].id;R(i,1,n) {ans+=T.qry(C[i]-1);T.upd(C[i],1);}printf("%lld",ans%MOD);//忘%wa一次QAQreturn 0; }

貨車運輸

傳送門

Solution

建最大生成樹，對詢問找lca，暴力

Code

//By Menteur_Hxy #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define F(i,a,b) for(register int i=(a);i<=(b);i++) #define R(i,a,b) for(register int i=(b);i>=(a);i--) #define E(i,u) for(register int i=head[u],v;i;i=T[i].nxt) using namespace std; typedef long long LL;LL read() {LL x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; }const int N=10010,M=50010,INF=0x3f3f3f3f; int n,m,q,cnt; int fa[N],f[N][33],dis[N],head[N],dep[N],vis[N]; struct Edg{int fr,to,cst,nxt;}E[M],T[N<<1];bool cmp(Edg a,Edg b) {return a.cst>b.cst;} int getf(int x) {return fa[x]==x?x:fa[x]=getf(fa[x]);}void dfs(int u,int pre) {vis[u]=1;E(i,u) if((v=T[i].to)!=pre) {//T,E不分QAQdep[v]=dep[u]+1;f[v][0]=u;dis[v]=T[i].cst;dfs(v,u);} }int getm(int x,int lca) {int res=INF;while(x!=lca) {res=min(res,dis[x]);x=f[x][0];}return res; }int lca(int x,int y) { int l=x,r=y;if(dep[x]<dep[y]) swap(x,y);int nd=dep[x]-dep[y];for(int i=0;nd;nd>>=1,i++) if(nd&1) x=f[x][i];if(x!=y) {R(i,0,32) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];x=f[x][0];}return min(getm(l,x),getm(r,x)); }int main() {n=read(),m=read();F(i,1,m) {int a=read(),b=read(),c=read();E[i]=(Edg){a,b,c};}sort(E+1,E+1+m,cmp);F(i,1,n) fa[i]=i;F(i,1,m) {int fu=getf(E[i].fr),fv=getf(E[i].to);if(fu==fv) continue; fa[fu]=fv;int a=E[i].fr,b=E[i].to,c=E[i].cst;T[++cnt]=(Edg){a,b,c,head[a]}; head[a]=cnt;T[++cnt]=(Edg){b,a,c,head[b]}; head[b]=cnt;if(cnt==((n-1)<<1)) break;}F(i,1,n) if(!vis[i]) dfs(i,0);//可能有多棵樹for(register int j=1;(1<<j)<=n;j++) F(i,1,n) if(f[i][j-1]) f[i][j]=f[f[i][j-1]][j-1];q=read();while(q--) {int x=read(),y=read();if(getf(x)!=getf(y)) puts("-1");else printf("%d\n",lca(x,y));}return 0; }

積木大賽

傳送門

Solution

顯然是差分后把正值加起來

Code

//By Menteur_Hxy #include <vector> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define F(i,a,b) for(register int i=(a);i<=(b);i++) #define R(i,a,b) for(register int i=(b);i>=(a);i--) using namespace std; typedef long long LL;int read() {int x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; }const int N=100010; int n; int da[N]; LL ans;int main() {n=read();F(i,1,n) da[i]=read();R(i,1,n) da[i]=da[i]-da[i-1];F(i,1,n) if(da[i]>0) ans+=da[i];printf("%lld",ans);return 0; }

花匠

傳送門

Solution

分(xian)析(ran)可知第一個數一定要有
分別討論第一個數是波峰還是波谷

Code

//By Menteur_Hxy #include <vector> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define F(i,a,b) for(register int i=(a);i<=(b);i++) #define R(i,a,b) for(register int i=(b);i>=(a);i--) using namespace std; typedef long long LL; typedef pair<int,int> PII;int read() {int x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; }const int N=100010; int n,opt,t1,t2; int da[N];int main() {n=read();F(i,1,n) da[i]=read();F(i,1,n) {if(da[i]>da[i-1]&&opt==0) t1++,opt=1;else if(da[i]<da[i-1]&&opt==1) t1++,opt=0;}opt=0;da[0]=da[1]+1;F(i,1,n) {if(da[i]>da[i-1]&&opt==1) t2++,opt=0;else if(da[i]<da[i-1]&&opt==0) t2++,opt=1;}printf("%d",max(t1,t2));return 0; }

華容道

傳送門

Solution

60-80分:bfs
正解回頭再說

Code

60-80分

//By Menteur_Hxy #include <queue> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define F(i,a,b) for(register int i=(a);i<=(b);i++) using namespace std;int read() {int x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; }const int N=40; int mv[5]={0,1,0,-1,0}; int n,m,q,ex,ey,sx,sy,tx,ty,ans,now; int vis[N][N][N][N]; bool map[N][N]; struct P{int x0,y0,x1,y1,dep;P(int a0=0,int b0=0,int a1=0,int b1=0,int deep=0) {x0=a0,y0=b0,x1=a1,y1=b1,dep=deep;} }; queue <P> Q;void bfs() {while(!Q.empty()) Q.pop();Q.push(P(ex,ey,sx,sy,0)); while(!Q.empty()) {P u=Q.front(); Q.pop();if(vis[u.x0][u.y0][u.x1][u.y1]==now) continue;vis[u.x0][u.y0][u.x1][u.y1]=now;// cout<<u.x0<<" "<<u.y0<<" "<<u.x1<<" "<<u.y1<<" "<<u.dep<<endl;if(u.x1==tx&&u.y1==ty) {ans=u.dep;return ;}if(u.x0==u.x1&&abs(u.y1-u.y0)==1) Q.push(P(u.x1,u.y1,u.x0,u.y0,u.dep+1));if(u.y0==u.y1&&abs(u.x1-u.x0)==1)Q.push(P(u.x1,u.y1,u.x0,u.y0,u.dep+1));F(i,0,3) {int x=u.x0+mv[i],y=u.y0+mv[i+1];if(!map[x][y]||(x==u.x1&&y==u.y1)) continue;Q.push(P(x,y,u.x1,u.y1,u.dep+1));}} }int main() {n=read(),m=read(),q=read();F(i,1,n) F(j,1,m) map[i][j]=read();for(now=1;now<=q;now++) {scanf("%d %d %d %d %d %d",&ex,&ey,&sx,&sy,&tx,&ty);// printf("%d %d %d %d %d %d\n",ex,ey,sx,sy,tx,ty);ans=-1; bfs();printf("%d\n",ans);}return 0; }

轉載于:https://www.cnblogs.com/Menteur-Hxy/p/9502496.html

總結

以上是生活随笔為你收集整理的Noip 2013 练习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。