A. City

大致题意:n*m的网格，求有多少线段----线段满足两端点在网格点上，并且线段中点在网格点上.
分析:暴力统计，偶数边的数量。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;


int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    ll ans=0;
    n++;
    m++;
    for( int i=1;i<=n;i++ )
    {
        for( int j=1;j<=m;j++ )
        {
            ans+=((j-1)/2)*((n-i)/2);
            ans+=((m-j)/2)*((n-i)/2);
            ans+=(m-j)/2+(n-i)/2;
        }
    }
    printf("%lld\n",ans);
}

E. Flow

大致题意:有n个点,起点是1(源点)，终点是n(汇点),1~n有很多条互斥的等长的路径，路径上每条边都有一个流量，你可以执行操作----让一条边的流量加一让另一个边的流量减一---，请问达到最大流量的最小操作次数。
分析:这道题题意我看了好久tm才看懂...显然就是一个楼梯注水问题，这道题就是多个楼梯灌水问题，我们先找出所有路径，然后每条路径的边排序.然后可以从最终状态入手，最大流的计算就是所有边流量之和/路径长度,然后算操作次数即可.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn=1e5+10;

int n,m,k;

vector< pair<ll,ll> >g[maxn];
vector<int> a[maxn];

void dfs( int x )
{
    if( x==n ) 
    {
        sort(a[k].begin(),a[k].end());
        return;
    }
    for( auto v:g[x] )
    {
        if( x==1 ) k++;
        a[k].push_back( v.second );
        dfs( v.first );
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    ll avg=0;
    for( int i=0;i<m;i++ )
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        g[u].push_back( make_pair(v,w) );
        avg+=w;
    }
    k=0;
    dfs(1);

    ll ans=0;
    avg/=a[1].size(); // 最大流量 
    for( int i=0;i<a[1].size();i++ )
    {
        ll tmp=0;
        for( int j=1;j<=k;j++ ) tmp+=a[j][i];
        if( tmp>=avg ) break;   
        ans+=avg-tmp;  // 操作次数 
    }
    printf("%lld\n",ans);
}

H. king

大致题意：给定一个序列，求最长的等比序列长度.要求长度大于等于n/2向上取整.
分析:我们要先找到公比再去验证是否存在长度大于n/2的等比序列，对于n/2的长度我们可以分析出公比的产生最多相隔一个位置或者相邻位置,那么我们用map存储找到的所有公比,然后对于公比出现次数大于1/6的公比进行check找序列长度是否满足即可.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn=2e5+10;
int mod,a[maxn],inv[maxn],tp[maxn];;
int t,n;


ll qpow( ll x,ll y )
{
    ll ans=1;
    while( y )
    {
        if( y&1 ) ans=ans*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return ans;
}

unordered_map<int,int> mp,p1;

int check( int x )
{
    p1.clear();
    int ans=-1;
    for( int i=n;i>=1;i-- )
    {
        tp[i]=1;
        int nex=1ll*a[i]*x%mod;
        if( p1.count(nex) ) tp[i]=tp[p1[nex]]+1;
        p1[a[i]]=i;
        ans=max(ans,tp[i]);
    }
    return ans;
}


int main()
{
    scanf("%d",&t);
    while( t-- )
    {
        mp.clear();
        scanf("%d%d",&n,&mod);
        for( int i=1;i<=n;i++ )
        {
            scanf("%d",&a[i]);
            inv[i]=qpow(a[i],mod-2);
        }
        for( int i=1;i<n;i++ )
        {
            int x=1ll*a[i+1]*inv[i]%mod;
            mp[x]++;
        }
        for( int i=1;i<n-1;i++ )
        {
            int x=1ll*a[i+2]*inv[i]%mod;
            mp[x]++;
        }
        int ans=-1;
        for( auto it:mp )
        {
            if( it.second>=n/4 )
            {
                ans=max( ans,check(it.first) );
            }
        }
        if( ans*2>=n ) printf("%d\n",ans);
        else puts("-1");
    }
    return 0;
}

M. value

大致题意：选择一些下标的集合，价值为下标对于的a数组值，如果下标集合中满足任意i>1,j>1,i^k=j则减去b[j]。问价值最大值.
分析：我们从i^k=j入手,可以发现对于2的幂次的数，3的幂次的数,5的幂次的数等等的选法互相独立，那么我们可以二进制枚举方案进行计算每个幂次下的最大贡献的是多少然后累加即可.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn=2e5+10;


int vis[maxn];
int a[maxn],b[maxn];

vector<int>p[maxn];
ll Max[maxn];
int n;


ll solve( int x ,int y )
{
    ll ans=0;
    vector<int> num;
    for( int i=0;i<p[y].size();i++ )
    {
        if( x & (1<<i) )
        {
             num.push_back(p[y][i]);
             ans+=a[p[y][i]];
        }
    }

    for( int i=0;i<num.size();i++ )
    {
        for( int j=i+1;j<num.size();j++ )
        {
            int p1=num[i],p2=num[j];
            while( p2>1 )
            {
                 if( p2%p1==0 ) p2/=p1;
                 else break;
            }
            if( p2==1 ) ans-=b[num[j]];
        }
    }
    return ans;

}

ll getMax( int x )
{
    ll ans=0;
    int cnt=1<<(p[x].size());
    for( int i=0;i<cnt;i++ )
    {
        ans=max( ans,solve(i,x) );
    }
    return ans;
}


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]);

    for( int i=2;i<=n;i++ )
    {
        if( vis[i] ) continue;
        p[i].push_back(i);
        for( ll j=i*i;j<=n;j*=i )
        {
            p[i].push_back(j);
            vis[j]=1;
        }
    }

//  for( int i=2;i<=n;i++ )
//  {
//      for( auto v:p[i] ) cout<<v<<" ";
//      cout<<endl;
//  }


    for( int i=2;i<=n;i++ )
    {
        if( vis[i] ) continue;
        Max[i]=getMax(i);  
    }

    ll ans=a[1];
    for(int i=1;i<=n;i++ ) ans+=Max[i];
    printf("%lld\n",ans);
}