iwtgm-9

题目链接
dp，自己写的时候没有考虑完全状态转移，其实是滑动窗口dp，需要维护一段区间的最小值
1-n内的数显然能一步得到，
考虑n+1到y，可由前面的状态加数得到也可以乘数得到，
考虑加，其实是区间长度为n的滑动窗口的最小值+1
考虑乘，若当前数i能整除mi，则dp[mi]+1

int a[N],dp[N],q[N],tt=-1,hh;
void solve(){
    int y,n,m;cin>>y>>n>>m;
    for(int i=1;i<=m;i++)cin>>a[i];
    for(int i=1;i<=y;i++){
        if(i<=n)dp[i]=1;
        else dp[i]=inf;
    }
    for(int i=1;i<=n;i++){
        if(tt>=hh&&i-n+1>q[hh])hh++;
        while(tt>=hh&&dp[q[tt]]>=dp[i])tt--;
        q[++tt]=i;
    }
    for(int i=n+1;i<=y;i++){
        dp[i]=dp[q[hh]]+1;
        for(int j=1;j<=m;j++){
            if(i%a[j]==0)dp[i]=min(dp[i],dp[i/a[j]]+1);
        }
        if(tt>=hh&&i-n+1>q[hh])hh++;
        while(tt>=hh&&dp[q[tt]]>=dp[i])tt--;
        q[++tt]=i;
    }
    cout<<dp[y];
}

题目链接

A.

a/b是他人得到的蛋挞数，a-a/b*b是牛牛得到的蛋挞数，
两者比大小输出即可

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
*/

void solve(){
    ll a,b;cin>>a>>b;
    ll ave=a/b,niu=a-a/b*b;
    if(ave>niu)cout<<"niuniu eats less than others";
    else if(ave==niu)cout<<"same";
    else cout<<"niuniu eats more than others";
}

B.

最贵的一定不会被送，而要买到全部的玩具
所以每次买一个最贵的，送一个第二贵的，直至买完

int n;
ll a[N];
bool cmp(ll x,ll y){
    return x>y;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    ll ans=0;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i+=2)ans+=a[i];
    cout<<ans;
}

C.

数据范围很小，所以全排列后无脑模拟，取最大的答案

struct node{
    ll full_points,ctime,base,cost,wa;
}a[15];
int b[15];
void solve(){
    ll n,t,p;cin>>n>>t>>p;
    for(ll i=1;i<=n;i++){
        cin>>a[i].full_points>>a[i].ctime>>a[i].base>>a[i].cost>>a[i].wa;
    }
    for(int i=1;i<=n;i++)b[i]=i;
    ll ans=-1;
    ll total,cost_time;
    do{
        total=0;cost_time=0;
        for(int i=1;i<=n;i++){
            int id=b[i];
            if(cost_time+a[id].cost<=t){
                cost_time+=a[id].cost;
                total+=max(a[id].base,a[id].full_points-cost_time*a[id].ctime-a[id].wa*p);
            }
        }
        ans=max(ans,total);
    } while (next_permutation(b+1,b+1+n));
    cout<<ans;
}

D.

并查集维护n个点联通
把边按权值从小到大排序，
然后遍历，若该边两个端点不在一个集合，则记录这条边的权值，在就跳过
最后把有用边的权值从大到小排序，化掉c元，剩最大的权值即为答案

int n,m;
ll c;
struct node{
    int u,v;
    ll cost;
}a[N];
int fa[N];
bool cmp(node x,node y){
    return x.cost<y.cost;
}
vector<ll>ve;
int find(int x){
    if(x==fa[x])return fa[x];
    return fa[x]=find(fa[x]);
}
bool cmp1(ll x,ll y){
    return x>y;
}
void solve(){
    cin>>n>>m>>c;
    for(int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v>>a[i].cost;
    }
    for(int i=1;i<=n;i++)fa[i]=i;
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=m;i++){
        int u=a[i].u,v=a[i].v;
        int fa_u=find(u),fa_v=find(v);
        if(fa_u==fa_v)continue;
        ve.push_back(a[i].cost);
        fa[fa_u]=fa_v;
    }
    sort(ve.begin(),ve.end(),cmp1);
    ll k=1;
    int id=0;
    for(int i=0;i<ve.size();i++){
        ll tmp=ve[i];
        if(c-k*tmp>=0){
            c-=k*tmp;k++;id++;
        }else break;
    }
    if(id>=ve.size())cout<<0;
    else cout<<ve[id];
}

E.

数据小，暴力三层for循环取三个点，判断是否有任两条边相等
用两边之和等于第三边判三点共线
距离用double

#define double long double
pair<double,double>a[410];
double get_dis(pair<double,double> x,pair<double,double> y){
    return sqrt((x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second));
}
void solve(){
    int n;cin>>n;
    double x,y;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        a[i].first=x;a[i].second=y;
    }
    int cnt=0;
    for(int i=1;i+2<=n;i++){
        for(int j=i+1;j+1<=n;j++){
            for(int k=j+1;k<=n;k++){
                //if(a[i].first==a[j].first&&a[k].first==a[i].first||a[i].second==a[j].second&&a[k].second==a[i].second)continue;
                double d1= get_dis(a[i],a[j]);
                double d2= get_dis(a[i],a[k]);
                double d3= get_dis(a[j],a[k]);
                if(d1==(d2+d3)||d2==(d1+d3)||d3==(d1+d2))continue;
                if(d1==d2||d1==d3||d2==d3)cnt++;
            }
        }
    }
    cout<<cnt;
}

还可以用叉积判面积为0则三点共线

if((a[j].first-a[i].first)*(a[k].second-a[i].second)-(a[j].second-a[i].second)*(a[k].first-a[i].first)==0)continue;

设向量a，b是三角形两条边的向量，则向量相乘取绝对值再除以2是该三角形的面积

F.

数据较大，不能用暴力三层循环，考虑其他解法
因为边的端点都是整数点，相当于格点，
而等边三角形不可能是格点三角形，因为等边三角形面积s=a^2*根号3/4是无理数，
如果是格点图形的话，其外围图形面积都是有理数，有理数-有理数=有理数，与等边三角形面积为无理数矛盾

两层for循环，计算出所有边长，边长相等的数量>=2，一定可以成为等腰三角形（以i为顶点）
注意:端点有顺序
判断三点共线：以i为顶点，那么另外两个点一定关于i点对称，故可以计算出第三个点的坐标，
判存不存在，若存在+1标记，
因为是两层循环，所以这一情况会被标记两次，
最后答案-标记/2即可

注意：map真的非常慢，用map写会超时，unordered_map也会超时

bool st[3010][3010];
int dx=1500;
pair<int,int>a[3010];
int cnt[3010*3010];
int get_dis(pair<int,int>x,pair<int,int>y){
    return (x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second);
}
pair<int,int>cal(pair<int,int>x,pair<int,int>y){
    return {x.first-(y.first-x.first)+dx,x.second-(y.second-x.second)+dx};
}
void solve(){
    int n;cin>>n;
    for(int i=0,x,y;i<n;i++){
        cin>>x>>y;
        a[i].first=x;a[i].second=y;
        st[a[i].first+dx][a[i].second+dx]=true;
    }
    ll ans=0,line=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)continue;
            int dis=get_dis(a[i],a[j]);
            ans+=cnt[dis];
            cnt[dis]++;
            pair<int,int> z=cal(a[i],a[j]);
            if(st[z.first][z.second])line++;
        }
        for(int j=0;j<n;j++){
            int dis= get_dis(a[i],a[j]);
            cnt[dis]=0;
        }
    }
    ans-=line/2;
    cout<<ans;
}