T1 【NOIP2008模拟】遨游
Solution
由于要求L最大，那么就仿照最大生成树（保证L值最大）的思想，找到L的值
在上述找到L值的过程中，其实很多都没必要走
于是就在最大生成树基础上（既保证L值不变）仿照最小生成树（保证联通性）找到R即可
Code
//By Menteur_Hxy
#include<cmath>
#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;
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]=c
int 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 【NOIP2008模拟】今天你AK了吗？
Solution
60分轻易到手
100分玄学高精
Code
60分：
//By Menteur_Hxy
#include<cmath>
#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;
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<<tp<<endl;
int cnt=0;
F(l,1,n) {
if(!vis[l]) {
cnt++;
if(cnt==j) {
printf("%d ",l),vis[l]=1;
k-=(j-1)*fac[n-i];
flag=1;
break;
}
}
}
}
tp+=fac[n-i];
}
}
F(i,1,n) if(!vis[i]) return printf("%d",i),0;
return 0;
}
100分:
压位高精qwq
//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++)
#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<kth[i];j++) if(!vis[j]) ++cnt;
vis[--j]=1; printf("%d ",j);
}
return 0;
}
T3 【NOIP2008模拟】简单数学题
Solution
(T=N-frac{N}{2k-1}) 2k-1为大于1的所有单数
Code
//By Menteur_Hxy
#include<cmath>
#include<ctime>
#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;
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("
%lf",time2-time1);
return 0;
}