circle

#include<cstdio> long long k,n,m,x; long long KSM(long long b,long long ans=1){ for(long long k=10%n;b>0;b>>=1,k=(k*k)%n)if(b&1)ans=(ans*k)%n; return ans; } int main(){ freopen("circle.in","r",stdin); freopen("circle.out","w",stdout); scanf("%I64d%I64d%I64d%I64d",&n,&m,&k,&x); printf("%I64d",((KSM(k)*m)%n+x)%n); return 0; }

match

#include<cstdio> #include<algorithm> struct data{ int v,id; bool operator < (const data &rhs)const{ return v<rhs.v; } }x[100005],y[100005]; int rk[100005],c[100005],n,ans,ret; void add(int x){ for(;x<=n;x+=(x&(-x)))++c[x]; } void sum(int x){ for(ret=0;x;x-=(x&(-x)))ret+=c[x]; } inline int read(){ static char ch;register int res; while((ch=getchar())<'0'||ch>'9');res=ch-48; while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)-48+ch; return res; } int main(){ freopen("match.in","r",stdin);n=read(); freopen("match.out","w",stdout); for(register int i=1;i<=n;++i)x[i].v=read(),x[i].id=i;std::sort(x+1,x+1+n); for(register int i=1;i<=n;++i)y[i].v=read(),y[i].id=i;std::sort(y+1,y+1+n); for(register int i=1;i<=n;++i)rk[x[i].id]=y[i].id; for(register int i=n;i>=1;--i)sum(rk[i]),add(rk[i]),ans=(ans+ret)%99999997; printf("%d",ans); return 0; }

truck

#include<cstdio> #include<vector> #include<algorithm> using namespace std; const int NN = 10005; const int QN = 30005; const int MN = 50005; const int INF = 0x3f3f3f3f; struct data{ int s,t,d; bool operator < (const data &rhs)const{ return d>rhs.d; } }e[MN]; int fa[NN],n,m,q,Q[QN][2]; int dp[NN][20],val[NN][20],h[NN]; bool f[NN]; vector<int>T[NN],D[NN]; //支持左对齐，放弃链表！ inline int find(int x){ //可维护式并查集 register int k,fx,tmp=x; for(fx=x;fa[fx];fx=fa[fx]); for(;fa[tmp];k=fa[tmp],fa[tmp]=fx,tmp=k); return fx; } inline int change(int &v,int H){ //动态实现(改变fa[]) register int ret=INF; for(register int i=19;i>=0;--i){ if(h[dp[v][i]]>=H){ ret=min(ret,val[v][i]); v=dp[v][i]; } } return ret; } void dfs(int v){ //建出生成树母图 在母图上进行修改 for(register int i=0;i<T[v].size();++i) if(!f[T[v][i]]){ dp[T[v][i]][0]=v,val[T[v][i]][0]=D[v][i],h[T[v][i]]=h[v]+1; f[T[v][i]]=1,dfs(T[v][i]); } } int query(int u,int v){//二分答案 if(find(u)!=find(v))return -1; register int ret=INF; if(h[u]!=h[v])ret=h[u]>h[v]?change(u,h[v]):change(v,h[u]); if(u==v)return ret; for(register int i=19;i>=0;--i){ if(dp[u][i]!=dp[v][i]){ ret=min(ret,min(val[u][i],val[v][i])); u=dp[u][i],v=dp[v][i]; } } ret=min(ret,min(val[u][0],val[v][0])); return ret; } inline int read(){ static char ch;register int res; while((ch=getchar())<'0'||ch>'9');res=ch-48; while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48; return res; } int main(){ freopen("truck.in","r",stdin); freopen("truck.out","w",stdout); n=read(),m=read(); for(register int i=0;i<m;++i)e[i].s=read(),e[i].t=read(),e[i].d=read();//最"大"生成树/* sort(e,e+m),q=read(); for(register int i=0;i<m;++i) if(find(e[i].s)!=find(e[i].t)){ fa[find(e[i].s)]=find(e[i].t); T[e[i].s].push_back(e[i].t),D[e[i].s].push_back(e[i].d); T[e[i].t].push_back(e[i].s),D[e[i].t].push_back(e[i].d); } //*/ for(register int i=1;i<=n;++i) if(!f[i])h[i]=0,f[i]=1,dfs(i),val[i][0]=INF,dp[i][0]=i; for(register int i=1;i<=19;++i){ for(register int j=1;j<=n;++j){ dp[j][i]=dp[dp[j][i-1]][i-1]; val[j][i]=min(val[j][i-1],val[dp[j][i-1]][i-1]); } } while(q--) printf("%d\n",query(read(),read())); return 0; }