T1
Solution
由于要求L最大,那么就仿照最大生成树(保证L值最大)的思想,找到L的值
在上述找到L值的过程中,其实很多都没必要走 于是就在最大生成树基础上(既保证L值不变)仿照最小生成树(保证联通性)找到R即可Code
//By Menteur_Hxy#include#include #include #include #include #include #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;int read() { int x=0,f=1; char c=getchar(); while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();} while(isdigit(c)) x=(x<<3)+(x<<1)+c-48,c=getchar(); return x*f;}const int N=50010,M=100010;int n,m,cnt,L,R,s,t,now;int nxt[M<<1],fr[M<<1],to[M<<1],head[N],bl[N],X[5010],fa[M<<1],id[M<<1];double cost[M<<1];bool cmp(int x,int y) {return cost[x]>cost[y];}int getf(int x) {return fa[x]==x?x:fa[x]=getf(fa[x]);}#define add(a,b,c) nxt[++cnt]=head[a],fr[cnt]=a,to[cnt]=b,cost[cnt]=cint main() { freopen("trip.in","r",stdin); freopen("trip.out","w",stdout); n=read(),m=read(); F(i,1,m) { int u=read(),v=read(),w=read(); add(u,v,w);add(v,u,w); } F(i,1,n) { int k=read(); F(j,1,k) bl[read()]=i; } F(i,1,n) X[i]=read(); s=read(),t=read(); F(i,1,m<<1) fa[i]=i; F(i,1,cnt) { id[i]=i; int u=fr[i],v=to[i]; if(bl[u]==bl[v]) cost[i]=cost[i]*X[bl[u]]/100.0; else cost[i]=cost[i]*(X[bl[u]]+X[bl[v]])/200.0; } sort(id+1,id+1+cnt,cmp); F(i,1,cnt) { int fu=getf(fr[id[i]]),fv=getf(to[id[i]]); if(fu==fv) continue; fa[fu]=fv; L=cost[id[i]]; if(getf(s)==getf(t)) {now=i;break;} } F(i,1,m<<1) fa[i]=i; R(i,1,now) { int fu=getf(fr[id[i]]),fv=getf(to[id[i]]); if(fu==fv) continue; fa[fu]=fv; R=(int)ceil(cost[id[i]]); if(getf(s)==getf(t)) break; } printf("%d %d",L,R); return 0;}
T2
Solution
60分轻易到手
100分玄学高精Code
60分:
//By Menteur_Hxy#include#include #include #include #include #include #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;}bool vis[20];LL fac[20];int main() { freopen("array.in","r",stdin); freopen("array.out","w",stdout); LL n=read(),k=read(); fac[0]=1; F(i,1,18) fac[i]=fac[i-1]*i; if(n==1) return puts("1"),0; F(i,1,n-1) { LL tp=0;bool flag=0; F(j,1,n) { if(flag) break; if(tp+fac[n-i]>=k) {// cout< <
100分:
压位高精qwq
//By Menteur_Hxy#include#include #include #include #include #include #define F(i,a,b) for(register int i=(a);i<=(b);i++)#define R(i,b,a) for(register int i=(b);i>=(a);i--)using namespace std;typedef long long LL;const int MAXW=4000,N=1e5+10;const LL MAX=1e8;int n,slen,now;LL a[4010],kth[N];char s[20010];bool vis[N];int main() { freopen("array.in","r",stdin); freopen("array.out","w",stdout); scanf("%d %s",&n,s); slen=strlen(s); now=MAXW; int tp=1; R(i,slen-1,0) { a[now]+=(s[i]-48)*tp; tp*=10; if(tp==MAX) now--,tp=1; } for(tp=MAXW;!a[tp];a[tp]=MAX-1,tp--); a[tp]--; F(i,1,n) { F(j,now,MAXW-1) { LL x=a[j]/i; a[j+1]+=MAX*(a[j]-x*i),a[j]=x; } kth[n-i+1]=a[MAXW]%i+1,a[MAXW]/=i; while(!a[now]) now++; } tp=max(0,n-6100); F(i,1,tp) printf("%d ",i); F(i,tp+1,n) { int j,cnt; for(j=tp+1,cnt=0;cnt
T3
Solution
\(T=N-\frac{N}{2k-1}\) 2k-1为大于1的所有单数
Code
//By Menteur_Hxy#include#include #include #include #include #include #include #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;}LL n,sqn,x,t1,t2,tot;LL ans[1000010];int main() { freopen("math.in","r",stdin); freopen("math.out","w",stdout); n=read();// double time1=time(0); sqn=sqrt(n); for(register int i=2;i<=sqn;i++) { x=n/i; if(x*i==n) { if(x&1ll) { t1=x-((x-1ll)>>1ll); t2=n/((t1<<1)-1); if(t2*((t1<<1)-1)==n) ans[++tot]=n-t2; } if(x!=i&&i&1ll) { t1=i-((i-1ll)>>1ll); t2=n/((t1<<1)-1); if(t2*((t1<<1)-1)==n) ans[++tot]=n-t2; } } } if(n&1&&n>2) ans[++tot]=n-1; sort(ans+1,ans+1+tot);// double time2=time(0); printf("%d ",tot); for(register int i=1;i<=tot;i++) printf("%lld ",ans[i]);// printf("\n%lf",time2-time1); return 0;}