1.
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,k,x; long long mul(long long x,long long y,long long mod) { if(y==0) return 0; if(y==1) return x%mod; long long res; res=mul(x,y>>1,mod); if((y&1)!=0) return(res+res+x)%mod; else return(res+res)%mod; } long long powermod(long long a,long long b,long long mod) { long long base=a,res=1; while(b!=0) { if(b&1!=0) res=mul(res,base,mod); base=mul(base,base,mod); b>>=1; } return res; } int main() { freopen("circle.in","r",stdin); freopen("circle.out","w",stdout); scanf("%d%d%d%d",&n,&m,&k,&x); int ans=(x+mul(m,powermod(10,k,n),n))%n; printf("%d\n",ans); return 0; }2.
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 100010 #define MOD 99999997 struct node { int v,t; }a[MAXN],b[MAXN]; short int cmp(node x,node y) { return x.v<y.v; } int n,c[MAXN],ans=0; int t[MAXN]; int lowbit(int x) {return x&(-x);} void Add(int x) { for(int i=x;i<=n;i+=lowbit(i)) ++t[i]; } int Sum(int x) { int rec=0; for( ;x;x-=lowbit(x)) rec+=t[x]; return rec; } int main() { freopen("match.in","r",stdin); freopen("match.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;++i) {scanf("%d",&a[i].v);a[i].t=i;} for(int i=1;i<=n;++i) {scanf("%d",&b[i].v);b[i].t=i;} sort(a+1,a+n+1,cmp); sort(b+1,b+n+1,cmp); for(int i=1;i<=n;++i) c[a[i].t]=b[i].t; for(int i=n;i>=1;i--) { ans+=Sum(c[i]); Add(c[i]); ans%=MOD; } printf("%d\n",ans); return 0; }3. 30分做法
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define inf 0x7fffffff #define N 10010 #define M 500010 int n,m,q,ne; int head[N]; struct data { int to,next,v; }e[M*2]; void add(int u,int v,int w) { ne++, e[ne].to=v, e[ne].v=w, e[ne].next=head[u], head[u]=ne; } void spfa(int x,int y) { int q[N],dis[N],t=0,w=1; int now,i; short int vis[N]; memset(vis,0,sizeof(vis)); memset(dis,-1,sizeof(dis)); q[0]=x, vis[x]=1, dis[x]=inf; while(t!=w) { now=q[t],t++; if(t==n) t=0; i=head[now]; while(i) { if(dis[e[i].to]<min(dis[now],e[i].v)) { dis[e[i].to]=min(dis[now],e[i].v); if(!vis[e[i].to]) { vis[e[i].to]=1, q[w]=e[i].to, w++; if(w==n) w=0; } } i=e[i].next; } vis[now]=0; } printf("%d\n",dis[y]); } int main() { freopen("truck.in","r",stdin); freopen("truck.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } scanf("%d",&q); while(q--) { int x,y; scanf("%d%d",&x,&y); spfa(x,y); } return 0; }60分做法
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define inf 0x7fffffff #define N 10010 #define M 500010 int n,m,q,ne; int head[N],father[N]; struct data1 { int x,y,v; }ed[M]; struct data2 { int to,next,v; }e[M*2]; int find(int x) {return x==father[x]?father[x]:father[x]=find(father[x]);} short int cmp(data1 a,data1 b) {return a.v>b.v;} void add(int u,int v,int w) { ne++, e[ne].to=v, e[ne].v=w, e[ne].next=head[u], head[u]=ne; } void spfa(int x,int y) { int q[N],dis[N],t=0,w=1; int now,i; short int vis[N]; memset(vis,0,sizeof(vis)); memset(dis,-1,sizeof(dis)); q[0]=x; vis[x]=1; dis[x]=inf; while(t!=w) { now=q[t],t++; if(t==n) t=0; i=head[now]; while(i) { if(dis[e[i].to]<min(dis[now],e[i].v)) { dis[e[i].to]=min(dis[now],e[i].v); if(!vis[e[i].to]) { vis[e[i].to]=1, q[w]=e[i].to, w++; if(w==n) w=0; } } i=e[i].next; } vis[now]=0; } printf("%d\n",dis[y]); } int main() { freopen("truck.in","r",stdin); freopen("truck.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) {scanf("%d%d%d",&ed[i].x,&ed[i].y,&ed[i].v);} sort(ed+1,ed+m+1,cmp); for(int i=1;i<=n;++i) father[i]=i; for(int i=1;i<=m;++i) { int x=ed[i].x,y=ed[i].y,v=ed[i].v; if(find(x)!=find(y)) { father[find(x)]=find(y); add(x,y,v);add(y,x,v); } } scanf("%d",&q); for(int i=1;i<=q;++i) { int x,y; scanf("%d%d",&x,&y); spfa(x,y); } return 0; }AC
#include<algorithm> #include<cstdio> #include<cstring> using namespace std; #define inf 0x7fffffff #define N 10010 #define M 50010 int n,m,q,cnt,tot,deep[N],head[N],f[N],fa[N][17],d[N][17]; short int vis[N]; struct edge { int x,y,v; }a[M]; struct e { int next,to,v; }e[M*2]; int find(int x) {return f[x]==x?x:f[x]=find(f[x]);} bool cmp(edge a,edge b) {return a.v>b.v;} void add(int u,int v,int w) { e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt; e[cnt].v=w; } void dfs(int x) { vis[x]=1; for(int i=1;i<=16;++i) { if(deep[x]<(1<<i)) break; fa[x][i]=fa[fa[x][i-1]][i-1]; d[x][i]=min(d[x][i-1],d[fa[x][i-1]][i-1]); } for(int i=head[x];i;i=e[i].next) { if(vis[e[i].to]) continue; fa[e[i].to][0]=x; d[e[i].to][0]=e[i].v; deep[e[i].to]=deep[x]+1; dfs(e[i].to); } } int lca(int x,int y) { if(deep[x]<deep[y])swap(x,y); int t=deep[x]-deep[y]; for(int i=0;i<=16;++i) if((1<<i)&t) x=fa[x][i]; for(int i=16;i>=0;i--) { if(fa[x][i]!=fa[y][i]) {x=fa[x][i];y=fa[y][i];} } if(x==y)return x; return fa[x][0]; } int ask(int x,int f) { int ans=inf; int t=deep[x]-deep[f]; for(int i=0;i<=16;++i) { if(t&(1<<i)) { ans=min(ans,d[x][i]); x=fa[x][i]; } } return ans; } int main() { freopen("truck.in","r",stdin); freopen("truck.out","w",stdout); memset(d,inf,sizeof(d)); scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) f[i]=i; for(int i=1;i<=m;++i) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v); sort(a+1,a+m+1,cmp); for(int i=1;i<=m;++i) { int x=a[i].x,y=a[i].y; int p=find(a[i].x),q=find(a[i].y); if(p!=q) { f[p]=q; add(x,y,a[i].v); add(y,x,a[i].v); tot++; if(tot==n-1) break; } } for(int i=1;i<=n;++i) if(!vis[i]) dfs(i); for(scanf("%d",&q);q;--q) { int x,y; scanf("%d%d",&x,&y); if(find(x)!=find(y)) {printf("-1\n");continue;} else { int t=lca(x,y); printf("%d\n",min(ask(x,t),ask(y,t))); } } return 0; }4.
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,x1=0,x2=0; long long ans=0; int main() { freopen("block.in","r",stdin); freopen("block.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d",&x1); if(x1>x2) ans+=x1-x2; x2=x1; } printf("%I64d\n",ans); return 0; }5.
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 1000005 int n,a[N],ans; int main() { freopen("flower.in","r",stdin); freopen("flower.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]); short int flag=0;ans=1; for(int i=1;i<=n-1;++i) { if(a[i+1]>=a[i]&&flag!=1) flag=1,ans++; if(a[i+1]<=a[i]&&flag!=2) flag=2,ans++; } printf("%d\n",ans); return 0; }6. 60分做法
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m,p; short int mp[31][31]; short int mark[31][31][31][31]; int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; struct data { int x,y,kx,ky; int step; }q[810001]; bool jud(int x,int y,int kx,int ky) { if(x<1||y<1||x>n||y>m||!mp[x][y]||!mp[kx][ky])return 0; if(mark[x][y][kx][ky])return 0; mark[x][y][kx][ky]=1; return 1; } void search() { memset(mark,0,sizeof(mark)); int t=0,w=0; int ex,ey,x,y,kx,ky; scanf("%d%d%d%d%d%d",&q[0].kx,&q[0].ky,&q[0].x,&q[0].y,&ex,&ey); if(ex==q[0].x&&ey==q[0].y){printf("0\n");return;} mark[q[0].x][q[0].y][q[0].kx][q[0].ky]=1; while(t<=w) { for(int i=0;i<4;++i) { x=q[t].x,y=q[t].y; kx=q[t].kx+xx[i],ky=q[t].ky+yy[i]; if(x==kx&&y==ky){x=q[t].kx;y=q[t].ky;} if(jud(x,y,kx,ky)) { w++; q[w].x=x;q[w].y=y; q[w].kx=kx;q[w].ky=ky; q[w].step=q[t].step+1; if(x==ex&&y==ey){printf("%d\n",q[w].step);return;} } } t++; } printf("-1\n"); return; } int main() { freopen("puzzle.in","r",stdin); freopen("puzzle.out","w",stdout); scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&mp[i][j]); for(int i=1;i<=p;++i) { search(); } return 0; }