Hello 2023！
【CF1025G】Company Acquisitions
考虑用势能函数去描述一个状态 \(A=\{a_1,a_2,...,a_n\}\)，令 \(w(A)=\sum_{i=1}^n f(a_i)\)，其中 \(f(a_i)\) 是一个关于 \(a_i\) 的式子。
假设一次操作选择了两个分别挂了 \(x,y\) 个白点的红点，则有：
\(w(A')-w(A)=\dfrac{1}{2}(-f(x)-f(y)+(x+y)f(0)+f(y+1))+\dfrac{1}{2}(-f(x)-f(y)+(x+y)f(0)+f(x+1))\)
化简可得其等于 \(\dfrac{f(x+1)-2f(x)+f(y+1)-2f(y)}{2}+(x+y)f(0)\)
如果令 \(f(0)=0,f(x+1)-2f(x)=1\)，即 \(f(x)=2^x-1\)，你会发现一次操作后 \(w(A)\) 期望增大 \(1\)，而最终状态的 \(w(A)=2^{n-1}-1\)，两者相减即可。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int fpow(int x,int b){
if(x==0) return 0;
if(b==0) return 1;
int res=1;
while(b>0){
if(b&1) res=res*x%mod;
x=x*x%mod;
b>>=1;
}
return res;
}
int n;
int a[505],cnt[505];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]!=-1) cnt[a[i]]++;
}
int w=0;
for(int i=1;i<=n;i++) if(a[i]==-1) w=(w+fpow(2,cnt[i])-1)%mod;
cout<<((fpow(2,n-1)-1-w)%mod+mod)%mod;
}
signed main()
{
int _=1;
//cin>>_;
while(_--) solve();
return 0;
}
1.2 模拟 T1
题意：给定序列 \(a,b\)，你需要在两个序列中分别选出一个长度相同的区间，且这个区间内对应位置上的数相加形成回文序列，求最大区间长度，\(1 \le n \le 10^5\)。
题解：观察到若能找到一个长度为 \(len\) 的合法区间，那么 \(len-2,len-4,...\) 都能找到，可以奇偶分别二分。
标签：return,int,res,笔记,2f,2023,const,define From： https://www.cnblogs.com/znstz2018/p/17026139.html