A.City

题意：

给一个网格，问有多少条线段两端是格点，同时中点也是格点

题解：

如果两个点的横坐标和纵坐标奇偶性都相同，那么就满足条件，所以只要求出四种情况的数量，每种情况各自算出结果相机即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(ll x)
{
    return x*(x-1)/2;
}
int main()
{
    ll n,m;
    scanf("%lld%lld",&n,&m);
    n++;
    m++;
    ll a1 = n/2,a2  = (n+1)/2,a3 = m/2,a4 = (m+1)/2;
    printf("%lld\n",f(a1*a3)+f(a1*a4)+f(a2*a3)+f(a2*a4));
    return 0;
}

C.Dirichlet k -th root（迪利克雷卷积）

题意：

给定函数f(x)自己迪利克雷卷积k次的结果g(x)，求f(x)的值，其中1<=x<=n

题解：

有一个结论：
，
那我们可以知道 ,如果有个式子满足 那么 就是我们要求的答案，对于 变形可得 ,就是拓展欧几里得，此时q就是k模mod的逆元，即inv(k),所以所求为 。因此我们求出inv(k),对于这n个数求出g(x)的inv(k)次卷积就是答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll f[maxn], g[maxn], t[maxn];
int n, k;
ll ksm(ll a, ll b, ll mod)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
void mul(ll x[], ll y[])
{
    memset(t, 0, sizeof(t));
    for (int i = 1; i * i <= n; i++)
    {
        t[i * i] = (t[i * i] + x[i] * y[i] % mod) % mod;
        for (int j = i + 1; i * j <= n; j++)
            t[i * j] = (t[i * j] + x[i] * y[j] % mod + x[j] * y[i] % mod) % mod;
    }
    for (int i = 1; i <= n; i++)
        x[i] = t[i];
}
void power(int p)
{
    memset(f, 0, sizeof(f));
    f[1] = 1;
    while (p)
    {
        if (p & 1)
            mul(f, g);
        mul(g, g);
        p >>= 1;
    }
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &g[i]);
    power(ksm(k, mod - 2, mod));
    for (int i = 1; i <= n; i++)
        printf("%lld ", f[i]);
    puts("");
    return 0;
}

E.Flow（贪心）

题意：

给你一个n个节点和m条路径的图，若干条从源点1到汇点n长度都相等的路，而且每一条源点到汇点的路径都是独立路径互不相交，类似与链，你可让一条边容量加1另外一条边容量减去1，问使得流尽量大的最少操作数

题解：

因此路径互不相交，我们可以分别将每条路径上所有路径按容量升序排序，又因为每条路径长度都相等，我们可以将各条路径依次合并为一条新的路径。然后就可以进行贪心了，从容量最小的开始依次枚举每一点，剩余流量能加就加上。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
struct Edge{
    int to,w,next;
}e[maxn];
int head[maxn];
int tot,cnt,n,m;
vector<int>g[maxn];
ll addflow[maxn];
void init()
{
    memset(head,-1,sizeof(head));
    cnt=tot=0;
}
void addedge(int u,int v,int w)
{
    e[tot].to=v;
    e[tot].w=w;
    e[tot].next=head[u];
    head[u]=tot++;
}
void dfs(int u,int fa)
{
    for(int i=head[u];~i;i=e[i].next)
    {
        int v = e[i].to;
        if(v==fa)continue;
        g[cnt].push_back(e[i].w);
        dfs(v,u);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    init();
    int len;
    ll flow=0;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
        flow+=w;
    }
    for(int i=head[1];~i;i=e[i].next)
    {
        int v = e[i].to;
        g[++cnt].push_back(e[i].w);
        dfs(v,1);
        len = g[cnt].size();
        sort(g[cnt].begin(),g[cnt].end());
        int l=0;
        while(l<len-1)
        {
            while(l<len-1&&g[cnt][l]==g[cnt][l+1])l++;
            if(l<len)addflow[l+1]+=g[cnt][l+1]-g[cnt][l];
            l++;
        }
        flow-=1ll*len*g[cnt][0];
    }
    ll ans=0;
    for(int i=1;i<len;i++)
    {
        if(flow<len)break;
        ll tmp = min(addflow[i],flow/len);
        ans += 1ll * tmp * i;
        flow -= 1ll * tmp * len;
    }
    printf("%lld\n",ans);
    return 0;
}

H.king（随机数）

题意：

给定T组数据，每组数据n个数，求每组数据中最长的等比数列长度，如果最长的等比数列长度小于数列长度的一半则输出-1

题解：

因为要求长度大于一半，所以如果存在等比数列相邻两个数只可能相差1或2。因此我们随机取80个数，依次求出与后2个数的公比，遍历整个数组算出长度即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
std::mt19937 rnd(time(0));
int n;
ll a[maxn];
ll p;
ll ksm(ll a, ll n)
{
    a %= p;
    ll res = 1;
    while (n)
    {
        if (n & 1)
            res = res * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return res;
}
int solve(int l,int r)
{
    ll pre;
    int res=2;
    ll q=a[r]*ksm(a[l],p-2)%p;
    pre = a[r];
    for(int i=r+1;i<=n;i++)
        if(pre*q%p==a[i])
        {
            pre=a[i];
            res++;
        }
    pre=a[l];
    for(int i=l-1;i>=1;i--)
        if(a[i]*q%p==pre)
        {
            pre=a[i];
            res++;
        }
    return res;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%lld",&n,&p);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        int ans=0;
        for(int i=1;i<=80;i++)
        {
            int x = rnd()%(n-1)+1;
            for(int j=x+1;j<=n&&j<=x+2;j++)
                ans=max(ans,solve(x,j));
        }
        if(ans<(n+1)/2)printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}

M.value

题意：

给定n个数，每个数都有一个值a和b，每选择一个数x那么最终结果就会加上对应的ax，但是你如果先前选择了一个数y， 那么最终结果就会减去bx，对于每个数都同理，所以最终结果只会加上一次ax，但是可以减很多次bx

题解：

可以发现只有基底相同的一些数才会相互有影响，那么我们可以对每组基底都单独算出最大贡献，最终结果就是各组贡献之和，对于每组基底我们只要暴力枚举所有的可能情况取最大值即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int n,a[maxn],b[maxn],vis[maxn],num[maxn],cnt,mark[maxn];
ll dfs(int pos)
{
    if(pos>cnt)
    {
        ll res=0;
        for(int i=1;i<=pos;i++)
        {
            if(mark[i])
            {
                res+=a[num[i]];
                for(int j=i*2;j<=cnt;j+=i)
                    if(mark[j])
                        res-=b[num[j]];
            }
        }
        return res;
    }
    mark[pos]=1;
    ll res = dfs(pos+1);
    mark[pos]=0;
    res=max(res,dfs(pos+1));
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    ll ans=a[1];
    for(int i=2;i<=n;i++)
    {
        if(vis[i])continue;
        cnt=0;
        for(ll j=i;j<=n;j*=i)
        {
            vis[j]=1;
            num[++cnt]=j;
        }
        ans+=dfs(1);
    }
    printf("%lld\n",ans);
    return 0;
} 

终榜