今天题目略水2333
依旧不粘题目了23333
T1
/*数学题 给定n个斜率 求有多少个三元组 保证两两斜率不同 ans=C(n,3)-ΣC(len[i],2)*(n-len[i])-ΣC(len[i],3)*/ #include<iostream> #include<cstdio> #include<algorithm> #define inf 1e10 #define ll long long #define maxn 300010 using namespace std; ll n,a,b,c,ans,len[maxn],cnt; struct node{ double k; ll C; }p[maxn]; ll init(){ ll x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } ll cmp(const node &x,const node &y){ return (x.k==y.k&&x.C<y.C)||x.k<y.k; } void Insert(ll x,ll y,ll z,ll o){ double K; if(y==0)K=inf; else K=-double(x)/double(y); p[o].C=z;p[o].k=K; } ll Cu(ll x,ll y){ if(y==2)return x*(x-1)/2; if(y==3)return x*(x-1)*(x-2)/6; } int main() { //freopen("trokuti.in","r",stdin); //freopen("trokuti.out","w",stdout); n=init(); for(ll i=1;i<=n;i++){ a=init();b=init();c=init(); Insert(a,b,c,i); } sort(p+1,p+1+n,cmp); double now=p[1].k; ll nowc=p[1].C;len[++cnt]++; for(ll i=2;i<=n;i++){ if(p[i].k==now&&p[i].C!=nowc){ nowc=p[i].C;len[cnt]++; } else if(p[i].k!=now){ len[++cnt]++; now=p[i].k;nowc=p[i].C; } } ans=n*(n-1)*(n-2)/6; for(ll i=1;i<=cnt;i++){ if(len[i]>=2)ans-=Cu(len[i],2)*(n-len[i]); if(len[i]>=3)ans-=Cu(len[i],3); } cout<<ans<<endl; return 0; }
T2/*可贪心 或者一边nlogn的LIS */ #include<cstdio> #include<algorithm> #define maxn 100010 using namespace std; int n,a[maxn],c[maxn],num; int init(){ int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } int main() { freopen("manage.in","r",stdin); freopen("manage.out","w",stdout); n=init(); for(int i=1;i<=n;i++) a[i]=init(); for(int i=1;i<=n;i++){ int x=a[i]; if(x>c[num]){ c[++num]=x;continue; } int pos=lower_bound(c+1,c+1+num,x)-c; c[pos]=x; } printf("%d ",num); return 0; }
T3/*暴力 枚举最大的能用的s 然后将合法的边按g为关键字MST m*m*logm +剪枝50分*/ #include<iostream> #include<cstdio> #include<algorithm> #define ll long long #define maxn 410 #define maxm 50010 #define inf 1e18 using namespace std; ll n,m,S,G,ms,mg,cnt,tot,fa[maxn],falg; ll ans=inf*3,mx,mig=inf; struct node{ ll u,v,s,g; }p[maxm]; struct edge{ ll u,v,o,g; }e[maxm]; ll init(){ ll x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } int cmp(const node &x,const node &y){ return (x.s==y.s&&x.g<y.g)||x.s<y.s; } int Cmp(const edge &x,const edge &y){ return x.g<y.g; } int find(int x){ if(x!=fa[x])fa[x]=find(fa[x]); return fa[x]; } bool Judge(int x){ cnt=0;tot=0;falg=0; for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=x;i++){ e[++cnt].o=i;e[cnt].g=p[i].g; e[cnt].u=p[i].u;e[cnt].v=p[i].v; } sort(e+1,e+1+cnt,Cmp); for(int i=1;i<=cnt;i++){ int r1=find(e[i].u); int r2=find(e[i].v); if(r1!=r2){ tot++;fa[r2]=r1; } if(tot==n-1){ mg=e[i].g;falg=1;break; } } return falg; } int main() { freopen("road.in","r",stdin); freopen("road.out","w",stdout); n=init();m=init();G=init();S=init(); ll u,v,g,s; for(int i=1;i<=m;i++){ u=init();v=init();g=init();s=init(); p[i].u=u;p[i].v=v;p[i].g=g; p[i].s=s;mig=min(mig,p[i].g); } sort(p+1,p+1+m,cmp); for(int i=1;i<=m;i++){ mx=p[i].s*S+mig*G; if(mx>=ans)break; if(Judge(i)){ ms=p[i].s; mx=ms*S+mg*G; ans=min(ans,mx); } } if(ans==inf*3)cout<<"-1"<<endl; else cout<<ans<<endl; return 0; } /* 后来看了题解的方法 在之前暴力的基础上优化一下 每次加入一条边 不用O(m)的跑MST 直接把这条边加到上一次MST的n-1条边里 还有就是每加入一条边 因为之前的n-1条是有序的 直接O(m)插入就好了 这样就成了O(mn) 可能我写的比较挫 先找一遍MST 这个略慢2333 可以卡掉 但是没数据 */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define maxn 410 #define maxm 50010 #define inf 1e18 using namespace std; int n,m,cnt,tot,fa[maxn],falg; ll ans=inf*3,S,G,ms,mg,mx,mi[maxm]; struct node{ int u,v;ll s,g; }p[maxm],pp[maxm],e[maxn],ee[maxm]; ll init(){ ll x=0;char s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x; } ll min(ll x,ll y){ return x<y?x:y; } int cmp(const node &x,const node &y){ return x.s<y.s; } int Cmp(const node &x,const node &y){ return x.g<y.g; } int find(int x){ if(x!=fa[x])fa[x]=find(fa[x]); return fa[x]; } bool Judge2(int x){ tot=0;falg=0;int P=cnt+1; e[++cnt]=p[x];cnt=0; for(int i=1;i<=n;i++)fa[i]=i; while(e[P].g<e[P-1].g){//插入这排序 快快快 swap(e[P],e[P-1]);P--; } for(int i=1;i<=n;i++){ int r1=find(e[i].u); int r2=find(e[i].v); if(r1!=r2){ ee[++cnt]=e[i]; tot++;fa[r2]=r1; } if(tot==n-1){ mg=e[i].g;falg=1;break; } } if(falg)for(int i=1;i<=n;i++)e[i]=ee[i]; return falg; } bool Judge1(int x){ tot=0;falg=0;cnt=0;int P=x; for(int i=1;i<=n;i++)fa[i]=i; while(pp[P].g<pp[P-1].g){//插入这排序 快快快 swap(pp[P],pp[P-1]);P--; } for(int i=1;i<=x;i++){ int r1=find(pp[i].u); int r2=find(pp[i].v); if(r1!=r2){ tot++;fa[r2]=r1; e[++cnt]=pp[i]; } if(tot==n-1){ mg=pp[i].g;falg=1;break; } } return falg; } int main() { freopen("road.in","r",stdin); freopen("road.out","w",stdout); n=init();m=init();G=init();S=init(); int u,v;ll g,s; for(int i=1;i<=m;i++){ u=init();v=init();g=init();s=init(); p[i].u=u;p[i].v=v;p[i].g=g;p[i].s=s; pp[i].u=u;pp[i].v=v;pp[i].g=g;pp[i].s=s; } memset(mi,127/3,sizeof(mi)); sort(p+1,p+1+m,cmp);sort(pp+1,pp+1+m,cmp); int start=0; for(int i=1;i<=m;i++) mi[i]=min(mi[i-1],p[i].g); for(int i=1;i<=m;i++){ mx=p[i].s*S+mi[i]*G; if(mx>=ans)break; if(Judge1(i)){ ms=p[i].s; mx=ms*S+mg*G; ans=min(ans,mx); start=i+1;break; } } for(int i=start;i<=m;i++){ mx=p[i].s*S+mi[i]*G; if(mx>=ans)break; if(Judge2(i)){ ms=p[i].s; mx=ms*S+mg*G; ans=min(ans,mx); } } if(ans==inf*3)cout<<"-1"<<endl; else cout<<ans<<endl; return 0; }