牛客6
A

签到（只有if，else）

B

二分，前缀和（记得用scanf，超时一部分数据过不去）
1.思想：每次查询时候先看修改了多少次
2.把下标先看作区间L，R==[x+1,n+修改数]（转化问题为[L,R]中多少个ai%ax==0）
3.用一个vector<>pos[]来记录数组i的倍数的下标
例如：数组为2，3，6  ；；那么pos[2]=1,3
a[1]=2,a[3]=6均为2的倍数
4.通过二分出pos[x]区间长度就是答案

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long LL;
vector<int>pos[N],num(1);
int n,q;
void add(int x,int idx)
{
    num.push_back(x);
    for(LL i=1;i*i<=x;i++)
    {
        if(x%i==0)
        {
            pos[i].push_back(idx);
            if(i*i!=x)
                pos[x/i].push_back(idx);
        }
    }
}
int ddd(int x)
{
    int t=num[x];
    return pos[t].end()-upper_bound(pos[t].begin(),pos[t].end(),x);
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        add(x,i);//查找谁是x的倍数，加进去下标i
    }
    for(int i=1;i<=q;i++)   
    {
        int x,op;
        scanf("%d%d",&op,&x);
        if(op==1)
            add(x,++n);//n+1是因为多了一个ai，后移
        else
            printf("%d\n",ddd(x));
    }
    return 0;
}

C

1.先用组合数求出合并的系数
2.再用ai和系数相乘相加

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const ll mod=1e9+7;
ll ans[1010],c[1010][1010];//组合数C
int main()
{
    for(int i=0;i<=1000;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(j==0) c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
    cin>>n;
    for(int i=1;i<=n/2;i++)
    {
        ans[i]=2*i-1;
        ans[n+1-i]=2*i;
    }
    if(n%2)ans[n/2+1]=n;
    ll sum=0;
    for(int i=1;i<=n;i++)
        sum=(sum+ans[i]*c[n-1][i-1])%mod;
    printf("%lld\n",sum);
    for(int i=1;i<=n;i++)
    {
        printf("%lld ",ans[i]);
    }
    puts("");
    return 0;
}

D

//S中T子序列的个数
//dp[i][j]，S串i的位置，j对应1~j在S中有多少子序列出现
//dp[7][2]实在S前7个字符中出现“ud”子序列，dp[7][1]是出现“u”子序列

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
char s[N],udu[]="*udu";//udu[0]=='*'
int n;
ll dpz[N][4],dpf[N][4];
void ddpp(ll dp[][4])
{
    dp[0][0]=1;//前0个字符无子序列则初始化为1
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=1;
        for(int j=1;j<=3;j++)
        {
            dp[i][j]=dp[i-1][j];//状态转移
            if(s[i]==udu[j])
                dp[i][j]+=dp[i-1][j-1];
        }
    }
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    ddpp(dpz);//子序列分正反两头顺序
    reverse(s+1,s+n+1);
    ddpp(dpf);
    reverse(s+1,s+n+1);
    ll ans=1e18,pos=-1;
    for(int i=1;i<=n;i++)
    {
        ll tmp=0;
        tmp+=dpz[i-1][3]*dpf[n-i][0];
        tmp+=dpz[i-1][2]*dpf[n-i][1];
        tmp+=dpz[i-1][1]*dpf[n-i][2];
        tmp+=dpz[i-1][0]*dpf[n-i][3];
        if(tmp<ans)
        {
            ans=tmp;
            pos=i;
        }
    }
    s[pos]='a';
    puts(s+1);
    return 0;
}

E

lcm最小公倍数，gcd最大公约数
//1~k+1和1求lcm最小
//考虑k+2~n （gcd）怎么样边权为最小
//需要找一个质数p,最好使得gcd(x,p)结果为1
//选取i：从区间[2,k+1]中暴力枚举选择i+k+1，
//直到遇到质数p使得gcd为1，break；
//gcd取到的边和lcm取到的再次比较大小，取min

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
int main()
{
    cin>>n>>k;
    ll num=min(n,k+1);
    ll ans=n-num;//k+2~n
    for(int i=2;i<=num;i++) //2~k+1
    {
        ll mn=i;//因为lcm和1取最小公倍数，取到就是本身枚举的i
        for(int j=i+k+1;j<=n;j++)
        {
            mn=min(mn,(ll)__gcd(i,j));//函数__gcd()
            if(mn==1)break;
        }
        ans+=mn;
    }
    printf("%lld\n",ans);
    return 0;
}

F

k的最大是1e9，但经过k次就会最终会收敛为1，不再变
所以k次操作要优化为【离线询问】：输入所有询问，排序，做一次
这题从小到大排序k次。例如：1，3，5，7
开一个set记录询问，查询询问时间是否范围内
小于等于2e5的数最多变化 4 次就会变成 1

#include<bits/stdc++.h>
using namespace std;
multiset<int,greater<int> >st;
int n,q,k,a[200010],ans[2000010];
int f(int x)
{
    int ans=0;
    while(x)
    {
        if(x&1)ans++;
        x>>=1;
    }
    return ans;
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        st.insert(a[i]);
    }
    int p=0;//记录次数
    while(!st.empty())
    {
        int mx=(*st.begin());
        st.erase(st.begin());
        p++;
        if(mx!=1)st.insert(f(mx));
        ans[p]=max(*st.begin(),1);//防止最后st空，结果为0.再多次f（x）最终ans为1
    }
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&k);
        printf("%d\n",ans[min(k,p)]);
    }
    return 0;
}

G

相当于双指针算法，首位选两个，末尾选两个比较哪一个大就+

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
int a[N],n,k;
LL res=0,t=0;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int l=1,r=n;
    sort(a+1,a+n+1);
    while(l<=r)
    {
        if(a[l]*a[l+1]>a[r]*a[r-1])
        {
            res+=a[l]*a[l+1];
            l+=2;
        }
        else
        {
            res+=a[r]*a[r-1];
            r-=2;
        }
        t++;
        if(t==k)break;
    }
    cout<<res<<endl;
    return 0;
}

H

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,L,R;
double res=0;
int main()
{
    cin>>n;
    cin>>L>>R;
    if(L>=n)cout<<double(0)<<endl;
    else if(n>R)cout<<double(1)<<endl;
    else cout<<double(double(n-1)-L+1)/double(R-L+1)<<endl;
    return 0;
}

I

无向图
1.第一种情况：从1~n无其他边，走过的路删掉，把下一条路变为1（w1+dist[n]-1）
2.第二种就是用其他边把当前边变成1.ans=dist[n]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=400020;
ll n,m,e[N],ne[N],h[N],w[N],idx,dist[N],a[N];
bool st[N];
void add(ll a,ll b,ll c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int bfs()//bfs
{
    queue<int> q;
    q.push(1);
    st[1]=true;
    ll minn=0x3f3f3f3f3f3f;
    while(!q.empty())
    {
        ll t=q.front();
        q.pop();
        for(ll i=h[t];i!=-1;i=ne[i])
        {
            ll j=e[i];
            if(st[j])continue;
            st[j]=true;
            dist[j]=dist[t]+1;
            q.push(j);
            if(t==1)
                minn=min(minn,w[i]);
        }
    }
    if(dist[n]<m)
        return dist[n];
    return minn+(dist[n]-1);
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(ll i=1;i<=m;i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    ll ans=bfs();
    cout<<ans<<"\n";
    return 0;
}