今天题目略水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=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';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==)K=inf;
else K=-double(x)/double(y);
p[o].C=z;p[o].k=K;
}
ll Cu(ll x,ll y){
if(y==)return x*(x-)/;
if(y==)return x*(x-)*(x-)/;
}
int main()
{
//freopen("trokuti.in","r",stdin);
//freopen("trokuti.out","w",stdout);
n=init();
for(ll i=;i<=n;i++){
a=init();b=init();c=init();
Insert(a,b,c,i);
}
sort(p+,p++n,cmp);
double now=p[].k;
ll nowc=p[].C;len[++cnt]++;
for(ll i=;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-)*(n-)/;
for(ll i=;i<=cnt;i++){
if(len[i]>=)ans-=Cu(len[i],)*(n-len[i]);
if(len[i]>=)ans-=Cu(len[i],);
}
cout<<ans<<endl;
return ;
}
T2/*可贪心 或者一边nlogn的LIS */
#include<cstdio>
#include<algorithm>
#define maxn 100010
using namespace std;
int n,a[maxn],c[maxn],num;
int init(){
int x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
int main()
{
freopen("manage.in","r",stdin);
freopen("manage.out","w",stdout);
n=init();
for(int i=;i<=n;i++)
a[i]=init();
for(int i=;i<=n;i++){
int x=a[i];
if(x>c[num]){
c[++num]=x;continue;
}
int pos=lower_bound(c+,c++num,x)-c;
c[pos]=x;
}
printf("%d\n",num);
return ;
}
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*,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=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';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=;tot=;falg=;
for(int i=;i<=n;i++)fa[i]=i;
for(int i=;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+,e++cnt,Cmp);
for(int i=;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-){
mg=e[i].g;falg=;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=;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+,p++m,cmp);
for(int i=;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*)cout<<"-1"<<endl;
else cout<<ans<<endl;
return ;
}
/*
后来看了题解的方法 在之前暴力的基础上优化一下
每次加入一条边 不用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*,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=;char s=getchar();
while(s<''||s>'')s=getchar();
while(s>=''&&s<=''){x=x*+s-'';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=;falg=;int P=cnt+;
e[++cnt]=p[x];cnt=;
for(int i=;i<=n;i++)fa[i]=i;
while(e[P].g<e[P-].g){//插入这排序 快快快
swap(e[P],e[P-]);P--;
}
for(int i=;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-){
mg=e[i].g;falg=;break;
}
}
if(falg)for(int i=;i<=n;i++)e[i]=ee[i];
return falg;
}
bool Judge1(int x){
tot=;falg=;cnt=;int P=x;
for(int i=;i<=n;i++)fa[i]=i;
while(pp[P].g<pp[P-].g){//插入这排序 快快快
swap(pp[P],pp[P-]);P--;
}
for(int i=;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-){
mg=pp[i].g;falg=;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=;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,/,sizeof(mi));
sort(p+,p++m,cmp);sort(pp+,pp++m,cmp);
int start=;
for(int i=;i<=m;i++)
mi[i]=min(mi[i-],p[i].g);
for(int i=;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+;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*)cout<<"-1"<<endl;
else cout<<ans<<endl;
return ;
}