2019 ICPC EC-Final重现
A.City
题意： 给n个m，表示有一个n*m的网格
在网格上任选两点连线，如果这条线的中点也在格点上则满足题意。
问有多少条这样的线（即端点在格点上，中点也在格点上，线的长度不为0）
数据范围：n,m<=1e3
思路: 枚举中点的位置即可。
code:
#include
using namespace std;
#define int long long
signed main(){
int n,m;
cin>>n>>m;
n++,m++;
int ans=0;
for(int i=1;
i<=n;
i++){//枚举中点
for(int j=1;
j<=m;
j++){
int a=min(i,n-i+1);
int b=min(j,m-j+1);
ans+=(a-1)*(b-1)*2+(a-1)+(b-1);
}
}
cout< C.Dirichlet k-th root( 卷积题，有空补
E.Flow 题意： 【2019|2019 ICPC EC-Final】给定n个节点m条边的带权无向图。其中起点1到终点n有一些独立路径，且路径节点数相同(路径长度相同)。每条边有边权。
一次操作可以让一条边的边权加一，另外一条边权减一。问使得起点到终点的总流量最大最少需要操作多少次。
数据范围：n<=1e5，m<=2e5，边权<=1e9
思路: 因为路径长度是相同的。假设把所有边权都累加到一条链上，可以推出最大流=边权和/(链的长度)，这就是最后的最大流。
将每条链按边权排序，然后分层，计算每一层的边权和。
因为要得到最大流，所以每一层的边权和都要大于等于最大流，小于最大流的就补全，这样就能计算出操作次数了。
code:
#include
using namespace std;
#define int long long
const int maxm=1e5+5;
int head[maxm],nt[maxm<<2],to[maxm<<2],w[maxm<<2],tot;
vectortemp;
int flow[maxm];
int n,m;
void add(int x,int y,int z){
tot++;
nt[tot]=head[x];
head[x]=tot;
to[tot]=y;
w[tot]=z;
}
void dfs(int x,int fa){
if(x==n)return ;
for(int i=head[x];
i;
i=nt[i]){
int v=to[i];
if(v==fa)continue;
temp.push_back(w[i]);
dfs(v,x);
}
}
signed main(){
cin>>n>>m;
int sum=0;
for(int i=1;
i<=m;
i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
sum+=c;
}
int elen=0;
//路径长度
for(int i=head[1];
i;
i=nt[i]){
temp.clear();
temp.push_back(w[i]);
dfs(to[i],1);
sort(temp.begin(),temp.end());
//排序
if(!elen)elen=temp.size();
for(int i=0;
i H.King 题意： 给一个长度为n的数组和一个质数p
定义一个序列s为king序列，序列s满足：s(i-1)*q%p=s(i)，(模意义下的等比数列)
现在要你从a中调出一个子序列，这个子序列是king序列，问最大长度是多少，如果最大长度小于n/2则输出-1。
数据范围：n<=2e5，p<=1e9+7，保证p是质数
思路: 这题的关键点在于那个n/2，(果然题目的每一个条件都不能忽视！)
因为长度至少为n/2，所以这个子序列一定至少有两个数相邻或者相隔1，所以公比肯定会产生在相邻或者相隔1
用map存下所有a(i-1)到a(i)以及a(i-2)的到a(i)的公比数量
显然公比q的出现次数一定会大于等于某个数
将出现次数大于n/8的check一下取max即可(n/6也行，推了好久不知道这数咋来的)
code:
#include
using namespace std;
#define ll long long
const int maxm=2e5+5;
unordered_mapmark;
int inv[maxm];
int a[maxm];
int n,p;
int ppow(int a,int b,int mod){
int ans=1%mod;
while(b){
if(b&1)ans=(ll)ans*a%mod;
a=(ll)a*a%mod;
b>>=1;
}
return ans;
}
int cal(int q){
unordered_mapdp;
int ans=0;
for(int i=n;
i>=1;
i--){
dp[a[i]]=dp[(ll)a[i]*q%p]+1;
ans=max(ans,dp[a[i]]);
}
return ans;
}
signed main(){
int T;
cin>>T;
while(T--){
unordered_mapt;
mark=t;
scanf("%d%d",&n,&p);
for(int i=1;
i<=n;
i++){
scanf("%d",&a[i]);
inv[i]=ppow(a[i],p-2,p);
}
for(int i=2;
i<=n;
i++){
int q=(ll)a[i]*inv[i-1]%p;
mark[q]++;
}
for(int i=3;
i<=n;
i++){
int q=(ll)a[i]*inv[i-2]%p;
mark[q]++;
}
int ans=0;
for(auto i:mark){
if(i.second>=n/8){
ans=max(ans,cal(i.first));
}
}
if(ans*2 M.Value 题意： 给长度为n的数组a和b
对于每一个位置i，可选可不选，如果选中了i，那么总得分就加上a(i)。
如果选中了i和j，且i，j>=2，且ik=j（k>=2），那么需要减去b(j)，如果又多个i满足这个条件，b(j)会被减去多次。
现在你要找到一个选择方案，使得最后的总得分最大，输出这个最大得分。
数据范围：n<=1e5，1<=a(i),b(i)<=1e9
思路: a(1)必选，因为他不影响其他数。
容易发现底数不同的数不会相互影响，例如8与9不会相互影响，因为8=23，9=32，
发现n只有1e5，217大于1e5，因此如果按底数分组，最大的组是底数为2的组，不多于17个数，其他组数量更少。
所以可以先按底数分组，对于每一组然后二进制枚举选择方案取max，累加就是答案。
code:
#include
using namespace std;
#define int long long
const int maxm=1e5+5;
vectorg[maxm];
int cnt=0;
int mark[maxm];
int a[maxm];
int b[maxm];
int solve(int x){//计算第x组的最大答案
int len=g[x].size();
int ans=0;
for(int i=0;
i<(1<>j&1){
temp+=a[g[x][j]];
temp-=mark[g[x][j]]*b[g[x][j]];
for(int k=g[x][j]*g[x][j];
k<=g[x][len-1];
k*=g[x][j]){
mark[k]++;
}
}
}
ans=max(ans,temp);
}
return ans;
}
signed main(){
int n;
cin>>n;
for(int i=1;
i<=n;
i++)cin>>a[i];
for(int i=1;
i<=n;
i++)cin>>b[i];
for(int i=2;
i<=n;
i++){//按底数分组
if(mark[i])continue;
cnt++;
for(int j=i;
j<=n;
j*=i){
mark[j]=1;
g[cnt].push_back(j);
}
}
int ans=a[1];
//a[1]必选,因为对后续无影响
for(int i=1;
i<=cnt;
i++){//对每一组二进制枚举
ans+=solve(i);
}
cout< 
