【MX-X2-T1】「Cfz Round 4」Awaken 题解
ダ月
·
·
题解
注意到 Subtask 1 中 m=n。我们依次枚举 z，所有满足 x+y=z 的二元对 (x,y)，要求 a_x+a_y 的值两两相等。时间复杂度：O(n^2)
应该随便写个指数级暴力就能过 Subtask 2 了吧。确信。
先猜一手结论：a_i 是等差序列。接下来进行证明。
若 n=5，我们有以下式子：
-
-
-
不过要特判 $m\le 1$。
如果 $m\ge 2$，我们只需要算出公差（要求是**整数**），然后看是否能够还原出一个等差数列。
时间复杂度：$O(n+m)$。
```
void solve(){
//don't forget to open long long;
int n,m;IO::cin>>n>>m;std::vector<int>v(n,1e9+1);
while(m--){int x,y;mp[x]++;;IO::cin>>x>>y;x--;v[x]=y;}
while(!v.empty()&&v.back()==1e9+1)v.pop_back();
reverse(all(v));
while(!v.empty()&&v.back()==1e9+1)v.pop_back();
reverse(all(v));
if(v.size()<=1)return IO::cout<<"Yes"<<'\n',void();
int d=v.size()-1;ll L=v[0],R=v[d];
if((R-L)%d)return IO::cout<<"No\n",void();
ll B=(R-L)/d;
for(int i=1;i<=d;i++){
if(v[i]==1e9+1)v[i]=v[i-1]+B;
if(v[i]!=v[i-1]+B)return IO::cout<<"No"<<'\n',void();
}IO::cout<<"Yes"<<'\n';
}
```
代码是去年的代码了，有点丑。/yun