[73] (NOIP集训) NOIP2024 加赛 7

这场真像 NOIP 难度吗，感觉还不如 CSP

两个点能对称当且仅当横坐标相等

\(nm\) 枚举所有点，横坐标相等的记录其对称轴位置，暴力给对称轴位置贡献加一

最后统计哪个位置贡献多即可

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
    int x,y;
};
node s[5001],x[5001];
#include<bits/extc++.h>
using namespace __gnu_pbds;
gp_hash_table<int,int>mp;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>s[i].x>>s[i].y;
    }
    for(int i=1;i<=m;++i){
        cin>>x[i].x>>x[i].y;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(s[i].x==x[j].x){
                mp[s[i].y+x[j].y]++;
            }
        }
    }
    int ans=0;
    for(auto i:mp){
        ans=max(ans,i.second);
    }
    cout<<ans<<'\n';
}

最大独立集定义：\(\max(|S|)\rightarrow \forall x\in S,y\in S,(x,y)\not\in E\)，还好学二分图的时候没摆烂

结论：从叶节点开始隔一层选一层最优，不用证，因为这是树，下一层的节点数量严格不低于上一层，所以这样选最优

先考虑 \(k\) 为偶数的情况

考虑每一层对答案的贡献就是该层的节点数目，而（以 \(k=4\) 为例）

可以发现一个以 \(k\) 为周期的规律：每一个周期都是上一个周期乘以 \(k_0k_1k_2k_3\)

设第一个周期的答案为 \(s\)（由于 \(k\) 较小，这是可以直接求的），那么答案就是：

项数就是 \(\lfloor\frac{n+1}{k}\rfloor\)，后面可能会有剩下的一小点，还是暴力处理即可

现在的问题就变成求这一大坨等比数列，毒瘤出题人把逆元卡了（然而并没有），因此可以考虑矩阵快速幂或者倍增等方法

矩阵快速幂的写法极其简单，不难构造出初始矩阵 \(\left[\begin{matrix}0&1\end{matrix}\right]\) 和转移矩阵 \(\left[\begin{matrix}1&0\\1&\prod k_i\end{matrix}\right]\)，直接快速幂取第一位即可

这是 \(k\) 为偶数的情况，那么 \(k\) 为奇数的情况咋处理，这个就比较简单了，直接 \(k\) 乘二就行了

#include<bits/stdc++.h>
#include<matrix.h>
using namespace std;
#define int long long
int n,k,p;
int a[500001];
matrix<int,4>mat,mat2;
int db(int x,int t){  //cal for 1+x+x^2+x^3+...+x^(t-1)
	mat.packed_clear({
		{1,0},
		{1,x}
	});
	mat2.packed_clear({
		{0,1}
	});
	mat.setmod(p);
	mat2.setmod(p);
	return (mat2*(mat|t))[1][1];
}
signed main(){
    cin>>n>>k>>p;
    for(int i=0;i<=k-1;++i){
        cin>>a[i];
    }
    int s=0,sizee=1;
    for(int i=0;i<=2*k-1;++i){
        if((i&1)==(n&1)) s=(s+sizee)%p;
        sizee=sizee*a[i%k]%p;
    }
    int tm=(n+1)/(2*k);
    int ans=(s*db(sizee,tm)%p)%p;
    sizee=power(sizee,tm);
    for(int i=tm*2*k;i<=n;++i){
        if((i&1)==(n&1)) ans=(ans+sizee)%p;
        sizee=sizee*a[i%k]%p;
    }
    cout<<ans<<endl;
}

\(n^2\) DP 比较简单

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,c,d;
int a[1000001],b[1000001];
int f[3001][3001]; //放了 i 个,其中有 j 个是红色的
signed main(){
    cin>>n>>c>>d;
    for(int i=1;i<=n;++i){
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=n;++i){
        for(int j=0;j<=i;++j){
            if(j!=i) f[i][j]=max(f[i][j],f[i-1][j]+b[i]+c*j);   //放蓝色
            if(j!=0) f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]+d*(i-j)); //放红色
        }
    }
    int ans=0;
    for(int i=0;i<=n;++i){
        ans=max(ans,f[n][i]);
    }
    cout<<ans<<'\n';
}

考虑贪心，所有红色点的贡献是 \(\sum a_i+d\times\sum\limits^{i-pre}_{j=1}j\)，其中 \(pre\) 是 \([1,i]\) 中红色点的个数，蓝色点同理

考虑拆出 \(\sum a_i+d\times\sum\limits i\)，可以发现，拆出来的这部分对每个点是独立的，剩下的那部分构成了一个等差数列，其值只与项数（红色点的个数）有关，因此直接枚举红色点的个数，这样后半段贡献就已知了，只需要最大化前半段贡献

先假设全是蓝色点，将一个蓝色点 \(i\) 变成一个红色点，对前半部分答案的贡献是 \((a_i+d\times i)-(b_i+c\times i)=a_i-b_i+i\times(d-c)\)，可以直接按这个值排序，然后贪心选点即可

还有一种奇怪的写法是直接钦定所有的贡献都是红色点产生的（和前面的蓝色点产生 \(c\) 的贡献，和后面的蓝色点产生 \(d\) 的贡献），这样也能做，写起来怪怪的

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,c,d;
int a[1000001],b[1000001];
int id[1000001];
inline int val(int x){
    return a[x]-b[x]+(x-1)*d+(n-x)*c;
}
signed main(){
    cin>>n>>c>>d;
    int sum=0,ans=0;
    for(int i=1;i<=n;++i){
        cin>>a[i]>>b[i];
        id[i]=i;
        sum+=b[i];
    }
    ans=sum;
    iota(id+1,id+n+1,1);
    sort(id+1,id+n+1,[](int x,int y){return val(x)>val(y);});
    for(int i=1;i<=n;++i){
        sum+=val(id[i]);
        ans=max(ans,sum-i*(i-1)/2*d-i*(i-1)/2*c);
    }
    cout<<ans<<endl;
}