T1 质因数分解
#include#include #include #include #define LL long long using namespace std;LL read(){ LL ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f;}LL n;LL find(LL n){ int x=2; while(x<=n&&n%x) x++; return x;}int main(){ n=read(); printf("%lld\n",n/find(n)); return 0;}
T2 寻宝
#include#include int a[10005][105],k[10005][105],c[10005];int main(){ int i,j,n,m,sum=0,go,ha,s; scanf("%d %d",&n,&m); for(i=1;i<=n;i++) for(j=0;j<=m-1;j++) { scanf("%d %d",&a[i][j],&k[i][j]); if(a[i][j]==1) c[i]++; } scanf("%d",&go); for(i=1;i<=n;i++) { sum=(sum+k[i][go])%20123; s=(k[i][go]-1)%c[i]+1; if(a[i][go]==1) ha=1; else ha=0; while(ha
T3 摆花
#include#include #include using namespace std;const int M=1007,mod=1000007;int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f;}int n,m,f[M][M],w[M];int main(){ n=read(); m=read(); for(int i=1;i<=n;i++) w[i]=read(); for(int i=0;i<=n;i++) f[i][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ f[i][j]=f[i-1][j]+f[i][j-1]; if(j-w[i]) f[i][j]-=f[i-1][j-w[i]-1]; f[i][j]=(f[i][j]+mod)%mod; } printf("%d\n",f[n][m]); return 0;}
T4 文化之旅
这道题还是有点需要说的 我写的是A* 先一波spfa预处理如果没有限制需要的路程
然后在有限制的跑一波dfs就好了
#include#include #include #define LL long longusing namespace std;const int M=155,inf=0x3f3f3f3f;int read(){ LL ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f;}int n,k,m,S,T,ans=inf,cnt;int w[M],d[M][M],map[M][M],dis[M],q[M],vis[M],usd[M];void spfa(){ memset(dis,0x3f,sizeof(dis)); int head=0,tail=1; q[0]=T; vis[T]=1; dis[T]=0; while(head!=tail){ int x=q[head++]; vis[x]=0;if(head>M) head=0; for(int now=1;now<=n;now++){ if(dis[now]>dis[x]+d[now][x]){ dis[now]=dis[x]+d[now][x]; if(!vis[now]){q[tail++]=now; vis[now]=1; if(tail>M) tail=0;} } } }}int check(int x){ for(int i=1;i<=cnt;i++) if(map[w[x]][usd[i]]||usd[i]==w[x]) return 0; return 1;}void dfs(int x,int h){ if(x==T){ans=min(ans,h); return ;} for(int now=1;now<=n;now++){ if(vis[now]||h+dis[now]>=ans||!check(now)) continue; vis[now]=1; usd[++cnt]=w[now]; dfs(now,h+d[x][now]); cnt--; vis[now]=0; }}int main(){ int x,y,v; memset(d,0x3f,sizeof(d)); n=read(); k=read(); m=read(); S=read(); T=read(); for(int i=1;i<=n;i++) w[i]=read(); for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) map[i][j]=read(); for(int i=1;i<=m;i++){ x=read(); y=read(); v=read(); if(!map[w[x]][w[y]]) d[y][x]=min(d[y][x],v); if(!map[w[y]][w[x]]) d[x][y]=min(d[x][y],v); } spfa(); vis[S]=1; usd[++cnt]=w[S]; dfs(S,0); if(ans